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

Question

我有一组2D点,没有组织,我想找到这个集合的"轮廓"(不是凸包).我不能使用alpha形状,因为我有一个速度目标(在普通计算机上不到10毫秒).我的第一种方法是计算网格并找到轮廓正方形(正方形,其中空方块作为邻居).所以我认为我有效地缩减了我的点数(大致从22000到3000).但是我仍然需要改进这个新的集合.

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

Answer 1

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

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

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

我们缺乏连接信息。因此，我们选择一个“轮廓”正方形，其邻居为 2 个或更少。然后我们选择一位邻居。从那时起，我们就可以开始扩展了。我们只需围绕当前方块绕一圈即可找到下一个“轮廓”方块，并且知道之前的“轮廓”方块。我们的轮廓标准防止我们陷入死胡同。

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

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

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

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

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