クワッドツリー

四分木は、各内部ノードが正確に 4 つの子を持つツリー データ構造です。四分木は八分木の 2 次元版であり、2 次元空間を再帰的に 4 つの象限または領域に分割して分割するために最もよく使用されます。リーフ セルに関連付けられたデータはアプリケーションによって異なりますが、リーフ セルは「興味深い空間情報の単位」を表します。

分割された領域は正方形や長方形、あるいは任意の形状にすることができます。このデータ構造は、1974年にラファエル・フィンケルとJLベントレーによって四分木と名付けられました。 ^{[1]同様の分割は}Q木としても知られています。

すべての形式の四分木には、いくつかの共通の特徴があります。

• それらは空間を適応可能な細胞に分解します。
• 各セル (またはバケット) には最大容量があります。最大容量に達すると、バケットは分割されます。
• ツリー ディレクトリは、四分木の空間分解に従います。

ツリーピラミッド（Tピラミッド）は「完全な」ツリーです。Tピラミッドのすべてのノードには、リーフノードを除く4つの子ノードがあります。すべてのリーフは同じレベルにあり、そのレベルは画像内の個々のピクセルに対応します。ツリーピラミッドのデータは、完全なバイナリツリーが配列にコンパクトに格納されるのと同様に、暗黙のデータ構造として配列にコンパクトに格納できます。^[2]

四分木は、領域、点、線、曲線など、表現するデータのタイプに応じて分類できます。また、木の形状がデータの処理順序に依存しないかどうかによって分類することもできます。次に、四分木の一般的なタイプを示します。

領域四分木は、領域を 4 つの等しい象限、サブ象限などに分解して 2 次元の空間の分割を表現します。各リーフ ノードには、特定のサブ領域に対応するデータが含まれます。ツリー内の各ノードには、正確に 4 つの子ノードが存在するか、子ノードが存在しない (リーフ ノード) かのいずれかです。この分解戦略に従う四分木の高さ (つまり、サブ象限にさらに改良が必要な興味深いデータがある限りサブ象限を細分化する) は、分解される空間内の興味深い領域の空間分布に敏感で、それに依存します。領域四分木はトライ木の一種です。

深さ n の領域クアッドツリーは、2 ⁿ × 2 ⁿピクセル (各ピクセルの値は 0 または 1) で構成される画像を表すために使用できます。ルート ノードは画像領域全体を表します。いずれかの領域のピクセルが完全に 0 または 1 でない場合は、その領域が再分割されます。このアプリケーションでは、各リーフ ノードは、すべて 0 またはすべて 1 であるピクセルのブロックを表します。これらのツリーを画像の保存に使用すると、スペースを節約できる可能性があることに注意してください。画像には、全体にわたって同じ色の値を持つかなり大きな領域が多数あることがよくあります。画像内のすべてのピクセルの大きな 2 次元配列を保存する代わりに、クアッドツリーは、通常必要となるピクセル解像度サイズのセルよりも潜在的に多くの分割レベル高い同じ情報を取得できます。ツリーの解像度と全体のサイズは、ピクセルと画像のサイズによって制限されます。

リージョン クアッドツリーは、データ フィールドの可変解像度表現としても使用できます。たとえば、あるエリア内の気温をクアッドツリーとして保存し、各リーフ ノードに、それが表すサブリージョンの平均気温を格納します。

ポイント クワッドツリー^{[3]は、2 次元のポイント データを表すために使用される}バイナリ ツリーの応用です。すべてのクワッドツリーの特徴を共有していますが、サブディビジョンの中心が常にポイント上にあるため、真のツリーです。2 次元の順序付けられたデータ ポイントを比較する場合に非常に効率的であり、通常はO(log n)時間で動作します。ポイント クワッドツリーは完全性のために言及する価値がありますが、一般化されたバイナリ検索のツールとしてはk -d ツリーに追い抜かれています。^[4]

ポイント クワッドツリーは次のように構築されます。挿入する次のポイントが与えられたら、そのポイントがあるセルを見つけてツリーに追加します。新しいポイントは、そのポイントを含むセルがポイントを通る垂直線と水平線によって四分円に分割されるように追加されます。その結果、セルは長方形になりますが、必ずしも正方形になるわけではありません。これらのツリーでは、各ノードに入力ポイントの 1 つが含まれます。

平面の分割はポイント挿入の順序によって決定されるため、ツリーの高さは挿入順序に敏感で、挿入順序に依存します。挿入順序が「悪い」場合、ツリーの高さは入力ポイントの数に比例する可能性があります (この時点でリンク リストになります)。ポイント セットが静的である場合、前処理を行ってバランスの取れた高さのツリーを作成できます。

ポイント クアッドツリーのノードは、バイナリ ツリーのノードに似ていますが、主な違いは、通常のバイナリ ツリーのように 2 つ (「左」と「右」) のポインターがあるのではなく、4 つのポインター (各象限に 1 つ) がある点です。また、キーは通常、x 座標と y 座標を参照する 2 つの部分に分解されます。したがって、ノードには次の情報が含まれます。

• 4 つのポインタ: quad['NW']、quad['NE']、quad['SW']、quad['SE']
• ポイント; これには次のものが含まれます:
  • キー。通常は x、y 座標で表されます。
  • 値、例えば名前

ポイントリージョン (PR) クアッドツリー^{[5] [6]}は、リージョンクアッドツリーと非常によく似ています。違いは、セルについて格納される情報の種類です。リージョンクアッドツリーでは、リーフのセルの領域全体に適用される均一な値が格納されます。一方、PR クアッドツリーのセルには、リーフのセル内に存在するポイントのリストが格納されます。前述のように、この分解戦略に従うツリーでは、高さはポイントの空間分布に依存します。ポイントクアッドツリーと同様に、PR クアッドツリーも、「悪い」セットが与えられた場合は線形の高さを持つ場合があります。

エッジ クアッドツリー^{[7] [8]} (PM クアッドツリーによく似ています) は、点ではなく線を格納するために使用されます。曲線は、セルを非常に細かい解像度で細分化することで近似され、具体的には、セルごとに 1 つの線分が存在するようになります。コーナー/頂点の近くでは、エッジ クアッドツリーは、最大レベルの分解に達するまで分割を続けます。これにより、非常に不均衡なツリーが生成され、インデックスの目的が達成されない可能性があります。

ポリゴンマップクアッドツリー（またはPMクアッドツリー）はクアッドツリーの一種で、退化している可能性のあるポリゴン（孤立した頂点またはエッジを持つポリゴン）のコレクションを格納するために使用されます。^{[9] [10]} PMクアッドツリーとエッジクアッドツリーの大きな違いは、セグメントがセル内の頂点で交わる場合、検討中のセルは細分化されないことです。

PM クワッドツリーには 3 つの主なクラスがあり、各ブラック ノード内に格納される情報によって異なります。PM3 クワッドツリーは、交差しないエッジを任意の数だけ格納でき、ポイントは最大 1 つまで格納できます。PM2 クワッドツリーは、すべてのエッジが同じエンドポイントを共有する必要がある点を除いて、PM3 クワッドツリーと同じです。最後に、PM1 クワッドツリーは PM2 に似ていますが、ブラック ノードにはポイントとそのエッジ、またはポイントを共有するエッジのセットのみを含めることができますが、ポイントとそのポイントを含まないエッジのセットを含めることはできません。

この節はサリエル・ハルペレドの著書の一部を要約したものである。^[11]

細分化されたセルに対応するすべてのノードを保存すると、多くの空のノードを保存することになります。このようなスパース ツリーのサイズは、興味深いデータを持つリーフを持つサブツリー (つまり、「重要なサブツリー」) のみを保存することで削減できます。実際には、サイズをさらに削減できます。重要なサブツリーのみを保持すると、剪定プロセスによって、中間ノードが次数 2 (1 つの親と 1 つの子へのリンク) であるツリーに長いパスが残る場合があります。このパスの先頭のノードを保存し (削除されたノードを表すメタデータを関連付け)、その末尾をルートとするサブツリーを にアタッチするだけでよいことがわかります。これらの圧縮されたツリーは、「悪い」入力ポイントが与えられた場合に線形の高さを持つ可能性があります。 ${\displaystyle u}$${\displaystyle u}$

この圧縮を実行するとツリーの大部分がトリミングされますが、 Zオーダー曲線を利用することで、対数時間の検索、挿入、および削除を実現できます。Zオーダー曲線は、完全な 4 分木 (したがって、圧縮された 4 分木も) の各セルを時間的に 1 次元の線にマッピングし (また、時間的に逆マッピングします)、要素に完全な順序を作成します。 したがって、4 分木を順序付きセットのデータ構造 (ツリーのノードを格納する) に格納できます。 ${\displaystyle O(1)}$${\displaystyle O(1)}$

先に進む前に、妥当な仮定を述べなければなりません。2進数として表現された 2 つの実数が与えられた場合、それらの異なる最初のビットのインデックスを時間内に計算できると仮定します。また、4 分木内の 2 つのポイント/セルの最下位の共通祖先を時間内に計算してそれらの相対的なZ順序を確立し、フロア関数を時間内に計算できると仮定します。 ${\displaystyle \alpha,\beta\in[0,1)}$${\displaystyle O(1)}$${\displaystyle O(1)}$${\displaystyle O(1)}$

これらの仮定により、特定のポイントの位置(つまり、 を含むセルの決定)、挿入、および削除操作はすべて、時間内 (つまり、基礎となる順序付きセット データ構造で検索を実行するのにかかる時間) に実行できます。 ${\displaystyle q}$${\displaystyle q}$${\displaystyle O(\log {n})}$

ポイントの位置を特定するには（つまり、圧縮されたツリー内でセルを見つけるには）： ${\displaystyle q}$

1. 圧縮されたツリー内で、Z順序で前に来る既存のセルを見つけます。このセルを と呼びます。${\displaystyle q}$${\displaystyle v}$
2. の場合、 を返します。${\displaystyle q\in v}$${\displaystyle v}$
3. それ以外の場合は、圧縮されていない四分木内の点とセルの最低共通祖先となるものを検索します。この祖先セルを と呼びます。${\displaystyle q}$${\displaystyle v}$${\displaystyle u}$
4. 圧縮されたツリー内でZ順序で前に来る既存のセルを見つけて返します。${\displaystyle u}$

具体的な詳細には立ち入りませんが、挿入と削除を実行するには、まず挿入/削除したいもののポイントの位置を特定し、次に挿入/削除します。必要に応じてノードを作成および削除し、ツリーを適切に再形成するように注意する必要があります。

• 画像表現
  
• 画像処理
• メッシュ生成^[12]
• 空間インデックス、ポイント位置クエリ、範囲クエリ
• 2次元での効率的な衝突検出
• 地形データの錐台カリングを表示する
• スプレッドシートの書式設定情報^[13]や一部の行列計算^{[要出典]などのスパースデータの保存}
• 多次元場の解法（数値流体力学、電磁気学）
• コンウェイのライフゲームシミュレーションプログラム。^[14]
• 状態推定^[15]
• 四分木はフラクタル画像解析の分野でも使用されている。
• 最大非結合集合

四分木、特に領域四分木は、画像処理アプリケーションに適しています。ここではバイナリ画像データに限定して説明しますが、領域四分木とそれに対して実行される画像処理操作はカラー画像にも適しています。^{[4] [16]}

画像操作にクアッドツリーを使用する利点の 1 つは、和集合演算と積集合演算を簡単かつ迅速に実行できることです。^{[4] [17] [18] [19] [20]} 2 つのバイナリ画像が与えられた場合、画像の和集合演算 (オーバーレイとも呼ばれる) により、入力画像のいずれかに同じ場所に黒いピクセルがある場合にピクセルが黒になる画像が生成されます。つまり、出力画像のピクセルは、両方の入力画像の対応するピクセルが白の場合にのみ白になり、それ以外の場合は出力ピクセルは黒になります。ピクセルごとに演算を行うのではなく、単一のノードで複数のピクセルを表すクアッドツリーの機能を活用することで、和集合演算をより効率的に計算できます。以下の説明では、サブツリーに黒と白のピクセルの両方が含まれる場合、そのサブツリーのルートは灰色であるとします。

このアルゴリズムは、出力クアッドツリーを構築しながら、2 つの入力クアッドツリー (および) を走査することによって機能します。非公式には、アルゴリズムは次のようになります。画像内の同じ領域に対応する ノードとを 検討します。${\displaystyle T_{1}}$${\displaystyle T_{2}}$${\displaystyle T}$${\displaystyle v_{1}\in T_{1}}$${\displaystyle v_{2}\in T_{2}}$

• またはが黒の場合、対応するノードが に作成され、黒色になります。どちらか一方のみが黒で、もう一方が灰色の場合、灰色のノードの下にサブツリーが含まれます。このサブツリーをトラバースする必要はありません。${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle T}$
• (それぞれ、) が白の場合、 (それぞれ、) となり、その下のサブツリー (存在する場合) が にコピーされます。${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{2}}$${\displaystyle v_{1}}$${\displaystyle T}$
• と の両方が灰色の場合、との対応する子が考慮されます。${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{1}}$${\displaystyle v_{2}}$

このアルゴリズムは機能しますが、それ自体では最小サイズの四分木を保証するものではありません。たとえば、サイズ のチェッカーボード (各タイルがピクセル) とその補数を結合した場合の結果を考えてみましょう。結果は巨大な黒い正方形であり、これはルートノード (黒色) のみの四分木で表現されるべきですが、代わりにアルゴリズムは深さ の完全な 4 元木を生成します。これを修正するには、結果の四分木をボトムアップに走査して、4 つの子ノードが同じ色であるかどうかを確認し、同じ色である場合は親を同じ色の葉で置き換えます。^[4]${\displaystyle 2^{k}\times 2^{k}}$${\displaystyle k}$

2 つの画像の交差は、ほぼ同じアルゴリズムです。2 つの画像の交差について考える 1 つの方法は、白いピクセルに関して結合を行うことです。したがって、交差を実行するには、結合アルゴリズムで黒と白の記述を入れ替えます。

バイナリ画像内の 2 つの隣接する黒ピクセルについて考えてみましょう。境界となる水平または垂直のエッジを共有している場合、それらは隣接しています。一般に、2 つの黒ピクセルが接続されていると判断されるのは、一方から他方まで隣接するピクセルへの移動によってのみ到達できる場合です (つまり、連続する各ペアが隣接する黒ピクセルのパスがそれらの間にある場合)。接続された黒ピクセルの最大セットはそれぞれ、接続されたコンポーネントです。Samet ^[21]は、画像の 4 分木表現を使用して、 4 分木のサイズに比例した時間でこれらの接続されたコンポーネントを見つけてラベル付けする方法を示しました。^{[4] [22]}このアルゴリズムは、ポリゴンの色付けにも使用できます。

アルゴリズムは次の 3 つのステップで動作します。

1. 黒ピクセル間の隣接関係を確立する
2. 最初のステップから同値関係を処理して、接続された各コンポーネントに1つの一意のラベルを取得します。
3. 黒いピクセルに、その接続されたコンポーネントに関連付けられたラベルを付ける

議論を簡略化するために、クアッドツリー内のノードの子はZ順序(SW、NW、SE、NE) に従うと仮定します。この構造を当てにすることができるため、どのセルについても、クアッドツリーをナビゲートして階層の異なるレベルにある隣接するセルを見つける方法がわかります。

ステップ 1 は、四分木の事後順序トラバーサルで実行されます。各黒の葉について、北隣と東隣のセルを表すノード (つまり、 のセルとエッジを共有する北と東のセル) を調べます。ツリーはZ順序で構成されていることから、南と西の隣はすでに処理され、考慮されているという不変条件があります。現在検討中の北または東の隣を とします。 が黒のピクセルを表す 場合:${\displaystyle v}$${\displaystyle v}$${\displaystyle u}$${\displaystyle u}$

• またはのいずれかにのみラベルがある場合は、そのラベルを他のセルに割り当てます。${\displaystyle u}$${\displaystyle v}$
• どちらにもラベルがない場合は、ラベルを作成して両方に割り当てます。
• とが異なるラベルを持っている場合は、このラベルの等価性を記録して先に進みます。${\displaystyle u}$${\displaystyle v}$

ステップ2は、union-findデータ構造を使用して実行できます。^[23]各一意のラベルを個別のセットとして開始します。最初のステップで記録されたすべての同値関係について、対応するセットを結合します。その後、残りの各個別のセットは、画像内の個別の接続コンポーネントに関連付けられます。

ステップ 3 では、別の後順トラバーサルを実行します。今回は、各黒ノードに対して、union-find の検索操作 ( の古いラベルを使用)を使用して、新しいラベル ( の一部である接続コンポーネントに関連付けられている) を検索して割り当てます。 ${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$

このセクションでは、Har-Peledとde Bergらによる書籍の章を要約します。^{[24] [25]}

メッシュ生成は、本質的には、さらなる処理を実行できるポイント セットの三角形分割です。したがって、結果の三角形分割には、さらなる処理を高速化し、エラーが発生しにくくするために、特定のプロパティ (非均一性、細すぎない三角形、疎らな領域に大きな三角形、密な領域に小さな三角形など) が備わっていることが望ましいです。ポイント セット上に構築された四分木を使用して、これらの望ましいプロパティを持つメッシュを作成できます。

四分木の葉とそれに対応するセルについて考えます。セルの辺が、各辺で隣接セルの角の点と最大 1 回交差している場合、四分木はバランスが取れていると言えます (メッシュ生成の場合)。つまり、 に隣接する葉の四分木レベルは、 のレベルと最大 1 しか異なりません。これがすべての葉に当てはまる場合、四分木全体がバランスが取れていると言えます (メッシュ生成の場合)。 ${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$${\displaystyle v}$

セルと、を中心とする同じサイズのセルの近傍を考えます。この近傍を拡張クラスタと呼びます。四分木がバランスが取れているとは、四分木がバランスが取れていて、点集合の点を含むすべての葉に対して、その拡張クラスタも四分木内にあり、拡張クラスタに点集合の他の点が含まれない場合です。 ${\displaystyle v}$${\displaystyle 5\times 5}$${\displaystyle v}$${\displaystyle u}$

メッシュの作成は次のように行います。

1. 入力ポイントに四分木を構築します。
2. 四分木のバランスが取れていることを確認します。各葉について、隣接する葉が大きすぎる場合は、隣接する葉を細分化します。この操作は、木のバランスが取れるまで繰り返されます。また、ポイントを含む葉については、各葉の拡張クラスターのノードが木内にあることを確認します。
3. ポイントを含むすべてのリーフ ノードについて、拡張されたクラスターに別のポイントが含まれている場合は、ツリーをさらに細分化し、必要に応じて再バランス調整します。の子ごとに、ツリー内に拡張されたクラスターのノードがあることを確認します (必要に応じて再バランス調整します)。${\displaystyle v}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$
4. 木のバランスが取れるまで前の手順を繰り返します。
5. 四分木を三角形に変換します。

ツリー セルの角の点を三角形分割の頂点と見なします。変換ステップの前に、いくつかの点を含むボックスが多数あります。変換ステップは、次の方法で実行されます。各点について、セルの最も近い角をその点に合うようにワープし、結果として得られる 4 つの四角形を三角形分割して「きれいな」三角形を作成します (「きれいな」三角形を作成する方法の詳細については、Har-Peled ^[24]の第 12 章を参照してください)。

残りの正方形は、いくつかの簡単なルールに従って三角形に分割されます。各正方正方形 (内部に点がなく、辺に角点がない) に対して、対角線を導入します。バランスの取れた特性を持つ点の分離方法により、角が辺と交差する正方形は歪んだ正方形にはなりません。したがって、次のようにして、角が交差する正方形を三角形に分割できます。交差する辺が 1 つある場合、交差点と反対の角を結ぶ長い対角線を追加することで、正方形は 3 つの三角形になります。交差する辺が 4 つある場合は、4 つの交差点のうち 2 つの間に辺を追加して正方形を半分に分割し、これらの 2 つの端点を残りの 2 つの交差点に接続します。その他の正方形については、中央に点を導入し、それを正方形の 4 つの角すべてと各交差点に接続します。

最後に、四分木から構築されたポイント セットのきれいな三角形メッシュが完成します。

次の疑似コードは、ポイントのみを処理する四分木を実装する 1 つの方法を示しています。他のアプローチも利用できます。

これらの構造が使用されると想定されます。

 // ポイントとベクトルを表すシンプルな座標オブジェクト
struct XY { float x ; float y ; function __construct ( float _x , float _y ) {...} } // 半分の次元と中心を持つ軸に沿った境界ボックスstruct AABB { XY center ; float halfDimension ; function __construct ( XY _center , float _halfDimension ) {...} function containsPoint ( XY point ) {...} function intersectsAABB ( AABB other ) {...} }  
 
      
      
 
          
 
 
 
  
 
      
      
 
          
        
        
 

このクラスは、1 つの四分木とそれがルートとなるノードの両方を表します。

 class QuadTree { // この四分木ノードに格納できる要素の数を示す任意の定数 constant int QT_NODE_CAPACITY = 4 ; //この四分木ノードの境界を表すために、軸に沿った境界ボックスが中心として格納され、その半分の次元が格納されますAABB boundary ; // この四分木ノードのポイントXY [ size = QT_NODE_CAPACITY ] pointsの配列; // 子QuadTree * northWest ; QuadTree * northEast ; QuadTree * southWest ; QuadTree * southEast ; // メソッドfunction __construct ( AABB _boundary ) {...} function insert ( XY p ) {...} function subdivide () {...} // この四分木を 4 つの等面積の四分木に完全に分割する 4 つの子を作成しますfunction queryRange ( AABB range ) {...} } 
 
     
         
 
     
     
      
 
     
           
 
     
      
      
      
      
 
     
        
        
        
        
 

次のメソッドは、必要に応じて分割しながら、四分木の適切な四分木にポイントを挿入します。

 class QuadTree { ... // QuadTree にポイントを挿入します。function insert ( XY p ) { // この四分木に属さないオブジェクトは無視します。if ( ! boundary . containsPoint ( p )) return false ; // オブジェクトは追加できません。 // この四分木にスペースがあり、細分化されていない場合は、ここにオブジェクトを追加します。if ( points . size < QT_NODE_CAPACITY && northWest == null ) { points . append ( p ); return true ; } // それ以外の場合は、細分化してから、それを受け入れるノードにポイントを追加します。if ( northWest == null ) subdivide (); //最後のノードだけにデータを保持させたい場合は、この四分木配列に含まれるポイント/データを新しい四分木に追加する必要があります。if ( northWest -> insert ( p )) return true ; if ( northEast -> insert ( p )) return true ; if ( southWest -> insert ( p )) return true ; if ( southEast -> insert ( p )) return true ; // それ以外の場合、何らかの不明な理由によりポイントを挿入できません (これは決して発生しないはずです) return false ; } } 
 
     
   
     
       
     
         
          
               
     
         
                
         
             
              
         
     
         
            
             
         
         
     
            
            
            
            
     
         
          
     
 

次のメソッドは、範囲に含まれるすべてのポイントを検索します。

 class QuadTree { ... // 範囲内に現れるすべてのポイントを検索しますfunction queryRange ( AABB range ) { // 結果の配列を準備しますXYの配列pointsInRange ; // 範囲がこの四角形と交差しない場合は自動的に中止しますif ( ! boundary . intersectsAABB ( range )) return pointsInRange ; // 空のリスト// この四角形レベルのオブジェクトを確認しますfor ( int p = 0 ; p < points . size ; p ++ ) { if ( range . containsPoint ( points [ p ])) pointsInRange . append ( points [ p ]); } // 子がいない場合はここで終了しますif ( northWest == null ) return pointsInRange ; // それ以外の場合は、子からポイントを追加しますpointsInRange . appendArray ( northWest -> queryRange ( range )); pointsInRange . appendArray ( northEast -> queryRange ( range )); pointsInRange.appendArray ( southWest -> queryRange ( range )); pointsInRange.appendArray ( southEast - > queryRange ( range ) ); pointsInRangeを返します; } } 
 
     
   
     
       
     
         
            
     
         
          
               
     
         
                 
         
              
                 
         
     
         
            
              
     
         
         
         
         
         
     
          
     
 

• 適応メッシュ改良
• バイナリ空間分割
• バイナリタイリング
• k -d ツリー
• オクトリー
• Rツリー
• UBツリー
• 空間データベース
• 下地舗装
• Zオーダー曲線

Aluru ^[4]とSamet ^{[22] [16]}による調査では、四分木の概要がよく示されています。

1. Raphael FinkelおよびJL Bentley ( 1974)。「Quad Trees: 複合キーによる検索のためのデータ構造」。Acta Informatica。4 ( 1) : 1–9。doi : 10.1007 /BF00288933。S2CID  33019699。
2. マーク・デ・バーグ、マルク・ファン・クレフェルト、マーク・オーヴァーマルス、オトフリード・シュワルツコップ（2000年）。計算幾何学(改訂第 2 版)。スプリンガー・フェルラーグ。ISBN 3-540-65620-0。{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)第14章: 四分木: pp. 291–306。
3. Samet, Hanan ; Webber, Robert (1985 年 7 月)。「四分木を使用したポリゴンのコレクションの保存」(PDF) 。2012年3 月 23 日閲覧。