Что это за алгоритм, сопоставляющий координаты с номерами?

Я пишу программу для визуализации кристаллов. В рамках программы я должен генерировать все различные базовые точки в структуре решетки. Для тех, кто не знаком с кристаллографией, вы можете найти наиболее общие случаи этих структур здесь: https://en.wikipedia.org/wiki/Hermann%E2%80%93Mauguin_notation#Lattice_types

Проблема заключалась в том, что я хотел отслеживать все эти моменты. Поэтому я дал им номер. Я пытался немного с ручкой и бумагой, и нашел хороший алгоритм для подключения координаты (либо в 2D, либо в 3D) с номером (и наоборот), записав его в двоичной форме.

Итак, если вы хотите, например, простую кубическую решетку в 2D, и вы хотите знать координаты точки номер 14. вы можете записать этот двоичный код как 001110. Вы делите число на 00 | 11 | 10, в (x, y) * 1, средняя часть части обозначает (x, y) * 2, левая часть означает (x, y) * 4 (что бесполезно для числа 14, просто чтобы все было ясно) и так далее. Таким образом, число 14 соответствует точке (3, 2).

Простая программа на С++ для создания координат для первых 50 ints:

int x, y;

for (int n = 0; n < 50; n++)
{
    x = 0;
    y = 0;

    bitset<16>  nset(n);

    for (int i = 0; i < 16/2; i++)
    {
        x+=(nset[2*i]*pow(2.,i));
        y+=(nset[2*i+1]*pow(2.,i));
    }

    cout  << n << "\t" << x << "\t" << y << endl;
}

Я распространил этот алгоритм на 3D, зарезервировав дополнительный столбец для z-значения, а для других типов решетки, зарезервировав первый один или два столбца с видом x + 1/2, y + 1/2, z +1/2, разные для каждого типа решетки.

Итак, вот мой вопрос: существует ли этот алгоритм уже? Имеет ли это имя? Или это просто очевидное применение бинарной математики? Я читал некоторые вещи о хэшмапах, но это кажется более эффективным для меня, по крайней мере, если вы имеете дело с целыми числами.

Это мой первый вопрос в stackexchange, сомневался, что я должен был опубликовать это здесь или на форуме физики. Или, может быть, на математическом форуме, потому что это своего рода биекция R ^ 2- > R. Поэтому, пожалуйста, поправьте меня, если этот вопрос не в нужном месте.

Ответ 1

Итак, вот мой вопрос: существует ли этот алгоритм уже? Это имя?

Это отображение называется кривой Z-порядка или Мортон-код:

В математическом анализе и информатике Z-порядок, порядок Мортона или код Мортона - это функция, которая отображает многомерные данные в один размер, сохраняя локальность точек данных. Он был представлен в 1966 году Г. М. Мортоном. Значение z в многомерности просто вычисляется путем чередования двоичных представлений его значений координат. После сортировки данных в этом порядке можно использовать любую одномерную структуру данных, такую как деревья двоичного поиска, B-деревья, списки пропусков или (с усеченными минимальными битами) хэш-таблицами. Результирующее упорядочение может быть эквивалентно описываться как порядок, который можно получить от первого пересечения квадранта на глубину.

Как показано в вашем примере кода С++, координата x сохраняется в четных битах, а координата y сохраняется в битах с нечетным номером. Отображение можно легко распространить на более высокие размеры.

Некоторые алгоритмы быстрого чередования битов для кодирования этих чисел с использованием операций манипуляции бит можно найти здесь.

Ответ 2

Я могу неверно истолковать ваш код, но похоже, что вы делаете, беру четные биты двоичного числа, объединяя их вместе, чтобы сформировать новый номер, и используя это число в качестве вашей координаты x. Вы, кажется, делаете то же самое для координаты y.

Я не думаю, что есть имя для этого алгоритма, хотя это похоже на довольно стандартную технику. Для чего это стоит, я думаю, что гораздо более простой способ выполнить то, что вы делаете здесь, используя побитовые операторы, а не bitset и pow:

for (int n = 0; n < kUpperBound; n++) {
    int x = 0;
    int y = 0;

    for (int i = 0; i < 8; i++) {
        if (n & (1 << (2*i)) != 0) {
           x += 1 << i;
        }
        if (n & (1 << (2*i + 1)) != 0) {
           y += 1 << i;
        }
    }
    cout << n << " " << x << " " << y << endl;
}

Значение 1 << k - это число, k-й бит которого равен 1, а в противном случае - 0. Использование побитового оператора AND с AND это число с n будет возвращать 0, если k-й бит n равен 0 и ненулевому числу в противном случае. Поэтому тест if (n & (1 << k) != 0) проверяет, установлен ли k-й бит n или нет. Затем вместо использования pow для оценки 2 ⁿ мы используем тот факт, что 1 << k имеет численное значение 2 ^k.

Надеюсь, это поможет!

Ответ 3

Это, вероятно, не поможет вам, к сожалению, но, как странный пустяк, это соответствует оператору INTERLEAVE (или MINGLE) из шуточный язык INTERCAL.

Я не знаю другого имени для этой кодировки. Но, как правило, он мало используется, поскольку с инструкциями, доступными на большинстве компьютеров, гораздо проще и быстрее просто объединить двоичные представления двух (или даже многих) целых чисел, что требует только времени O (d) (и, возможно, как d-1 машинные инструкции) для d-размеров. Об одном преимуществе, которое я могу придумать для вашего кодирования, является то, что он не требует, чтобы вы фиксировали фиксированный размер бита для каждого измерения, поэтому максимальное количество бит, необходимое для кодирования точки решетки, пропорционально журналу максимальное координатное значение - это то, что вы на самом деле используете?