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

Question

Я пишу программу для визуализации кристаллов. В рамках программы я должен генерировать все различные базовые точки в структуре решетки. Для тех, кто не знаком с кристаллографией, вы можете найти наиболее общие случаи этих структур здесь: 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).

Простой C++, программа для генерации координат для первых 50 целых чисел:

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. Поэтому, пожалуйста, исправьте меня, если этот вопрос не в нужном месте.

Answer 1

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

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

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

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

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

Answer 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 это число, которое КТН бит 1 и который равно нулю. С помощью побитового оператора И с И это число с n вернет 0, если k-й бит n равен 0 и в противном случае будет ненулевое число. Поэтому в тесте if (n & (1 << k) != 0) проверяется, установлен ли k-й бит n. Затем вместо использования pow для оценки 2 ⁿ мы используем тот факт, что 1 << k имеет численное значение 2 ^k.

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

Answer 3

Возможно, вам это не поможет, но, как странный кусочек мелочей, это соответствует оператору INTERLEAVE (или MINGLE) от joke language INTERCAL.

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