一种给定平面点集凸壳算法  

An algorithm for determining convex hull of a given planar point set

作　　者：蒋联源[1] 陈发住 郭明明[3] 张显全[3] 

机构地区：[1]广西工学院计算机工程系,柳州545006 [2]广西高速公路管理局西南处,崇左532200 [3]广西师范大学计算机科学系,桂林541004

出　　处：《信息技术》2007年第9期5-7,共3页Information Technology

基　　金：广西自然科学基金资助课题(0447035)

摘　　要：凸壳问题是计算机图形学、图像处理、模式识别等众多领域中的一个基本问题。将正切线算法应用到给定平面点集凸壳的计算中,并实现了正切线算法中新加入点的自动编号。通过极值点把点集分成若干个区域,对于点集中的每一个点,若落于中间区域,则淘汰掉该点;若落于其它区域,则通过该点与它所在区域的原单调段进行计算得到新单调段,从而得到给定平面点集的凸壳。算法效率高,在最坏情况下的时间复杂度为O(nlogm),m为凸壳的顶点数。Convex hull problem is one of the fundamental problems in computer graphics, image processing, and pattern recognition. In this paper, the tangent algorithm is applied to the computation of the convex hull of a given planar point set, and the automatic numbering for each newly added point has been realized. First, the point set is divided into several regions by extreme points . For each point, if it falls in the middle area, then it is removed, otherwise it is computed with the former monotone segment of the region in which it falls to update the monotone segment, and then the entire convex hull is obtained accordingly. Tne algorithm has high efficiency with O（nlogm） worstcase time complexity, where m is the number of hull vertices.

关 键 词：凸壳 单调段 极值点 正切线算法 

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