データ構造と座標値群の取り扱い
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/11/26 09:37 UTC 版)
「Z階数曲線」の記事における「データ構造と座標値群の取り扱い」の解説
下図に 2次元における z値 について整数の座標群 0 ≤ x ≤ 7, 0 ≤ y ≤ 7 （10進数と2進数で表示）の範囲で図示する。2進数の相互配置的な並びに着目すると、2進数で表した座標値（＝インデックス値）には2進数の z値 が含まれる。 z値 を数値的に昇順に繋げるとZ字型の曲線が生成される。2次元におけるZ値群は quadkey （意訳; 四つ子の鍵）とも呼ばれる。 座標のx値はZ値にモーサー-ドブリュン数列（英語: Moser–de Bruijn sequence）による2進数値群として0ビット目、2ビット目、4ビット目のように偶数ビット群に現れる: x[] = {0b000000, 0b000001, 0b000100, 0b000101, 0b010000, 0b010001, 0b010100, 0b010101} 2つのx値の和と差はビット単位演算により計算できる: x[i+j] = ((x[i] | 0b10101010) + x[j]) & 0b01010101x[i-j] = ((x[i] & 0b01010101) - x[j]) & 0b01010101 但し i >= j の場合 この性質から、現在の z値 の座標を右（x値を増加）、左（x値を減少）、下（y値を増加）、上（y値を減少）へオフセットした他の座標の z値を計算できる: 上 = ((z & 0b10101010) - 1 & 0b10101010) | (z & 0b01010101)下 = ((z | 0b01010101) + 1 & 0b10101010) | (z & 0b01010101)左 = ((z & 0b01010101) - 1 & 0b01010101) | (z & 0b10101010)右 = ((z | 0b10101010) + 1 & 0b01010101) | (z & 0b10101010) 2つの2次元のZ値群に一般化すると: 和 = ((z | 0b10101010) + (w & 0b01010101) & 0b01010101) | ((z | 0b01010101) + (w & 0b10101010) & 0b10101010)
※この「データ構造と座標値群の取り扱い」の解説は、「Z階数曲線」の解説の一部です。
「データ構造と座標値群の取り扱い」を含む「Z階数曲線」の記事については、「Z階数曲線」の概要を参照ください。
- データ構造と座標値群の取り扱いのページへのリンク
