Loading AI tools
ウィキペディアから
四分木（しぶんぎ、英: 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座標に対応する。従って、ノードには以下の情報が格納されている。
辺四分木 (edge quadtree) は、点ではなく線を格納するのに使われる。曲線はセルを微細に分割することで近似的に表す。結果として得られる木構造は非常にアンバランスであり、インデックス付けの用途には向かない。
四分木は八分木の2次元版と見ることもできる。
幾何学的分割で各象限のアイテム数が減らない場合（データがオーバーラップしている場合など）、四分木による分割は失敗し、アルゴリズムが続く限りメモリを消費し続けることになる。例えば、1つの象限の容量の上限が8の場合、(0, 0) に9つの点があるとすると、分割しても3つの象限は空で、残る1つに9つの点が含まれることになる。従って、再帰的に分割が必要になるが、どこまで分割しても上限を超えてしまう。そのような場合、1つの象限に8個以上の点を許容せざるを得ないので、四分木は任意の幾何学的データ群について O(N) の複雑性に漸近していく。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
