Z-order coordinates

Question

How can I access data that is stored using a Z-order with O (1) time complexity in an array? I need quick access to each element by their coordinates. Do I have a faster way to access this data than use bit offsets?

One way is to use lookup tables (I have a static data size)

EDIT:

One idea that I had now is to keep the leaves in sequence using y * SIZE + x

EDIT 2 .:

I am telling bits in a square tree in std :: bitset. I am trying to do checks if some data is available. in matrices of size 128 * 128. Therefore, I can skip the search in the rough matrix for empty data.

Answer 1

You can calculate the value of an order z curve using 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; } 

It was taken from here. Tweedling Hacks Bit

From your 128x128 array (or any other size) you can easily calculate the zz curve value from any position. For instance:

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

The maximum array size for the example code is 65536 * 65536. Just use power 2 for convenience, in this case the maximum space is wasted for approx. 3/4