一种平面点集的高效凸包算法  

An Effective 2D Convex Hull Algorithm

作　　者：刘凯[1] 夏苗 杨晓梅[1] 

机构地区：[1]四川大学电气信息学院,四川成都610065

出　　处：《工程科学与技术》2017年第5期109-116,共8页Advanced Engineering Sciences

基　　金：国家自然科学基金资助项目(NSFC61473198)

摘　　要：凸包问题是计算几何的基本问题之一。为实时计算平面点集的凸包,近年来许多学者提出很多优秀的算法,但依然不能满足实际中的实时性需求。为此,本文提出一种简单但高效快速的凸包算法。由于凸包点必然位于平面点集边缘,本文算法能够快速地筛选出极少量的凸包点候选点集,这是本算法的核心优势。然后,使用本文另外提出的一种简单易于实现的改进的Graham扫描算法,或其他任何已有的凸包检测方法,即可快速而准确地计算出点集的凸包。经典的Graham扫描算法使用一个基点计算凸包,本文的改进算法则是根据凸包候选点的分布情况,将点集分成4个子块,也即使用4个基点分别在每块中进行凸包检测,最后将每个子块中的检测结果进行合并,得到最终的完整凸包。实验中,采用一组公开的动物骨骼点云数据作为一次测试集。在凸包计算完全正确的情况下,当点数约为3×1 0~5左右时,本算法的计算时间比其他算法减少2.22倍;当点数约为3×10~6时,本算法的计算时间比其他方法减少5.42倍。点数越多,所提出算法就表现出越明显的优势。Convex hull is one of the essential issues in computational geometric of planar points set.In recent years,many scholars have put forward many excellent algorithms to calculate the convex hull of the plane point set in real time,which,however,still can not satisfy the practical real-time demand.To this end,a simple but efficient and fast convex hull algorithm is proposed in this paper.Due to the fact that the convex hull points must be located at the edge of the planar point set,the algorithm in this paper can quickly find out the few candidate points of the convex wrapping point,which is the core advantage of this algorithm.Then,by using a simple and effectively-improved Graham scan algorithm which is also put forward by this paper,or any other existing convex hull methods,the points set of the convex hull can be calculated quickly and accurately.Conventional Graham scan algorithm calculate convex hull with one basis point.Based on the convex hull of distribution of candidate points set,the improved algorithm of this paper divides basis points into four subsystems,namely 4 basis points are tested respectively in each part,then mergers all the test results of each parts,and finally gets the complete convex hull.In the experiment,a set of public animals bone points clouds were used.The convex hull calculation is perfectly correct,but the calculation time of this algorithm is 2.22 times less than that of other algorithms when the number of points is about 3 × 10^5.When the number of points is about 3 × 10^6,the computation time of this algorithm is 5.42 times less than that of other methods.The more points,the more obvious advantages of this algorithm.

关 键 词：凸包 预处理算法 改进的Graham扫描算法 平面点集 

分 类 号：TP311.1[自动化与计算机技术—计算机软件与理论]