Z-order-curve coordinates

Question

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)

EDIT:

One idea i had right now is to store leaves in sequence using y*SIZE+x

EDIT 2.:

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.

Snocat

please give more information. Do you only store things at integer z coordinates or you use real numbers? What is the number of object(upper bound)? What complexity do you need for a query(i.e. how many queries do you expect)? – Nevski

dictionary? or lookup table.. – Uphill

Actually i would like to access data at that location fast as possible because it can hold 32k elements(bits) per one chunk. And this data can be in one pass accessed 6 or more times. What i am trying to access are leaves of quad tree in array! – Snocat

Answer 1

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;
}

It was taken from here Bit Twiddling Hacks

From your 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

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

Danaus

This is really helpful for a problem I have. Is this in any way extendable to 3D, or would one have to take another approach? – Schleicher

@Victor Sand: For the 3-dimensional case you might want to use a b-tree. – Danaus

Could you be so kind as to explain how do the bit masks influence the end result? Much obliged. – Favorable

@Favorable The Wikipedia entry does it already better than I can. There are great visualisations how it works (including bits). – Danaus

Answer 2

Reproduce Wiki results at 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;
}

Reparation

You have clearly copied your code directly from somewhere without formatting it properly here. Try and edit it to clear this up, including removing the unneeded comment – Hashim