Flame Maker – Etape 2 – Dessinateur IFS

La classe IFS du paquetage ch.epfl.flamemaker.ifs modélise les fractales IFS. Cette classe est non modifiable et équipée d'un seul champ privé et non modifiable de type List<AffineTransformation> (où List est l'interface de l'API Java, qui se trouve dans le paquetage java.util) contenant les transformations affines caractérisant la fractale.

La classe IFS est équipée du seul constructeur suivant :

• IFS(List<AffineTransformation> transformations), qui construit une fractale caractérisée par les transformations données. La liste de transformations doit absolument être copiée par le constructeur pour garantir l'immuabilité de la fractale.

Cette classe possède de plus une seule méthode publique :

• IFSAccumulator compute(Rectangle frame, int width, int height, int density), qui calcule, au moyen de l'algorithme du chaos, la fractale dans la région du plan délimitée par le cadre frame et stocke le résultat dans un nouvel accumulateur de largeur width et hauteur height, qui est retourné. Le nombre d'itérations à effectuer est calculé en fonction du paramètre density, comme expliqué plus bas.

Le fonctionnement de cette méthode est détaillé dans les sections qui suivent.

En pseudo-code, l'algorithme du chaos peut s'exprimer ainsi :

p = (0, 0)
répéter 20 fois
  i = entier aléatoire uniformément distribué entre 0 et n-1
  p = F[i](p)

S = {}
répéter m fois
  i = entier aléatoire uniformément distribué entre 0 et n-1
  p = F[i](p)
  ajouter p à S

La programmation de cet algorithme en Java ne pose pas de problème particulier. Trois questions se posent toutefois :

1. Comment choisir un entier aléatoire uniformément distribué dans un intervalle donné ?
2. Comment représenter l'ensemble S ?
3. Quelle valeur faut-il choisir pour m, le nombre d'itérations à effectuer ?

Les sections ci-dessous répondent à ces questions.

La solution la plus simple pour produire des entiers (pseudo-)aléatoires consiste à utiliser la classe java.util.Random de l'API Java. Une fois une instance de la classe Random créée, il suffit d'appeler sa méthode nextInt pour obtenir un nouvel entier uniformément distribué entre 0 et la valeur passée en argument, cette dernière n'étant pas incluse.

Une manière de représenter l'ensemble \(S\) serait d'utiliser une des classes implémentant l'interface Set de l'API Java, qui modélise des ensembles mathématiques. Toutefois, représenter l'ensemble \(S\) n'est pas vraiment nécessaire ici, puisque le but final est de produire une image. Ainsi, au lieu de calculer l'ensemble \(S\), on peut calculer directement l'image finale, ou quelque chose qui s'en approche.

Lors de l'exécution de l'algorithme du chaos, on stocke donc uniquement une information booléenne pour chaque pixel de l'image finale, qui dit si la zone du plan correspondant à ce pixel contient au moins un point de \(S\). Cette information est stockée dans un objet nommé accumulateur, qui est une grille de cases, chacune des cases correspondant à un pixel de l'image finale. Les cases contiennent pour l'instant une simple valeur booléenne, qui est vraie si et seulement si au moins un point de \(S\) se trouve dans la zone du plan correspondant à la case. Lors des étapes suivantes, des informations plus détaillées seront stockées dans les cases, afin de pouvoir produire des images en niveaux de gris d'abord, puis en couleur ensuite.

L'image ci-dessous montre une partie du plan, un ensemble de points du plan et un accumulateur de 6×5 cases. Le cadre de l'accumulateur, c-à-d le rectangle du plan qu'il couvre, est représenté en gras. Les cases grisées sont celles qui contiennent au moins un point de l'ensemble \(S\), et dont le booléen est donc vrai. Les cases sont identifiées par leurs coordonnées (entières), et la case de coordonnées (0,0) se trouve en bas à gauche, conformément aux conventions mathématiques. Six points se trouvent en dehors du cadre de l'accumulateur et n'ont aucun effet sur celui-ci.¹

En Java, l'accumulateur est modélisé par la classe non modifiable IFSAccumulator. Cette classe n'est pas grand-chose d'autre qu'un tableau bi-dimensionnel de booléens encapsulé de façon à être non modifiable. Elle possède donc un unique champ privé et non modifiable de type boolean[][] contenant les éléments de l'accumulateur. Elle possède le constructeur suivant :

• IFSAccumulator(boolean[][] isHit), qui construit un accumulateur avec le tableau bi-dimensionnel donné. Ce tableau doit absolument être copié en profondeur par le constructeur afin de garantir l'immuabilité de l'accumulateur.

L'accumulateur est de plus équipé des méthodes suivantes :

• int width(), qui retourne la largeur (en nombre de cases) de l'accumulateur.
• int height(), qui retourne la hauteur (en nombre de cases) de l'accumulateur.
• boolean isHit(int x, int y), qui retourne vrai si et seulement si la case de l'accumulateur aux coordonnées données contient au moins un point de \(S\) (on dit alors que la case a été touchée, d'où le nom de la méthode). Lève l'exception IndexOutOfBoundsException si l'une des deux coordonnées est invalide.

La classe IFSAccumulator étant non modifiable, il est nécessaire d'avoir un moyen de créer progressivement son contenu lors de l'exécution de l'algorithme du chaos. Pour cela, une classe séparée, nommée IFSAccumulatorBuilder, existe². Son but est de construire progressivement un IFSAccumulator. Cette classe est équipée d'un seul constructeur :

• IFSAccumulatorBuilder(Rectangle frame, int width, int height), qui produit un bâtisseur d'accumulateur pour la région du plan délimitée par le cadre frame, de largeur width et hauteur height (en nombre de cases). Lève l'exception IllegalArgumentException si la largeur ou la hauteur n'est pas strictement positive (c-à-d supérieure à zéro).

Cette classe possède également les méthodes suivantes :

• void hit(Point p), qui met à vrai la case de l'accumulateur correspondant au point du plan donné. Ne fait rien si le point est en dehors de la région du plan couverte par l'accumulateur, c-à-d le cadre frame passé au constructeur de cette classe.
• IFSAccumulator build(), qui retourne un accumulateur contenant les points collectés jusqu'à présent.

Conseils de programmation :

1. Dans la méthode hit, vous aurez probablement besoin d'obtenir la partie entière par défaut d'un nombre, ce qui peut se faire au moyen de la méthode statique floor de la classe Math du paquetage java.lang.
2. Pour obtenir les coordonnées de la case de l'accumulateur contenant un point, il faut passer des coordonnées du plan aux coordonnées de l'accumulateur. Une manière de le faire est de calculer, lors de la construction du bâtisseur d'accumulateur, la transformation (affine) permettant d'effectuer ce changement de coordonnées, puis d'utiliser cette transformation dans la méthode hit pour déterminer la case de l'accumulateur affectée par le point reçu. Voilà une occasion d'utiliser votre classe AffineTransformation dans un autre contexte que la fractale IFS elle-même.

Il semble logique que le nombre d'itérations à effectuer dépende du nombre de cases de l'accumulateur : plus l'accumulateur est grand, et plus le nombre d'itérations de l'algorithme du chaos doit l'être également.

La méthode compute prend donc un paramètre nommé densité à partir duquel le nombre d'itérations à effectuer \(m\) est calculé, selon la formule suivante : \[ m = d\times w\times h \] où \(d\) est la densité, \(w\) la largeur de l'accumulateur (en nombre de cases) et \(h\) sa hauteur (en nombre de cases).