データ構造における圧縮された四分木と八分木

圧縮された四分木

細分化されたセルに対応するすべてのノードを格納するときに、多くの空のノードを格納してしまう可能性があります。このようなまばらなツリーのサイズを縮小するには、葉に興味深いデータがあるサブツリー（つまり、「重要なサブツリー」）のみを保存します。ここでも、実際にサイズをさらに縮小することができます。重要なサブツリーのみを考慮する場合、プルーニングプロセスは、中間ノードの次数が2（1つの親と1つの子へのリンク）であるツリー内の長いパスを回避する場合があります。このパスの先頭にノードUを格納し（そして削除されたノードを表すためにいくつかのメタデータをそれに関連付けて）、その最後にルートされたサブツリーをUにアタッチするだけでよいことがわかります。これらの圧縮されたツリーにはまだ「悪い」入力ポイントが与えられたときの線形の高さ。

この圧縮を実行するとツリーの多くが削減されますが、Z階数曲線を利用することで、対数時間の挿入、削除、および検索を実現できます。 Z階数曲線は、O（1）時間で完全な四分木（したがって圧縮された四分木でさえ）の各セルを1次元の線に変換し（そしてO（1）時間でも変換し直し）、全順序を構築します要素に。これで、順序集合（ツリーのノードを格納する）のデータ構造に四分木を格納できるようになりました。ここで、続行する前に合理的な仮定を述べる必要があります。2進数で表される2つの実数α、β€[0,1]が与えられた場合、O（1）時間でそれらが含まれる最初のビットのインデックスを計算できると仮定します。異なる。また、四分木内の2つのポイント/セルの最小の共通祖先をO（1）時間で計算し、それらの相対的なZ順序を確立できると仮定し、O（1）時間で床関数を計算できます。これらの仮定により、特定のポイントQのポイント位置（つまり、Qを含むセルを見つける）、削除および挿入操作はすべて、O（n log n）時間（つまり、検索の実行にかかる時間）で実行できます。基礎となる順序付きセットのデータ構造）。

Qのポイント位置を実行するには（つまり、圧縮されたツリー内のセルを決定するため）

• 既存のセルは、ZオーダーでQの前にある圧縮ツリーにあります。このセルをVと呼びます。
• Q€Vが実行された場合は、Vを返します。
• それ以外の場合は、圧縮されていない四分木で点QとセルVの最小の共通祖先を見つけます。この祖先セルをUと呼びます。
• ZオーダーでUの前にある圧縮ツリーで既存のセルを見つけて、それを返します。

具体的な詳細に立ち入ることなく、挿入と削除を実行するには、最初に挿入/削除したいもののポイント位置を実行し、次にそれを挿入/削除します。必要に応じてツリーの形状を変更し、必要に応じてノードを構築および削除するように注意する必要があります。

八分木

八分木は、各内部ノードが正確に8つの子に関連付けられているツリーデータ構造として定義されます。

八分木は、ほとんどの場合、3次元空間を8つの八分木に再帰的に分割することによって3次元空間を分割するために実装されます。

八分木は、四分木の3次元アナログとして扱われます。名前はoct+treeから作成されますが、通常は「t」が1つだけの「octree」と記述されていることに注意してください。

オクトリーは、多くの場合、3Dグラフィックスおよび3Dゲームエンジンに実装されています。

空間表現用

八分木の各ノードは、それが表す空間を8つの八分木に細分化する責任があります。ポイントリージョン（PR）

octreeの場合、ノードは明示的な3次元ポイントを格納します。これは、そのノードのサブディビジョンの「中心」です。ポイント

8人の子のそれぞれのコーナーの1つを指定します。行列ベース（MX）の八分木の場合、細分割点は暗黙的にノードによって表される空間の中心になります。 PRオクツリーのルートノードは、無限の空間を表すことができます。 MX octreeのルートノードは、暗黙の中心が明確に定義されるように、有限の有界空間を表すことができなければなりません。

一般的な用途

• 3Dコンピュータグラフィックスでの詳細度レンダリング
• 空間インデックス
• 最寄りの近所を検索する
• 3次元での効率的な衝突検出
• 有限要素の分析
• スパースボクセル八分木
• 状態の見積もり
• セットの見積もり