c++ - 点云线搜索算法

Question

我正在使用 2D 点云，我想找到它遵循的形状，并确定它是否是一个闭环。你不得不原谅我糟糕的油漆插图，但基本上我希望能够从黑点画出红线，并确认它是否关闭。我目前正在研究 RANSAC 等方法，但它们似乎都适合与我面临的任务略有不同的任务。我将在 C++ 中实现该解决方案。

有谁知道在给定黑点的情况下计算红线并确定它是否关闭的好方法/算法？

Answer 1

我的建议是：

1. 对点集进行三角剖分。
2. 找到通过所有线路的短路径，基本上是旅行商问题。贪心算法可能足以达到这个目的。
3. 使用线条简化算法来“整理”线条（RDP 算法效果很好）。
4. 考虑大于 X 乘以点之间的平均距离（从步骤 2 开始）的任何值，基本上是数据中的异常值作为确定是打开还是关闭的间隙。

请记住，第 3 步和第 4 步是高度固执己见的。它们都要求你定义你认为“足够好”的东西，并且需要一些实验来设置最佳值。