[[四分木]]

四分木

基本的に、n分木といったら「子が必ずn個である木構造」を指すが、特に四分木は2次元座標を分割するのに使われる。

各節は領域を表し、x, y座標を2つずつ、つまり4つに分割した領域を子に持つ。

例えば大量の弾があるシューティングゲームで、自機と全ての弾との衝突判定を計算していては時間がかかる。四分木を利用すれば2次元平面上にある大量のオブジェクトを効率的に管理できるため、「自機に衝突する可能性のある近い弾」を絞り込める。

分割の仕方

単に四分木という場合、大きく分けて、2つの分け方がある。

  • 常に半分で分割
    • 指定した領域にかぶる領域の探索が得意
  • 常に点の位置で分割
    • 特定の点を見つける探索が得意

特に四分木特有のデータ構造が活かせるのは、半分で分割する方なので、そちらについて説明する。

常に半分で分割

各節は領域を表す

┌───┐  ┌─┬─┐  ┌┬┬┬┐
│      │  │  │  │  ├┼┼┼┤
│      │→├─┼─┤→├┼┼┼┤
│      │  │  │  │  ├┼┼┼┤
└───┘  └─┴─┘  └┴┴┴┘

常に点の位置で分割

この場合、各節は領域で無く点を表す。

┌─────┐  ┌──┬──┐  ┌─┬┬──┐
│  ・      │  │  ・│    │  ├─・┤    │
│    ・    │→├──・──┤→├┬┴・┬─┤
│・        │  │・  │    │  ├・─┤│  │
│      ・  │  │    │・  │  ││  ├・─┤
│        ・│  │    │  ・│  ││  ││・│
└─────┘  └──┴──┘  └┴─┴┴─┘

領域番号の振り方

モートン符号という振り方を用いる。Z型に振る。

領域番号
 階層0      階層1     階層2
┌───┐  ┌─┬─┐
│      │  │2│3│  10 11 14 15
│  0  │→├─┼─┤→8 9 12 13
│      │  │0│1│  2 3 6 7
└───┘  └─┴─┘  0 1 4 5

これを、1次元配列で持てるように全階層でつなげて一意にしたのが、以下

インデックス
 階層0      階層1     階層2
┌───┐  ┌─┬─┐
│      │  │3│4│  15 16 19 20
│  0  │→├─┼─┤→13 14 17 18
│      │  │1│2│  7 8 11 12
└───┘  └─┴─┘  5 6 9 10

こうすると何が良いかというと、「親のインデックス×4+1~4」で、子の4つのインデックスが表せ、親子関係を辿りやすい。

また、階層Lのインデックスの最大値は初項1, 公比4の公比級数の和となるため、$\displaystyle \frac{4^{L+1} - 1}{4 - 1}-1$ で表される。階層L,領域番号Nにある領域のインデックスは、親の階層のインデックス最大値に、自身の領域番号+1を足したものとなる。つまり、$\displaystyle \frac{4^L - 1}{3}+N$となり、インデックスと領域番号の変換も単純な演算で可能となる。

programming_algorithm/data_structure/quadtree.txt · 最終更新: 2017/10/13 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0