Octreeの最近隣の検索

Question

NNアルゴリズムはどのようにしてオクトリーで動作しますか？私は良い説明を探しましたが、人々はKDツリーを代わりに使用すると言っていました。私はそれを行うことはできません、私はoctreeのNNアルゴリズムを視覚化する必要があります。

私が最も論理的な方法はにだろうと考えることができたよう：ポイントが属するサブ八分円を探す）

1。

2）

3その八分円内の最も近い点までの距離を計算し）、その距離

4内の隣接するオクタントを有する任意の重複があるかどうかを確認してください）により近い点が見つかった場合、探索距離を再計算。すべての可能なオクタントが

6を横断されるまで

5）が最も近い点

を返しますが、私は、このいずれかの段階の可視化によって、良好なステップアップだと思うカント）を繰り返します。

Answer 1

検索ポイントに最も近いポイントを検索したり、距離の大きい順にポイントのリストを取得するには、ポイントとツリーの内部ノードを保持できるプライオリティキューを使用できます。距離の順序。

ポイント（葉）の場合、距離は検索ポイントからのポイントの距離になります。内部ノード（オクタント）の場合、距離は、探索点からオクタント内にある可能性のある任意の点までの最小距離である。検索する今

、あなただけのプライオリティキューにツリーのルートを置く、と繰り返し：

1. プライオリティキューの先頭を削除します。
2. キューの先頭がポイントだった場合は、まだ返されていないツリー内の最も近いポイントです。これは、内部ノードに近い点がある可能性がある場合は、優先順位キューから最初に戻されるため、これが分かります。
3. キューの先頭には、内部ノードだった場合、これは、探索点からの距離の増加のために、ツリー内のすべてのポイントが生成されますキューに戻っ

をその子を置きます。同じアルゴリズムがKDツリーに対しても機能します。