Реализация карты Гильберта в Интернете

Ответ 1

Это довольно легко, так как кривая Гильберта является фрактальной, то есть рекурсивной. Он работает, разбивая каждый квадрат по горизонтали и вертикали, разделяя его на четыре части. Таким образом, вы берете два бита IP-адреса за раз, начиная с левой стороны, и используете их для определения квадранта, а затем продолжайте использовать следующие два бита с этим квадрантом вместо всего квадрата и так далее, пока не будете исчерпали все биты в адресе.

Основная форма кривой в каждом квадрате подковообразна:

 0 3
 1 2

где числа соответствуют верхним двум битам и, следовательно, определяют порядок обхода. На карте xkcd этот квадрат является порядком обхода на самом высоком уровне. Возможно, что он вращается и/или отражается, эта форма присутствует на каждом квадрате 2x2.

Определение того, как "подкова" ориентирована в каждом из подзапросов, определяется одним правилом: угол 0 квадрата 0 находится в углу большего квадрата. Таким образом, подзапрос, соответствующий 0 выше, должен быть пройден в порядке

 0 1
 3 2

и, посмотрев на весь предыдущий квадрат и показывая четыре бита, получим следующую форму для следующего деления квадрата:

 00 01 32 33
 03 02 31 30
 10 13 20 23
 11 12 21 22

Так квадрат всегда делится на следующем уровне. Теперь, чтобы продолжить, просто сосредоточьтесь на последних двух битах, ориентируйте эту более детальную форму в соответствии с тем, как форма подковообразности этих бит ориентирована и продолжит аналогичное деление.

Чтобы определить фактические координаты, каждый два бита определяют один бит бинарной точности в координатах действительных чисел. Итак, на первом уровне первый бит после двоичной точки (при условии координат в диапазоне [0,1]) в координате x равен 0, если первые два бита адреса имеют значение 0 или 1 и 1 в противном случае. Аналогично, первый бит в координате y равен 0, если первые два бита имеют значение 1 или 2. Чтобы определить, следует ли добавить бит 0 или 1 в координаты, вам необходимо проверить ориентацию подков на этом уровне.

EDIT: я начал разрабатывать алгоритм, и получается, что это не так сложно в конце концов, так что здесь некоторые псевдо-C. Это псевдо, потому что я использую суффикс b для двоичных констант и обрабатываю целые числа как массивы бит, но изменение его на правильное С не должно быть слишком сложным.

В коде pos представляет собой 3-битное целое число для ориентации. Первые два бита представляют собой координаты x и y 0 в квадрате, а третий бит указывает, имеет ли 1 ту же координату x, что и 0. Начальное значение pos составляет 011b, что означает, что координаты 0 равны (0, 1), а 1 имеет ту же координату x, что и 0. ad - это адрес, рассматриваемый как массив n -элемент из 2-битных целых чисел и начинающийся с наиболее значимых бит.

double x = 0.0, y = 0.0;
double xinc, yinc;
pos = 011b;
for (int i = 0; i < n; i++) {
    switch (ad[i]) {
        case 0: xinc = pos[0]; yinc = pos[1]; pos[2] = ~pos[2]; break;
        case 1: xinc = pos[0] ^ ~pos[2]; yinc = pos[1] ^ pos[2]; break;
        case 2: xinc = ~pos[0]; yinc = ~pos[1]; break;
        case 3: xinc = pos[0] ^ pos[2]; yinc = pos[1] ^ ~pos[2];
            pos = ~pos; break;
    }
    x += xinc / (1 << (i+1)); y += yinc / (1 << (i+1));
}

Я протестировал его с помощью нескольких 8-битных префиксов и разместил их правильно в соответствии с картой xkcd, поэтому я уверен, что код верен.

Ответ 2

По сути, вы бы разложили число, используя пары бит, от MSB до LSB. Пара битов сообщает вам, находится ли место в верхнем левом (0) нижнем левом (1) нижнем правом (2) или верхнем правом (3) квадранте, в масштабе, который становится более тонким при перемещении по числу.

Кроме того, вам нужно отслеживать "ориентацию". Это обмотка, которая используется на шкале, на которой вы находитесь; начальная обмотка, как указано выше (UL, LL, LR, UR), и в зависимости от того, на каком квадранте вы окажетесь, обмотка на следующей шкале вниз (повернута -90, 0, 0, +90) от текущей обмотки.

Итак, вы можете накапливать смещения:

Предположим, что я начинаю с 0,0, а первая пара дает мне 2, я смещения смещения до 0,5, 0,5. Обмотка в правом нижнем углу такая же, как у моей начальной. Следующая пара уменьшает масштаб, поэтому мои настройки составят 0,25 дюйма.

Эта пара - 3, поэтому я переводю только мою координату x, и я нахожусь в .75,.5. Теперь обмотка повернута, и мой следующий снимок будет (LR, LL, UL, UR). Шкала теперь .125 и так далее и так далее, пока у меня не закончится бит в моем адресе.

Ответ 3

Я ожидаю, что на основе кода википедии для кривой Гильберта вы можете отслеживать свою текущую позицию (как (x, y )) и вернуть эту позицию после посещения n ячеек. Тогда положение, масштабируемое на [0..1], будет зависеть от того, насколько высокая и широкая кривая Гильберта будет завершена.

from turtle import left, right, forward

size = 10

def hilbert(level, angle):
    if level:
        right(angle)
        hilbert(level - 1, -angle)
        forward(size)
        left(angle)
        hilbert(level - 1, angle)
        forward(size)
        hilbert(level - 1, angle)
        left(angle)
        forward(size)
        hilbert(level - 1, -angle)
        right(angle)

По общему признанию, это было бы решением грубой силы, а не решением замкнутой формы.