Série 3 – L-systèmes : corrigé

Introduction

Le code du corrigé est fourni sous la forme d'une archive Zip, et des explications concernant les principales difficultés des exercices sont données ci-dessous.

Exercice 1 : L-système non évolutif

Pour la première partie, seul le constructeur mérite d'être discuté, les méthodes d'accès étant triviales. La solution évidente pour définir ce constructeur serait de faire en sorte qu'il :

copie la table associative des règles (pour garantir l'immuabilité de la classe) avant de la stocker dans l'attribut correspondant,
convertisse la chaîne représentant l'ensemble des caractères de dessin de ligne en un ensemble avant de le stocker dans l'attribut correspondant,
stocke les autres paramètres dans les attributs correspondants.

Toutefois, cette solution aurait deux inconvénients lorsque le constructeur est appelé par la méthode d'évolution (evolve) définie plus bas, à savoir :

la table associative des règles devrait être copiée à chaque évolution, ce qui n'est pas nécessaire dans le cas présent, la table passée au constructeur par la méthode evolve étant immuable,
l'ensemble des caractères de dessin devrait être à nouveau converti en chaîne avant de pouvoir être passé au constructeur, qui s'empresserait de le reconvertir en ensemble.

Dès lors, il paraît plus judicieux de définir deux constructeurs séparés :

le premier, qui est le constructeur principal, est privé, ne copie pas la table des règles et prend l'ensemble des caractères de dessin sous forme d'une ensemble et pas d'une chaîne, ensemble qu'il ne copie pas non plus,
le second, un constructeur secondaire, est publique et se contente de copier la table des règles et de convertir la chaîne des caractères de dessin en ensemble avant d'appeler le premier.

Avec cette organisation, la méthode evolve peut appeler le premier constructeur, en lui garantissant que la table des règles et le tableau des caractères de dessin sont immuables. Dans ce cas particulier, le gain en performances et utilisation mémoire est négligeable, mais cette technique est utilisable dans d'autres contextes et mérite d'être connue.

Les deux constructeurs sont donc définis ainsi :

private LSystem(String string,
                Map<Character, String> rules,
                Set<Character> lineChars,
                int turningAngle) {
  this.string = string;
  this.rules = rules;
  this.lineChars = lineChars;
  this.turningAngle = turningAngle;
}

public LSystem(String string,
               Map<Character, String> rules,
               String lineChars,
               int turningAngle) {
  this(string,
       Collections.unmodifiableMap(new HashMap<>(rules)),
       setFromString(lineChars),
       turningAngle);
}

le second s'aidant de la méthode de conversion d'une chaîne en ensemble de caractères ci-dessous :

private static Set<Character> setFromString(String s) {
  Set<Character> set = new HashSet<>();
  for (int i = 0; i < s.length(); ++i)
    set.add(s.charAt(i));
  return Collections.unmodifiableSet(set);
}

Exercice 2 : L-système évolutif

Pour faire évoluer un L-système, il suffit de parcourir les caractères de sa chaîne de départ, et de remplacer chacun d'eux par la chaîne leur correspondant dans les règles. Etant donné que les caractères pour lesquels aucune règle n'existe doivent être gardés tels quels, la méthode getOrDefault de l'interface Map peut être utilisée ici à bon escient.

public LSystem evolve() {
  StringBuilder b = new StringBuilder();
  for (int i = 0; i < string.length(); ++i) {
    char c = string.charAt(i);
    b.append(rules.getOrDefault(c, String.valueOf(c)));
  }
  String s = b.toString();
  return new LSystem(s, rules, lineChars, turningAngle);
}

Une fois la première méthode d'évolution définie, il n'est pas difficile de définir la seconde, qui consiste simplement à appliquer la première le nombre de fois donné.

public LSystem evolve(int steps) {
  if (! (steps >= 0))
    throw new IllegalArgumentException();

  LSystem l = this;
  for (int i = 0; i < steps; ++i)
    l = l.evolve();
  return l;
}

Exercice 3 : flocon de Koch

En examinant le flocon de Koch, on se rend compte qu'il est composé de trois courbes de Koch organisées en triangle. Pour l'obtenir, il suffit donc d'utiliser la chaîne de départ suivante :

F++F++F

A noter que le sens de rotation est important (c-à-d qu'il n'est pas possible d'utiliser systématiquement - à la place de + dans cette chaîne) car la pointe de la courbe de Koch doit se trouver à l'extérieur du triangle formant le flocon.

Exercice 4 : L-systèmes divers

La définition des L-systèmes de cet exercice est très simple, son principal intérêt étant les images produites par ces systèmes.

Triange de Sierpinski

private static LSystem sierpinski() {
  Map<Character, String> rules = new HashMap<>();
  rules.put('A', "+B-A-B+");
  rules.put('B', "-A+B+A-");
  return new LSystem("A", rules, "AB", 60);
}

Courbe de Hilbert

private static LSystem hilbert() {
  Map<Character, String> rules = new HashMap<>();
  rules.put('A', "-BF+AFA+FB-");
  rules.put('B', "+AF-BFB-FA+");
  return new LSystem("A", rules, "F", 90);
}

Arbre

private static LSystem tree() {
  Map<Character, String> rules = new HashMap<>();
  rules.put('F', "FF+[+F-F-F]-[-F+F+F]");
  return new LSystem("----F", rules, "F", 25);
}

Plante

private static LSystem plant() {
  Map<Character, String> rules = new HashMap<>();
  rules.put('X', "F-[[X]+X]+F[+FX]-X");
  rules.put('F', "FF");
  return new LSystem("---X", rules, "F", 30);
}

Série 3 – L-systèmes : corrigé