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

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

種類

編集

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

領域四分木

編集

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

深さ 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次元版と見ることもできる。

注意点

編集

幾何学的分割で各象限のアイテム数が減らない場合(データがオーバーラップしている場合など)、四分木による分割は失敗し、アルゴリズムが続く限りメモリを消費し続けることになる。例えば、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.

関連項目

編集

外部リンク

編集