Z-order-curve tọa độ

Question

Làm cách nào tôi có thể truy cập dữ liệu đang được lưu trữ sử dụng Z-order với độ phức tạp O (1) trong mảng? Tôi cần truy cập nhanh vào từng phần tử theo tọa độ của chúng. Tôi có cách nào nhanh hơn để truy cập dữ liệu này hơn là sử dụng khi chuyển bit?

Một cách sẽ được sử dụng các bảng tra cứu (i có kích thước tĩnh của dữ liệu)

EDIT:

Một ý tưởng tôi đã có ngay bây giờ là để lưu trữ lá theo thứ tự sử dụng y * SIZE + x

EDIT 2 .:

tôi storying bit trong cây quad trong std :: bitset. Tôi đang cố gắng kiểm tra nếu một số dữ liệu có sẵn. trong ma trận có kích thước 128 * 128. Vì vậy, tôi có thể bỏ qua tìm kiếm ma trận bruteforce cho dữ liệu trống.

Answer 1

Bạn có thể tính giá trị đường cong thứ tự z với đoạn mã sau:

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

Nó được lấy từ đây Bit Twiddling Hacks

Từ bạn 128x128 mảng (hoặc bất kỳ kích thước khác), bạn có thể tính toán một cách dễ dàng z giá trị đường cong thứ tự từ vị trí bất kỳ. Ví dụ:

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

Kích thước mảng tối đa cho mã ví dụ là 65536 * 65536. Chỉ cần sử dụng một sức mạnh của 2 cho dễ dàng, trong trường hợp đó không gian lãng phí tối đa là khoảng. 3/4