L-systèmes

CS-108 — Série 5

Introduction

Le but de cette série est de vous familiariser avec l'utilisation des ensembles et des tables associatives, en les utilisant pour mettre en œuvre les L-systèmes, décrits ci-dessous. Les L-systèmes permettent de générer facilement et élégamment des images dites fractales.

L-Système

Un L-système (ou système de Lindenmayer) est un système de récriture permettant de générer des chaînes de caractères à partir de règles. Un L-système a deux composantes principales :

  1. une chaîne de départ,
  2. au moins une règle de récriture.

Les règles décrivent comment faire évoluer, par récriture, la chaîne de départ pour en obtenir une nouvelle, généralement plus longue. Comme nous le verrons plus loin, ces chaînes peuvent ensuite être interprétées comme des instructions de dessin afin de générer des images.

Pour illustrer cette idée, considérons un premier L-système, composé de la chaîne de départ :

F

et d'une unique règle de récriture :

F → F-F++F-F

Cette règle stipule que le caractère F (à gauche de la flèche) doit être récrit en la chaîne F-F++F-F (à droite de la flèche).

Pour faire évoluer ce L-système, on applique simplement la règle de récriture aux caractères de la chaîne de départ. Ce faisant, on obtient pour notre exemple la chaîne suivante :

F-F++F-F

Bien entendu, il est possible de faire évoluer cette chaîne une seconde fois, afin d'obtenir la deuxième évolution du L-système original. Notez que lorsqu'un caractère n'apparaît pas à gauche d'une règle, comme - ou + ici, il est simplement laissé tel quel. Dès lors, seul le caractère F est remplacé dans la chaîne ci-dessus, mais comme il y apparaît quatre fois, la règle est appliquée quatre fois. On obtient alors :

F-F++F-F-F-F++F-F++F-F++F-F-F-F++F-F

Et ainsi de suite, autant de fois que l'on désire.

Générer de telles chaînes n'est pas très intéressant en soi. Toutefois, en les interprétant comme des instructions de dessin, on obtient des images qui le sont beaucoup plus.

Interprétation

Une chaîne de caractères produite par un L-système peut être interprétée comme une séquence d'instructions de dessin. Par exemple, on peut attribuer la signification suivante aux caractères F, - et + apparaissant dans les chaînes ci-dessus :

  • le caractère F signifie : dessiner un trait dans la direction courante,
  • le caractère - signifie : tourner à gauche de 60°,
  • le caractère + signifie : tourner à droite de 60°.

En admettant que la direction initiale soit de 0°, donc vers l'est de l'écran, la chaîne F-F++F-F s'interprète ainsi :

  1. dessiner un trait (F),
  2. tourner de 60° vers la gauche (-), c-à-d en direction du nord-est,
  3. dessiner un trait (F),
  4. tourner de 120° vers la droite (++), c-à-d en direction du sud-est,
  5. dessiner un trait (F),
  6. tourner de 60° vers la gauche (-), c-à-d en direction de l'est,
  7. dessiner un trait (F).

En suivant ces instructions, on obtient l'image suivante :

koch1;8.png
Figure 1 : La courbe de Koch après 1 évolution

En faisant évoluer ce L-système trois fois encore, on obtient une chaîne qui, interprétée, produit l'image ci-dessous, une fractale connue sous le nom de courbe de Koch :

koch4;8.png
Figure 2 : La courbe de Koch après 4 évolutions

Squelette

Pour faciliter votre travail, nous vous fournissons un squelette de projet dans une archive Zip. Après avoir extrait son contenu, créez un projet à partir du répertoire LSYS qu'elle contient.

L'archive contient :

  • un squelette de la classe LSystem, qui représente un L-système et qui est à compléter dans le cadre des exercices 1 et 2,
  • les classes LSystemTracer et Turtle, qui permettent d'interpréter un L-système pour produire une image,
  • la classe Main, qui définit un L-système, le transforme en image, et affiche celle-ci à l'écran.

Vous n'avez pas besoin de comprendre le fonctionnement des classes LSystemTracer et Turtle, ni de la classe Main, à l'exception de sa méthode koch et de la première ligne de sa méthode main, qui définit le L-système à dessiner.

Exercice 1 : L-système non évolutif

Pour commencer, complétez partiellement la classe LSystem en définissant :

  • son constructeur,
  • les méthodes d'accès string, rules, lineChars et turningAngle.

Notez qu'il s'agit d'une classe immuable, il faut dès lors penser à copier au besoin les entités non immuables passées au constructeur avant de les stocker dans des attributs.

L'attribut string contient la chaîne de départ du L-système.

L'attribut rules contient les règles de récriture, représentées par une table associant à chaque caractère à récrire la chaîne en laquelle il doit être récrit. Logiquement, cette table a le type Map<Character, String>. Au besoin, vous pouvez examiner la méthode koch de la classe Main pour comprendre comment la règle de récriture donnée plus haut est exprimée au moyen d'une table associative.

L'attribut lineChars spécifie l'ensemble des caractères provoquant le dessin d'une ligne droite. Dans le cas de la courbe de Koch, par exemple, le seul caractère de dessin était le caractère F. Nous verrons plus loin que certains L-systèmes ont plus d'un caractère de dessin. Logiquement, cet attribut est un ensemble de caractères, de type Set<Character>. Toutefois, pour faciliter l'utilisation de la classe LSystem, son constructeur accepte une chaîne en argument, qu'il convertit en un ensemble contenant tous ses caractères. Par exemple, il interprète la chaîne ABC comme l'ensemble des trois caractères A, B et C.

Finalement, turningAngle est l'angle de la rotation provoquée par les caractères - et +. Il est spécifié en degrés, sous la forme d'un entier pour éviter les erreurs d'arrondis que provoquerait l'utilisation du type double.

Une fois le constructeur et les méthodes ci-dessus définis, vous devriez être capable d'obtenir l'image de la figure 1 plus haut en définissant la variable lSystem de la méthode main ainsi :

LSystem lSystem = new LSystem("F-F++F-F", Map.of(), "F", 60);

Bien entendu, ce L-système n'est pas très intéressant car il ne possède aucune règle, mais il permet de vérifier que tout est en place pour l'exercice suivant.

Exercice 2 : L-système évolutif

Terminez la classe LSystem en écrivant tout d'abord la méthode evolve sans arguments, qui retourne la version évoluée une fois du L-système auquel on l'applique. Ce nouveau L-système a les mêmes attributs que celui auquel on l'applique, à l'exception de la chaîne de départ, qui est le résultat d'une étape d'évolution — donc d'une et une seule application des règles — de la chaîne de départ du L-système original.

Une fois la première variante de la méthode evolve terminée, écrivez la seconde, qui applique la première un certain nombre de fois et retourne le L-système final.

Vérifiez que vos méthodes d'évolution fonctionnent en définissant la variable lSystem de la méthode main ainsi :

LSystem lSystem = koch().evolve(4);

et en comparant l'image obtenue à celle de la figure 2.

Exercice 3 : flocon de Koch

La méthode koch qui vous est fournie permet de générer la courbe de Koch illustrée plus haut. En modifiant uniquement la chaîne de départ du L-système, arrivez-vous à dessiner le flocon de Koch, montré ci-dessous après 4 itérations ?

koch-flake4;8.png
Figure 3 : Le flocon de Koch après 4 évolutions

Exercice 4 : L-systèmes divers

Utilisez votre classe LSystem pour modéliser et dessiner les L-systèmes décrits ci-dessous. Contrairement à celui de la courbe de Koch, ces L-systèmes ont souvent plus d'une règle, et parfois une chaîne de départ composée de plus d'un caractère.

Attention : certains de ces systèmes produisent très vite des chaînes énormes, commencez donc toujours par un petit nombre d'évolutions (4 ou 5).

Triangle de Sierpinski

Le triangle de Sierpinski a pour chaîne de départ A, pour angle de rotation 60°, pour caractères de dessin A et B et pour règles :

A → +B-A-B+
B → -A+B+A-

Courbe de Hilbert

La courbe de Hilbert a pour chaîne de départ A, pour angle de rotation 90°, pour caractère de dessin F et pour règles :

A → -BF+AFA+FB-
B → +AF-BFB-FA+

Arbre

L'arbre a pour chaîne de départ ----F, pour angle de rotation 25°, pour caractère de dessin F et pour règle :

F → FF+[+F-F-F]-[-F+F+F]

Ce L-système est le premier à utiliser les caractères [ et ], qui permettent respectivement de sauvegarder la position et la direction actuelles de dessin, et de les restaurer plus tard.

Plante

La plante a pour chaîne de départ ---X, pour angle de rotation 30°, pour caractère de dessin F et pour règles :

X → F-[[X]+X]+F[+FX]-X
F → FF

Courbe du dragon

La courbe du dragon a pour chaîne de départ FX, pour angle de rotation 90°, pour caractère de dessin F et pour règles :

X → X+YF+
Y → -FX-Y