KD TREES(3-D)最近邻搜索

Question

我正在查看KD树最近邻搜索的维基百科页面.

维基百科中给出的伪代码在点为2-D(x,y)时起作用.

我想知道,当点是3-D(x,y,z)时,我应该做出什么改变.

我google了很多,甚至在堆栈溢出中经历了类似的问题链接,但我没有找到任何地方的3-d实现,所有以前的问题都需要2-D点作为输入,而不是我的3-D点寻找.

用于构建KD树的Wiki中的伪代码是::

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;
}

如何在建造KD树后找到最近的邻居？

谢谢!

Answer 1

您可以在"最近邻居搜索"标题下的维基百科页面上找到最接近的邻居.这里的描述适用于任何数量的维度.那是:

• 从根目录下递归到树,就好像你要插入你正在寻找最近邻居的点一样.
• 当你到达一片叶子时,请注意它是最好的.
• 在再次向上的路上,为您遇到的每个节点:
  • 如果它比最好的那么近,那就更新最好的.
  • 如果从最远到目标点的距离大于在该节点处从目标点到分裂超平面的距离,
  • 处理节点的另一个子节点(使用相同的递归).