Реализация Гильбертовой карты Интернета
В комических 195 XKCD дизайн для карты пространства Интернет-адреса предлагается с помощью Гильбертовой кривой так, чтобы объекты от подобного IP адреса кластеризировались вместе.
Учитывая IP-адрес, как я вычислил бы его 2D координаты (в нуле диапазона к одному) на такой карте?
3 ответа
Это довольно просто, так как кривая Гильберта является фрактальной, то есть рекурсивной. Она работает, разбивая каждый квадрат на биссектрисы по горизонтали и вертикали, разделяя его на четыре части. Таким образом, вы берете два бита IP-адреса одновременно, начиная слева, и используете их для определения квадранта, затем продолжаете, используя следующие два бита, с этим квадрантом вместо целого квадрата, и так далее, пока не исчерпаете все биты адреса.
Основная форма кривой в каждом квадрате похожа на подкову:
0 3 1 2
где числа соответствуют двум верхним битам и, следовательно, определяют порядок обхода. В xkcd-карте эта клетка представляет собой порядок обхода на самом высоком уровне. Возможно, повернутая и/или отраженная, эта форма присутствует в каждом квадрате 2х2.
Определение ориентации "подковы" в каждом из подквадратов определяется одним правилом: 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: Я начал прорабатывать алгоритм, и оказалось, что это все-таки не так уж и сложно, так что вот немного псевдо-С. Это псевдо, потому что я использую суффикс b для двоичных констант и рассматриваю целые числа как массивы битов, но поменять его на правильный C не должно быть слишком сложно.
В коде pos - это 3-битное целое число для ориентации. Первые два бита - это координаты x и y 0 в квадрате, а третий бит указывает, имеет ли 1 ту же самую координату x, что и 0. Начальное значение pos равно 011b, что означает, что координаты 0 равны (0, 1) и 1 имеют ту же самую координату х, что и 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, так что я несколько уверен, что код корректен.
.По сути, вы бы разложили число, используя пары битов, 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, и так далее, и так далее, пока у меня не закончатся биты в моем адресе
.Я ожидаю, что, основываясь на коде википедии для кривой Гильберта, вы могли бы следить за своим текущим положением (как координата (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)
Правда, это будет решение с грубой силой, а не с закрытой формой.
.