点列表的 3D 轮廓(凹包)

Question

我在 C# 中有一个 Vector3 点列表，我需要计算这些点的凹轮廓。确实有很多引用资料，尤其是 -convex- 分辨率(我已经成功实现了，多亏了 graham 的算法)，

但是，由于我现在需要有效地计算凹轮廓，所以我迷路了:维基百科确实列出了很多用于凸计算的资源，但没有列出 -concave-。

任何具有数学知识的人都可以指导我了解可用的凹包算法吗？

我也很关心性能，因此能够先验地对算法速度进行基准测试会非常有帮助。

谢谢。

Answer 1

“凹壳”不是一个定义明确的数学概念；有许多可能的算法给出不同的合理结果，这就是为什么它的资源很少。尝试使用谷歌搜索“3D alpha 形状”来寻找可能适合您需要的东西，例如http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html