点列表的 3D 轮廓(凹壳) [英] 3D contour of a list of points (concave hull)

问题描述

我在 c# 中有一个 Vector3 点的列表，我需要计算这些点的凹轮廓.周围确实有很多参考资料，特别是对于凸分辨率(由于格雷厄姆的算法，我已经成功实现了)，

I have a list of Vector3 points in c#, and I need to calculate the concave contour of these. There's really a lot of references around, especially for -convex- resolution (which I have successfully implemented already, thanks to graham's algorithm),

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

however, since my need is now to effectively compute a concave contour, I'm lost: wikipedia does list a lot of resources for convex calculation, but none for -concave-.

任何具有数学知识的人都可以为我提供有关可用凹包算法的线索?

Anybody with math knowledge that can give me a lead on the available concave hull algorithms?

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

I have a concern for performance, too, so being able to benchmark the algorithm speed a priori would be very helpful.

谢谢.

推荐答案

'Concave hull' 不是一个明确定义的数学概念；有许多可能的算法给出不同的合理结果，这就是为什么关于它的资源很少.尝试在谷歌上搜索3D alpha 形状"以获得可能适合您需求的东西，例如http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html

'Concave hull' is not a well-defined mathematical concept; there are many possible algorithms giving different reasonable results, which is why there are few resources on it. Try googling '3D alpha shapes' for something that might suit your needs, e.g. http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Alpha_shapes_3/Chapter_main.html

这篇关于点列表的 3D 轮廓(凹壳)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！