Coordenadas de la curva de orden Z

Question

¿Cómo puedo acceder a los datos que se almacenan usando el orden Z con O (1) complejidad de tiempo en la matriz? Necesito acceso rápido a cada elemento por sus coordenadas. ¿Hay alguna forma más rápida de acceder a estos datos que utilizar mientras se desplazan bits?

Una forma sería utilizando tablas de búsqueda (no tengo el tamaño de datos estático)

EDIT:

Una idea que tenía en este momento es la de almacenar hojas en secuencia utilizando y * TAMAÑO + x

EDIT 2 .:

estoy Narrativa bits en árbol cuádruple en std :: bitset. Estoy tratando de hacer comprobaciones si algunos datos están disponibles. en matrices de tamaño 128 * 128. Así que puedo omitir la búsqueda de matriz bruta para datos vacíos.

Answer 1

Se puede calcular el valor de la curva para z con el siguiente código:

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

Fue tomado de aquí Bit Twiddling Hacks

De ti 128x128 array (o cualquier otro tamaño) se puede calcular fácilmente la z valor de curva de orden desde cualquier posición. Por ejemplo:

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

El tamaño máximo de matriz para el código de ejemplo es 65536 * 65536. Simplemente use una potencia de 2 para facilitar, en ese caso, el espacio máximo desperdiciado es de aprox. 3/4