Introduction

La récursivité et les fractales sont intimement liées. Pour illustrer ceci, nous allons dessiner une figure fractale que l’on définira de façon récursive. Cette figure sera en fait un ensemble de Julia que l’on peut obtenir en pliant une feuille de papier.

Le principe est de prendre une feuille de papier, la plier en deux en rabattant la partie gauche sur la partie droite et de recommencer plusieurs fois. On déplie ensuite la feuille obtenue en essayant de conserver à chaque pli un angle de 90°. Par exemple, après 3 plis, on obtient une figure ressemblant à

Dragon

Si l’on était capable de répéter cette opération plus de 10 fois (l’épaisseur du papier rend le pliage difficile au delà de 6 plis consécutifs), on pourrait obtenir une figure comme

Grand dragon

Primitives graphiques

Pour dessiner avec ocaml, nous allons utiliser la bibliothèque graphique graphics.cma. L’inclusion de cette bibliothèque se fait à l’aide de la ligne

#load "graphics.cma";;

Sont ensuite disponibles de nombreuses fonctions graphiques définies dans la documentation de cette bibliothèque. Nous utiliserons les suivantes :

fonction rôle
open_graph : string -> unit Créer une fenêtre graphique
moveto : int -> int -> unit Déplacer le point courant
lineto : int -> int -> unit Tracer une ligne jusqu’à un point
current_point : unit -> int*int Coordonnées du point courant
set_color : color -> unit Changer la couleur des prochains lignes
clear_graph : unit -> unit Effacer le dessin

Par exemple, on utilisera le code suivant :

#load "graphics.cma";;
Graphics.open_graph ":0 800x800";;
Graphics.moveto 200 600;;

let direction = ref 0;;
let avance n = let x, y = Graphics.current_point () in
  match !direction with
   | 0 -> Graphics.lineto x (y+n)
   | 1 -> Graphics.lineto (x+n) y
   | 2 -> Graphics.lineto x (y-n)
   | _ -> Graphics.lineto (x-n) y
;;
let droite () = direction := (!direction+1) mod 4;;
let gauche () = direction := (!direction+3) mod 4;;

Nous avons ici ouvert une fenêtre, déplacé le curseur et défini des fonctions droite, gauche et avance qui permettent de donner des ordres de dessin. Ainsi, le code suivant va tracer un carré rouge :

Graphics.set_color Graphics.red;;
avance 100;;
droite ();;
avance 100; droite ();;
avance 100; droite ();;
avance 100; droite ();;

Effaçons ce carré :

Graphics.clear_graph ();;

Pliage

Nous allons représenter la suite des plis par une liste de 0 et de 1. Si l’on déplie entièrement le papier et qu’on le pose à plat, les plis creux seront des 0, les plis en relief seront des 1. Les premières suites seront donc les suivantes :

[0]
[1; 0; 0]
[1; 1; 0; 0; 1; 0; 0]
  • Écrire une fonction pli qui prend une liste représentant un certain pliage et renvoie la liste représentant la feuille après un pliage de plus.
  • Écrire une fonction dragon qui pour un entier n donne la liste pour n pliages.
  • Écrire une fonction dessine qui prend un entier d et une liste et à l’aide des fonctions avance, droite et gauche dessine le profil correspondant à l’aide de segments de longueurs d. Par exemple dessine 100 [1; 1; 1; 1] devra dessiner un carré de côté 100 comme ci-dessus.
  • Dessiner le dragon numéro 13 avec des segments de longueur 5.

Conclusion

Dragons imbriqués

Pour aller plus loin: