在半径上找到最近的邻居

Question

我的空间中有一组点 a （Geo点，但我可以假设它们在2D平面上）。

我有另一组点 b 。

对于 b 的每一点，我想在一个半径 r 内部的 a 中的每一个点，与 B 设置。

我用kdtree做了它，这为我提供了一个非常快速简便的算法来创建数据结构，找到邻居但它没有找到半径的每个点，因为它可以避免路径其中包含我的半径中的元素，但不在Radius中心的相同子集中。

kdtree失败的最小示例：

在探索kdtree时，目标点（红色）位于点数1的行下。这将继续探索线下的点，这将错过红点半径内的实点。

哪些算法或数据结构允许100％正确性？

我知道我是否会更糟糕，但我正在寻找搜索速度和完全正确性之间的平衡。

Answer 1

K-D树是解决此问题的良好数据结构。但是，您无法盲目地将搜索程序应用于中心点，你必须有点聪明。

在搜索KD树的同时为您的积分，每次必须选择左侧或右侧的子项搜索，检查分割平面是否位于圆圈的左侧，相交，或者是圆圈的右侧。

如果拆分平面位于圆圈的左侧，则必须继续在右侧搜索，反之亦然。但是，当分裂平面相交时您的圈子，您必须搜索两个儿童。