四分木

四分木（しぶんぎ、英: Quadtree）は、各内部ノードが4個までの子ノードを持つ木構造のデータ構造である。四分木は主に、2次元空間を再帰的に4つの象限または領域に分割するのに使われる。領域は四角形または矩形の場合もあるし、任意の形状の場合もある。このデータ構造は1974年、Raphael Finkel と J.L. Bentley が四分木と名づけた。同様の分割手法はQ木 (Q-tree) とも呼ばれている。四分木に共通する特徴は以下の通りである。

空間を適応可能セルに分割する。
各セル（またはバケット）は容量の上限がある。容量が最大に達すると、バケットは分割される。
木構造ディレクトリは四分木の空間分割に従う。

種類

四分木は表現するデータの型によって分類され、領域 (area)、点 (point)、線 (line)、曲線 (curve) などがある。また、木構造の形状とデータを処理する順序が独立しているかどうかでも分類される。典型的な四分木について以下に解説する。

領域四分木

領域四分木は、2次元の空間を同じ大きさの4つの象限に再帰的に分割していくもので、各ノードは特定の領域に対応したデータを保持する。各ノードは4つの子ノードを持つか、あるいは全く子ノードを持たないか（つまり葉ノード）のどちらかである。領域四分木は、分割位置がデータに依存していないため、厳密には木構造ではないとされる。より厳密に言えばTrieに近い。

深さ n の領域四分木は、 $2^{n}*2^{n}$ ピクセルで各ピクセルの値が0か1の画像を表現するのにも使われる。根ノードはその画像領域全体を表している。ある部分領域に属するピクセルが全て0あるいは1でない場合、その部分領域はさらに分割される。つまり、各葉ノードは全ピクセルが0あるいは1のブロックを表している。

領域四分木は、平面上のデータの分布を表すのにも使われる。例えば、ある領域の温度の分布を四分木に格納すると、葉ノードは同じ温度の領域を表すことになる。

座標データ群（例えば、都市の緯度と経度）を四分木に格納する場合、各葉ノードが最大1つの座標点を格納する状態になるまで分割が行われる。

点四分木

点四分木は、二分木を2次元座標データを表すように適応させたものである。分割の中心点には常に1つの点データが対応する。木構造の形状はデータを処理する順序に依存する。2次元座標データ列を効率的に比較することができ、一般的な処理時間は O(log n) である。

点四分木のノード構造

点四分木のノードは二分木のノードに似ているが、子ノードが4つあるところが大きく異なる（二分木は右と左の2つ）。またキーは2つの成分に分かれていて、一般にx座標とy座標に対応する。従って、ノードには以下の情報が格納されている。

4つのポインタ - 北西象限、北東象限、南西象限、南東象限
点 - さらに以下の内容が点データとして含まれる
- キー - x座標とy座標で表される
- 値 - 名前など

辺四分木

辺四分木 (edge quadtree) は、点ではなく線を格納するのに使われる。曲線はセルを微細に分割することで近似的に表す。結果として得られる木構造は非常にアンバランスであり、インデックス付けの用途には向かない。

主な用途

空間インデックス
画像データ格納
2次元における効率的当たり判定
地形データの視野判定
スプレッドシートまたは何らかの行列計算のためのフォーマッティング情報などの疎なデータを格納する。
多次元の場を解く（数値流体力学、電磁気学）
セル・オートマトン（ハッシュライフ）

四分木は八分木の2次元版と見ることもできる。

注意点

幾何学的分割で各象限のアイテム数が減らない場合（データがオーバーラップしている場合など）、四分木による分割は失敗し、アルゴリズムが続く限りメモリを消費し続けることになる。例えば、1つの象限の容量の上限が8の場合、(0, 0) に9つの点があるとすると、分割しても3つの象限は空で、残る1つに9つの点が含まれることになる。従って、再帰的に分割が必要になるが、どこまで分割しても上限を超えてしまう。そのような場合、1つの象限に8個以上の点を許容せざるを得ないので、四分木は任意の幾何学的データ群について O(N) の複雑性に漸近していく。

参考文献

Raphael Finkel and J.L. Bentley (1974年). “Quad Trees: A Data Structure for Retrieval on Composite Keys”. Acta Informatica 4 (1): 1–9. doi:10.1007/BF00288933.
Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000年). Computational Geometry (2nd revised edition ed.). Springer-Verlag. ISBN 3-540-65620-0 Chapter 14: Quadtrees: pp.291–306.

外部リンク

種類