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

发布时间：2018-08-21 09:31

【摘要】：凸包问题是计算几何的基本问题之一。为实时计算平面点集的凸包,近年来许多学者提出很多优秀的算法,但依然不能满足实际中的实时性需求。为此,本文提出一种简单但高效快速的凸包算法。由于凸包点必然位于平面点集边缘,本文算法能够快速地筛选出极少量的凸包点候选点集,这是本算法的核心优势。然后,使用本文另外提出的一种简单易于实现的改进的Graham扫描算法,或其他任何已有的凸包检测方法,即可快速而准确地计算出点集的凸包。经典的Graham扫描算法使用一个基点计算凸包,本文的改进算法则是根据凸包候选点的分布情况,将点集分成4个子块,也即使用4个基点分别在每块中进行凸包检测,最后将每个子块中的检测结果进行合并,得到最终的完整凸包。实验中,采用一组公开的动物骨骼点云数据作为一次测试集。在凸包计算完全正确的情况下,当点数约为3×1 0~5左右时,本算法的计算时间比其他算法减少2.22倍;当点数约为3×10~6时,本算法的计算时间比其他方法减少5.42倍。点数越多,所提出算法就表现出越明显的优势。
[Abstract]:Convex hull problem is one of the basic problems in computational geometry. In order to compute the convex hull of the plane point set in real time, many scholars have proposed many excellent algorithms in recent years, but they still can not meet the real time requirement in practice. Therefore, this paper presents a simple but efficient and fast convex hull algorithm. Because convex hull points must be located at the edge of the plane point set, this algorithm can quickly filter out a few candidate point sets of convex hull points, which is the core advantage of this algorithm. Then, using a simple and easy to implement improved Graham scan algorithm, or any other existing convex hull detection method, the convex hull of the point set can be calculated quickly and accurately. The classical Graham scan algorithm uses one basis point to calculate convex hull. The improved algorithm is to divide the point set into four sub-blocks according to the distribution of convex hull candidate points, that is, to detect convex hull in each block using four basis points. Finally, the detection results in each subblock are merged to obtain the final complete convex hull. In the experiment, a set of published animal bone point cloud data was used as a test set. When the computation of convex hull is correct, the computation time of this algorithm is 2.22 times less than that of other algorithms when the number of points is about 3 脳 10 ~ 5, and 5.42 times less than that of other methods when the number of points is about 3 脳 10 ~ 6. The more the number of points, the more obvious the advantages of the proposed algorithm.
【作者单位】：四川大学电气信息学院;
【基金】：国家自然科学基金资助项目(NSFC61473198)
【分类号】：O18

【相似文献】