Współrzędne krzywej o kolejności Z

Question

W jaki sposób mogę uzyskać dostęp do danych, które są przechowywane przy użyciu porządku Z, z złożonością czasu O (1) w tablicy? Potrzebuję szybkiego dostępu do każdego elementu przez ich współrzędne. Czy istnieje jakiś szybszy sposób uzyskania dostępu do tych danych, a nie za pomocą przesunięcia bitów?

Jednym ze sposobów będzie za pomocą tabel przeglądowych (mam statyczną rozmiaru danych)

EDIT:

Jeden pomysł miałem teraz jest przechowywanie liście w kolejności przy użyciu y * SIZE + x

EDIT 2 .:

ja storying bity w drzewie quad w std :: bitset. Próbuję sprawdzić, czy niektóre dane są dostępne. w matrycach o rozmiarze 128 * 128. Tak więc mogę pominąć wyszukiwanie w macierzy bruteforce pustych danych.

Answer 1

Można obliczyć zamówienia oo wartość krzywej za pomocą następującego kodu:

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

została ona podjęta stąd Bit Twiddling Hacks

od ciebie 128x128 tablicy (lub innej wielkości) można obliczyć łatwo oo Krzywa zamówienia z dowolnej pozycji. Na przykład:

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

Maksymalny rozmiar tablicy dla przykładowego kodu to 65536 * 65536. Po prostu użyj mocy 2, w tym przypadku maksymalna zmarnowana przestrzeń to ok. 3/4