求解简单多边形和平面点集凸包的新算法  

New Algorithms for Computing the Convex Hulls of a Simple Polygon and a Planar Point Set

作　　者：刘光惠[1] 陈传波[1] 

机构地区：[1]华中科技大学计算机学院,武汉430074

出　　处：《计算机科学》2007年第12期222-226,共5页Computer Science

基　　金：国家863项目(2004AA420100)

摘　　要：沿一定方向遍历凸多边形的边,其内部在边的同一侧。本文依据凸多边形的这一特性,提出求解简单多边形凸包的新算法,进而扩展得到求解平面点集凸包的新算法。新点集凸包算法先找到点集的极值点,得到极值点间的候选点子集,再求得相邻极值点间的有序凸包点列,最后顺序连接极值点间的有序凸包点列,得到凸包。新算法达到目前平面点集凸包问题的渐进最好算法的时间复杂度O(nlogh),其中,n为平面点集的点数,h为平面点集凸包的顶点数。相比相同复杂度的凸包算法,新算法简单、易于实现。又由于是顺序求得凸包上的点,新算法还具有更易于实现基于其上的有效空间算法的优点。Based on one of the characteristics of convex polygons, i.e. when the edges of a convex polygon are traversed along one direction, the interior of the convex polygon is always on the same side of these edges, a new algorithm for computing the convex hull of a simple polygon is proposed first, which is then extended to a new algorithm for computing the convex hull of a planar point set. To compute the convex hull of a planar point set, first to find the extreme points of the planar point set and get the sub collections of points candidate for vertices of the convex hull between them. Then the sorted convex hull point arrays between extreme points are constructed separately and concatenated by removing redundant extreme points to get the convex hull. The time complexity of the new planar convex hull algorithm is O（n log h）, which is equal to the time complexity of best output-sensitive planar convex hull algorithms. Compared with the same time complexity algorithms, the new algorithm is simple and easy to be implemented, and owing to its sequentially computing the vertices on the convex hull, it is easier to get a space-efficient planar convex hull algorithm based on the new planar convex hull algorithm than others.

关 键 词：计算几何 凸包 极值点 有序凸包点列 有效空间 

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