Curva de Hilbert

La curva de Hilbert (también conocida como la curva que recubre el plano de Hilbert) es una curva fractal continua que recubre el plano descrita inicialmente por el matemático alemán David Hilbert en 1891,^[1] como una variante de las curvas que recubren el plano descubiertas por Giuseppe Peano en 1890.^[2]

Debido a que recubre el plano, su dimensión de Hausdorff-Besicovitch es $2$ (precisamente, su imagen es el cuadrado unitario, cuya dimensión es 2 en cualquier definición de dimensión; su gráfico es un conjunto compacto homeomórfico al intervalo cerrado de la unidad, con una dimensión de Hausdorff de 2).

$H_{n}$ es la $n$ ésima aproximación al límite de la curva. La distancia euclidiana de $H_{n}$ es $\textstyle 2^{n}-{1 \over 2^{n}}$ , i.e., crece exponencialmente con $n$ , a la vez que está siempre contenida en un cuadrado de área finita.

Aplicaciones y algoritmos de correspondencia editar

Tanto la curva de Hilbert original como sus aproximaciones discretas son útiles porque proveen una correspondencia entre el espacio 1D y 2D que conserva bastante bien la localidad. Si (x,y) son las coordenadas de un punto dentro del cuadrado unitario, y d es la distancia a lo largo de la curva cuando se llega a ese punto, entonces los puntos que tienen distancias cercanas a d también tienen valores cercanos a (x ,y). Lo contrario no siempre puede ser cierto, ya que puntos con coordenadas (x, y) cercanas, pueden tener valores de d muy alejados. Esto es inevitable cuando se asigna un espacio 2D a un espacio 1D. Sin embargo, la curva de Hilbert consigue mantener bastante bien los valores de d cercanos gran parte del tiempo. Así que las asignaciones en ambas direcciones mantienen bastante bien la localidad.

Debido a esta propiedad de localidad, la curva de Hilbert se utiliza en la informática. Por ejemplo, el rango de las direcciones IP usadas por equipos puede ser representado gráficamente en una imagen utilizando la curva de Hilbert. El código para generar la imagen tendría que hacer una correspencia de 2D a 1D para encontrar el color de cada píxel y la curva de Hilbert se utiliza a veces, ya que mantiene direcciones IP similares cerca entre sí en la imagen. Una fotografía en escala de grises se puede convertir en una imagen en blanco y negro interpolada usando umbrales, con la cantidad sobrante de cada píxel añadida al siguiente pixel a lo largo de la curva de Hilbert. El código para hacer esto hace una correspondencia de 1D a 2D, y la curva de Hilbert se usa a veces porque no crea los patrones de distracción que serían visibles al ojo si el orden fuera simplemente de izquierda a derecha en cada fila de píxeles. Las curvas de Hilbert en dimensiones superiores son una generalización de los códigos de Gray, que se utilizan para propósitos similares, por las mismas razones. Para bases de datos multidimensionales, se ha propuesto el uso del orden de Hilbert en lugar del Z orden porque se comporta mejor preservando la localidad.

Dada esta variedad de aplicaciones, es útil disponer de algoritmos de correspondencia en ambas direcciones. En muchos lenguajes de programación, esto se implementa mejor usando iteración en vez de recursividad. El siguiente código en C realiza las correspondencias en ambas direcciones utilizando iteración y operaciones de bits en lugar de recursividad. Supone un cuadrado dividido en n por n celdas, siendo n una potencia de 2, con coordenadas enteras, con (0,0) en la esquina inferior izquierda y (n -1, n-1) en la esquina superior derecha, y una distanciad que comienza en 0 en la parte inferior de la esquina inferior izquierda y llega a $d^{2}-1$ en la esquina inferior derecha.

//convierte (x,y) a d
int xy2d (int n, int x, int y) {
    int rx, ry, s, d=0;
    for (s = n/2; s > 0; s /= 2) {
        rx = (x & s) > 0;
        ry = (y & s) > 0;
        d += s * s * ((3 * rx) ^ ry);
        rot(s, &x, &y, rx, ry);
    }
    return d;
}

//convierte d a (x,y)
void d2xy(int n, int d, int *x, int *y) {
    int rx, ry, s, t=d;
    *x = *y = 0;
    for (s = 1; s < n; s *= 2) {
        rx = 1 & (t/2);
        ry = 1 & (t ^ rx);
        rot(s, x, y, rx, ry);
        *x += s * rx;
        *y += s * ry;
        t /= 4;
    }
}

//rotar/voltear un cuadrante apropiadamente
void rot(int n, int *x, int *y, int rx, int ry) {
    int t;
    if (ry == 0) {
        if (rx == 1) {
            *x = n-1 - *x;
            *y = n-1 - *y;
        }
        t  = *x;
        *x = *y;
        *y = t;
    }
}

Se usan las siguientes convenciones de C: el símbolo & es un AND binario, el símbolo ^ es un XOR binario, el operador += añade a una variable, y el operador /= divide una variable. El manejo de booleanos en C supone que en xy2d, la variable rx se pone a 0 o 1 para representar al bit s de x, y análogamente para ry.

La función xy2d trabaja de arriba abajo, comenzando con el bit más significativo de x e y, y construyendo los bits más significativos de d primero. La función d2xy trabajan en orden inverso, comenzando con los bits menos significativos de d, y construyendo x e y comenzando por los bits menos significativos. Ambas funciones usan la función de rotación para rotar e invertir el sistema de coordenadas (x,y) apropiadamente.

Los dos algoritmos de correspondencia funcionan de manera similar. El cuadrado completo se ve como compuesto por cuatro regiones, dispuestas en 2 por 2. Cada región está compuesta por cuatro regiones más pequeñas, y así sucesivamente, para una serie de niveles. En el nivel s, cada región consiste en s por s celdas. Hay un simple bucle FOR que recorre los niveles. En cada iteración, se añade una cantidad a d o x e y, determinada por en cuál de las cuatro regiones se encuentra en el nivel actual. La región actual de los 4 es (rx, ry), donde rx y ry son 0 o 1. Por lo que consume 2 bits de entrada, (ya sean 2 de d o cada 1 de x e y), y genera dos bits de salida. También invoca a la función de rotación de manera que (x, y) sean los adecuados para el siguiente nivel, en la siguiente iteración. Para xy2d, se inicia en el nivel superior del cuadrado completo y se abre camino hasta el nivel más bajo de las celdas individuales. Para d2xy, comienza en la parte inferior de las celdas, y trabaja para incluir todo el cuadrado.

Representación como un sistema de Lindenmayer editar

La Curva de Hilbert se puede expresar como un sistema de reescritura (Sistema-L).

Alfabeto : A, B

Constantes : f, l, r

Axioma : A

Reglas de producción:

A → l B fr A f A rf B l

B → r A fl B f B lf A r

Donde, f significa "dibuja hacia delante", l significa "gira a la izquierda 90°", y r significa "gira a la derecha 90°" (véase gráficas tortuga).

Arthur Butz^[3] diseñó un algoritmo para calcular la curva de Hilbert en varias dimensiones.

Graphics Gems II^[4] discute la coherencia de la curva de Hilbert, y provee una implementación.

Implementación editar

En lenguaje de programación Python:

from turtle import left, right, forward

size = 4

def hilbert(level, angle):
    if level == 0:
        return
    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)

hilbert(5, 90)

Véase también editar

Referencias editar

↑ D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Math. Ann. 38 (1891), 459–460.
↑ G.Peano: Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen 36 (1890), 157–160.
↑ A.R. Butz: Alternative algorithm for Hilbert’s space filling curve. IEEE Trans. On Computers, 20:424-42, April 1971.
↑ Voorhies, Douglas: Space-Filling Curves and a Measure of Coherence, p. 26-30, Graphics Gems II.

Enlaces externos editar

Wikimedia Commons alberga una galería multimedia sobre Curva de Hilbert.
Dynamic Hilbert curve with JSXGraph
JSHilbert - Calculate normalised distances along Hilbert curve for points in the unit square.

Datos: Q1366592
Multimedia: Hilbert curves / Q1366592

[1] D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Math. Ann. 38 (1891), 459–460.

[2] G.Peano: Sur une courbe, qui remplit toute une aire plane. Mathematische Annalen 36 (1890), 157–160.

[3] A.R. Butz: Alternative algorithm for Hilbert’s space filling curve. IEEE Trans. On Computers, 20:424-42, April 1971.

[4] Voorhies, Douglas: Space-Filling Curves and a Measure of Coherence, p. 26-30, Graphics Gems II.

[1]

[2]

[3]

[4]