L'IFS (Iterated Function System) est un moyen de représenter les
fractales. Il est défini par un espace métrique complet et un
ensemble d'applications contractantes. L'ensemble recherché,
qui peut être fractal est l'attracteur de l'IFS. Il est
invariant selon toutes les applications qui composent l'IFS.
Nous nous intéresserons uniquement à la construction de
l'attracteur, connaissant l'IFS. Il existe cependant un théorème,
dû à Barnsley, qui permet de construire un IFS tel que son
attracteur soit proche d'un objet de départ.
Algorithme
Afin de résoudre le problème posé en introduction, nous faisons
appel à un algorithme itératif. En effet, fixons un
point de départ dans un plan, par exemple (0,0). Appliquons lui une
des transformations de l'IFS prise au hasard. On obtient un autre
point du plan. Appliquons lui le même traitement., nous obtenons un
autre point. Si l'on répète l'opération un grand nombre de fois,
on obtient finalement une bonne approximation de l'ensemble recherché.
On peut donner une ébauche de justification. En appliquant
un certain nombre de fois les applications au point de départ, on
va entrer à un moment donné dans l'attracteur. Cet ensemble peut
s'apparenter à un point fixe, on ne va donc plus en sortir lors des
itérations successives. A un certain moment, l'ensemble sera
suffisament bien décrit pour pouvoir se le représenter
visuellement. Le triangle de Sierpinski ci-dessous
illustre ce phénomène.
Remarque: Pour optimiser la vitesse de convergence vers
l'attracteur, il est conseillé lors du choix aléatoire de la
transformation d'appliquer une loi de probabilité spécifque. Cette
donnée est souvent fournie avec la "matrice" IFS par
l'ajout d'une colonne.
L'algorithme va donc être le suivant:
Initialisation: On fixe un point de départ.
Boucle:
Choix d'une coordonée selon la loi de probabilité.
Le point suivant est l'image du point courant par la
transformation choisie.
Condition d'arret: On atteint un nombre d'itérations
fixés par l'utilisateur.
Méthodes d'édition
En premier lieu, un paramètre modifie à lui tout seul la vitesse
de rendu d'une fractale générée par IFS. Il s'agit du nombre de
points, plus il est important et meilleur (et plus fidèle) sera le
résultat, cependant le calcul sera quant à lui plus long.
Le triangle de Sierpinski en fonction du nombre
de points:
100 points
1000 points
10.000 points
Les programmes d'IFS prennent en paramètres une quantité de
transformations consistant en un similitude (rotation+homotétie),
une translation et un facteur de probabilité.
Une transformation en 2 dimensions sera donc representée sur une
ligne par 7 valeurs, respectivement on trouvera dans l'ordre:
les 4 coefficients de la matrice de similitude
les 2 coefficients du vecteur de translation
la fréquence d'appel de cette transformation sous forme de
probabilité
Bien sûr la somme des probabilités de chaque transformation doit
être égale à 1, mais moins évident: les transformations doivent
être absolument contractantes (c'est à dire que tous les points
doivent être contenu dans un ensemble fermé).
Sachant cela, il est nécesaire de savoir si certains points ne
divergent pas, on peut tester de diverses manières selon le type
d'optimisation souhaitée.
Programme: IFS
Documentation
"IFS" est un programme permettant de calculer une
fractale à partir d'une matrice IFS dont la syntaxe est conforme à
la structure décrite plus haut, il génère un fichier image au
format ppm (portable pixmap).
Ci-contre, à droite, se trouvent des images générées par le
programme ainsi que des liens sur les fichiers .ifs qui ont permis
de les calculer.
Pour obtenir une aide au sujet des options, tappez juste le nom de
l'exécutable:
