Z-order曲线坐标

Question

Z-order曲线坐标

6

如何在数组中使用Z-order存储数据并具有O(1)时间复杂度访问每个元素的坐标？除了使用位移，是否有更快的方式访问这些数据？一种方法是使用查找表（我有静态数据大小）。另一个想法是按顺序存储叶子节点，使用y*SIZE+x编码。我正在std::bitset中使用四叉树存储位，并尝试检查矩阵大小为128 * 128的空数据，以跳过暴力矩阵搜索。

- BlackCat

请提供更多信息。您只在整数z坐标处存储物品还是使用实数？对象数量上限是多少？您需要查询的复杂度是多少（即您期望有多少查询）？ - Ivaylo Strandjev

字典？还是查找表？ - Karoly Horvath

实际上，我想尽快访问该位置处的数据，因为它可以在一个块中容纳32k个元素（位）。而且这些数据可以一次性访问6次或更多次。我试图访问的是数组中四叉树的叶子节点！ - BlackCat

2个回答

-1

在https://en.wikipedia.org/wiki/Z-order_curve上重现维基结果

#include <stdio.h>
static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
static const unsigned int S[] = {1, 2, 4, 8};
unsigned int zorder2D(unsigned x, unsigned y){
    
    x = (x | (x << S[3])) & B[3];
    x = (x | (x << S[2])) & B[2];
    x = (x | (x << S[1])) & B[1];
    x = (x | (x << S[0])) & B[0];

    y = (y | (y << S[3])) & B[3];
    y = (y | (y << S[2])) & B[2];
    y = (y | (y << S[1])) & B[1];
    y = (y | (y << S[0])) & B[0];
    return x | (y << 1);
}

int main()
{    
    const unsigned nx=8,ny=8;
    unsigned res[ny][nx];

    for(unsigned y=0; y<ny; y++){
        for(unsigned x=0; x<nx; x++){
            res[y][x] = zorder2D(x,y);
            printf("yx=%d %d z=%d\n",y,x,res[y][x]);    
        }
    }
    for(unsigned y=0; y<ny; y++){
        for(unsigned x=0; x<nx; x++){
            printf("%-4d",res[y][x]);
        }
        printf("\n");
    }
    return 0;
}

- Lu Liqiang

你显然是直接从其他地方复制了代码，没有正确地进行格式化。请尝试编辑它以清除这个问题，包括删除不必要的注释。 - incarnadine

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aggsol · Accepted Answer

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