algorithm - 最近的顶点搜索

Question

我正在寻找有效的算法来找到最接近点 P(x, y, z) 的顶点。顶点集是固定的，每个请求都带有新的点 P。我尝试了 kd-tree 和其他已知方法，但我到处都遇到同样的问题：如果 P 更接近则一切都很好，只对少数树节点执行搜索. 但是，如果 P 足够远，那么应该扫描越来越多的节点，最终速度变得无法接受。在我的任务中，我无法指定一个小的搜索半径。这种情况有什么解决方案？

谢谢伊戈尔

Answer 1

加快搜索速度的一种可能方法是将空间离散为大量以规则间隔隔开的矩形棱柱。例如，您可以将空间分成许多 1 × 1 × 1 单位的立方体。然后，您将空间中的点分布到这些体积中。这为您提供了一种“散列函数”，用于将点分布到包含它们的体积中。

完成此操作后，请执行快速预计算步骤，并为每个卷找到最接近的非空卷。您可以通过检查距离卷一步，然后两步等所有卷来做到这一点。

现在，要进行最近邻搜索，您可以执行以下操作。首先将空间中的点散列到包含它的卷。如果该卷包含任何点，则遍历所有点以找到最接近的点。然后，对于您在此过程的第一步中找到的每个卷，遍历这些点以查看它们是否更接近。生成的最近点是离您的测试点最近的邻居。

如果您的卷最终包含太多点，您可以通过将这些卷细分为更小的卷并重复相同的过程来改进此方法。您也可以创建一堆较小的 kd 树，每个卷一个，以进行最近邻搜索。通过这种方式，每棵 kd 树拥有的点数比您的原始 kd 树要少得多，并且每个卷内的点都是最近邻的合理候选者。因此，搜索应该快得多。

这种设置在本质上类似于八叉树，不同之处在于您将空间划分为一堆更小的区域，而不是八个。

希望这可以帮助！

Answer 2

好吧，这不是所使用的索引结构的问题，而是您的查询的问题：

离数据集越远，最近的邻居就越模糊。

所以我怀疑任何其他索引都会对你有很大帮助。

但是，您可以在搜索中插入阈值。即“找到最近的邻居，但只有在最大距离 x 内”。

对于具有欧式距离的静态、内存中的 3-d 点双向量数据，kd-tree 实际上很难被击败。它只是非常非常快地拆分数据。八叉树有时可能更快，但我猜主要用于窗口查询。

现在，如果您确实只有很少的对象但有数百万个查询，您可以尝试做一些混合方法。大致是这样的：计算数据集凸包上的所有点。计算中心和半径。每当查询点距离 x 倍远（您需要自己进行 3d 数学运算以找出正确的 x）时，它的最近邻居必须是凸包点之一。然后再次使用 kd-tree，但仅包含船体点。

或者更简单。找到每个维度中的最小/最大点。也许添加一些额外的极端（在 x+y、xy、x+z、xy、y+z、yz 等）。所以你得到了一小部分候选人。所以现在让我们假设是 8 分。预先计算这 6 个点的中心和距离。设 m 为从中心到这 8 个点的最大距离。对于查询，计算到中心的距离。如果这大于 m，则首先计算这 6 个候选者中最接近的。然后查询kd-tree，但将搜索绑定到这个距离。这会花费您 1（近距离）和 7（远邻居）距离计算，并且可以通过尽早提供好的候选者来显着加快搜索速度。为了进一步加速，也可以将这 6-26 个候选者组织在一个 kd-tree 中，以快速找到最佳边界。