geometry - 查找二维无组织点云的轮廓

Question

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

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

Answer 1

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

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

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

我们缺乏连接信息。所以我们选择一个“Contour”正方形，它有 2 个或更少的“Contour”邻居。然后我们选择其中一个邻居。从此，我们就可以开始展开了。我们只是绕着当前方格转圈来寻找下一个“等高线”方格，知道之前的“等高线”方格。我们的轮廓标准防止我们走上死胡同。

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

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

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

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

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

Answer 2

你真的应该使用 alpha 形状。也许只使用绿点作为 alpha alpha 算法的输入。