Z阶曲线坐标

Question

如何在数组中以O(1)时间复杂度访问使用Z顺序存储的数据？我需要通过坐标快速访问每个元素.我有没有更快的方式来访问这些数据而不是使用何时移位？

一种方法是使用查找表(我有静态大小的数据)

编辑:

我现在的一个想法是使用y*SIZE + x按顺序存储叶子

编辑2:

我在std :: bitset的四叉树中编辑故事.我正在尝试检查是否有一些数据可用.在矩阵128*128的矩阵中.所以我可以跳过bruteforce矩阵搜索空数据.

Answer 1

您可以使用以下代码计算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