我正在寻找一种可以在网格中进行高效搜索的算法。
我有一个大的阵列，它包括所有的质心点(x，y，z(
现在，对于给定的位置(xp，yp，zp(，我想找到离p位置最近的质心。
目前，我正在进行强力搜索，基本上，对于每个点p，我都会遍历所有点，计算到位置p的距离，然后通过这个搜索找出哪个质心。
我知道八叉树搜索和kd树可能会有所帮助，但不太确定如何处理它，或者哪一个会更好。
我会给你一个空间索引，比如kd树或四叉树/八叉树(你建议的(，或者可能是一个基于R-树的解决方案。
把你所有的质心都放进索引里。通常，您可以将索引中的任何点与一些附加数据相关联，因此如果需要，您可以提供对网格的反向引用，例如网格坐标(。
在索引中查找最近的点应该非常快。返回的数据允许您返回到网格中。
在某种程度上，四叉树/八叉树本身只是一个离散网格，如果点密度增加，网格会变得更细。网格的区别在于它是分层的，并且根本不存储空白区域。