Introduction
- De nombreuses méthodes récursives permettent de générer des
objets fractals que ce soit sur un plan comme en 3 dimensions.
L'"éponge", ci-contre, est un exemple de récursivité
dont la convergence est très rapide, en effet au bout de quelques
transformations, l'objet atteint un volume quasiment nul.
- Alors que l'IFS décrit un ensemble à partir d'une diffusion aléatoire
de points ayant subi des transformations successives, la récursivté
suit plus clairement la logique des fractales, elle construit
l'ensemble en appliquant des transformations à des échelles
variables.
- En résumé cette méthode respecte invariablement une quantité
de lois qui, comme dans la nature, peuvent connaître de légères
variations (que l´on peut appeler erreurs). Mais qu'il s'agisse
d'IFS ou de récursivité, on tendra toujours vers les même
ensembles (attracteurs) .
- Les algorithmes sont tous très simples, l'invariant consistant à
appeler une transformation pour chaque sous objet résultant de la
transformation précédente. Mais la transformation peut, quant à
elle, être assez complexe. C'est pourquoi, selon les cas, la méthode
itérative sera préférable.
- Reste qu'il est nécessaire de trouver une condition d'arrêt
pendant le calcul ou l'affichage d'un ensemble. Une solution
courrament utilisée consiste à retenir la profondeur de récursion
(celle-ci permettant en général de décrire le facteur d'échelle
qui s'applique sur l´objet en cours de transformation), et de
tester si celle-ci n'excède pas un nombre limite.
- Ainsi, contrairement à la méthode itérative, la récursivité
peut faire converger le résultat très vite vers l'attracteur.
Selon le rapport d'échelle, on peut obtenir en peu de temps un
ensemble quasi semblable à la réalité, bien que celle-ci soit
difficilement modélisable dans son intégralité.
- Pour ce qui est des atuces de constructions, une des plus faciles
à implémenter est la méthode de substitution par matrices.
- Par exemple avec une matrice 2x2 de ce type:
( 0 1 )
( 1 1 )
- Pour chaque 1 rencontré on remplace le coefficient par cette
matrice, et pour chaque 0 on le remplace par une matrice nulle. Au
bout d'un certain nombre de substititions (profondeur de récursion),
on obtient une matrice NxN, où N est un nombre en puissance de 2
(l'exposant étant précisément la profondeur de récursion
globale). Ansi 3 étapes nous donneront dans cette exemple une
matrice 8x8.
- Au final, on obtiendra....le triangle de Sierpinski (voir image).
Pour obtenir une aide au sujet des options, tappez juste le nom
de l'exécutable.
>recursion
Usage: recursion <fichier.ppm> [options]
|
Options |
|
Defauts |
Valeurs: |
|
-l |
<largeur> |
(256) |
{>=1} |
|
-h |
<hauteur> |
(256) |
{>=1} |
|
-i |
<fichier.rec> |
(stdin) |
|
|
-r |
<recursions> |
(8) |
{>=1} |
Un fichier .rec doit avoir la syntaxe suivante:
> 3 nombres (largeur, hauteur, nombre
de matrices)
> les coefficients des matrices à la
suite, séparés par des espaces ou des retours à la ligne.
n m c
x11 x12 ... x1n
x21 ...
...
xm1 xm2 ... xmn
y11 y12 ... y1n
y21 ...
...
ym1 ym2 ... ymn
...
Les coefficients sont des nombres indexant la matrice à
appeler à la prochaine récursion. Il y a deux nombres
particuliers:
0 désigne la non appartenance à l'ensemble
-1 signifie l'inverse
exemples de fichier .rec:
- carre.rec
- triangle.rec
- matrice.rec
Liens
- les fractales - projet ESSI2
|
Sierpinski 3D
- Cet objet est basé sur la méthode de construction du tapis de
Sierpinski:
carre.rec
- On subdivise le carré en 9 parties égales, on enlève le carré
central, puis on continue l'opération pour chaque carré restant.
Arbres construits récursivement
- Voici des arbres représentés en fonction de la profondeur de récursion:
 p=1 |
 p=2 |
 p=3 |
 p=4 |
 p=5 |
 p=6 |
 p=7 |
 p=8 |
- Remarque: pour rendre l'arbre plus réaliste on applique
une erreur aléatoire de plus ou moins grande amplitude sur chaque
paramètre de la transformation. Par exemple ici sur l'inclinaison
des branches, leur épaisseur et leur longueur.
- Dans cette animation, seul un paramètre change, il s'agit du
facteur de réduction entre deux étapes récursives. Il évolue de
0 à 0.7, cela signifie qu'à la fin, un branche fille est 0.7 fois
plus petite que sa mère.
- Arbre
grand format avec 8 niveaux de récursivité.
Le triangle de Sierpinski en 3D
profondeur: 1 |
profondeur: 2 |
profondeur: 3 |
profondeur: 4 |
- La transformation est similaire au triangle. Ici on subdivise le
cube en 8 parties identiques, on supprime le cube en haut à gauche
le plus proche de nous, on réitère pour chaque sous-cube.
triangle.rec
- Triangle de Sierpinski. En 2D, c'est de carré dont il s'agit. On
reconnait une des faces de l'objet 3D plus haut.
|
