Implementación de un mapa de Hilbert de Internet

Question

En el XKCD comic 195 se sugiere un diseño para un mapa del espacio de direcciones de Internet utilizando un Hilbert curve para que los elementos de una dirección IP similar se agrupen.

Dada una dirección IP, ¿cómo calcularía sus coordenadas 2D (en el rango de cero a uno) en dicho mapa?

Answer 1

Esto es bastante fácil, ya que la curva de Hilbert es un fractal, es decir, es recurrente. Funciona dividiendo cada cuadrado horizontal y verticalmente, dividiéndolo en cuatro pedazos. Así que toma dos bits de la dirección IP a la vez, comenzando desde la izquierda, y los utiliza para determinar el cuadrante, luego continúa, utilizando los siguientes dos bits, con ese cuadrante en lugar de todo el cuadrado, y así sucesivamente hasta que tenga agotado todos los bits en la dirección.

La forma básica de la curva en cada cuadrado es de herradura como:

 
0 3 
1 2 

donde los números corresponden a los dos bits superiores y por lo tanto determinan el orden de recorrido. En el mapa xkcd, este cuadrado es el orden transversal al más alto nivel. Posiblemente girado y/o reflejado, esta forma está presente en cada cuadrado de 2x2.

La determinación de cómo se orienta la "herradura" en cada una de las subesferas está determinada por una regla: la esquina 0 del cuadrado 0 está en la esquina del cuadrado más grande.Por lo tanto, el subcuadrado correspondiente a 0 anterior debe ser recorrido en el orden

 
0 1 
3 2 

y, mirando a toda la plaza anterior y mostrando cuatro bits, se obtiene la siguiente forma para la siguiente división de la plaza:

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

Así es como el cuadrado siempre se divide en el siguiente nivel. Ahora, para continuar, solo concéntrese en los últimos dos bits, oriente esta forma más detallada según la orientación de la forma de herradura de esos bits y continúe con una división similar.

Para determinar las coordenadas reales, cada dos bits determinan un bit de precisión binaria en las coordenadas del número real. Entonces, en el primer nivel, el primer bit después del punto binario (asumiendo coordenadas en el rango [0,1]) en la coordenada x es 0 si los primeros dos bits de la dirección tienen el valor 0 o 1, y 1 en caso contrario. De forma similar, el primer bit en la coordenada y es 0 si los primeros dos bits tienen el valor 1 o 2. Para determinar si se debe agregar un bit de 0 o 1 a las coordenadas, debe verificar la orientación de la herradura en ese nivel.

EDIT: Empecé a trabajar en el algoritmo y resulta que no es tan difícil después de todo, así que aquí hay un pseudo-C. Es pseudo porque uso un sufijo b para constantes binarias y trato enteros como matrices de bits, pero cambiarlo a C apropiado no debería ser demasiado difícil.

En el código, pos es un número entero de 3 bits para la orientación. Los primeros dos bits son las coordenadas xey de 0 en el cuadrado y el tercer bit indica si 1 tiene la misma coordenada x 0. El valor inicial de pos es 011b, lo que significa que las coordenadas de 0 son (0, 1) y 1 tiene la misma coordenada x 0. ad es la dirección, tratada como una matriz de elementos n de enteros de 2 bits y comenzando por los bits más significativos.

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

he comprobado con un par de prefijos de 8 bits y se les coloca correctamente de acuerdo con el mapa xkcd, así que estoy un poco seguros de que el código es correcto.

Answer 2

Esencialmente descompondrías el número, usando pares de bits, MSB a LSB. El par de bits le dice si la ubicación está en el cuadrante superior izquierdo (0) inferior izquierdo (1) inferior derecho (2) o superior derecho (3), en una escala que se vuelve más fina a medida que se desplaza por el número.

Además, debe rastrear una "orientación". Este es el devanado que se usa en la escala en la que se encuentra; el devanado inicial es como el anterior (UL, LL, LR, UR), y dependiendo del cuadrante en el que termine, el devanado en la siguiente reducción de escala es (girado -90, 0, 0, +90) desde su devanado actual .

Por lo que podría acumular compensaciones:

Supongamos que empiezo a 0,0, y el primer par me da 2, I Shift compensaciones a 0,5, 0,5. El bobinado en la esquina inferior derecha es el mismo que el inicial. El siguiente par reduce la escala, por lo que mis ajustes van a tener una longitud de 0,25.

Este par es un 3, entonces traduzco solo mi coordenada x y estoy en .75, .5. El devanado ahora gira y mi próxima reducción será (LR, LL, UL, UR). La escala ahora es .125, y así sucesivamente hasta que me queden sin bits en mi dirección.

Answer 3

Espero que en base al wikipedia code for a Hilbert curve pueda hacer un seguimiento de su posición actual (como una coordenada (x, y)) y devolver esa posición después de que se hayan visitado n celdas. Entonces, la posición escalada en [0..1] dependería de qué tan alta y ancha iba a ser la curva de Hilbert al finalizar.

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) 

Es cierto que esto sería una solución de fuerza bruta en lugar de una solución de forma cerrada.