【しぶんぎ】
四分木（Quadtree） とは？
公開:
💡 地図を四つに、混んだ場所はさらに四つに
2次元の領域を再帰的に四つへ分けて管理する木構造。点の位置検索や画像の領域管理などに使い、細かく調べたい部分だけを深く分割できる。
📌 このページのポイント
- 2次元領域を四つの子領域へ分割し、必要な場所で再帰的に繰り返す
- 等分する方式や点を基準に分ける方式などの種類がある
- 点の集中や重複に備え、分割の停止条件を決める必要がある
ひよこ 四分木は、何を四つにするの？
ペンギン先生 平面の領域だよ。ここでは正方形を同じ大きさの四つに分ける方式を考えよう。点が多い子領域だけをさらに四つに分ければ、全体を同じ細かさの格子にしなくても位置を管理できるんだ。
ひよこ 何回も分けたら、領域はいくつになるの？
ペンギン先生 図では最初の四つのうち右上だけをさらに四つに分けるよ。右上の1領域を4領域に置き換えるので、末端の領域は3＋4で7個。全領域を同じ深さまで分けるわけではないんだ。
ひよこ 全部が同じ場所にある点なら？
ペンギン先生 分け続けても別れないよね。そこで同じ座標の点をまとめて持つ、深さや最小サイズの上限を置く、といった規則が必要だよ。D3の実装では同じ座標の点を連結リストで保持しているんだ。
ひよこ 近くの点を探すときは、同じマスだけ見ればいい？
ペンギン先生 境界をまたいですぐ近くにある点もあるから、同じマスだけでは足りないよ。検索範囲と交わる領域をたどり、必要なら実際の距離を調べるんだ。関係しない領域をまとめて外せるのが利点で、いつでも一定の速さで終わるわけではないね。
もっと詳しく知りたい人へ
k-d木とどう違いますか？
k-d木は基本的に一つの軸に沿って二分し、四分木は2次元を四領域に分けます。ただし四分木にも点を境界の基準にする種類などがあるため、「必ず等しい正方形に分ける」は全種類には当てはまりません。図は等分型の例です。
まとめ：ざっくりこれだけ覚えればOK！
「四分木（Quadtree）」って出てきたら「平面を四つずつ分け、必要な場所を細かく管理する木」と思えればだいたいOK！