L-Systems

stephane sikora

stephane sikora

— 3 min read
L-Systems

Le principe des L-Systems est relativement simple, il s’agit essentiellement d’un système de réécriture de chaînes de symboles. Dit ainsi, cela parait abstrait, mais nous allons rendre les choses plus concrètes, en donnant une représentation graphique à ces chaines de symboles. Supposons que l’on dispose d’une ‘tortue graphique’, que l’on peut piloter a l’aide de commandes représentées par des symboles:

  • Le symbole ‘L’ pour tracer une ligne d’une longueur prédéfinie

  • Les symboles + et -, qui permettent de changer l’orientation de la tortue (et donc de toute nouvelle ligne tracée) selon un angle prédéfini

Sur cette image, observons la première figure en partant haut: c’est une ligne horizontale, ce qui correspond à l’interprétation de la commande ‘L’. De même, la seconde figure est obtenue par la séquence L+L–L+L :

Courbe de Von Koch générée par un L-System

Voyons comment construire les figures sur les lignes suivantes: L’approche des L Systems consiste a définir une règle de réécriture pour remplacer des symboles d’une chaîne initiale (l’axiome), par de nouvelles chaines , qui remplace par exemple ici le symbole L par la chaîne L+L–L+L, ce que l’on note:

  • Axiome: L
  • Regle: L -> L+L–L+L

Partant de l’axiome L, en appliquant successivement la règle définie ici, on obtient les chaines suivantes.

  1. L
  2. L+L–L+L
  3. L+L–L+L+L+L–L+L–L+L–L+L+L+L–L+L
  4. L+L–L+L+L+L–L+L–L+L–L+L+L+L–L+L+L+L–L+L+L+L–L+L–L+L–L+L+L+L–L+L–L+L–L+L+L+L–L+L–L+L–L+L+L+L–L+L+L+L–L+L+L+L–L+L–L+L–L+L+L+L–L+L
  5. ..

C’est ainsi que l’on obtient toutes les figures de l’image précédente.  La même règle, en partant d’un axiome initial différent, et en fixant l’angle de rotation:

En complétant la liste de symbole pour permettre de mémoriser puis restaurer l’état de la tortue (à l’aide d’une pile), il est possible de produire des structures arborescentes, comme dans la séquence suivante:

Bien entendu, il est possible d’utiliser d’avantage de symboles, et donner de nouvelles capacités à la tortue graphique, afin d’ajouter de la complexité aux formes obtenues.

Une application WebGL  permet de jouer avec les formules des L-Systems.

            

Read more