Robitex's Blog

Ideas in the web

Il triangolo di Sierpiński


Il disegno della ricorsione

Visualizzare la ricorsione è l’idea di questo post. E la figura ricorsiva più semplice da disegnare mi sembra proprio il triangolo di Sierpiński. Dopo qualche notizia essenziale sul software che userò, passeremo al codice…

Sierpinski Triangle

Sierpinski Triangle of 6 level (click to download the pdf file)

Il linguaggio grafico di Asymptote

Per le nostre sperimentazioni useremo un software chiamato Asymptote, che consiste in un linguaggio di alto livello derivato dal METAPOST, piuttosto espressivo, simile a C++ e Java, quindi fortemente tipizzato.

Si possono instanziare i classici tipi numerici come int o real, e produrne di nuovi per mezzo del costrutto struct.

Infine, occorre terminare le istruzioni con il punto e virgola, utilizzare le parentesi graffe per definire i blocchi di codice, e produrre i commenti nel formato C++, ma vediamo subito un esempio (supporremo che una versione di Asymptote sia installata sul vostro sistema Windows, Linux o Mac OS che sia, magari tramite la TeX Live 2009).

Per disegnare una spezzata scrivete in un file di testo con estensione .asy il seguente codice, dove le coordinate sono separate da un doppio trattino che significa come in molti altri linguaggi del mondo LaTeX, una linea retta:

draw((0,0)--(2.5,2.5)--(5,0.5)--(7.5,5));

Poi in una finestra di console, date il comando di compilazione: asy -f pdf nomefile.asy. Al termine dell’elaborazione verrà rilasciato un file pdf contenente il risultato grafico desiderato.

Qualcosa di più complesso

Cominciamo a disegnare quello che sarà il triangolo di livello 0, utilizzando il tipo pair ovvero il tipo che in Asymptote corrisponde ad una coppia di numeri reali:

// triangle line length
real ell = 100;

// level 0 triangle:
pair p1 = (0,0);
pair p2 = (ell,0);
pair p3 = (ell/2,sqrt(3)*ell/2);
draw(p1--p2--p3--cycle);

Il termine cycle specifica che il percorso da disegnare sarà chiuso e corrisponde di fatto al primo punto p1.

Sierpiński

Il triangolo del matematico polacco venne da lui elaborato nel 1915, quando i sovietici tentavano di impossessarsi del cuore di quel popolo.

Disegnato un triangolo (che supporremo equilatero) detto di livello 0, si disegna il triangolo i cui vertici sono i punti di mezzo dei lati del triangolo principale, poi si applica ricorsivamente lo stesso procedimento ai tre sotto triangoli nord, sud-est e sud-ovest.

La struttura è un frattale in quanto è autosomigliante. Una semplice osservazione ci dice che man mano che si scende di livello le lunghezze dei lati dei triangoli si dimezzano, per cui se l_0 è la misura del lato del triangolo del livello 0, quella del lato a livello n sarà:

\displaystyle l_n = \frac{l_0}{2^n}.

Il numero dei triangoli t in funzione del livello v si ottiene considerando che scendendo di un livello il loro numero cresce di 3^v-1. In formule:

\displaystyle t = 1 + \sum_{i=1}^v 3^{i-1}

Per esempio al livello 5 i triangoli disegnati sono 122, ma al 10° salgono a 29.525 ed al 14° sono ben 2.391.485.

Il codice (non ottimizzato)

Per terminare i cicli ricorsivi altrimenti infiniti, è possibile utilizzare un criterio grafico: se lo spessore di tracciamento delle linee è tale che i triangoli dei livelli ulteriori risultano coperti, è inutile proseguire con il disegno.

La funzione ricorsiva chiamata sierpinski() prende i tre punti vertici del triangolo ed effettua immediatamente il test seguente (s è lo spessore del tratto ed l la lunghezza del lato del triangolo):

\displaystyle \frac{s}{2}\geq \frac{l}{2\sqrt{3}}

Se il test è falso significa che possiamo procedere al disegno del sotto-triangolo con i vertici nei punti di mezzo dei lati del triangolo principale, ed incrementare l’intero che conterrà alla fine il numero totale dei triangoli disegnati.

Il passo finale è lanciare ricorsivamente tre volte la funzione stessa sui sotto-triangoli del livello successivo.

Il codice non è ottimizzato perché in realtà non serve calcolare la distanza tra due punti per ottenere la lunghezza del lato del triangolo del livello attuale perché è ottenibile semplicemente dimezzando quella corrispondente al livello precedente.

Ecco il listato:

//
// Sierpinsky triangle: draw it with a recursive function
// Copyright (c) 2009 Roberto Giacomelli
// Term of licence see: https://robitex.wordpress.com/legalese/
//

// var setup
int n = 1;
real l0 = 100;
real s = 1.0;

// set the linewidth
defaultpen(s);

// main triangle
pair p1 = (0,0);
pair p2 = (l0,0);
pair p3 = (l0/2,sqrt(3)*l0/2);
draw(p1--p2--p3--cycle);

// function med() return the midpoint
// of the line ab
pair med(pair a, pair b){
return ((a.x+b.x)/2 , (a.y+b.y)/2);
}

// function dist() computes the length
// of line ab
real dist(pair a, pair b){
return sqrt((a.x-b.x)^2+(a.y-b.y)^2);
}

// main recursive function
void sierpinski(pair a, pair b, pair c){
// check graphic stop condition
if ( s<= dist(a,b)/sqrt(3) ){return;}

// draw subtriangle of the level
pair am = med(b,c);
pair bm = med(a,c);
pair cm = med(a,b);
draw(am--bm--cm--cycle);
++n;

//well, and now recursive running
// sublevel south east triangle
sierpinski(a,cm,bm);
// sublevel south west triangle
sierpinski(cm,b,am);
// sublevel north triangle
sierpinski(c,bm,am);
}
// draw the Sierpinski figure
sierpinski(p1,p2,p3);

// write on console the number
// of drawed triangles
write(n);

Scarica l’esempio in pdf : Sierpinski Triangle Figure
Alla prossima!

Una risposta a “Il triangolo di Sierpiński

  1. Pingback:Il triangolo di Sierpiński con METAPOST « Robitex’s Blog

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: