四分木

四分木（Quadtree）とは

四分木とは、各ノードが最大4つの子ノードを持つ木構造のデータ構造です。主に2次元空間を再帰的に4分割する際に利用され、空間インデックスとして機能します。1974年にRaphael FinkelとJ.L. Bentleyによって提唱されました。Q木（Q-tree）と呼ばれることもあります。

四分木の特徴

空間の適応的分割: 空間を均等なセルに分割するのではなく、データ分布に合わせて分割します。
容量制限: 各セル（バケット）には容量上限があり、上限に達するとセルがさらに分割されます。
木構造: 空間分割は木構造で表現されます。

四分木の種類

四分木は表現するデータの種類によって、いくつかの種類に分類されます。代表的なものとして、領域四分木、点四分木、辺四分木があります。

領域四分木

領域四分木は、2次元空間を同じサイズの4つの象限に再帰的に分割するものです。各ノードは特定の領域に対応するデータを保持します。領域四分木は、分割位置がデータに依存しないため、厳密には木構造ではなく、Trieに近い構造です。

領域四分木の応用例

画像の表現: 画像をピクセル単位で分割し、各ピクセルの値を保持します。領域を分割し、各領域が同じ色のピクセルのみを持つように分割を繰り返すことで、画像データを効率的に格納します。
空間データの表現: 例えば、ある地域の温度分布を格納する場合、各葉ノードは同じ温度の領域を表します。これにより、温度変化の少ない領域をまとめて管理できます。

点四分木

点四分木は、2次元座標データを表現するために二分木を拡張したものです。各ノードは、分割の中心となる座標点を持ちます。木構造はデータの追加順序によって変化します。

点四分木のノード構造

点四分木のノードは、以下の情報を含みます。

4つのポインタ: 北西、北東、南西、南東の各象限へのポインタ
点データ: キー（x座標とy座標）と値（名前など）

辺四分木

辺四分木は、点を表現するのではなく、線を表現するために用いられます。曲線は、セルを細かく分割することで近似的に表現します。しかし、構造が非常にアンバランスになるため、インデックスには不向きです。

四分木の主な用途

四分木は、以下のような様々な用途で利用されています。

空間インデックス: 地理情報システム（GIS）など、空間データの効率的な検索を可能にします。
画像データ格納: 画像データを効率的に圧縮・格納するために利用されます。
当たり判定: 2次元空間における衝突判定を高速化できます。
地形データの視野判定: 3Dゲームなどにおける地形の描画範囲を高速に決定できます。
疎なデータ格納: スプレッドシートや行列計算における欠損値を効率的に管理します。
数値流体力学: 多次元の場を数値的に解く際に利用されます。
セル・オートマトン: ライフゲームなどのシミュレーションに利用されます。

四分木の注意点

幾何学的分割によって、各象限のアイテム数が減らない場合（データが重なっている場合など）は、分割を繰り返してもメモリを消費し続ける可能性があります。例えば、1つの象限の最大容量が8の場合、(0, 0) に9つの点があると、分割しても1つの象限に9つ点が残ってしまいます。その結果、無限に分割を繰り返すことになり、四分木の効率が低下します。

このような場合は、1つの象限に許容する最大数を大きくするか、他のデータ構造を検討する必要があるでしょう。最悪の場合、四分木の計算量は O(N) に近づきます。

まとめ

四分木は、2次元空間におけるデータの効率的な管理と検索のための強力なツールです。画像処理、地理情報システム、ゲーム開発など、さまざまな分野で活用されています。その応用範囲は広く、適切に利用することで、計算の高速化やメモリ効率の向上が期待できます。

参考文献

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.

関連項目

八分木
バイナリ空間分割
kd木
R木
空間インデックス

外部リンク

A discussion of the Quadtree and an application
* Considerable discussion and demonstrations of Spatial Indexing

もう一度検索