环状分布平面点集的凸包快速生成算法

A Fast Convex Hull Algorithm for Ring-Distributed Planar Point Sets

针对栅格辅助法在处理环状分布平面点集时计算效率较低的问题,提出了一种格网2次处理算法.通过比较离散点所在网格的空间位置关系,经2次剔除点集中绝大部分不可能成为凸包顶点的内点,减少了参与Graham扫描的点数,提高了计算效率.实验结果表明,与栅格辅助法相比,格网2次处理算法能够明显提高处理环状分布平面点集的效率,而且对于其他空间分布较为均匀的平面点集的处理效率也有一定程度的提高.

Aimed at the problem that the grid-aided algorithm does not perform well in constructing convex hull of a ring-distributed point set, a grid-reprocessing algorithm was proposed. By comparing the spatial relationship between related cells, the proposed algorithm eliminated most of the points never proved to be vertices of the convex hull twice. As a result, the number of points to be Graham-scanned was greatly reduced and the computational efficiency improved. The experimental results show that the grid-reprocessing algorithm significantly improves the efficiency of handling ring-distributed point sets and is more efficient, to a certain extent, than the grid aided algorithm when dealing with evenly distributed point sets.