5

これは私の理解です: 1. ELEMENT が存在する場合、左または右のサブツリーにあるかどうかに従って、左または右のサブツリーを取得して、ツリーを再帰します。2. 到達する最初のリーフ ノードとして CURRENT_BEST を設定します。3. 再帰的に戻って、ELEMENT が CURRENT_BEST よりも分割超平面に近いかどうかを確認します。その場合は、CURRENT_BEST を現在のノードとして設定します。

これは、Wikipediaと私のクラスから取得した部分であり、理解できない部分です。 4. 3. で選択された分割ポイントの他のサブツリー内のノードが、分割ポイントよりも ELEMENT に近いかどうかを確認します。 .

4. を実行する必要がある理由がわかりません。なぜなら、分割ノードの 1 つのサブツリーにある可能性のあるポイントは、他のサブツリーのどのポイントよりも分割ノードに近くなければならないからです。

アルゴリズムに欠陥があるのは明らかに私の理解であるため、助けていただければ幸いです。

4

3 に答える 3

9

ステップ 4 はステップ 3 の 'else' で、平面が点よりも近い場合に何をするかです。見つけた点が、隣人を見つけている点と同じ長方形にあるからといって、それが最も近いとは限りません。

次のシナリオを想像してみてください: kD ツリーに A と B の 2 つのポイントがあります。A は長方形の中央にあり、B はエッジのすぐ上にあり、A の隣の分割された領域にあります。 B のすぐ隣にある点 C の最近傍の場合、たまたまエッジの反対側にあり、A のパーティション領域にある場合、選択する最初の点は最初の深さ優先検索により A になります。検索ポイントと同じパーティションになります。ただし、実際には B の方が近いため、A を選択したとしても、B の方が近いかどうかを確認する必要があります。そうしないと、kD ツリーで実際に正しい結果が得られません。

これを視覚化する良い方法は、それを描くことです:

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

A は DFS で最初に見つけたポイント、C は最近傍を求めるポイント、B は実際の最近傍です。私たちの分割面です。

それを考える別の方法は、点 C の周りに半径 dist(A,C) の円を描くことです。他の長方形の一部がこの円内に収まる場合、それらが点を保持している可能性があります。 A よりも C に近いため、チェックする必要があります。B が見つかった場合は、(B の方が近いため) 円の半径を小さくして、交差する可能性のある四角形を減らし、円と交差するすべての四角形をチェックしたら (円の半径を小さくして、より近い隣人を見つける)、より近い点はないと断言できます。

于 2012-12-14T14:43:14.353 に答える
2

githubで基本的なC++ 実装を作成しました。反復バージョンと再帰バージョンの両方があります。

于 2012-12-05T07:59:08.180 に答える
-4 
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;
}
于 2012-11-22T07:15:52.877 に答える