Z次曲线坐标 [英] Z-order-curve coordinates
问题描述
如何在阵列中访问使用O(1)时间复杂度的Z顺序存储的数据?我需要通过他们的坐标快速访问每个元素。
How could i access data which is being stored using Z-order with O(1) time complexity in array? I need fast access to each of element by their coordinates. I there any faster way to access this data than using while to shift bits?
一种方法是使用查找表(我有静态数据大小)
One way would be using lookup tables (i have static size of data)
编辑:
我现在想到的一个想法是使用y * SIZE + x
One idea i had right now is to store leaves in sequence using y*SIZE+x
编辑2。:
树在std :: bitset。我试图做检查,如果一些数据可用。在尺寸为128 * 128的矩阵中。
I am storying bits in quad tree in std::bitset. I am trying to do checks if some data is available. in matrices of size 128*128. So i can skip bruteforce matrix search for empty data.
推荐答案
您可以使用以下代码计算z顺序曲线值: / p>
You can calculate the z order curve value with the following code:
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;
}
从您的128x128数组(或任何其他大小),你可以很容易计算z任何位置的阶次曲线值。例如:
From you 128x128 array (or any other size) you can calculate easily the z order curve value from any position. For example:
xPos = 2, yPos = 3 -> z order curve value = 7
示例代码的最大数组大小为65536 * 65536。只是使用2的幂为了方便,在这种情况下最大浪费的空间是约。 3/4
The max array size for the example code is 65536*65536. Just use a power of 2 for ease, in that case the maximum wasted space is approx. 3/4
这篇关于Z次曲线坐标的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!