KD树（3-D）最近邻搜索

Question

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

维基百科中给出的伪代码适用于二维点(x,y)。

我想知道，当点是三维的(x,y,z)时，应该做出哪些改变。

我进行了大量谷歌搜索，甚至查看了stack overflow中的类似问题链接，但我没有找到任何3D实现，所有以前的问题都以2D点作为输入，而不是我所寻找的3D点。

维基中构建KD树的伪代码如下：

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树后找到最近的邻居？

谢谢！

- user1134599

Answer 1

按照维基百科“最近邻搜索”章节中的描述，您可以找到最近的邻居。该描述适用于任意维度。具体步骤如下：

从根节点开始，递归地向下遍历树，就好像要插入您正在查找最近邻居的点一样。

当到达叶子节点时，将其记录为最佳匹配点。

在沿着树向上返回的过程中，对于每个节点：

- 如果它比目前的最佳匹配点更接近，则更新最佳匹配点。 - 如果从最佳匹配点到目标点的距离大于目标点到该节点分裂超平面的距离, - 则还需处理该节点的另一个子节点（使用相同的递归方法）。

- Gareth McCaughan

Answer 2

我最近编写了一个用于在三维空间中进行最近邻搜索的KD树，并遇到了与NNS相关的相同问题，特别是维基百科的3.2部分。最终我使用了这个算法，在我的所有测试中似乎都有效：

以下是初始叶子节点搜索：

public Collection<T> nearestNeighbourSearch(int K, T value) {
    if (value==null) return null;

    //Map used for results
    TreeSet<KdNode> results = new TreeSet<KdNode>(new EuclideanComparator(value));

    //Find the closest leaf node
    KdNode prev = null;
    KdNode node = root;
    while (node!=null) {
        if (KdNode.compareTo(node.depth, node.k, node.id, value)<0) {
            //Greater
            prev = node;
            node = node.greater;
        } else {
            //Lesser
            prev = node;
            node = node.lesser;
        }
    }
    KdNode leaf = prev;

    if (leaf!=null) {
        //Used to not re-examine nodes
        Set<KdNode> examined = new HashSet<KdNode>();

        //Go up the tree, looking for better solutions
        node = leaf;
        while (node!=null) {
            //Search node
            searchNode(value,node,K,results,examined);
            node = node.parent;
        }
    }

    //Load up the collection of the results
    Collection<T> collection = new ArrayList<T>(K);
    for (KdNode kdNode : results) {
        collection.add((T)kdNode.id);
    }
    return collection;
}

这里是从最近的叶节点开始的递归搜索:

private static final <T extends KdTree.XYZPoint> void searchNode(T value, KdNode node, int K, TreeSet<KdNode> results, Set<KdNode> examined) {
    examined.add(node);

    //Search node
    KdNode lastNode = null;
    Double lastDistance = Double.MAX_VALUE;
    if (results.size()>0) {
        lastNode = results.last();
        lastDistance = lastNode.id.euclideanDistance(value);
    }
    Double nodeDistance = node.id.euclideanDistance(value);
    if (nodeDistance.compareTo(lastDistance)<0) {
        if (results.size()==K && lastNode!=null) results.remove(lastNode);
        results.add(node);
    } else if (nodeDistance.equals(lastDistance)) {
        results.add(node);
    } else if (results.size()<K) {
        results.add(node);
    }
    lastNode = results.last();
    lastDistance = lastNode.id.euclideanDistance(value);

    int axis = node.depth % node.k;
    KdNode lesser = node.lesser;
    KdNode greater = node.greater;

    //Search children branches, if axis aligned distance is less than current distance
    if (lesser!=null && !examined.contains(lesser)) {
        examined.add(lesser);

        double nodePoint = Double.MIN_VALUE;
        double valuePlusDistance = Double.MIN_VALUE;
        if (axis==X_AXIS) {
            nodePoint = node.id.x;
            valuePlusDistance = value.x-lastDistance;
        } else if (axis==Y_AXIS) {
            nodePoint = node.id.y;
            valuePlusDistance = value.y-lastDistance;
        } else {
            nodePoint = node.id.z;
            valuePlusDistance = value.z-lastDistance;
        }
        boolean lineIntersectsCube = ((valuePlusDistance<=nodePoint)?true:false);

        //Continue down lesser branch
        if (lineIntersectsCube) searchNode(value,lesser,K,results,examined);
    }
    if (greater!=null && !examined.contains(greater)) {
        examined.add(greater);

        double nodePoint = Double.MIN_VALUE;
        double valuePlusDistance = Double.MIN_VALUE;
        if (axis==X_AXIS) {
            nodePoint = node.id.x;
            valuePlusDistance = value.x+lastDistance;
        } else if (axis==Y_AXIS) {
            nodePoint = node.id.y;
            valuePlusDistance = value.y+lastDistance;
        } else {
            nodePoint = node.id.z;
            valuePlusDistance = value.z+lastDistance;
        }
        boolean lineIntersectsCube = ((valuePlusDistance>=nodePoint)?true:false);

        //Continue down greater branch
        if (lineIntersectsCube) searchNode(value,greater,K,results,examined);
    }
}

完整的 Java 源代码可以在这里找到。

- Justin

Answer 3

我想知道，当点是3D(x,y,z)时，我应该做哪些更改。

您可以在此行上获取当前轴。

var int axis := depth mod k;

现在根据轴的不同，通过比较相应的属性来找到中位数。例如，如果axis = 0，则与x属性进行比较。实现此方法的一种方式是在执行搜索的程序中传递一个比较函数。

- Nick Dandoulakis