データ構造「四分木（クアッドツリー）」とは？仕組みと活用例を徹底解説

四分木（クアッドツリー）とは

四分木（クアッドツリー、Quadtree）は、2次元空間上の点データを効率的に格納するために設計された木構造のデータ構造です。この木では、各ノードが最大4つの子ノードを持ちます。

四分木の構築手順

2次元の領域から四分木を構築するには、以下の手順を繰り返し実行します。

• 現在の2次元空間を4つの矩形（ボックス）に分割します。
• 矩形の中に1つ以上の点が含まれている場合は、その矩形の2次元空間を格納する子ノードを作成します。
• 矩形に点が1つも含まれていない場合は、子ノードを作成しません。
• それぞれの子ノードに対して、同じ処理を再帰的に実行します。

四分木の主な応用例

画像圧縮への応用

四分木は画像圧縮の分野でも広く利用されています。この場合、各ノードはその子ノードの色の平均値を保持します。

木を深くたどるほど、画像の細部がより精細に表現される仕組みになっています。

2次元空間内の探索への応用

四分木は、2次元領域内のノード検索にも活用されます。例えば、指定された座標に最も近い点を求めたい場合にも、四分木を使うことで効率的に計算できます。

挿入関数（Insert）

挿入関数は、既存の四分木にノードを追加するために使用されます。まず、指定されたノードが現在のクアッド（領域）の境界内に存在するかどうかを確認します。境界外であれば、その時点で挿入を中止します。境界内であれば、ノードの位置に基づいて適切な子ノードを選択し、そこに格納します。この関数の計算量はO(log N)です。ここでNは距離のサイズを表します。

探索関数（Search）

探索関数は、指定されたクアッド内のノードを見つけるために使用されます。工夫を加えれば、指定した点に最も近いノードを返すことも可能です。この関数は、与えられた点を子クアッドの境界と比較しながら再帰的に処理を進めることで実現されます。計算量は挿入関数と同様にO(log N)です。

四分木の主な用途

• 画像の表現
• 画像処理
• メッシュ生成
• 2次元空間における効率的な衝突判定
• 多次元場の求解（数値流体力学、電磁気学など）
• 状態推定
• フラクタル画像解析