Robitex's Blog

Ideas in the web

La curva di Hilbert in METAPOST


Figura misteriosa…

The Hilbert Curve artwork

Si tratta di un quadro in stile geometrico di qualche artista contemporaneo da appendere a casa o al lavoro…? No, è solamente una rappresentazione delle curve di Hilbert dei primi tre livelli eseguita in METAPOST… ah ah ah.

Ancora una figura frattale…

Dopo il triangolo di Sierpinski ed il fiocco di Von Kock, consultabili qui, mi sono riproposto di disegnare la curva di Hilbert, ovvero una curva frattale in grado di riempire un intero quadrato.
Questo tipo di curve è stato studiato dal matematico italiano Giuseppe Peano ed esistono come curva limite di una successione infinita. Si può dimostrare infatti che la curva limite esiste come funzione e ricopre interamente un quadrato nel piano.

Le iterazioni della curva

Il primo passo per costruire la curva di Hilbert è disegnare tre lati consecutivi di un quadrato passanti per i quattro punti base. Su questa prima figura si disegnano gli stessi tre lati di lunghezza pari a metà della precedente, centrandoli sui quattro punti base, ruotandoli e collegandoli con tre segmenti come nella seguente figura.

The recursive drawing of the Hilbert Curve

Nell’immagine sono disegnati sovrapposti i primi due livelli, il primo in colore blu chiaro con i quattro punti base, il secondo in colore blu scuro, con i tre segmenti di collegamento in colore rosso scuro.

Per il terzo livello si procede allo stesso modo, considerando i nuovi punti basi del secondo livello e disegnando i relativi collegamenti. Nell’immagine di apertura, il primo livello è in colore verde, il secondo è in un rosso scuro ed il terzo è in blu.

Contiamo i lati ed i punti della curva

Ad ogni passo della successione i segmenti che compongono la curva si moltiplicano per quattro aggiungendosene tre per i collegamenti. In formule ciò si scrive (dove n è il numero del livello a partire da 1):

\displaystyle L(n)=3\sum_{i=0}^{n-1} 4^i = 4^n - 1.

Il numero dei punti della curva si ricava aggiungendo 1 al numero dei segmenti L(n)+1 = 4^n, dunque la crescita è esponenziale! All’ottava iterazione il numero dei punti è 65536!

Entra in scena METAPOST

Per disegnare i tre lati consecutivi dell’iterazione consideriamo il centro c ed il punto di mezzo del lato centrale x. Analizziamo il seguente codice:

beginfig(1)
  def trelati(expr c, x)=
    pair ax, bx, a, b;
    ax := c  rotatedabout(x, 90);
    bx := c  rotatedabout(x,-90);
    a  := ax shifted 2(c - x);
    b  := bx shifted 2(c - x);

    % disegno linee
    pickup pencircle scaled 5;
    draw a--ax--bx--b;
    drawarrow x--c withcolor .75blue;
  enddef;

   base = 100;
   pair cen, cx;
   cen := (base,base);  % centro
   cx  := (base,0);     % base

   trelati(cen, cx);
   trelati(cen shifted 3cx, cen shifted 4cx);
   trelati((base,-1.5base),(base,-.5base));
   trelati((4base,-1.5base),(3base,-1.5base));
endfig;
end
METAPOST Drawing test

METAPOST Drawing test

I quattro punti base ax, bx, a, b vengono definiti con trasformazioni geometriche dei punti centro e base c, x. Nel codice si mostra come la scelta del vettore che viene evidenziato dalla freccia blu, quindi l’ordine con il quale si passano gli estremi del vettore è essa stessa un informazione essenziale.

La ricorsione risolve la curva

La soluzione ricorsiva che vi presento la trova particolarmente elegante (ed adatta a chiudere l’anno), se non altro perché risolve un primo tentativo che oltre a non funzionare prevedeva altri due punti come argomento della funzione.

%
% Recursive Hilbert function
%

vardef hilbertCurve(expr c, x, level)=
    % the four basepoint
    save hilpath;
    path hilpath;
    save ax, bx, a, b;
    pair ax, bx, a, b;

    ax := c  rotatedabout(x, 90);
    bx := c  rotatedabout(x,-90);
    a  := ax rotatedabout(c ,-90);
    b  := bx rotatedabout(c , 90);

    if level = 1:
        hilpath := a--ax--bx--b;
    else:
        save atemp, btemp, axtemp, bxtemp;
        pair atemp, btemp, axtemp, bxtemp;

	atemp  := 0.25[a,b];
	btemp  := 0.25[b,a];
	axtemp := 1.25[a,ax];
	bxtemp := 1.25[b,bx];

        hilpath :=
        reverse hilbertCurve( a,  atemp, level-1) --
	        hilbertCurve(ax, axtemp, level-1) --
	        hilbertCurve(bx, bxtemp, level-1) --
        reverse hilbertCurve( b,  btemp, level-1);
    fi
    hilpath
enddef;

beginfig(1)
    pickup pencircle scaled 5;
    draw hilbertCurve(origin,(0,-100),4) withcolor red;
endfig;
end

La parola chiave reverse inverte il path e con questo si riesce a disegnare la curva di Hilbert posizionata comunque nel piano e del livello voluto (che dipende dalla memoria disponibile per METAPOST).

Scaricate pure questo file pdf della curva all’iterazione 5.

Buon anno a tutti!!!

Lascia un commento

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger cliccano Mi Piace per questo: