Programmation Fonctionnelle, TP

Version & licenses
Creative Commons License

TP : Dessiner des spirales avec des rectangles homothètes

Guyslain Naves
Image without legend

Le but de ce TP est de tracer une jolie spirale construite en utilisant un systême de rectangles que l'on subdivise plusieurs fois d'affilée. Pour en savoir plus sur la création de cette spirale, toute l'histoire est dans cet article.

Nous partons d'un seul rectangle que nous subdivisions une fois :

Image without legend

Deux fois :

Image without legend

Trois fois :

Image without legend

Puis on trouve une joli spirale en ajoutant deux arcs de cercles dans chaque carré évidé de la construction.

Image without legend

Trouver les proportions du rectangle

Tous les rectangles utilisés sont de mêmes proportions : leur ratio longueur divisée par hauteur est égal à une constante $\alpha$. On commence par calculer $\alpha$. Un peu de géométrie et d'algèbre permette d'obtenir que $\alpha$ est racine du polynôme $x^3 - x - 1 = 0$. De plus, $\alpha$ vaut entre $1$ et $2$.

Écrire une fonction procédant par dichotomie pour trouver une racine d'un polynôme quelconque, à partir de deux valeurs dont les images sont de signes opposés.

Utiliser cette fonction pour déterminer $\alpha$.

En profiter pour aussi définir $\pi$ :

  1. let pi = acos (-1.)

Les vecteurs

Nous allons faire un peu de manipulation géométrique. Ce sera bien plus simple avec un petit module de calcul vectoriel.

Implémenter une module avec la signature suivante :

  1. module Vector : sig
  2. type t
  3. val create : float -> float -> t
  4. val zero : t
  5. val x : t -> float (* first projection *)
  6. val y : t -> float (* second projection *)
  7. val (+:) : t -> t -> t
  8. val (-:) : t -> t -> t
  9. val ( *: ) : float -> t -> t (* multiply both coordinates by a scalar *)
  10. val rotate : angle:float -> t -> t (* in degree *)
  11. val angle : t -> int (* in degree *)
  12. end

L'arbre des subdivisions

Le type des rectangles

Proposer un type pour nos rectangles. Ceux-ci peuvent être placé n'importe où et dans n'importe quelle direction sur le plan. Il est conseillé d'utiliser un vecteur pour coder l'angle du rectangle par rapport à l'horizontal, par exemple avec un vecteur normalisé de même direction que le grand axe du rectangle.

Comme nos rectangles sont tous de même proportion, on ne stockera par contre que leur longueur. On utilisera du coup le même type pour coder les carrés.

L'arbre des subdivisions

Le motif formé par subdivisions successives est stocké comme un arbre, dont les feuilles sont les carrés et les rectangles partitionnant le rectangle initial. Les noeuds internes correspondent à des rectangles ayant été subdivisés en plusieurs autres arbres.

Proposer un type pattern pour les arbres de subdivisions.

L'arbre initial

Nous commençons avec un rectangle de largeur $\alpha$ et de hauteur $1$. Donner l'arbre correspondant.

Ajouter un niveau de subdivision

L'arbre est successivement raffiné en remplaçant toutes les feuilles rectangulaires par un arbre de hauteur 1 avec deux rectangles et un carré, selon le motif du dessin suivant.

Image without legend

Écrire un algorithme qui prend une fonction des rectangles vers les arbres, et remplace dans l'arbre chaque feuille rectangulaire par son image par cette fonction.

Subdivision élémentaire d'un rectangle

Écrire maintenant la fonction qui a un rectangle, construit l'arbre de hauteur 1 correspondant, en partitionnant ce rectangle en 2 rectangles et un carré.

Répéter

Pour obtenir un arbre de hauteur $n$, il suffit de répéter $n$ fois l'ajout d'un niveau depuis l'arbre initial comprenant un seul rectangle.

Ajouter donc la fonction repeat et écrire une fonction depth : int -> pattern créant la subdivision de hauteur donnée.

Afficher la spirale

Pour afficher la spirale, il faut dessiner deux arcs d'un quart de cercle dans chacun des carrés.

Faire une action pour chaque feuille

Écrire une fonction qui prend :

  • une fonction ~on_rectangle des rectangles vers unit,
  • une fonction ~on_square des rectangles vers unit,
  • un arbre,

et applique à chaque feuille l'une de ces fonctions, selon la nature de la feuille. Cette fonction ne renvoie rien.

Charger la librairie graphique

La méthode pour charger la librairie graphique est toujours la même :

  1. #load "graphics.cma";;

  2. let _ =
  3. Graphics.open_graph "";
  4. Graphics.resize_window (int_of_float (alpha *. 400.)) 400

  5. let int_of_coord x = int_of_float (400. *. x)

Avec ce code la fenêtre est de la taille du plus grand rectangle. La fonction int_of_coord permet de transformer les coordonnées de nos rectangles en coordonnées utilisées par la librairie graphique.

Utiliser int_of_coord pour écrire une fonction pixel_of_vector qui retourne pour un vecteur les coordonnées graphiques correspondantes, sous la forme d'un couple d'entiers.

Dessiner un arc de cercle

Voici le code permettant de dessiner un quart de cercle.

  1. let draw_quarter_circle center radius middle_vec =
  2. let (xcenter,ycenter) = pixel_of_vector center in
  3. let radius = int_of_coord radius in
  4. let start_angle = Vector.angle middle_vec - 45 in
  5. Graphics.draw_arc xcenter ycenter radius radius (start_angle) (start_angle+90)

Quelle est la signification de chaque argument ?

Dessiner un carré

Écrire une fonction qui, pour un carré, dessine les deux arcs de cercles désirés sur la fenêtre graphique.

Tracer la spirale

Assembler le tout pour tracer la spirale.

À vous de jouer

Modifier le code de draw_quarter_circle afin que la largeur du trait soit proportionnelle à la longueur du rayon.

Image without legend

Modifier votre code pour tracer d'autres spirales.