假设有一个点云在x-y-z三维空间中有50000个点。对于这个云中的每一个点，应该实现什么样的算法或数据限制来找到距离[r，r]范围内的给定点的k个邻居？最简单的方法是对50000个点的49999个点逐一进行度量测试但这种方法需要很长时间。就像kd树可以在很短的时间内找到最近的邻居一样，是否有一些实时的ds/algo实现来预处理点云以在最短的时间内达到目标？
最佳答案
您的问题是Nearest Neighbor Search主题的一部分，或者更准确地说，是k-Nearest Neighbor Search主题的一部分问题的答案取决于用于存储点的数据结构。如果您使用R-trees或类似R*-trees的变体，并且在数据库上执行多个搜索，您可能会发现，与原始线性搜索相比，二维或三维空间的性能有了显著的提高。在高维空间中，空间分割方案往往表现得不如线性搜索。