z-order-curve - 範囲外の制限がある Z-Index

Question

2 つの座標 x、y から平面上の点の Z-Index (Morton) を計算する必要があります。

従来、これはビットインターリーブによって解決されていました。

ただし、境界があり、ポイントの z-index がアクティブな領域の内側にある場合にのみモートンカウントを増やし、外側にある場合はカウントをスキップするようにします。

明確にするために、4x4 正方形の一般的な z オーダーは次のとおりです。

|  0  1  4  5 |
|  2  3  6  7 |
|  8  9 12 13 |
| 10 11 14 15 |

ただし、3x3 のアクティブエリアがある場合、次のようにインデックスを計算する必要があります。

|  0  1  4  x |
|  2  3  5  x |
|  6  7  8  x |
|  x  x  x  x |

00-11 のクワッドがいっぱいであることがわかるように、02-13 は、20-31 と 22-33 の場合と同じように、アクティブエリアの外にある 2 つのポイントのカウントをスキップしています。

重要: 反復せずにこれを行いたいです。

この問題の既知の解決策はありますか?

score 0 · Accepted Answer

長方形の領域を処理するには、すべての次元を最も近い 2 の累乗に切り上げ、長軸を線形にパックします。

たとえば、次のように 5x4 の長方形のポイント (2,3) をエンドコーディングします。

5x4 を最も近い 2 の累乗に切り上げると、8x4、つまり 3 ビットと 2 ビットになります。

エンコーディングポイント 2,3 最初に 0b010、0b11 の 2 ビットをインターリーブすると、0b1110 が得られ、x 次元からの 3 ビット目が結果の 5 ビット目になります。

エンコーディング 4,2, 0b100, 0b11 は 0b11010 になります

3x3 領域の z オーダーを見つけるには、上記の逆の方法を使用して 4x4 領域の逆マッピングを見つけ、マップの生成中に 3x3 領域外のポイントをスキップします。

マッピングは次のようになります

(0,0) -> (0,0)
(0,1) -> (1,0)
(0,2) -> (0,1)
(0,3) -> (1,1)
(1,0) -> (2,0)
(1,2) -> (2,1)
(2,0) -> (0,2)
(2,1) -> (1,2)
(3,0) -> (2,2)

1 に答える 1