基于最大基线倾角智能逼近的凸壳新算法  

A New Algorithm for Finding Convex Hull Based on Intelligent Approximating with a Maximum Pitch of Base Lines

作　　者：周启海[1] 黄涛[1] 吴红玉[1] 张元新[1] 

机构地区：[1]西南财经大学经济信息工程学院,成都610074

出　　处：《计算机科学》2007年第9期206-208,共3页Computer Science

基　　金：西南财经大学科研基金项目(No.06K75)

摘　　要：本文评述了有代表性的折半分治递归凸壳算法,并利用同构化凸壳基本定理提出效率更高的最大倾角智能逼近凸壳新算法。本新算法的同构化特点是:1)找出给定二雏点集最外点(指最左、最右、最高、最低点),即其X轴、Y轴坐标值最大、最小的四个初始极点;2)用该初始极点,把原二维点集分布域划分为四个子分布域;3)分别在这四个子分布域中,各基于自身最新所得极点依次动态构造其基线倾角最大的当前极点,并用这些极点作凸边,来逐步智能逼近和最终生成该给定二维点集的凸壳。In this paper, comment on a representative algorithm convex hull with half-dividing and recurrenc; and a more efficient new algorithm to find a convex hull based on intelligent approximating with a maximum pitch is given by the isomorphic fundamental theorem of the convex hull. The isomorphic characters of the new algorithm are： 1） find out the outside-most poles which are the leftmost, rightmost, topmost and bottommost points on the convex hull, i. e. the four initial poles which have the maximum or the minimum coordinate value of the X or Y axis among all the points in given 2D point set; 2） divides the original distributed domain into four sub-domain with the initial poles; 3） in every sub-domain, constructs a current pole with a maximum pitch to its base line based on its last pole got just dynamically and sequentially, and draw the rims of this convex polygon with these poles for intelligent approximating for a convex hull of the given 2D point set step by step.

关 键 词：同构化 凸壳算法 分布域 最大倾角 智能逼近 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]