Série 9 – Fractales IFS, jokers

Introduction

Le but de cette série est double : premièrement, de vous faire utiliser la programmation par flots en dessinant des fractales IFS, et deuxièmement de vous faire utiliser les jokers. Elle est donc séparée en deux parties, que vous pouvez faire dans l'ordre qui vous convient le mieux.

Partie 1 : fractales IFS

Un système de fonctions itérées (iterated function system ou IFS) est un ensemble de fonctions \(\{F_1, F_2, \ldots, F_n\}\), chacune d'entre elles faisant correspondre un point du plan à un autre point du plan. A partir d'un tel ensemble de fonctions, on peut construire l'ensemble \(S\) des points du plan satisfaisant l'équation :

\[S = \bigcup_{i=1}^n F_i(S)\]

Ensuite, il est possible d'obtenir une image à partir de cet ensemble, simplement en coloriant d'une certaine couleur (p.ex. en noir) tous les points qui en font partie. Ces images sont nommées fractales IFS.

Différentes techniques existent pour déterminer (une approximation de) l'ensemble \(S\). Celle utilisée ici s'appelle algorithme du chaos et consiste à calculer la suite suivante de points \(p_j\) pour \(j\) allant de 0 à une valeur maximale \(m\) donnée :

\begin{align*} p_0 &= (0,0),\\ p_1 &= F_{i_1}(p_0),\\ p_2 &= F_{i_2}(p_1),\\ &\vdots\\ p_m &= F_{i_m}(p_{m - 1}) \end{align*}

où \(i_1, \ldots, i_m\) sont des entiers aléatoires compris entre 1 et \(n\). Une fois cette suite de points calculée, l'ensemble \(S\) est simplement défini comme celui des éléments de cette suite amputée de ses 20 premiers éléments :

\[ S = \{\,p_{20}, p_{21}, \ldots, p_m\,\} \]

Par exemple, l'IFS composé des trois fonctions \(F_1, F_2, F_3\) suivantes :

\begin{align*} F_1(x, y) &= \left(\tfrac{1}{2} x, \tfrac{1}{2}y\right)\\ F_2(x, y) &= \left(\tfrac{1}{2} x + \tfrac{1}{2}, \tfrac{1}{2}y\right)\\ F_3(x, y) &= \left(\tfrac{1}{2} x + \tfrac{1}{4}, \tfrac{1}{2}y + \tfrac{1}{2}\right)\\ \end{align*}

a pour ensemble \(S\) les points qui forment le fameux triangle de Sierpiński, illustré à la figure 1 ci-dessous.

Le but de cette première partie est de mettre en œuvre l'algorithme du chaos ci-dessus au moyen de la programmation par flots, afin de pouvoir dessiner des fractales IFS.

Squelette

Pour vous aider à démarrer, nous vous fournissons un squelette dans une archive Zip, qui contient les classes suivantes :

  • Point, une classe immuable représentant un point du plan,
  • IFS, une classe immuable représentant un système de fonctions itérées,
  • IFSComponent, un composant Swing capable d'afficher les points d'un système de fonctions itérées,
  • Main, la classe principale, qui crée l'interface graphique (une fenêtre contenant un composant IFSComponent).

Les classes susmentionnées sont les seules utiles à l'exercice 1. L'archive contient encore deux classes, destinées à n'être utilisée que dans le cadre de l'exercice 2 :

  • Pair, une paire générique immuable, identique à celle déjà utilisée dans plusieurs autres séries,
  • PCG, un générateur aléatoire simple et immuable.

Exercice 1

A première vue, l'algorithme du chaos s'exprime très bien sous la forme d'un flot, puisqu'il suffit d'appliquer de manière répétée l'une des fonctions du système, choisie aléatoirement, à un point initial. C'est exactement ce que permet la fonction iterate de l'interface Stream. Toutefois, un problème se pose : comment choisir aléatoirement, à chaque itération, la fonction à utiliser ?

Une première solution consiste à utiliser un générateur aléatoire de la bibliothèque Java, c-à-d une instance de la classe Random. Pour des raisons expliquées à l'exercice suivant, cette solution n'est pas très propre, mais elle a l'avantage d'être simple. C'est donc celle que nous vous proposons d'utiliser dans un premier temps.

En vous basant sur cette idée, écrivez le corps de la méthode points de la classe IFS. Elle doit retourner une liste contenant exactement le nombre de points passés en arguments, et ces points doivent être ceux obtenus par l'algorithme du chaos décrit plus haut et mis en œuvre au moyen d'un flot dont les éléments sont collectés dans une liste. Vous pouvez vous aider de la méthode privée apply pour appliquer une des fonctions choisie aléatoirement.

Si votre méthode est correcte, vous devriez voir s'afficher le triangle de Sierpiński de la figure ci-dessous. Notez que même si l'image finale ressemble à celle obtenue dans la série sur les L-systèmes, la manière dont elle est obtenue est radicalement différente.

Vous pouvez essayer de changer le nombre de points calculés (l'attribut pointsCount de IFSComponent) pour voir l'influence que cela a sur le dessin, ou dessiner l'autre fractale IFS définie dans la classe principale, le tapis de Sierpiński.

ifs_sierpinski-triangle.png

Figure 1 : Le triangle de Sierpiński, version IFS

Exercice 2

La solution utilisée dans l'exercice précédent pour choisir aléatoirement la fonction à appliquer n'est pas très propre. En effet, étant donné l'utilisation du générateur aléatoire de type Random, la fonction passée à la méthode iterate de Stream n'est pas une fonction au sens mathématique du terme. Pour mémoire, le résultat d'une fonction mathématique dépend uniquement des arguments qu'on lui fourni. Or l'utilisation du générateur aléatoire par la fonction passée à iterate fait que ce n'est justement pas le cas : son résultat dépend bien de son argument — le point à transformer — mais aussi de l'état du générateur aléatoire, qui ne fait pas partie de ses arguments.

Lorsque le résultat d'une fonction dépend d'autre chose que de ses arguments et n'est donc pas une fonction au sens mathématique, on dit qu'elle a un effet de bord (side effect). Les fonctions à effet de bord sont problématiques pour de nombreuses raisons — entre autres car il est difficile de raisonner à leur sujet — et il est généralement souhaitable de les éviter autant que possible. La programmation dite fonctionnelle consiste d'ailleurs principalement à programmer sans effets de bord, et l'intérêt des classes immuables vient du fait que toutes leurs méthodes sont généralement dénuées d'effets de bord.

Il est possible d'écrire une version de la méthode points de IFS sans effets de bord, c-à-d qui passe une fonction mathématique à la méthode iterate de Stream. Cela impose toutefois l'utilisation d'un autre générateur aléatoire que celui fourni par la classe Random de Java, car celui-ci n'est pas immuable. Si l'on dispose d'un générateur aléatoire immuable, on peut l'utiliser pour construire un flot de paires de valeurs : la première valeur de cette paire est le point, comme ci-dessus, et la deuxième est l'état actuel du générateur aléatoire. La fonction passée à iterate transforme cette paire en une nouvelle paire dont le point est celui de la précédente transformé par une fonction choisie en fonction de l'état actuel du générateur aléatoire, tandis que l'état de son générateur aléatoire est l'état suivant, calculé en fonction de l'actuel. Ce nouveau flot pourrait s'écrire ainsi :

\begin{align*} \langle p_0, s_0\rangle &= \langle (0,0), S\rangle\\ \langle p_1, s_1\rangle &= \langle F_{i(s_0)}, N(s_0)\rangle\\ &\vdots\\ \langle p_m, s_m\rangle &= \langle F_{i(s_{m-1})}, N(s_{m-1})\rangle\\ \end{align*}

où \(\langle\rangle\) dénote une paire, \(S\) est l'état initial du générateur aléatoire et \(N\) est la fonction permettant de calculer le prochain état du générateur à partir de l'actuel.

Bien entendu, étant donné que l'état du générateur aléatoire n'est utile que pour déterminer quelle fonction appliquer, on peut par la suite s'en passer en transformant le flot de paires ci-dessus en un simple flot de points, exactement comme avant.

Ecrivez une seconde version de la méthode points basée sur cette idée, en utilisant la classe Pair pour représenter les paires du flot, et la classe PCG comme générateur aléatoire immuable. Cela fait, vérifiez que vous obtenez bien (quasiment) les mêmes images pour les différentes fractales.

Exercice 3

Ajoutez une troisième fractale IFS au programme, le pentagone de Sierpiński, définie par les fonctions suivantes :

\begin{align*} F_1(x, y) &= \left(0.382\,x, 0.382\,y\right)\\ F_2(x, y) &= \left(0.382\,x + 0.618, 0.382\,y\right)\\ F_3(x, y) &= \left(0.382\,x + 0.809, 0.382\,y + 0.588\right)\\ F_4(x, y) &= \left(0.382\,x + 0.309, 0.382\,y + 0.951\right)\\ F_5(x, y) &= \left(0.382\,x - 0.191, 0.382\,y + 0.588\right)\\ \end{align*}

Le cadre contenant l'ensemble \(S\) a une largeur de 1.8 unités et son coin bas-gauche a les coordonnées (-0.4, -0.1).

Partie 2 : jokers

Comme vu au cours, les jokers (ou wildcards) permettent, entre autres, de généraliser le type des paramètres de certaines méthode génériques. Ainsi, une méthode addAll qui ajoute à la liste à laquelle on l'applique tous les éléments de la liste reçue en argument peut être définie ainsi : 

interface List<E> {
    // ...
    void addAll(List<? extends E> other);
}

Comparée à une version prenant une liste de type List<E> en argument, celle-ci est plus générale puisqu'elle permet, p.ex., l'appel suivant : 

List<Number> l = new LinkedList<>();
List<Integer> li = new LinkedList<>();
li.add(1);
l.addAll(li);

Cet appel serait invalide si addAll prenait un argument de type List<E>. Pour plus de détails, voir le cours.

Exercice

Afin de vous entraîner à utiliser les jokers, nous vous fournissons une archive Zip contenant un fichier Lists.java définissant une classe Lists (notez le s à la fin !) qui offre trois méthodes statiques travaillant sur les listes Java :

  1. addMany, qui ajoute un certain nombre d'occurrences d'un élément à la fin d'une liste,
  2. copy, qui copie le contenu d'une première liste à la fin d'une seconde liste,
  3. max, qui retourne le plus grand élément d'une liste selon un comparateur reçu en argument.

Nous vous fournissons de plus un test JUnit pour cette classe dans le fichier ListsTest.java. Ce test comporte 13 appels aux trois méthodes susmentionnées, numérotés par des commentaires. Dans la version que nous vous fournissons, tous ces appels sont signalés comme erronés par Eclipse.

Examinez chacun de ces 13 appels et déterminez s'il pourrait être valide ou non. Si oui, généralisez le type de la fonction appelée (dans la classe Lists) au moyen de jokers. Si non, mettez l'appel en commentaire et justifiez votre choix. Attention, vous n'avez pas le droit de modifier le code des fonctions de Lists, seulement le type de leurs arguments et variables locales.