新的高效平面点集凸壳构建算法

New efficient algorithm for creating convex hull for planar point set

提出一种新的平面点集凸壳构建算法,算法基于角域处理的过程对点集分而治之计算凸壳,基于特征角计算的方法成对查找角域特征点,利用初始角域划分和角域更新的机制不断缩小问题规模,从而迅速逼近凸壳边。针对大规模数据点集,算法又引入迭代思想,利用算法本身对非凸壳点的快速删除能力进一步加速凸壳求解进程,使得算法性能进一步提升,算法时间复杂度和空间复杂度均为O(n)。实验结果表明,这是一个可行、高效而且稳定的算法,易于推广到三维,也容易改进成并行算法。

This paper presented a new algorithm for creating convex hull for planar point set. It used the strategy of divide-conquer to calculate the convex hull by triangle-region processing, finding trait-points in pair by means of trait-angle calculation, decreasing the scale of the problem by the mechanism of initial triangle-region partition and updating, thereby rapidly approaching to the edge of the convex hull. For large scale data set of points, the idea of iteration was introduced in, which used the ability of quickly deleting the non convex hull points to accelerate the process of getting convex hull, making the performance of the algorithm enhanced further. Both of the time complexity and the space complexity of the algorithm are O（n）. The experiments manifest that it is a feasible, efficient and stable algorithm. Furthermore, this algorithm is easy to be extended to three-dimensional space as well as be improved to parallel type.