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