假设在 x-y-z 3D 空间中有一个包含 50 000 个点的点云。对于这个云中的每个点，应该实现什么算法或数据结构来找到给定点在 [R,r] 距离内的 k 个邻居？天真的方法是对 50 000 个点中的每个点都检查 49 999 个点中的每个点并进行度量测试。但这种方法将花费大量时间。就像有 kd 树可以在短时间内找到最近的邻居一样，是否有一些实时 DS/算法实现来预处理点云以实现最短时间的目标？
最佳答案
您的问题是Nearest Neighbor Search 主题的一部分，或更准确地说，k-Nearest Neighbor Search .您问题的答案取决于您用来存储点的数据结构。如果你使用 R-trees或类似 R*-trees 的变体，并且您正在对数据库进行多次搜索，与简单的线性搜索相比，您可能会发现在二维或三维空间中的性能有了实质性的改进。在更高维度中，空间划分方案往往不如线性搜索。
关于在一定范围内找到k个邻居的算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30814854/