使用点云库高效查找从 K-d 树到直线的 k 个最近点

Question

使用点云库（PCL），我从点云创建了 K-d 树。我想找到从 K-d 树到一条线的 k 个最近点。有没有办法使用 PCL 高效做到这一点？

显然我们可以使用蛮力方法来找到每个点与直线的距离并保留 k 个最近点。然而，我希望我们可以使用 K-d 树更快地找到 k-近邻。

八叉树数据结构具有查找与直线相交的体素索引的功能。然而，这对我的应用程序来说不太适用，因为一条线可能非常接近位于不与该线相交的体素中的点，因此该点将从结果中排除。

Answer 1

您已经明确表示您想要找到几行的 k 最近点，所以这是我上面评论中的想法，但更具体： 我认为高效解决方案的最佳选择是通过创建一个新函数来返回距离一条线最近的 k 个点，从而使 PCL 的八叉树实现适应您的需求。然后，八叉树结构将用于了解哪些点值得考虑，就像现有的nearestKSearch 函数一样。
您必须创建

getKNearestNeighborRecursive

的改编版（https://github.com/PointCloudLibrary/pcl/blob/master/octree/include/pcl/octree/impl/octree_search.hpp#L224），并且到目前为止正如我所看到的，你只需要通过计算

pointSquaredDist

（计算两点之间的平方距离）的函数来切换点和线之间的平方距离（

pcl/common/distances.h

有执行此操作的函数）。最后，调用递归函数的

nearestKSearch

(https://github.com/PointCloudLibrary/pcl/blob/master/octree/include/pcl/octree/impl/octree_search.hpp#L82) 的改编。 kd-tree 也可以实现类似的功能，但是实现起来有多容易或困难取决于 kd-tree 的实现。