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 :
Deux fois :
Trois fois :
Puis on trouve une joli spirale en ajoutant deux arcs de cercles dans chaque carré évidé de la construction.
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$ :
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 :
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.
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.
Nous commençons avec un rectangle de largeur $\alpha$ et de hauteur $1$. Donner l'arbre correspondant.
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.
É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.
É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é.
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.
Pour afficher la spirale, il faut dessiner deux arcs d'un quart de cercle dans chacun des carrés.
Écrire une fonction qui prend :
et applique à chaque feuille l'une de ces fonctions, selon la nature de la feuille. Cette fonction ne renvoie rien.
La méthode pour charger la librairie graphique est toujours la même :
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.
Voici le code permettant de dessiner un quart de cercle.
Quelle est la signification de chaque argument ?
Écrire une fonction qui, pour un carré, dessine les deux arcs de cercles désirés sur la fenêtre graphique.
Assembler le tout pour tracer la spirale.
Modifier le code de draw_quarter_circle afin que la largeur du trait soit proportionnelle à la longueur du rayon.
Modifier votre code pour tracer d'autres spirales.
