data-structures - 快速找到点云中的特定形状

Question

我有一个点云，并且想检测我的代码中某些点模式的出现。

假设我在 3d 空间中有 1000 个点，我想检测 3 个点的所有实例，这些点形成一个“L”形，其中 L 的每个段都有特定的长度。点云可能没有完全匹配，但可能非常接近(即在点云中，“L”段的长度可能比理想值略长/短)

我最初的想法是这样的:

记录我们试图检测的形状中所有点之间的距离

创建一个空的“潜在形状”

对于我们潜在形状中的每个点，检查位于/接近第 1 部分中找到的距离的所有点)

如果我们找到一个点，将其添加到我们的潜在形状中，并重复第 3 部分)直到我们拥有所有点。然后检查点之间的角度以验证形状确实正确。如果不正确，我们继续下一点，重新开始

问题是这种方法有一个可怕的最坏情况运行时间。理想情况下，我希望有某种数据结构来加快我对“查找距离给定点的 distanceMin 和 distanceMax 之间的所有点”的查询。有人可以指出一些有用的数据结构可能会有所帮助。

我正在考虑将所有点放在八叉树中以加快访问时间。

关于如何提高运行时间的任何其他建议？启发式加快速度？

注意:我试图找到的形状是可变的。它们并不总是“L”。我尝试查看霍夫变换，但它们似乎仅对检测特定的预定形状(如线条/圆圈)有用。

Answer 1

在 PCL 库中有 Sample 共识模块，直接从文档中引用:

holds SAmple Consensus (SAC) methods like RANSAC and models like planes and cylinders. These can combined freely in order to detect specific models and their paramters in point clouds.

也许您可以创建一些组合这些图元的形状并在云中搜索它们？