差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
| programming:algorithm:data_structure:quadtree [2017/10/06] – ikatakos | programming:algorithm:data_structure:quadtree [2017/10/06] – ikatakos | ||
|---|---|---|---|
| 行 13: | 行 13: | ||
| 単に四分木という場合、大きく分けて、2つの分け方がある。 | 単に四分木という場合、大きく分けて、2つの分け方がある。 | ||
| + | |||
| + | * 常に半分で分割 | ||
| + | * 指定した領域にかぶる領域の探索が得意 | ||
| + | * 常に点の位置で分割 | ||
| + | * 特定の点を見つける探索が得意 | ||
| + | |||
| + | 特に四分木特有のデータ構造が活かせるのは、半分で分割する方なので、そちらについて説明する。 | ||
| ====常に半分で分割==== | ====常に半分で分割==== | ||
| 行 37: | 行 44: | ||
| └─────┘ | └─────┘ | ||
| </ | </ | ||
| + | |||
| + | =====領域番号の振り方===== | ||
| + | |||
| + | 領域番号を振り、親の領域番号から子の領域番号を一意に計算できると、木構造を1次元の配列で持つことができて効率的。 | ||
| + | |||
| + | モートン符号という振り方を用いる。Z型に振る。 | ||
| + | |||
| + | < | ||
| + | ┌───┐ | ||
| + | │ │ │３│４│ | ||
| + | │ ０ │→├─┼─┤→13 14 17 18 | ||
| + | │ │ │１│２│ | ||
| + | └───┘ | ||
| + | </ | ||
| + | |||
| + | こうすると何が良いかというと、「親の領域番号×４＋１～４」で、子の4つの領域番号が表せる点。 | ||
| + | |||
| + | |||
| + | |||
