6

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.

3
  • 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)? Aug 28, 2012 at 11:01
  • dictionary? or lookup table.. Aug 28, 2012 at 11:05
  • 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!
    – BlackCat
    Aug 28, 2012 at 11:17

2 Answers 2

11

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

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

4
  • 1
    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? Apr 10, 2013 at 0:20
  • @Victor Sand: For the 3-dimensional case you might want to use a b-tree.
    – aggsol
    Apr 17, 2013 at 11:16
  • 1
    Could you be so kind as to explain how do the bit masks influence the end result? Much obliged. Oct 31, 2017 at 18:21
  • @theSongbird The Wikipedia entry does it already better than I can. There are great visualisations how it works (including bits).
    – aggsol
    Nov 1, 2017 at 8:04
-1

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;
}
1
  • 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 Sep 2, 2020 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.