6

Z オーダーを使用して配列に O(1) 時間の複雑さで格納されているデータにアクセスするにはどうすればよいですか? 座標によって各要素にすばやくアクセスする必要があります。while を使用してビットをシフトするよりも高速にこのデータにアクセスする方法はありますか?

1つの方法は、ルックアップテーブルを使用することです（データの静的サイズがあります）

編集：

私が今持っていた1つのアイデアは、y * SIZE + xを使用して葉を順番に保存することです

編集2.:

std::bitset の四分木でビットをストーリー化しています。いくつかのデータが利用可能かどうかを確認しようとしています。サイズ 128*128 の行列で。したがって、空のデータの総当たり行列検索をスキップできます。

4

2 に答える 2

11

次のコードを使用して、z オーダー カーブの値を計算できます。

uint32_t calcZOrder(uint16_t xPos, uint16_t yPos)
{
    static const uint32_t MASKS[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
    static const uint32_t SHIFTS[] = {1, 2, 4, 8};

    uint32_t x = xPos;  // Interleave lower 16 bits of x and y, so the bits of x
    uint32_t y = yPos;  // are in the even positions and bits from y in the odd;

    x = (x | (x << SHIFTS[3])) & MASKS[3];
    x = (x | (x << SHIFTS[2])) & MASKS[2];
    x = (x | (x << SHIFTS[1])) & MASKS[1];
    x = (x | (x << SHIFTS[0])) & MASKS[0];

    y = (y | (y << SHIFTS[3])) & MASKS[3];
    y = (y | (y << SHIFTS[2])) & MASKS[2];
    y = (y | (y << SHIFTS[1])) & MASKS[1];
    y = (y | (y << SHIFTS[0])) & MASKS[0];

    const uint32_t result = x | (y << 1);
    return result;
}

ここから取られましたBit Twiddling Hacks

128x128 配列 (またはその他のサイズ) から、任意の位置から z オーダー曲線値を簡単に計算できます。例えば：

xPos = 2, yPos = 3 -> z order curve value = 7

サンプル コードの最大配列サイズは 65536*65536 です。簡単にするために 2 のべき乗を使用してください。3/4

于 2013-02-13T12:22:47.557 に答える