K-d 树：最近邻搜索算法

Question

这是我的理解： 1. 递归遍历树，根据ELEMENT是否存在于左子树或右子树中，选择相应的子树。 2. 将CURRENT_BEST设置为第一个叶节点。 3. 在回溯过程中，检查ELEMENT是否比CURRENT_BEST更接近分割超平面。如果是，则将CURRENT_BEST设置为当前节点。 这是我从Wikipedia和我的课堂中学到的部分，但我不理解的部分是： 4. 检查在步骤3中单独指定的分裂点的另一个子树中是否有任何节点比分裂点更接近ELEMENT。 我不明白为什么需要执行步骤4.，因为可能位于分裂节点的一个子树中的任何点都必须比另一子树中的任何点更接近分裂节点。 显然，我的算法理解存在缺陷，所以非常感谢您的帮助。

- Kaiser Octavius

---

你从哪篇维基百科文章中获取了这些信息？能否在你的问题中提供一个链接？ - didierc

@didierc -- 添加，三年后 - Martin F

第三步的条件是反过来了吗？ - user352102

Answer 1

第四步是第三步中的“否则”，当飞机比点更接近时，你需要做什么。仅仅因为你找到的点与你正在寻找邻居的点在同一个矩形中，并不意味着它就是最近的。

想象以下情景：你的kD-Tree中有两个点A和B。A位于其矩形的中心，而B则在边缘上，在A旁边的分区域内。如果你现在搜索距离点C最近的邻居，C恰好在B旁边，但碰巧在A的另一侧边缘和分区域内，你选择的第一个点将是A，因为初始深度优先搜索选择与你的搜索点在同一分区域的任何内容。然而，B实际上更接近，因此即使你选择了A，你也需要检查是否B更接近，否则你的kD-Tree将无法给出正确的结果。

一个很好的可视化方法是将其绘制出来：

A-------------C--|--B

A是我们在DFS中发现的第一个点，C是我们想要最近邻居的点，B是实际上最近的邻居，|是分割平面。

另一种思考方式是在点C周围以dist（A，C）半径画一个圆。如果任何其他矩形的任何部分落在这个圆内，那么它们可能持有比A更接近C的点，因此必须进行检查。如果你现在找到B，你可以减小你的圆的半径（因为B更接近），以便更少的矩形有机会相交，一旦你检查了所有与你的圆相交的矩形（随着你发现更接近的邻居而减小你的圆的半径），你可以明确地说没有更接近的点了。

- jkflying

Answer 2

我在github上编写了一个基本的C++实现。它有迭代和递归两个版本。

- gvd

Answer 3

function kdtree (list of points pointList, int depth)
{
    // Select axis based on depth so that axis cycles through all valid values
    var int axis := depth mod k;

    // Sort point list and choose median as pivot element
    select median by axis from pointList;

    // Create node and construct subtrees
    var tree_node node;
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, depth+1);
    return node;
}

- Sainath Bysani

---

该算法描述的是构建 k-d 树而不是寻找最近邻。 - Jernej Jerin