2

ウィキペディアのO（log n）最近傍アルゴリズムをよく理解していません。

  1. …</li>
  2. …</li>
  3. アルゴリズムはツリーの再帰を巻き戻し、各ノードで次の手順を実行します。
    1. ..。
    2. アルゴリズムは、分割平面の反対側に、現在の最良のものよりも検索ポイントに近いポイントがあるかどうかをチェックします。概念的には、これは、現在の最も近い距離に等しい半径を持つ検索ポイントの周りの超球と分割超平面を交差させることによって行われます。超平面はすべて軸に沿って配置されているため、これは、検索ポイントと現在のノードの分割座標の差が、検索ポイントから現在の最良までの距離（全体の座標）よりも小さいかどうかを確認するための単純な比較として実装されます。
      1. ハイパースフィアが平面を横切る場合、平面の反対側に近いポイントが存在する可能性があるため、アルゴリズムは、検索全体と同じ再帰プロセスに従って、現在のノードからツリーのもう一方のブランチを下に移動して、より近いポイントを探す必要があります。 。
      2. ハイパースフィアが分割平面と交差しない場合、アルゴリズムはツリーを上に移動し続け、そのノードの反対側のブランチ全体が削除されます。

私を混乱させているのは3.2であり、私はこの質問を見てきました。私は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の完全なソースコードはここにあります。

ヘルプ/ポインタをありがとう。

4

3 に答える 3

1

同じ問題を探している他の人に役立つことを願って、これを追加しています。私は次のコードで3.2に対処することになりました。ただし、100％正しいかどうかはわかりません。それは私が思いついたすべてのテストに合格しました。上記の元のコードは、同じテストケースの多くで失敗しました。

Point、Line、Rectangle、およびCubeオブジェクトを使用したより明確なソリューション：

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

この単純なコードも機能するはずです。上記のコードと同じテストにすべて合格しています。

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);
    }
}
于 2012-06-27T17:48:02.500 に答える
0

3から次のことに注意することが重要です。

「アルゴリズムはツリーの再帰を巻き戻し、各ノードで次の手順を実行します。」

あなたの実装は再帰的な呼び出しをしているだけで、再帰の巻き戻し時には何もしていないようです。

交差を正しく検出しているように見えますが、再帰のバックアウト（巻き戻し）の手順を実行していません。再帰呼び出しが行われた後、実行されるステップは0です（3.2を含む）。

3.2の状態：「超球が分割平面と交差しない場合、アルゴリズムはツリーを上っていき続け、そのノードの反対側のブランチ全体が削除されます」

これは何を意味するのでしょうか？基本ケースに到達すると（アルゴリズムがリーフノードに到達すると）、再帰が巻き戻され始めます。再帰の各レベルが巻き戻された後、アルゴリズムは、サブツリーに近い隣接ツリーが含まれる可能性があるかどうかを確認します。可能であれば、そのサブツリーで別の再帰呼び出しが行われます。そうでない場合、アルゴリズムは巻き戻しを続けます（ツリーを上に移動します）。

これから始める必要があります：

「ルートノードから始めて、アルゴリズムは、検索ポイントが挿入されている場合と同じように、ツリーを再帰的に下に移動します。」

そして、再帰の解明中に、どのような手順をいつ実行するかについて考え始めます。

これはやりがいのあるアルゴリズムです。このデータ構造のinsert（）メソッドを完了している場合は、それをこのアルゴリズムの開始フレームワークとして使用できます。

編集：

//Used to not re-examine nodes
Set<KdNode> examined = new HashSet<KdNode>();

「訪問済み」としてマークできるフラグを各ノードに配置する方が簡単で高速であり、使用するメモリも少なくて済みます。理想的には、HashSetは一定時間のルックアップを持っていますが、これを保証する方法は実際にはありません。そうすれば、訪問するたびにノードのセットを検索する必要がありません。ツリーの検索を行う前に、これらすべての値をO(N)時間内にfalseに初期化できます。

于 2012-06-26T17:56:59.967 に答える
0

はい、ウィキペディアのKDツリーでのNN（Nearest Neighbour）検索の説明を理解するのは少し難しいです。NN KDツリー検索で上位のGoogle検索結果の多くがまったく間違っていることは役に立ちません！

正しい説明/アルゴリズムについては、https：//stackoverflow.com/a/37107030/591720を参照してください。

于 2016-05-09T02:39:01.977 に答える