Вопрос по c++ – Координаты Z-порядка

5

Как я могу получить доступ к данным, которые хранятся с использованием Z-порядка с O (1) временной сложностью в массиве? Мне нужен быстрый доступ к каждому элементу по его координатам. Есть ли более быстрый способ получить доступ к этим данным, чем использовать while для сдвига битов?

Одним из способов будет использование справочных таблиц (у меня есть статический размер данных)

EDIT:

Одна идея, которая у меня была сейчас, - хранить листья в последовательности, используя y * SIZE + x.

EDIT 2.:

Я рассказываю биты в квад-дереве в std :: bitset. Я пытаюсь сделать проверки, если некоторые данные доступны. в матрицах размером 128 * 128. Так что я могу пропустить поиск по грубой матрице пустых данных.

На самом деле я хотел бы получить доступ к данным в этом месте как можно быстрее, потому что он может содержать 32 тыс. Элементов (бит) на один блок. И эти данные могут быть доступны за один проход 6 или более раз. То, что я пытаюсь получить доступ, это листья дерева квадрантов в массиве! BlackCat
пожалуйста, дайте больше информации. Вы храните вещи только в целочисленных координатах z или используете реальные числа? Каков номер объекта (верхняя граница)? Какая сложность вам нужна для запроса (т. Е. Сколько запросов вы ожидаете)? Ivaylo Strandjev
толковый словарь? или справочная таблица .. Karoly Horvath

Ваш Ответ

1   ответ
6

да:

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

Это было взято отсюдаБит Тиддлинг Хаки

Из массива 128x128 (или любого другого размера) вы можете легко рассчитать значение кривой z-порядка из любой позиции. Например:

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

Максимальный размер массива для примера кода составляет 65536 * 65536. Просто используйте степень 2 для простоты, в этом случае максимальная потеря пространства составляет прибл. 3/4

Это действительно полезно для моей проблемы. Является ли это каким-либо образом распространяемым на 3D, или нужно было бы принять другой подход?
Не могли бы вы объяснить, как битовые маски влияют на конечный результат? Весьма признателен.
@Victor Sand: для трехмерного случая вы можете использовать b-дерево.
@theSongbirdThe Wikipedia entry делает это уже лучше, чем я могу. Есть отличные визуализации, как это работает (включая биты).

Похожие вопросы