algorithm - curva - archimedean chords

Implementando 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 una curva de Hilbert, de modo 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 ese mapa?

Answer 1

Esencialmente, se descompondría el número, utilizando pares de bits, MSB a LSB. El par de bits le indica 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 avanza en el número.

Además, necesita seguir una "orientación". Este es el devanado que se utiliza en la escala en la que se encuentra; el devanado inicial es el anterior (UL, LL, LR, UR) y, dependiendo del cuadrante en el que termine, el devanado en la siguiente escala hacia abajo es (girado -90, 0, 0, +90) de su devanado actual .

Para que puedas acumular compensaciones:

Supongo que empiezo en 0,0, y el primer par me da un 2, cambio las compensaciones a 0.5, 0.5. El enrollamiento en la parte inferior derecha es el mismo que el de mi inicial. El siguiente par reduce la escala, por lo que mis ajustes tendrán una longitud de 0.25.

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

Answer 2

Esto es bastante fácil, ya que la curva de Hilbert es un fractal, es decir, es recursiva. Funciona dividiendo cada cuadrado en forma horizontal y vertical, dividiéndolo en cuatro partes. Así que toma dos bits de la dirección IP a la vez, comenzando desde la izquierda, y los usas para determinar el cuadrante, luego continúas, usando los siguientes dos bits, con ese cuadrante en lugar de todo el cuadrado, y así sucesivamente hasta que tengas Agotado todos los bits en la dirección.

La forma básica de la curva en cada cuadrado es similar a una herradura:

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 en el nivel más alto. Posiblemente girada y / o reflejada, esta forma está presente en cada cuadrado de 2x2.

La determinación de cómo se orienta la "herradura" en cada una de las subscuares está determinada por una regla: la esquina 0 de la casilla 0 está en la esquina de la casilla más grande. Por lo tanto, la subcuadrícula correspondiente a 0 arriba debe ser atravesada en el orden

0 1 3 2

y, observando todo el cuadrado anterior y mostrando cuatro bits, obtenemos la siguiente forma para la siguiente división del cuadrado:

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 enfóquese en los dos últimos bits, oriente esta forma más detallada de acuerdo con 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 las coordenadas en el rango [0,1] ) en la coordenada x es 0 si los dos primeros bits de la dirección tienen el valor 0 o 1 , y 1 contrario . De manera similar, el primer bit en la coordenada y es 0 si los dos primeros bits tienen el valor 1 o 2 . Para determinar si agregar un 0 o 1 bit a las coordenadas, debe verificar la orientación de la herradura en ese nivel.

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

En el código, pos es un entero de 3 bits para la orientación. Los dos primeros bits son las coordenadas x e y de 0 en el cuadrado y el tercer bit indica si 1 tiene la misma coordenada x que 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 que 0 . ad es la dirección, tratada como una matriz de n -elementos de enteros de 2 bits, y partiendo de 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));
}

Lo probé con un par de prefijos de 8 bits y los colocé correctamente de acuerdo con el mapa xkcd, así que estoy un poco seguro de que el código es correcto.

Answer 3

Supongo que, basándose en el código de wikipedia para una curva de Hilbert , podría hacer un seguimiento de su posición actual (como una coordenada (x, y)) y devolver esa posición después de haber visitado n celdas. Entonces, la posición escalada en [0..1] dependerá de qué tan alta y ancha sería la curva de Hilbert al final.

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.