Curva di Hilbert

Questa voce o sezione sull'argomento matematica è ritenuta da controllare.

Motivo: traduzione automatica dall'Inglese, a tratti incomprensibile

Partecipa alla discussione e/o correggi la voce. Segui i suggerimenti del progetto di riferimento.

Primi 8 passi per costruire la curva di Hilbert

La curva di Hilbert (anche conosciuta come la curva che riempie il piano di Hilbert) è una curva frattale continua che riempie il piano descritto inizialmente dal matematico tedesco David Hilbert nel 1891,^[1] come una variante delle curve che riempiono il piano scoperto per Giuseppe Peano nel 1890.^[2]

Dato che copre il piano, la sua dimensione di Hausdorff è $2$ (precisamente, la sua immagine è quadrato unitario, la cui dimensione è 2 in qualsiasi definizione di dimensione, il suo grafico è un insieme compatto omeomorfo all'intervallo chiuso con dimensione di Hausdorff 2).

La curva $H_{n}$ è l' $n$ -esimo elemento della successione che tende alla curva limite. La lunghezza di $H_{n}$ è $2^{n}-{n \over 2^{n}}$ cioè cresce esponenzialmente con $n,$ rimanendo sempre contenuta entro un quadrato di area finita.

Applicazioni e algoritmi di corrispondenza

[modifica | modifica wikitesto]

Tanto la curva di Hilbert originale come le sue approssimazioni discrete sono utili perché forniscono una corrispondenza tra lo spazio 1D e 2D che conserva abbastanza bene la posizione. Se (x,y) Sono le coordinate di un punto dentro il quadrato unitario, e d è la distanza lungo la curva quando si arriva a questo punto, allora i punti che hanno distanze vicine a d anche hanno valori vicini a (x,y). Il caso contrario può non essere sempre vero, poiché i punti di coordinate (x,y) vicino, possono avere valori lontani da d. Questo è inevitabile quando si assegna uno spazio 2D ad uno spazio 1D. Tuttavia, la curva Hilbert è in grado di mantenere i valori di d per la maggior parte del tempo abbastanza bene. Quindi, le assegnazioni in entrambe le direzioni rimangono abbastanza ben localizzate.

Dovuto a questa proprietà di località, la curva di Hilbert si utilizza in informatica. Ad esempio, l'intervallo di indirizzi IP utilizzati dai computer può essere rappresentato graficamente su un'immagine utilizzando la curva di Hilbert. Il codice per generare l'immagine dovrebbe fare una corrispondenza di 2D a 1D per trovare il colore di ogni pixel e la curva di Hilbert si utilizza a volte, giacché mantiene indirizzi IP simili vicino tra sé nell'immagine. Una fotografia in scala di grigi può trasformarsi in un'immagine in bianco e nero interpolati usando soglie, con la quantità rimanente di ciascun pixel aggiunto al pixel successivo lungo la curva di Hilbert. Il codice per fare ciò fa una corrispondenza di 1D a 2D, e la curva di Hilbert si usa a volte perché non crea modelli di distrazione che sarebbero visibili a occhio se l'ordine è stato semplicemente da sinistra a destra in ciascuna riga di pixel. Le curve di Hilbert di dimensioni superiori sono una generalizzazione di codici Gray, che vengono utilizzati per scopi analoghi, per gli stessi motivi. Per i database multidimensionali, ci ha proposto l'uso di ordine Hilbert invece l'ordine Z perché si comporta meglio preservare la posizione.

Data questa varietà di applicazioni, è utile disporre di algoritmi di confronto in entrambe le direzioni. In molti linguaggi di programmazione, questo è meglio implementato usando un'iterazione invece che la ricorsione. Il seguente codice in C esegue la mappatura in entrambe le direzioni utilizzando iterazioni e operazioni di bit invece della ricorsione. Rappresenta un quadrato diviso in $x\times n$ celle, una potenza di 2, dove $n,$ con coordinate intere, con $(0,0)$ nell'angolo inferiore sinistro e $(n-1,n-1)$ in alto a destra, e distanza che inizia da 0 nell'angolo in basso a sinistra e va a $d^{2}-1$ nell'angolo in basso a destra.

//Converte (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;
}

//converte 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;
    }
}

//ruotare/capovolgere un quadrante correttamente
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;
    }
}

Si usano le seguenti convenzioni di C: il simbolo & è un AND binario, il simbolo ^ è un XOR binario, l'operatore += aggiunge a una variabile, e l'operatore /= divide una variabile. La manipolazione di booleani in C suppone che in xy2d, la variabile rx si mette a 0 o 1 per rappresentare al bit s di x, e analogamente per ry.

La funzione xy2d lavora dall'alto in basso, cominciando con il bit più significativo di x e y, costruendo i bits più significativi del primo d. La funzione d2xy lavora in ordine inverso, cominciando con i bits meno significativi di d, e costruendo x e y cominciando dai bits meno significativi. Entrambe le funzioni usano la funzione di rotazione per ruotare e capovolgere il sistema di coordinate (x,y) correttamente.

I due algoritmi di corrispondenza funzionano di maniera simile. Il quadrato completo si vede come composto da quattro regioni, disposte in 2 per 2. Ogni regione è composta per quattro regioni più piccole, e così successivamente, per una serie di livelli. Nel livello s, ogni regione consiste in s per s celle. C'è un semplice ciclo FOR che viene eseguito attraverso i livelli. In ogni iterazione, si aggiunge una quantità a d o x e y, determinata da quale delle quattro regioni si trova nel livello corrente. La regione corrente dei 4 è (rx, ry), dove rx e ry sono 0 o 1. Come si consuma due bit di ingresso, (2 o d ciascuno di x e y), e genera due bit di uscita. Inoltre richiama la funzione di rotazione in modo che (x, y) siano adeguate al livello successivo, nella successiva iterazione. Per xy2d, si inizia nel livello più alto del quadrato completo e si apre il cammino fino al livello più basso delle celle individuali. Per d2xy, comincia nella parte inferiore delle celle, e lavora per completare tutto il quadrato.

Rappresentazione come un sistema di Lindenmayer

[modifica | modifica wikitesto]

La curva di Hilbert si può esprimere come un sistema di riscrittura (sistema-L).

Alfabeto : A, B

Costanti : f, l, r

Assioma : A

Regole di produzione:

A → l B fr A f A rf B l

B → r A fl B f B lf A r

Dove, f Significa "disegna in davanti", l significa "gira alla sinistra 90°", e r significa "gira alla destra 90°" (vedere grafici tartaruga).

Arthur Butz^[3] Disegnò un algoritmo per calcolare la curva di Hilbert in varie dimensioni.

Graphics Gems II^[4] discute la coerenza della curva di Hilbert, e provvede alla sua implementazione.

Implementazione

[modifica | modifica wikitesto]

In linguaggio di programmazione 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)

In linguaggio Matlab, la seguente funzione ricorsiva restituisce le coordinate dei vertici della curva di ordine $n$ nel quadrato di lato $1$ centrato su $(0,0)$ in un piano cartesiano^[5]:

function [x,y] = hilbert(n)
if n<=0
  x=0;
  y=0;
else
  [xo,yo]=hilbert(n-1);
  x=.5*[-.5+yo -.5+xo .5+xo  .5-yo];
  y=.5*[-.5+xo  .5+yo .5+yo -.5-xo];
end

Galleria d'immagini

[modifica | modifica wikitesto]

Curva di Hilbert, primo ordine
Curve di Hilbert, primo e secondo ordine
Curve di Hilbert, dal primo al terzo ordine

Curva di Hilbert in 3 dimensioni
Curva di Hilbert in 3 Dimensioni mostra la progressione di colore

Note

[modifica | modifica wikitesto]

^ D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück.
^ G.Peano: Sur une courbe, qui remplit toute une aire plane.
^ A.R. Butz: Alternative algorithm for Hilbert’s space filling curve.
^ Voorhies, Douglas: Space-Filling Curves and a Measure of Coherence, p. 26-30, Graphics Gems II.
^ Hilbert Curve - File Exchange - MATLAB Central