Writing an uncomplicated, robust, and scalable three-dimensional convex hull algorithm is challenging and problematic. This includes, coplanar and collinear issues, numerical accuracy, performance, and complexity trade-offs. While there are a number of methods available for finding the convex hull based on geometric calculations, such as, the distance between points, but do not address the technical challenges when implementing a usable solution (e.g., numerical issues and degenerate cloud points). We explain some common algorithm pitfalls and engineering modifications to overcome and solve these limitations. We present a novel iterative method using support mapping and surface projection to create an uncomplicated and robust 2d and 3d convex hull algorithm.
翻译:编写一个简单、稳健、可扩展的三维凸壳算法具有挑战性和问题,包括共面和共线问题、数值精度、性能以及复杂度折衷。虽然有许多基于几何计算的方法可用于查找凸包,如点之间的距离,但不能解决当实现可用的解决方案时可能遇到的技术挑战(例如数值问题和退化点云)。我们解释了一些常见的算法缺陷和工程修改,以克服和解决这些限制。我们提出了一种新颖的迭代方法,采用支撑映射和表面投影来创建一个简单而强健的二维和三维凸壳算法。