geometry - 查找 2D 无组织点云的轮廓

Question

我有一组 2D 点，无组织，我想找到这个集合的“轮廓”(不是凸包)。我不能使用 alpha 形状，因为我有一个速度目标(在普通计算机上小于 10 毫秒)。
我的第一种方法是计算网格并找到轮廓方块(以空方块作为邻居的方块)。所以我认为我有效地减少了我的点数(大致从 22000 到 3000)。但是我仍然需要完善这个新系列。



我的问题是:如何在绿点中找到真正的轮廓点？

Answer 1

经过一个充满反射(reflection)的周末，我可能找到了一个方便的解决方案。

所以我们需要一个网格，我们需要用我们的点来填充它，这里没有困难。

我们必须决定哪些正方形被视为“轮廓”。我们的标准是:至少 1 个空邻居和至少 3 个非空邻居。

我们缺乏连接信息。所以我们选择一个“Contour”方块，它作为 2 个“Contour”邻居或更少。然后我们选择一位邻居。从那以后，我们就可以开始扩展了。我们只是围绕当前方块寻找下一个“Contour”方块，知道之前的“Contour”方块。我们的轮廓标准可防止我们陷入死胡同。

我们现在有连接正方形的向量，通常如果我们的形状没有洞，只有一个连接正方形的向量!

现在对于每个正方形，我们需要找到轮廓的最佳点。我们选择离我们平面重心更远的那个。它适用于大多数形状。另一种技术是计算所选正方形的空邻居的重心并选择最近的点。



红点是绿点的轮廓。所使用的技术是平面重心技术。

对于一组 28000 个点，这种技术需要 8 毫秒。对于 28000 个点，CGAL 的 Alpha 形状平均需要 125 毫秒。

PS:我希望我说清楚，英语不是我的母语:s