差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン | ||
programming:algorithm:data_structure:quadtree [2017/10/06] – ikatakos | programming_algorithm:data_structure:quadtree [2017/10/13] (現在) – ikatakos | ||
---|---|---|---|
行 3: | 行 3: | ||
* [[wpjp> | * [[wpjp> | ||
* [[wpjp> | * [[wpjp> | ||
+ | * [[http:// | ||
+ | * [[http:// | ||
基本的に、n分木といったら「子が必ずn個である木構造」を指すが、特に四分木は2次元座標を分割するのに使われる。 | 基本的に、n分木といったら「子が必ずn個である木構造」を指すが、特に四分木は2次元座標を分割するのに使われる。 | ||
行 8: | 行 10: | ||
各節は領域を表し、x, | 各節は領域を表し、x, | ||
- | 例えば大量の弾があるシューティングゲームで、自機と全ての弾との衝突判定を計算していては時間がかかるため、何とか「自機に衝突する可能性のある弾だけ」と衝突判定を行いたい、など、2次元平面上にある大量のオブジェクトを効率的に管理できる。 | + | 例えば大量の弾があるシューティングゲームで、自機と全ての弾との衝突判定を計算していては時間がかかる。四分木を利用すれば2次元平面上にある大量のオブジェクトを効率的に管理できるため、「自機に衝突する可能性のある近い弾」を絞り込める。 |
=====分割の仕方===== | =====分割の仕方===== | ||
単に四分木という場合、大きく分けて、2つの分け方がある。 | 単に四分木という場合、大きく分けて、2つの分け方がある。 | ||
+ | |||
+ | * 常に半分で分割 | ||
+ | * 指定した領域にかぶる領域の探索が得意 | ||
+ | * 常に点の位置で分割 | ||
+ | * 特定の点を見つける探索が得意 | ||
+ | |||
+ | 特に四分木特有のデータ構造が活かせるのは、半分で分割する方なので、そちらについて説明する。 | ||
====常に半分で分割==== | ====常に半分で分割==== | ||
行 37: | 行 46: | ||
└─────┘ | └─────┘ | ||
</ | </ | ||
+ | |||
+ | =====領域番号の振り方===== | ||
+ | |||
+ | モートン符号という振り方を用いる。Z型に振る。 | ||
+ | |||
+ | < | ||
+ | 領域番号 | ||
+ | | ||
+ | ┌───┐ | ||
+ | │ │ │2│3│ | ||
+ | │ 0 │→├─┼─┤→8 9 12 13 | ||
+ | │ │ │0│1│ | ||
+ | └───┘ | ||
+ | </ | ||
+ | |||
+ | これを、1次元配列で持てるように全階層でつなげて一意にしたのが、以下 | ||
+ | |||
+ | < | ||
+ | インデックス | ||
+ | | ||
+ | ┌───┐ | ||
+ | │ │ │3│4│ | ||
+ | │ 0 │→├─┼─┤→13 14 17 18 | ||
+ | │ │ │1│2│ | ||
+ | └───┘ | ||
+ | </ | ||
+ | |||
+ | こうすると何が良いかというと、「親のインデックス×4+1~4」で、子の4つのインデックスが表せ、親子関係を辿りやすい。 | ||
+ | |||
+ | また、階層Lのインデックスの最大値は初項1, | ||
+ | |||
+ | |||