Alberi Ricorsivi

Stefano Berardi

Come usare le definizioni ricorsive per produrre disegni autosimili di alberi. Gli alberi ricorsivi sono un particolare esempio di un tipo di figure matematiche detta Frattale, figure che non descriveremo qui.

Torino, 5 Giugno 2001

Un procedimento ricorsivo per generare alberi. Partiamo da un tronco, alla fine di esso aggiungeremo due tratti di ramo, alla fine di ognuno di essi altri due e così via, per un numero finito n di passi. La direzione, lo spessore e la lunghezza di ciascuno dei tratti di ramo aggiunti dipenderà dalla direzione, dallo spessore e dalla lunghezza del tratto di ramo di provenienza. Le direzioni dei due rami aggiunti formeranno due angoli fissi , con la direzione del ramo di provenienza. Lo spessore e la lunghezza dei due rami aggiunti avranno un rapporto fisso , ,, con lo spessore e la lunghezza del ramo di provenienza.

Cosa si ottiene. Questa legge consente di disegnare alberi, ma anche fiori, erbe, arbusti, figure geometriche astratte, e oggetti artificiali (come le antenne televisive) che hanno gli alberi reali solo una vaga analogia di forma.

Autosomiglianza degli alberi ricorsivi. Un aspetto singolare di questi alberi ricorsivi, che sarà evidente dai disegni, ma che possiamo già osservare adesso, è il seguente. Ogni ramo di un albero ricorsivo (completo di tutti i rami più piccoli che nascono da esso) è una copia (semplificata) dell'albero originario. Tale copia è ruotata di un angolo α, ha lunghezza diminuita di un fattore ρ, e spessore diminuito di un fattore s. Questo perchè a partire da ogni ramo ripetiamo lo stesso procedimento eseguito sul tronco dell'albero: l'unica differenza sta nella direzione, nella lunghezza e nello spessore del ramo. Tale caratteristica degli alberi ricorsivi è detta autosomiglianza.
L'unica differenza tra un albero ricorsivo e una sua parte è che, se a partire dal tronco ripetiamo il procedimento n volte, a partire da un ramo il procedimento sarà ripetuto solo n-1 volte, n-2 volte, eccetera. Dunque un ramo risulterà più semplice dell'albero di cui fa parte. Tuttavia, idealmente, se ripetessimo il procedimento infinite volte, ogni ramo sarebbe una copia perfetta dell'albero originario.
Notiamo inoltre che il tronco non è simile all'albero di partenza, solo i rami lo sono. In altre parole, l'autosomiglianza non si estende ad ogni parte di cui è composto l'albero.

Piano di lavoro. In § 1 vedremo qualche primo esempio di albero generato secondo la legge ricorsiva di cui sopra. In § 2 scriveremo un procedimento per generare un albero dati i parametri , ,  , ,, . In § 3, per migliorare la resa del disegno, assegneremo un colore al tronco, uno ai rami più esterni, e colori intermedi ai rami intermedi. In § 4 applicheremo tale procedimento a numerosi casi particolari. In § 5 generalizzeremo il procedimento aumentando il numero dei rami aggiunti in ogni passo a tre.
Infine, in § 6, per curiosità, genereremo un "albero frattale", la cui chioma (l'insieme dei rametti più esterni) sarà un frattale, la "curva a C".

§ 1. Primi esempi di alberi ricorsivi.

  Disegnamo un caso particolare di albero ricorsivo. Partiamo da un "tronco" rappresentato da un segmento da (0,0) in (0,1), poi aggiungiamo al termine di esso due rami, di lunghezza contratta dello stesso fattore = , e ruotati di = 45 gradi, = -45 gradi rispetto al tronco. Tali rami avranno quindi origine in (0,1), e fine, rispettivamente, in (+1/2, 1+1/2) e (-1/2, 1+1/2). Ripetiamo la stessa operazione su ognuno dei due rami ottenuti, e cosi' via.
Il risultato dopo 2 passi è un albero composto di 1+2 = 3 linee:

Disegnamo l'albero usando una linea rossa di spessore fisso, pari al 2% del disegno (dunque = = 1). Nel disegno, usiamo un rapporto altezza/base di 3/2.

Dopo 3 passi otteniamo un albero composto di 1+2+2*2=7 linee, e dopo 4 passi un albero composto di 1+2+2*2+2*2*2=15 linee. Il calcolo dei punti iniziali e finali per ognuna di queste 15 linee diventa lungo, ma resta concettualmente semplice.

Disegnamo l'albero con una linea rossa di spessore pari al 2% del disegno, e un rapporto altezza/base di 3/2.

Vogliamo ora definire un procedimento che costruisca un albero dati: il numero ord di volte che vogliamo ripetere il procedimento, i parametri , ,  , ,, , lo spessore iniziale T, e i colori del tronco e dei rami più esterni.

§ 4. Esempi di alberi generati ricorsivamente.

Alberi simmetrici.

Consideriamo innanzitutti esempi di alberi simmetrici rispetto alla linea passante per il tronco. Negli alberi ricorsivi simmetrici, i due rami che escono da un ramo dato sono immagini speculari l'uno dell'altro. Per ottenere questo effetto dobbiamo scegliere =-,=, = (cioè due angoli speculari, e lo stesso fattore di contrazione per lunghezze e spessori nei due rami).

Diamo alcuni esempi. Prima un albero, ottenuto con diramazioni di 20 e -20 gradi, poi con un fiore, ottenuto con diramazioni di 10 e -10 gradi, infine un'antenna televisiva arrugginita, ottenuta con diramazioni di 90 e -90 gradi.

  Il Baobab. Disegnamo un albero, colorando il tronco di marrone, poi sfumando il colore dei rami fino al verde. In ogni diramazione, i rami formano un angolo di 40 gradi.

Autosomiglianze del disegno. Sono curiose e interessanti le autosomiglianze che riscontriamo nel disegno. Se consideriamo il primo ramo sinistro, e se ignoriamo le sovrapposizioni con gli altri rami, notiamo che esso ha una forma quasi identica a quella dell'albero tutto intero. Lo stesso vale per il primo ramo destro, e per i rami successivi e più piccoli. Tuttavia, tale somiglianza diventa sempre più vaga, fino a svanire del tutto per i rami più esterni.
Ritroveremo l'autosomiglianza tra un albero ricorsivo e ogni suo ramo in tutti i disegni successivi.

  Il Geranio. Disegnamo ora un fiore, colorando lo stelo di verde e marrone, poi sfumando il colore delle diramazioni fino al rosa. In ogni diramazione, i rami formano un angolo di 20 gradi.

  Un'antenna televisiva rettangolare. Disegnamo ora un'antenna televisiva, con colori dal grigio scuro al rosso scuro, per dare un'idea di ruggine. Ogni "ramo" è curvato rispetto al precedente di +90 o -90 gradi: il risultato è un disegno rettangolare. In ogni diramazione, i rami formano un angolo di 180 gradi (un angolo piatto).

Un'antenna televisiva trapezoidale. Modifichiamo il disegno precedente ampliando gli angoli tra le diramazioni a +120, -120 gradi. Il risultato è un'antenna televisiva trapezoidale. In ogni diramazione, i rami formano un angolo di 240 gradi (due terzi di giro, un angolo concavo).

Notiamo che la differenza tra l'albero, il fiore e le antenne televisive sta essenzialmente nell'ampiezza dell'angolo di diramazione. Un angolo basso dà un'erba o un fiore; un angolo medio, dà un albero; un angolo alto fornisce un oggetto dall'aspetto artificiale, simile, come abbiamo detto, ad un'antenna televisiva.

Alberi asimmetrici.

Proviamo ora a rendere asimmetrico l'albero: lasciamo liberi di variare i 6 parametri , ,  , ,, , senza supporre legami tra i parametri relativi a un ramo e quelli relativi a un altro.

Il Salice. Diamo un esempio di un albero con diramazioni di angolo 60 gradi: +40 per il ramo sinistro e -20 per il ramo destro. Contraiamo la lunghezza del ramo sinistro meno rapidamente della lunghezza di quello destro. Contraiamo, al contrario, gli spessori più rapidamente a sinistra che non a destra.
In questo modo la parte sinistra dell'albero sarà lunga, sottile e storta (dato che l'angolo sinistro è più elevato di quello destro). La parte destra, invece, sarà corta, tozza, e quasi diritta. Il risultato è una forma a "salice piangente".

Il Piumino. Ripetiamo il procedimento precedente, ma scegliendo diramazioni più strette, 10 gradi e -2 gradi, dunque 12 gradi di angolo tra i due rami. Otteniamo un filo d'erba che termina in una sorta di piumino.

§ 5. Alberi con diramazione 3.

Definiamo un procedimento per stampare alberi con tre rami anzichè due che si dipartono da ogni ramo precedente.

Diamo alcuni esempi di disegni con diramazione 3.

Il Garofano. Riprendiamo ora il disegno del Baobab (un albero con una diramazione di 40 gradi tra i rami) e aggiungiamo un ramo centrale. Cambiamo la colorazione, poichè il disegno così ottenuto ci suggerisce un fiore più che un albero.

La Felce. Disegnamo ora un arbusto con una diramazione ampia tra i due rami laterali (160 gradi, quasi un angolo piatto), un ramo principale al centro, leggermente inclinato a destra. Facciamo decrescere la lunghezza e lo spessore dei rami laterali molto più rapidamente della lunghezza e spessore del ramo centrale.

Il Rovo. Riprendiamo il disegno precedente, della Felce, facendo piegare il tronco molto più a destra di prima. La figura contorta così ottenuta ci suggerisce un rovo: modifichiamo i colori di conseguenza, usando tinte cupe.

Il Pino. Riprendiamo ancora il disegno della Felce (160 gradi di diramazione tra il ramo sinistro e quello destro), ma consideriamo ora un tronco perfettamente diritto. Diminuiamo anche la differenza tra il tronco centrale e i rami laterali. Otteniamo una figura che ci ricorda un Pino.

L'Ulivo. Disegnamo ora un albero con tre rami dello stesso spessore e lunghezza, tutti fortemente piegati. L'effetto è un arbusto contorto, ma senza la prevalenza di uno ramo centrale come per la Felce e il Rovo. Chiamiamo l'albero così ottenuto un Ulivo.

La Quercia. Riprendiamo il disegno precedente limitandoci ad aumentare lo spessore dei rami. L'effetto cambia completamente.

§ 6. L'albero frattale (una fantasia geometrica).

Disegnamo ora, per curiosità, un albero la cui chioma (l'insieme dei rami più esterni) è una curva studiata più estesamente in altra sede: la curva a C. Congetturiamo che tale curva sia un frattale, e chiameremo "albero frattale" l'albero la cui chioma dà la curva a C.
L'"albero frattale", nonostante il suo nome, ha un angolo di diramazione alto, e una forma rigorosamente geometrica che non gli permette alcuna somiglianza con un albero reale. Si tratta di un disegno astratto e molto singolare.

La legge di generazione dell'albero frattale è particolarmente semplice. L'albero frattale è simmetrico, ogni ramo è inclinato di +45 o -45 gradi (dunque i due rami formano tra loro un angolo retto), lo spessore e la lunghezza di un ramo diminuiscono ogni volta di .
Disegneremo l'albero frattale quattro volte, cambiando solo i colori scelti per la chioma (chioma che, come abbiamo detto, è una Curva a C). Usiamo il verde-chiaro per la versione primaverile, il verde-marrone per la versione estiva, l'arancio-scuro per la versione autunnale, l'azzurro-chiaro per la versione invernale. Il tronco viene disegnato marrone in ogni caso.

Albero frattale: versione primaverile.

Albero frattale: versione estiva.

Albero frattale: versione autunnale.

Albero frattale: versione invernale.