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