java - KD树——最近邻算法

Question

我不太了解 wikipedia 中的 O(log n) 最近邻算法.

1. …
2. …
3. The algorithm unwinds the recursion of the tree, performing the following steps at each node:
   1. ...
   2. The algorithm checks whether there could be any points on the other side of the splitting plane that are closer to the search point than the current best. In concept, this is done by intersecting the splitting hyperplane with a hypersphere around the search point that has a radius equal to the current nearest distance. Since the hyperplanes are all axis-aligned this is implemented as a simple comparison to see whether the difference between the splitting coordinate of the search point and current node is less than the distance (overall coordinates) from the search point to the current best.
      1. If the hypersphere crosses the plane, there could be nearer points on the other side of the plane, so the algorithm must move down the other branch of the tree from the current node looking for closer points, following the same recursive process as the entire search.
      2. If the hypersphere doesn't intersect the splitting plane, then the algorithm continues walking up the tree, and the entire branch on the other side of that node is eliminated.

让我困惑的是 3.2，我看到了 this问题。我正在用 Java 实现该算法，但不确定我是否做对了。

//Search children branches, if axis aligned distance is less than current distance
if (node.lesser!=null) {
    KdNode lesser = node.lesser;
    int axis = lesser.depth % lesser.k;
    double axisAlignedDistance = Double.MAX_VALUE;
    if (axis==X_AXIS) axisAlignedDistance = Math.abs(lastNode.id.x-lesser.id.x);
    if (axis==Y_AXIS) axisAlignedDistance = Math.abs(lastNode.id.y-lesser.id.y);
    else if (axis==Z_AXIS) axisAlignedDistance = Math.abs(lastNode.id.z-lesser.id.z);

    //Continue down lesser branch
    if (axisAlignedDistance<=lastDistance && !set.contains(lesser)) {
        searchNode(value,lesser,set,K);
    }
}
if (node.greater!=null) {
    KdNode greater = node.greater;
    int axis = greater.depth % greater.k;
    double axisAlignedDistance = Double.MAX_VALUE;
    if (axis==X_AXIS) axisAlignedDistance = Math.abs(lastNode.id.x-greater.id.x);
    if (axis==Y_AXIS) axisAlignedDistance = Math.abs(lastNode.id.y-greater.id.y);
    else if (axis==Z_AXIS)axisAlignedDistance = Math.abs(lastNode.id.z-greater.id.z);

    //Continue down greater branch
    if (axisAlignedDistance<=lastDistance && !set.contains(greater)) {
        searchNode(value,greater,set,K);
    }
}

上面的代码是否完成了算法的 3.2 方面？特别是我填充“axisAlignedDistance”变量的位置。

您可以找到 KDTree 的完整源代码 here .

感谢任何帮助/指点。

Answer 1

我添加这个，希望它能帮助其他搜索到相同问题的人。我最终使用以下代码解决了 3.2。虽然，我不确定它是否 100% 正确。它已经通过了我提出的所有测试。上面的原始代码在许多相同的测试用例上都失败了。

使用点、线、矩形和立方体对象的更明确的解决方案:

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

    boolean lineIntersectsRect = false;
    Line line = null;
    Cube cube = null;
    if (axis==X_AXIS) {
        line = new Line(new Point(value.x-lastDistance,value.y,value.z), new Point(value.x+lastDistance,value.y,value.z));
        Point tul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Point tur = new Point(node.id.x,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Point tlr = new Point(node.id.x,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Point tll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Rectangle trect = new Rectangle(tul,tur,tlr,tll);
        Point bul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY);
        Point bur = new Point(node.id.x,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY);
        Point blr = new Point(node.id.x,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY);
        Point bll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY);
        Rectangle brect = new Rectangle(bul,bur,blr,bll);
        cube = new Cube(trect,brect);
        lineIntersectsRect = cube.inserects(line);
    } else if (axis==Y_AXIS) {
        line = new Line(new Point(value.x,value.y-lastDistance,value.z), new Point(value.x,value.y+lastDistance,value.z));
        Point tul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Point tur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Point tlr = new Point(Double.POSITIVE_INFINITY,node.id.y,Double.NEGATIVE_INFINITY);
        Point tll = new Point(Double.NEGATIVE_INFINITY,node.id.y,Double.NEGATIVE_INFINITY);
        Rectangle trect = new Rectangle(tul,tur,tlr,tll);
        Point bul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY);
        Point bur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY);
        Point blr = new Point(Double.POSITIVE_INFINITY,node.id.y,Double.POSITIVE_INFINITY);
        Point bll = new Point(Double.NEGATIVE_INFINITY,node.id.y,Double.POSITIVE_INFINITY);
        Rectangle brect = new Rectangle(bul,bur,blr,bll);
        cube = new Cube(trect,brect);
        lineIntersectsRect = cube.inserects(line);
    } else {
        line = new Line(new Point(value.x,value.y,value.z-lastDistance), new Point(value.x,value.y,value.z+lastDistance));
        Point tul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Point tur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Point tlr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Point tll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Rectangle trect = new Rectangle(tul,tur,tlr,tll);
        Point bul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,node.id.z);
        Point bur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,node.id.z);
        Point blr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,node.id.z);
        Point bll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,node.id.z);
        Rectangle brect = new Rectangle(bul,bur,blr,bll);
        cube = new Cube(trect,brect);
        lineIntersectsRect = cube.inserects(line);
    }

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

    boolean lineIntersectsRect = false;
    Line line = null;
    Cube cube = null;
    if (axis==X_AXIS) {
        line = new Line(new Point(value.x-lastDistance,value.y,value.z), new Point(value.x+lastDistance,value.y,value.z));
        Point tul = new Point(node.id.x,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Point tur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Point tlr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Point tll = new Point(node.id.x,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Rectangle trect = new Rectangle(tul,tur,tlr,tll);
        Point bul = new Point(node.id.x,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY);
        Point bur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY);
        Point blr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY);
        Point bll = new Point(node.id.x,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY);
        Rectangle brect = new Rectangle(bul,bur,blr,bll);
        cube = new Cube(trect,brect);
        lineIntersectsRect = cube.inserects(line);
    } else if (axis==Y_AXIS) {
        line = new Line(new Point(value.x,value.y-lastDistance,value.z), new Point(value.x,value.y+lastDistance,value.z));
        Point tul = new Point(Double.NEGATIVE_INFINITY,node.id.y,Double.NEGATIVE_INFINITY);
        Point tur = new Point(Double.POSITIVE_INFINITY,node.id.y,Double.NEGATIVE_INFINITY);
        Point tlr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Point tll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY);
        Rectangle trect = new Rectangle(tul,tur,tlr,tll);
        Point bul = new Point(Double.NEGATIVE_INFINITY,node.id.y,Double.POSITIVE_INFINITY);
        Point bur = new Point(Double.POSITIVE_INFINITY,node.id.y,Double.POSITIVE_INFINITY);
        Point blr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY);
        Point bll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY);
        Rectangle brect = new Rectangle(bul,bur,blr,bll);
        cube = new Cube(trect,brect);
        lineIntersectsRect = cube.inserects(line);
    } else {
        line = new Line(new Point(value.x,value.y,value.z-lastDistance), new Point(value.x,value.y,value.z+lastDistance));
        Point tul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,node.id.z);
        Point tur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,node.id.z);
        Point tlr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,node.id.z);
        Point tll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,node.id.z);
        Rectangle trect = new Rectangle(tul,tur,tlr,tll);
        Point bul = new Point(Double.NEGATIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY);
        Point bur = new Point(Double.POSITIVE_INFINITY,Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY);
        Point blr = new Point(Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY);
        Point bll = new Point(Double.NEGATIVE_INFINITY,Double.POSITIVE_INFINITY,Double.POSITIVE_INFINITY);
        Rectangle brect = new Rectangle(bul,bur,blr,bll);
        cube = new Cube(trect,brect);
        lineIntersectsRect = cube.inserects(line);
    }

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

我认为this更简单的代码也应该可以工作，它已经通过了与上述代码相同的所有测试。

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 p1 = Double.MIN_VALUE;
    double p2 = Double.MIN_VALUE;
    if (axis==X_AXIS) {
        p1 = node.id.x;
        p2 = value.x-lastDistance;
    } else if (axis==Y_AXIS) {
        p1 = node.id.y;
        p2 = value.y-lastDistance;
    } else {
        p1 = node.id.z;
        p2 = value.z-lastDistance;
    }
    boolean lineIntersectsCube = ((p2<=p1)?true:false);

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

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

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