Robitex's Blog

Ideas in the web

Il triangolo di Sierpiński con METAPOST


La ricorsione è sempre la via migliore?

A not recursive algorithm for the Sierpinski fractal triangle

A not recursive algorithm for the Sierpinski fractal triangle

Sembra che il miglior modo di affrontare una struttura ricorsiva come il triangolo del matematico polacco sia appunto un algoritmo ricorsivo.

Tuttavia leggendo il codice relativo nel post predecente ho cominciato a ragionare sulla possibilità di chiamare ricorsivamente la funzione di disegno nominata sierpinski() una sola volta anziché tre volte, una per ciascun triangolo del livello inferiore.

L’idea che mi è venuta è quella di disegnare il triangolo dal basso, triplicando per ciascun livello successivo il disegno. Tuttavia questo si può elegantemente fare con un ciclo iterativo semplice!

Dunque vi propongo una seconda soluzione (scritta in METAPOST) in cui il disegno è ottenuto con un normalissimo ciclo for.

Il codice spiegato passo passo

Come d’abitudine propongo l’implementazione dell’idea sviluppandola di pari passo con il codice, seguito dal disegno che ne deriva.

Per prima cosa disegniamo il primo triangolo equilatero (per una breve e mirata introduzione a METAPOST potete far riferimento utile al post precedente su questo stesso blog).

beginfig(1);

u = 40 mm;
fill origin -- (u,0) -- u * dir(60)-- cycle
withcolor .625red;
drawarrow origin -- u * dir(60)
withpen pencircle scaled 5 pt;
endfig;
end

An example with the dir() METAPOST function

An example with the dir() METAPOST function

Impostare una variabile unità qui settata a 40 mm è molto comodo, ma quello che dovreste notare di questo codice è l’uso della funzione dir() per fornire al path le coordinate del vertice alto del triangolo equilatero. La funzione restituisce un vettore unitario che forma l’angolo specificato con l’asse x di senso antiorario con centro nell’origine.
Questo vettore viene visualizzato con il comando drawarrow seguente.

METAPOST disegna il vettore restituito da dir() come un punto corrispondente al secondo estremo dello stesso. Del resto sarebbe scomodo se nel path andasse il vettore piuttosto che il punto.

Nel prossimo esempio possiamo vedere l’uso del costrutto for impiegando la funzione dir() a riprova che dir(angolo) produce il disegno di un punto:

beginfig(2);
numeric u;
u = 40 mm;

for ang = 0 step 15 until 345:
draw u * dir(ang)
withpen pencircle scaled 12 pt;
endfor;
endfig;

A polar example with dir() METAPOST function

A polar example with dir() METAPOST function

Per andare avanti sul nostro obbiettivo Sierpinski, occorre spiegare il concetto di picture. I comandi grafici non fanno altro che plottare disegni in una picture. Ci sono sempre disponibili due oggetti picture, quella corrente detta currentpicture e quella vuota detta nullpicture. Un po’ di codice chiarirà di cosa si tratta:

beginfig(3);
% set the thin of the pen
pickup pencircle scaled 3pt;

draw fullcircle scaled 80pt
withcolor 0.5 green;

picture pic;
pic := currentpicture;
currentpicture := nullpicture;

draw pic;
draw pic shifted (80pt,0);
endfig;

The METAPOST picture concept at work

The METAPOST picture concept at work

All’oggetto pic di tipo picture viene assegnato il disegno corrente, che in quel momento contiene un cerchio verde, poi il disegno viene cancellato. In questo momento il cerchio verde si trova memorizzato in un solo luogo: la picture pic.
Allora possiamo tornare a riempire currentpicture disegnando prima pic nella sua posizione e poi in quella traslata a destra.

L’idea iterativa Sierpinski

% set the unit size
u = 10 mm;

% a picture object
picture sier;

sier:= currentpicture;
draw sier shifted (u,0);
draw sier shifted (dir(60) scaled u);

The basic idea for a iterative Sierpinski drawing method

The basic idea for a iterative Sierpinski drawing method

Questo frammento di codice è il cuore del programma che disegna il triangolo frattale in maniera iterativa e non ricorsiva.
Si presuppone che la currentpicture contenga all’inizio il triangolino di base molto piccolo. Dapprima si memorizza il disegno corrente nella variabile sier, di tipo picture naturalmente, e semplicemente l’aggiungiamo al disegno corrente stesso prima a destra e poi in alto a 60° al posto giusto.

In altre parole come si vede in figura, il triangolo rosso viene memorizzato in una picture e poi viene riaggiunto due volte nella posizione dei triangoli blu. Basterà iterare all’infinito questo procedimento!

Il ciclo for Sierpinski

beginfig(4);
% set the unit size
u = 0.65 mm;

% draw the basic smallest triangle
fill origin--(u,0)-- dir(60) scaled u --cycle
withcolor .625red;

% a picture object
picture sier;

% recursive level
level = 8;

% main drawing cycle
for i=0 upto level-1:
tmp := u * (2**i);
sier:= currentpicture;
draw sier shifted (tmp,0);
draw sier shifted (dir(60) scaled tmp);
endfor;

endfig;

Adesso il codice è completo. L’operazione precedente di copia a destra ed a 60° è inserita nel ciclo iterativo for che produce il triangolo del livello desiderato (ho scelto il livello 8).
Aggiungo che ad un dato livello i la copia del disegno deve esser fatta ad una distanza di u \cdot 2^i, poichè ogni volta che si sale di un livello, il lato del triangolo raddoppia (il doppio asterisco significa quindi elevamento a potenza).

Alla prossima!

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: