[[四分木]]

差分

このページの2つのバージョン間の差分を表示します。

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
programming_algorithm:data_structure:quadtree [2017/10/08] – ↷ programming:algorithm:data_structure:quadtree から programming_algorithm:data_structure:quadtree へページを移動しました。 ikatakosprogramming_algorithm:data_structure:quadtree [2017/10/13] (現在) ikatakos
行 3: 行 3:
   * [[wpjp>木 (数学)]]   * [[wpjp>木 (数学)]]
   * [[wpjp>四分木]]   * [[wpjp>四分木]]
 +  * [[http://1st.geocities.jp/shift486909/program/QuadTree1.html|14-1.四分木探索(理論編)]]
 +  * [[http://1st.geocities.jp/shift486909/program/QuadTree2.html|14-2.四分木探索(実装編)]]
  
 基本的に、n分木といったら「子が必ずn個である木構造」を指すが、特に四分木は2次元座標を分割するのに使われる。 基本的に、n分木といったら「子が必ずn個である木構造」を指すが、特に四分木は2次元座標を分割するのに使われる。
行 8: 行 10:
 各節は領域を表し、x, y座標を2つずつ、つまり4つに分割した領域を子に持つ。 各節は領域を表し、x, y座標を2つずつ、つまり4つに分割した領域を子に持つ。
  
-例えば大量の弾があるシューティングゲームで、自機と全ての弾との衝突判定を計算していては時間がかかるため、何とか「自機に衝突る可能性のある弾だけ」と衝突判定を行いたい、など、2次元平面上にある大量のオブジェクトを効率的に管理できる。+例えば大量の弾があるシューティングゲームで、自機と全ての弾との衝突判定を計算していては時間がかかる。四分木を利用れば2次元平面上にある大量のオブジェクトを効率的に管理できるため、「自機に衝突する可能性のある近い弾」を絞り込める。
  
 =====分割の仕方===== =====分割の仕方=====
行 46: 行 48:
  
 =====領域番号の振り方===== =====領域番号の振り方=====
- 
-領域番号を振り、親の領域番号から子の領域番号を一意に計算できると、木構造を1次元の配列で持つことができて効率的。 
  
 モートン符号という振り方を用いる。Z型に振る。 モートン符号という振り方を用いる。Z型に振る。
  
 <code> <code>
 +領域番号
 + 階層0      階層1     階層2
 +┌───┐  ┌─┬─┐
 +│      │  │2│3│  10 11 14 15
 +│  0  │→├─┼─┤→8 9 12 13
 +│      │  │0│1│  2 3 6 7
 +└───┘  └─┴─┘  0 1 4 5
 +</code>
 +
 +これを、1次元配列で持てるように全階層でつなげて一意にしたのが、以下
 +
 +<code>
 +インデックス
 + 階層0      階層1     階層2
 ┌───┐  ┌─┬─┐ ┌───┐  ┌─┬─┐
 │      │  │3│4│  15 16 19 20 │      │  │3│4│  15 16 19 20
行 59: 行 73:
 </code> </code>
  
-こうすると何が良いかというと、「親の領域番号×4+1~4」で、子の4つの領域番号が表せる点+こうすると何が良いかというと、「親のインデックス×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