computational-geometry - 用于排序点集的凸包算法

Question

我需要一种算法来计算 3 维和更高维的有序点集的凸包。我也需要在凸包的下部，并且没有必要构造一个完整的凸包。是否有任何有效且快速的算法可用于我的目的？

Answer 1

我相信 Seidel 已经确定，对点进行排序在渐近时间复杂度方面没有帮助，当然下半部分几乎可以是整个船体，所以这也无济于事。随机增量（Clarkson 和 Shor）也许是最好的选择。这是该算法的小程序说明：Tufts link。

Answer 2

我实现了这个用于凸包查找的 hull 算法，发布在 GitHub 上。这是 Python，可以为您提供以下结果：

Answer 3

用于在 R3 中查找点的凸包的 GPL C++ 代码可在http://www.newtonapples.net/code/NewtonAppleWrapper_11Feb2016.tar.gz获得 该算法基于对 z(x(y)) 中的点进行排序，然后按顺序排列将点包裹到外壳中。相当吸引人的是，该算法以巧克力命名。