2D点云的轮廓

Question

我有一些散乱的二维点云数据。我的问题是想获取边界点以得到点云轮廓。

我知道'Marching square'这个算法，但它通常用于2D像素。请问有谁知道如何从2D点云数据中获取轮廓，或者有关'Marching square'算法的详细信息吗？另外，凸包在我的情况下不起作用。

提前感谢。

- stephie

---

我认为采用Marching Squares方法仍然是你最好的选择（如果我错了，请有经验的人纠正我）。你需要将2D点映射到“像素”值，更新该像素周围点的密度。因此，如果许多点靠近某个像素，则密度比只有一个点在上面或附近时要高。从那里开始，你可以继续使用Marching Squares算法。 - Bart

谢谢。您能否解释一下“将我的2D点映射到像素”是什么意思？ - stephie

我在考虑类似于三维元球（metaballs）的东西（或者您可以查看基于SPH流体模拟的表面重建方法）。这个链接包含了我所提示的大部分内容: http://www.geisswerks.com/ryan/BLOBS/blobs.html 当然，您可以忽略三维和光线投射。像这样的东西是否适合您？另一个有趣的链接可能是这个: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch07.html - Bart

Answer 1

我认为2D“Alpha shapes”算法是适合你的正确选择。

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html

Alpha shapes可以被视为“凸包”算法的一种概括，允许生成更一般的形状。

通过使用alpha shapes，您可以通过改变alpha参数值来控制结果形状所捕获的细节级别。

您可以在这里尝试Java小程序：http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html，以便更好地了解此算法的作用。

- Moustafa Alzantot

Answer 2

我建议使用德劳内三角剖分作为基础算法，然后删除所有太大的三角形（从而将云分成组），然后删除被多个三角形使用的所有边。

- Itai Bar-Haim