差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | |||
programming_algorithm:data_structure:quadtree [2017/10/08] – ↷ programming:algorithm:data_structure:quadtree から programming_algorithm:data_structure:quadtree へページを移動しました。 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次元平面上にある大量のオブジェクトを効率的に管理できるため、「自機に衝突する可能性のある近い弾」を絞り込める。 |
=====分割の仕方===== | =====分割の仕方===== | ||
行 46: | 行 48: | ||
=====領域番号の振り方===== | =====領域番号の振り方===== | ||
- | |||
- | 領域番号を振り、親の領域番号から子の領域番号を一意に計算できると、木構造を1次元の配列で持つことができて効率的。 | ||
モートン符号という振り方を用いる。Z型に振る。 | モートン符号という振り方を用いる。Z型に振る。 | ||
< | < | ||
+ | 領域番号 | ||
+ | | ||
+ | ┌───┐ | ||
+ | │ │ │2│3│ | ||
+ | │ 0 │→├─┼─┤→8 9 12 13 | ||
+ | │ │ │0│1│ | ||
+ | └───┘ | ||
+ | </ | ||
+ | |||
+ | これを、1次元配列で持てるように全階層でつなげて一意にしたのが、以下 | ||
+ | |||
+ | < | ||
+ | インデックス | ||
+ | | ||
┌───┐ | ┌───┐ | ||
│ │ │3│4│ | │ │ │3│4│ | ||
行 59: | 行 73: | ||
</ | </ | ||
- | こうすると何が良いかというと、「親の領域番号×4+1~4」で、子の4つの領域番号が表せる点。 | + | こうすると何が良いかというと、「親のインデックス×4+1~4」で、子の4つのインデックスが表せ、親子関係を辿りやすい。 |
+ | また、階層Lのインデックスの最大値は初項1, | ||