Curva de Hilbert

Curva de Hilbert

Primers 8 passos per a construir la curva de Hilbert

La curva de Hilbert (també coneguda com la curva que recobrix el pla de Hilbert) és una curva fractal contínua que recobrix el pla descrita inicialment pel matemàtic alemà David Hilbert en 1891, com una variant de les curves que recobrixen el pla descobertes per Giuseppe Peano en 1890.

Degut a que recobrix el pla, el seu dimensió de Hausdorff-Besicovitch és $2$ (precisament, la seua image és el quadrat unitari, la dimensió del qual és 2 en qualsevol definició de dimensió; el seu gràfic és un conjunt compacte homeomórfico a l'interval tancat de l'unitat, en una dimensió de Hausdorff de 2).

$H_n$ és la $n$ésima aproximació al llímit de la curva. La distància euclidiana de $H_n$ és $2^n-\frac{1}{2^n}$, i.i., creix exponencialment en $n$, al mateix temps que està sempre continguda en un quadrat d'àrea finita.

Aplicacions i algoritmes de correspondència

Tant la curva de Hilbert original com les seues aproximacions discretes són útils perque proveïxen una correspondència entre l'espai 1D i 2D que conserva prou be la localitat. Si (x,i) són les coordenades d'un punt dins del quadrat unitari, i d és la distància a lo llarc de la curva quan s'aplega a eixe punt, llavors els punts que tenen distàncies propenques a d també tenen valors propencs a (x ,i). Ho contrarie no sempre pot ser cert, ya que punts en coordenades (x, i) propenques, poden tindre valors de d molt alluntats. Açò és inevitable quan s'assigna un espai 2D a un espai 1D. No obstant, la curva de Hilbert conseguix mantindre prou ben els valors de d propencs gran part del temps. Aixina que les assignació en abdós direccions mantenen prou be la localitat.

Per esta propietat de localitat, la curva de Hilbert s'utilisa en l'informàtica. Per eixemple, el ranc de les direccions IP usades per equips pot ser representat gràficament en una image utilisant la curva de Hilbert. El còdic per a generar l'image tindria que fer una correspencia de 2D a 1D per a trobar el color de cada píxel i la curva de Hilbert s'utilisa a voltes, ya que manté direccions IP similars prop entre sí en l'image. Una fotografia en escala de grises es pot convertir en una image en blanc i negre interpolada usant llindars, en la cantitat sobrera de cada píxel afegida al següent pixel a lo llarc de la curva de Hilbert. El còdic per a fer açò fa una correspondència de 1D a 2D, i la curva de Hilbert s'usa a voltes perque no crea els patrons de distracció que serien visibles a l'ull si l'orde fora simplement d'esquerra a dreta en cada fila de píxels. Les curves de Hilbert en dimensions superiors són una generalisació dels còdics de Gray, que s'utilisen per a propòsits similars, per les mateixes raons. Per a bases de senyes multidimensionales, s'ha propost l'us de l'orde de Hilbert en lloc del Z orde perque es comporta millor preservant la localitat.

Donada esta varietat d'aplicacions, és útil dispondre d'algoritmes de correspondència en abdós direccions. En molts llenguages de programació, açò s'implementa millor usant iteración en lloc de recursividad. El següent còdic en C realisa les correspondències en abdós direccions utilisant iteración i operacions de bits en lloc de recursividad. Supon un quadrat dividit en n per n celes, sent n una potència de 2, en coordenades sanceres, en (0,0) en el cantó inferior esquerre i (n -1, n-1) en el cantó superior dret, i una distanciad que comença en 0 en la part inferior del cantó inferior esquerre i aplega a $d^2-1$ en el cantó inferior dret.

//convertix (x,i) a
d int xy2d (int n, int x, int i) {

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

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

//rotar/voltear un quadrant apropiadament
void rot(int n, int x, int i, int rx, int ry) {
    int t;
    if (ry == 0) {
        if (rx == 1) {
            x = n-1 - x;
            i = n-1 - i;
        }
        t  = x;
        x = i;
        i = t;
    }
}

S'usen les següents convencions de C: el símbol & és un AND binari, el símbol ^ és un XOR binari, l'operador += afig a una variable, i l'operador /= dividix una variable. El maneig de booleanos en C supon que en xy2d, la variable rx es posa a 0 o 1 per a representar al bit s de x, i análogamente per a ry.

La funció xy2d treballa de dalt avall, començant en el bit més significatiu de x i i, i construint els bits més significatius de d primer. La funció d2xy treballen en orde invers, començant en els bits menys significatius de d, i construint x i i començant pels bits menys significatius. Abdós funcions usen la funció de rotació per a rotar i invertir el sistema de coordenades (x,i) apropiadament.

Els dos algoritmes de correspondència funcionen de manera similar. El quadrat complet es veu com a compost per quatre regions, dispostes en 2 per 2. Cada regió està composta per quatre regions més menudes, i aixina successivament, per a una série de nivells. En el nivell s, cada regió consistix en s per s celes. Hi ha un simple bucle FOR que recorre els nivells. En cada iteración, s'afig una cantitat a d o x i i, determinada per en quin de les quatre regions es troba en el nivell actual. La regió actual dels 4 és (rx, ry), a on rx i ry són 0 o 1. Per lo que consumix 2 bits d'entrada, (ya siguen 2 de d o cada 1 de x i i), i genera dos bits d'eixida. També invoca a la funció de rotació de manera que (x, i) siguen els adequats per al següent nivell, en la següent iteración. Per a xy2d, s'inicia en el nivell superior del quadrat complet i s'obri camí fins al nivell més baix de les celes individuals. Per a d2xy, comença en la part inferior de les celes, i treballa per a incloure tot el quadrat.

Representació com un sistema de Lindenmayer

La Curva de Hilbert es pot expressar com un sistema de reescritura (Sistema-L).

Alfabet : A, B

Constants : f, l, r

Axioma : A

Regles de producció:

A → l B fr A f A rf B l

B → r A fl B f B lf A r

A on, f significa "dibuixa cap a davant", l significa "gira a l'esquerra 90°", i r significa "gira a la dreta 90°" (vore gràfiques tortuga).

Arthur Butz va dissenyar un algoritme per a calcular la curva de Hilbert en vàries dimensions.

Graphics Gems II discutix la coherència de la curva de Hilbert, i proveïx una implementació.