文書の過去の版を表示しています。
四分木
基本的に、n分木といったら「子が必ずn個である木構造」を指すが、特に四分木は2次元座標を分割するのに使われる。
各節は領域を表し、x, y座標を2つずつ、つまり4つに分割した領域を子に持つ。
例えば大量の弾があるシューティングゲームで、自機と全ての弾との衝突判定を計算していては時間がかかるため、何とか「自機に衝突する可能性のある弾だけ」と衝突判定を行いたい、など、2次元平面上にある大量のオブジェクトを効率的に管理できる。
分割の仕方
単に四分木という場合、大きく分けて、2つの分け方がある。
- 常に半分で分割
- 指定した領域にかぶる領域の探索が得意
- 常に点の位置で分割
- 特定の点を見つける探索が得意
特に四分木特有のデータ構造が活かせるのは、半分で分割する方なので、そちらについて説明する。
常に半分で分割
各節は領域を表す
┌───┐ ┌─┬─┐ ┌┬┬┬┐ │ │ │ │ │ ├┼┼┼┤ │ │→├─┼─┤→├┼┼┼┤ │ │ │ │ │ ├┼┼┼┤ └───┘ └─┴─┘ └┴┴┴┘
常に点の位置で分割
この場合、各節は領域で無く点を表す。
┌─────┐ ┌──┬──┐ ┌─┬┬──┐ │ ・ │ │ ・│ │ ├─・┤ │ │ ・ │→├──・──┤→├┬┴・┬─┤ │・ │ │・ │ │ ├・─┤│ │ │ ・ │ │ │・ │ ││ ├・─┤ │ ・│ │ │ ・│ ││ ││・│ └─────┘ └──┴──┘ └┴─┴┴─┘
領域番号の振り方
領域番号を振り、親の領域番号から子の領域番号を一意に計算できると、木構造を1次元の配列で持つことができて効率的。
モートン符号という振り方を用いる。Z型に振る。
┌───┐ ┌─┬─┐ │ │ │３│４│ 15 16 19 20 │ ０ │→├─┼─┤→13 14 17 18 │ │ │１│２│ ７ ８ 11 12 └───┘ └─┴─┘ ５ ６ ９ 10
こうすると何が良いかというと、「親の領域番号×４＋１～４」で、子の4つの領域番号が表せる点。
