python - 高效的最近邻搜索特定任务？

Question

我正在寻找 3D 中最近邻搜索的实现。

我目前正在使用 scipy.spatial。问题是我需要非常频繁地更新树/索引，并且使用此实现似乎每次我需要更新时都会重新构建树，从而导致执行时间非常长。

我要解决的任务如下:对于大量的 3D 点，将彼此距离太近(比指定间隙值更近)的点联合起来。

我目前通过遍历点列表来解决这个问题，如果它没有任何太近的邻居，则向索引添加一个新点，如果找到一个邻居，则为该点分配一个邻居的坐标。

如果有任何其他快速替代方案可以解决此问题，我将不胜感激。

Answer 1

对于快速最近邻搜索，我可以推荐 flann ( http://www.cs.ubc.ca/~mariusm/index.php/FLANN/FLANN )。对于点云，我会尝试 PCL ( http://pointclouds.org/ )。两者都有 python 绑定(bind)。

例如，一个想法是使用 PCL 对点进行聚类并联合聚类。 (segmentation.html">http://docs.pointclouds.org/trunk/group_segmentation.html)