4分木の効率的な構築への応用

ウィキペディア小見出し辞書

4分木の効率的な構築への応用

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/26 09:37 UTC 版)

「Z階数曲線」の記事における「4分木の効率的な構築への応用」の解説

Z階数曲線の応用により4分木を効率的に構築できる。基本戦略としてz値に基いた並び替えを施す。一度この並び替えを済ませれば、格納されたデータに対し直接的に2分木探索を行える線形4分木構造となる。 通常、入力点群は次元ごとに正の整数へ正規化し機械語が対応するサイズとするが、範囲 [ 0, 1 ] の固定小数点表現とする事もある。何れにせよ最上位の非零のビットは定数時間で探索可能となる。4分木の内包する4つの正方形は辺の長さが2の冪乗で、角の座標は辺の長さの倍数となる。このうちの2点を決定すれば、その両方の点に囲まれた derived square （ 子要素の正方形 ）も決まる。なお、この手法では x 要素と y 要素のビット群の相互配置性は shuffle （ 混ぜ合わせ ）と呼ぶ。これらの特徴はより高次元に対しても拡張できる。 点群は実際にビットの相互配置をせずとも shuffle からソート可能である。先ず次元ごとに、2点の最上位ビットの排他的論理和を評価し、次に最上位ビットが最大の次元で shuffle の順位を決める。 排他的論理和は2点の座標が同一の場合最上位ビットをマスクする。shuffle は上位から下位へとビットを相互配置するので、最大の最上位ビットを持つ座標を識別でき、異なる shuffle 順位の最初のビットも識別でき、よって2点の座標を比較できる。 以下に Python のソースコードを示す: def cmp_zorder(a, b): j = 0 k = 0 x = 0 for k in range(dim): y = a[k] ^ b[k] if less_msb(x, y): j = k x = y return a[j] - b[j] 各点で底2の対数の床値を比較していることが最も重要である。これは以下と等価であり、排他的論理和しか使用しない: def less_msb(x, y): return x < y and x < (x ^ y) 浮動小数点数についても同様に比較可能である。その場合、 less_msb 関数は最初に指数部を比較するよう変更する。そして指数部が等しい場合にのみ元の less_msb 関数を適用する。 一度、点群が順位により並び替えられたなら、次の2つの特性により4分木を容易に構築可能となる: 第1に、4分木の正方形に含まれる点群はz値による並び替えにより隣接した相互配置を構築できる特性。第2に、ある正方形に2つ以上の点が含まれているならば、それは derived square （子要素の正方形）となっている特性。 derived square の隣接する点の対ごとの正方形の辺の長さは元となる最初の大きな正方形から計算できる。 derived square の相互配置ごとに4分木の正方形に相当する圧縮された4分木が得られ、ノード群には入力点または2つ以上の子要素が保存される。必要に応じて非圧縮の4分木も復元できる。 こうして、ポインターに基づいた4分木ではなく2分木のようなデータ構造で点群を維持できる。これにより、点の追加と削除は O(log n) 時間で可能となる。また、2つの4分木の結合も2つの並べ替え済みとした点群から行え、重複も削除できる。点の位置の前後の走査も容易にできる。