我有一个点云，并且想检测我的代码中某些点模式的出现。
假设我在 3d 空间中有 1000 个点，我想检测 3 个点的所有实例，这些点形成一个“L”形，其中 L 的每个段都有特定的长度。点云可能没有完全匹配，但可能非常接近（即在点云中，“L”段的长度可能比理想的略长/短）
我最初的想法是这样的：
- 记录我们试图检测的形状中所有点之间的距离
- 创建一个空的“潜在形状”
- 对于我们潜在形状中的每个点，检查位于/接近第 1 部分中找到的距离的所有点）
- 如果我们找到一个点，将其添加到我们的潜在形状中，并重复第 3 部分）直到我们拥有所有点。然后检查点之间的角度以验证形状确实正确。如果不正确，我们继续下一点并重新开始
问题是这种方法有一个可怕的最坏情况运行时间。理想情况下，我希望有某种数据结构来加快我对“查找距离给定点的距离最小值和距离最大值之间的所有点”的查询。有人可以指出一些有用的数据结构可能会有所帮助。
我正在考虑将所有点放在八叉树中以加快访问时间。
关于如何提高运行时间的任何其他建议？启发式加快速度？
注意：我试图找到的形状是可变的。它们并不总是“L”。我尝试查看霍夫变换，但它们似乎仅对检测特定的预定形状（如线条/圆圈）有用。