search - 网格中最近点搜索的高效算法

我正在寻找一种可以在网格中进行有效搜索的算法。

我有一个包含所有质心点（x，y，z）的大数组

现在对于给定的位置 (xp,yp,zp)，我想找到离该 p 位置最近的质心。

目前我正在做一个蛮力搜索，基本上对于每个点 p 我都会遍历所有点，计算到位置 p 的距离，然后找出那个质心。

我知道八叉树搜索和 kd-tree 可能会有所帮助，但不太确定如何解决它或哪个更好。

标签： searchbinary-search-treekdtreeoctree

我想要一个空间索引，例如 kd-tree 或四叉树/八叉树（您建议），或者可能是基于 R-Tree 的解决方案。

将所有质心放入索引中。通常，您可以将索引中的任何点与一些附加数据相关联，因此如果需要，您可以提供对网格的反向引用，例如网格坐标）。

在索引中找到最近的点应该非常快。然后返回的数据允许您返回网格。

在某种程度上，四叉树/八叉树本身只不过是一个离散网格，如果点密度增加，它会变得更精细。网格的不同之处在于它是分层的，并且根本不存储空白区域。