求平面点集凸壳的一种新算法  

New method for computing convex hulls of point sets on plane

作　　者：刘润涛[1] 王三[2] 安晓华[2] 

机构地区：[1]哈尔滨理工大学信息与计算科学研究所,哈尔滨150080 [2]哈尔滨理工大学应用科学学院,哈尔滨150080

出　　处：《计算机工程与应用》2009年第3期58-59,69,共3页Computer Engineering and Applications

基　　金：国家自然科学基金(No.10571037);黑龙江省教育厅项目(No.11511027)~~

摘　　要：在研究了大量的求平面点集凸包的算法基础上,提出了一种新的构造平面点集的凸壳算法。此算法先求出四个极值点,构造出一个四边形。对于四边形外面的点依次用二分法进行判断是属于哪个线段区域;对于一个线段区域上的点只需要找出右侧的点,分别和线段的两个端点连接得到新的多边形链,依次这样处理每个点,直到结束。这样就得到四个简单多边形单调链,然后对单调链求凸点,时间复杂度为O(n),最后求得的每个凸点就是平面点集的凸壳,此算法总的时间复杂度不超过O(nlogn)。A new algorithm of computing convex hulls of plane point sets is presented,based on the research on a large amount of algorithms of computing the convex hulls of plane point sets.In the algorithm,the four extreme points are first computed,which compose a quadrangle,then for the points out of the quadrangle we figure out which line sections they belong to in order with the method of bisection.For the points in the same line section,we just find out the points on the right side,then connect them with the two endpoints of the line section separately to compose a new polygon chain,then process each point in the same way until the last one.In this way,four monotonic chains of simple polygons are obtained,then the vertices of the convex hulls of the four monotonic chains are computed.Its time complexity is O（n）.All the vertices are the ones of the convex hull of the plane point set.The total time complexity of this algorithm is not more than O（n log n）.

关 键 词：点集 单调链 凸壳 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]