四分木
基本的に、n分木といったら「子が必ずn個である木構造」を指すが、特に四分木は2次元座標を分割するのに使われる。
各節は領域を表し、x, y座標を2つずつ、つまり4つに分割した領域を子に持つ。
例えば大量の弾があるシューティングゲームで、自機と全ての弾との衝突判定を計算していては時間がかかる。四分木を利用すれば2次元平面上にある大量のオブジェクトを効率的に管理できるため、「自機に衝突する可能性のある近い弾」を絞り込める。
分割の仕方
単に四分木という場合、大きく分けて、2つの分け方がある。
- 常に半分で分割
- 指定した領域にかぶる領域の探索が得意
- 常に点の位置で分割
- 特定の点を見つける探索が得意
特に四分木特有のデータ構造が活かせるのは、半分で分割する方なので、そちらについて説明する。
常に半分で分割
各節は領域を表す
┌───┐ ┌─┬─┐ ┌┬┬┬┐ │ │ │ │ │ ├┼┼┼┤ │ │→├─┼─┤→├┼┼┼┤ │ │ │ │ │ ├┼┼┼┤ └───┘ └─┴─┘ └┴┴┴┘
常に点の位置で分割
この場合、各節は領域で無く点を表す。
┌─────┐ ┌──┬──┐ ┌─┬┬──┐ │ ・ │ │ ・│ │ ├─・┤ │ │ ・ │→├──・──┤→├┬┴・┬─┤ │・ │ │・ │ │ ├・─┤│ │ │ ・ │ │ │・ │ ││ ├・─┤ │ ・│ │ │ ・│ ││ ││・│ └─────┘ └──┴──┘ └┴─┴┴─┘
領域番号の振り方
モートン符号という振り方を用いる。Z型に振る。
領域番号 階層０ 階層１ 階層２ ┌───┐ ┌─┬─┐ │ │ │２│３│ 10 11 14 15 │ ０ │→├─┼─┤→８ ９ 12 13 │ │ │０│１│ ２ ３ ６ ７ └───┘ └─┴─┘ ０ １ ４ ５
これを、1次元配列で持てるように全階層でつなげて一意にしたのが、以下
インデックス 階層０ 階層１ 階層２ ┌───┐ ┌─┬─┐ │ │ │３│４│ 15 16 19 20 │ ０ │→├─┼─┤→13 14 17 18 │ │ │１│２│ ７ ８ 11 12 └───┘ └─┴─┘ ５ ６ ９ 10
こうすると何が良いかというと、「親のインデックス×４＋１～４」で、子の4つのインデックスが表せ、親子関係を辿りやすい。
また、階層Lのインデックスの最大値は初項1, 公比4の公比級数の和となるため、$\displaystyle \frac{4^{L+1} - 1}{4 - 1}-1$ で表される。階層L,領域番号Nにある領域のインデックスは、親の階層のインデックス最大値に、自身の領域番号+1を足したものとなる。つまり、$\displaystyle \frac{4^L - 1}{3}+N$となり、インデックスと領域番号の変換も単純な演算で可能となる。
