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

摘要：

凸包问题是计算几何的基本问题之一.为实时计算平面点集的凸包,近年来许多学者提出很多优秀的算法,但依然不能满足实际中的实时性需求.为此,本文提出一种简单但高效快速的凸包算法.由于凸包点必然位于平面点集边缘,本文算法能够快速地筛选出极少量的凸包点候选点集,这是本算法的核心优势.然后,使用本文另外提出的一种简单易于实现的改进的Graham扫描算法,或其他任何已有的凸包检测方法,即可快速而准确地计算出点集的凸包.经典的Graham扫描算法使用一个基点计算凸包,本文的改进算法则是根据凸包候选点的分布情况,将点集分成4个子块,也即使用4个基点分别在每块中进行凸包检测,最后将每个子块中的检测结果进行合并,得到最终的完整凸包.实验中,采用一组公开的动物骨骼点云数据作为一次测试集.在凸包计算完全正确的情况下,当点数约为3×105左右时,本算法的计算时间比其他算法减少2.22倍;当点数约为3×106时,本算法的计算时间比其他方法减少5.42倍.点数越多,所提出算法就表现出越明显的优势.

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

所属期刊栏目：49

分类号：TP311.1(计算技术、计算机技术)

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

在线出版日期：2017-11-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：109-116