空间点集卷包裹算法的优化实现

An Optimized Implementation of the Gift-Wrapping Algorithm for Three-Dimensional Convex Hull

凸包计算是计算几何研究中的基本问题之一 ,在许多领域均有应用。本文对求解空间点集凸包的卷包裹算法的实现问题进行了讨论。提出了 2点优化措施 ,并解决了实现中可能出现的共面点及由此带来的退化问题。

Convex hull computation is one of the fundamental problems in computational geometry , and is of wide application in many fields. In this paper the efficient implementation of the gift-wrapping method for computing the convex hull of 3D point sets is discussed. Two optimization methods to improve the efficiency are presented, and also proposed is a solution to the coplanar points and derived degeneracy problems, which might occur during the algorithm running.