algorithm - 空间数据结构中的不同搜索方法

Question

我正在尝试编写一个空间数据结构(例如 K-D 树 或 QuadTree)，给定一个点，它会找到 x 离它最近的点。

我上面提到的数据结构的问题是它们主要支持径向/区域搜索。因此他们将获得给定点/节点的 y 半径范围内的点。

改变这些结构来搜索我想要的内容将是低效的。我假设我需要多次重复径向搜索，从较短的径向距离开始，并不断增加它，直到我在给定点附近得到所需的 x 数量的点。当然，这违背了数据结构背后的全部目的。

几乎所有空间数据结构都在径向搜索上运行。我可以将哪些其他高效 搜索方法应用于QuadTree，或我需要考虑的任何其他空间数据结构以实现我的意思？有什么建议吗？

Answer 1

我不确定您的假设是否正确。 Wikipedia article on kd-trees指示该结构如何用于支持查找搜索点的 x 最近邻居。是的，它本质上是重复查找最近的邻居 x 次，但我不确定您是否有权期望算法在 kd-tree 上获得更高效的性能。

如果这对您来说还不够好，您可能需要将您的点存储在不同的数据结构中。如果 x 很小且有界，您可以将点存储在加权图中，其中边权重当然是点之间的距离。

如果 x 既不小也没有边界，您可以将空间简单分割为 k*m 均匀单元(此处为 2D，必要时膨胀为 3+D) .对于每个搜索点，直接转到包含它的单元格，找到同一单元格中的其他点。如果它们中的 x 比单元格的边界更靠近搜索点，那么这些就是您要查找的内容。如果不是，也搜索附近边界另一侧的单元格。

如果您发现自己需要同时支持径向/区域搜索和x-最近邻搜索，那么如果您必须维护 2 种数据结构，一种支持每种类型的数据结构，那还不是世界末日询问。对于许多搜索问题，有效解决方案的第一步是将数据放入正确的结构中以进行有效搜索。做出此决定取决于您尚未向我们提供的数字。