Il padre della teoria dei frattali è considerato Benoit Mandelbrot, che per primo formalizzò le proprietà di queste figure, prima di lui considerate degli oggetti eccezionali, "mostri matematici"; diversi frattali classici sono infatti stati descritti da celebri matematici del passato, come Cantor, Peano, Hilbert, von Koch, Sierpinski, ma fu solo con The fractal geometry of nature che essi trovarono posto in una teoria unificata, che ne sottolineava i legami con forme tipiche della natura (alberi, foglie, coste, etc.).
Un frattale è, intuitivamente, una figura in un cui un singolo motivo viene ripetuto su scale descrescenti; ingrandendo una parte della figura, possiamo individuarvi una copia in scala della figura stessa, come si può vedere osservando la curva di Von Koch:
Si considera frattale un insieme che goda di tutte o molte delle seguenti proprietà:
Inoltre, in molti casi un frattale ha una semplice definizione ricorsiva e un aspetto "naturale", ispirato cioè ad organismi presenti in natura.
In questo progetto, sono state esplorate due metodologie di generazione di figure frattali: L-Systems e IFS.
Gli L-Systems (abbreviazione per Lindenmayer Systems) furono concepiti come una teoria matematica dello sviluppo delle piante e successivamente utilizzati in grafica per il disegno di figure frattali, specialmente piante e organismi vegetali in genere.
Alla base degli L-Systems vi è il concetto di riscrittura: oggetti complessi vengono definiti mediante la successiva sostituzione di un semplice oggetto iniziale, usando un insieme di regole di riscrittura (anche dette produzioni). I sistemi di riscrittura maggiormente studiati e noti operano su stringhe di caratteri: per esempio, è dovuta a Chomsky la definizione, negli anni '50, di grammatiche formali, basate sul concetto di riscrittura, per descrivere le caratteristiche sintattiche dei linguaggi naturali. Anche gli L-Systems, introdotti nel 1968, sono meccanismi di riscrittura di stringhe, ma si differenziano dalle grammatiche di Chomsky per il metodo di applicazione delle produzioni: mentre nelle grammatiche di Chomsky le produzioni vengono applicate sequenzialmente, negli L-Systems l'applicazione è parallela e coinvolge contemporaneamente tutti i simboli nella stringa data.
La classe più semplice di L-Systems è rappresentata dai cosiddetti D0L-Systems, cioè gli L-systems deterministici e
context-free. Sia V un alfabeto, V* l'insieme di tutte le parole su V e
V+ l'insieme delle parole non vuote su V.
Un 0L-System è una tripletta ordinata G = áV, w, Pñ, dove V è l'alfabeto del sistema,
w Î V+ è una parola detta assioma e P Ì V × V* è un insieme finito
di produzioni. Una produzione (a, c) Î P è scritta
come a ® c; la lettera a e la parola
c sono chiamati rispettivamente predecessore e successore della produzione. Si assume che per ogni
lettera a Î V ci sia almeno una parola
c Î V*
tale che a ® c.
Se nessuna produzione viene specificata esplicitamente per un dato predecessore a Î V , si assume che
la produzione identità a ® a appartenga all'insieme P delle produzioni.
Un 0L-System viene detto deterministico (D0L-System) se e solo se per ogni a Î V esiste
esattamente un c Î V*
tale che a ® c.
Sia m = a1 ¼ am una parola arbitraria su
V. La parola
n = c1 ¼ cm
Î V* è derivata direttamente da m,
e si scrive m Þ n,
se e solo se ai ® ci per tutti gli
i = 1, ¼, m. Una parola n è generata da G
in una derivazione di lunghezza n se esiste una sequenza di sviluppo di parole
m0, ¼, mn tale che
m0 = w,
mn = n e
m0 Þ ¼ Þ mn.
Inoltre, è possibile costruire i cosiddetti Bracketed 0L-Systems (L-Systems parentesizzati), particolarmente adatti a descrivere
figure con diramazioni rispetto ad un asse principale, come nel caso di alberi, cespugli, ecc.
Le stringhe di un L-System possono essere interpretate geometricamente secondo la cosiddetta interpretazione tartaruga. Lo stato della tartaruga è definito da una tripletta (x, y, a), dove le coordinate cartesiane (x, y) rappresentano la posizione della tartaruga e l'angolo a, detto direzione, è interpretato come la direzione in cui la tartaruga si sta muovendo. Data la lunghezza del passo d e l'incremento d'angolo d, la tartaruga può rispondere ai comandi forniti attraverso i seguenti simboli:
Data una stringa n, lo stato iniziale della tartaruga (x0, y0, a0) e i parametri fissati d e d, l'interpretazione tartaruga di n è proprio la figura (cioè l'insieme di segmenti) disegnata dalla tartaruga in risposta alla stringa n. In questo modo, è possibile ottenere una rappresentazione grafica delle produzioni di un L-System e visualizzare figure di varia complessità, anche ispirate al mondo naturale.
Molte figure, generalmente legate ad immagini naturalistiche, possono essere generate grazie agli Iterated Function System (IFS), cioè insiemi di trasformazioni il cui risultato finale è proprio una figura frattale. Spesso, infatti, strutture naturali come felci, foglie e alberi sono caratterizzate da evidenti proprietà di auto-similarità su diverse scale (ad esempio, il ramo di un albero può essere visto come una copia rimpicciolita dell'albero stesso oppure come un ingrandimento di alcune sue parti), il che rende adatta una loro rappresentazione grafica proprio tramite un frattale.
Un IFS consiste generalmente in una collezione di k trasformazioni affini che, applicate iterativamente ad un'immagine di partenza, producono sempre la stessa figura (detta attrattore), qualunque sia l'insieme di punti di partenza. Il processo iterativo tende dunque ad un attrattore ben definito, come pu�essere la foglia di una felce o un albero.
Ricordiamo che un'affinit�fra due piani è un'applicazione biiettiva che fa corrispondere al punto P di coordinate (x, y) il punto P' di coordinate (x', y'), secondo le equazioni:
x' = ax + by + e
y' = cx + dy + f
Un'affinità gode delle seguenti proprietà:
Le trasformazioni IFS prevedono tipicamente composizioni di rotazioni, traslazioni (entrambe isometrie, cioè affinità che conservano le distanze, la forma e la grandezza delle figure), e omotetie (che conservano l'ampiezza degli angoli). Una trasformazione IFS mappa quindi il punto (x, y) in (x', y') utilizzando due angoli, q e f, per la rotazione, i valori r e s per la riduzione di scala ed infine h e k per la traslazione:
x' = r cos(q) x + s sin(f) y + h
y' = -r sin(q) x + s cos(f) y + k
Illustriamo ora più in dettaglio il procedimento IFS.
Durante la prima iterazione, la figura generatrice viene sostituita con altre k che sono il risultato di riduzioni di scala,
rotazioni e traslazioni. Ciascuna nuova figura così ottenuta diviene a sua volta generatrice e trasformata nel medesimo modo.
Questo processo, applicato per un numero elevato di iterazioni, tende a produrre un attrattore, cioè la figura desiderata, a condizione che
le trasformazioni siano contrattive, ovvero tali per cui ogni figura trasformata risulti la copia ridotta, secondo un certo fattore di scala, dell'originale.
La correttezza del procedimento �garantita dal Collage Theorem (Barnsley, 1985), che assicura che,
dato un IFS che approssimativamente copre un insieme di punti, l'attrattore finale approssimerà lo stesso insieme di punti.
La seguente figura mostra l'effetto dell'applicazione di 4 trasformazioni volte alla produzione della celebre felce di Barnsley (la quarta trasformazione, che in realtà non è un'affinità, realizza lo stelo):
In questa figura possiamo invece visualizzare le trasformazioni che producono la foglia:
I coefficienti delle trasformazioni per la realizzazione di molte figure frattali sono noti in letteratura, grazie ai numerosi studi effettuati per riprodurre efficacemente figure naturalistiche mediante frattali. In questo progetto (vd. Applet IFS) abbiamo scelto di adottare come figura di partenza una generica curva di Bezier (infatti, per quanto detto, qualunque sia la figura iniziale, il risultato finale sarà sempre identico, a patto di ripetere il processo per un elevato numero di iterazioni). Lo scopo è quello di capire in che modo la figura generatrice influenzi il risultato finale del processo su poche iterazioni e quindi se una curva che si autointerseca oppure una curva simmetrica possano generare risultati graficamente differenti.
Applicare k (per la felce, 4) iterazioni ad una curva di Bezier, come ad ogni figura più complessa di un singolo punto, è tuttavia molto dispendioso dal punto di vista computazionale; questo rende praticamente impossibile, per un computer odierno, iterare il processo per un numero significativo di volte. Di conseguenza, la figura non risulta completamente formata e quindi la curva di partenza, ancora ben visibile, ha molta importanza sul risultato finale. È quindi compito di chi utilizza l'applicazione trovare la curva di Bezier di partenza più adatta per ottenere il risultato voluto.
Le trasformazioni IFS possono quindi essere applicate a partire da una generica figura in maniera deterministica,
cioè applicando a ciascun punto della figura corrente ciascuna delle k trasformazioni che descrivono l'attrattore,
come abbiamo appena visto.
Alternativamente, è possibile realizzare il cosiddetto Chaos Game. Nel Chaos Game, a partire da un unico punto
si applica una sola delle trasformazioni previste, scelta a caso con una probabilità fissata (alcune trasformazioni hanno quindi
maggior probabilità di essere selezionate); ad ogni passo, un nuovo punto, così calcolato, viene aggiunto alla
figura, che man mano diventa più dettagliata. Il vantaggio di questa tecnica è la sua leggerezza computazionale:
adottando il Chaos Game è possibile infatti disegnare figure frattali composte di migliaia di punti (e quindi molto ben definite) con facilità.
Esempi di coefficienti IFS possono essere trovati qui.