Remplissage géométrique
Dans ce TP, on se limitera à des polygones simples, définis par une suite de sommets (ordonnés dans le sens trigonométrique) dont les coordonnées sont dans la partition du plan euclicien (window).
On utilisera le polygone de test dont les coordonnées sont : (59,52), (41,45), (40,70), (29,64), (22,70), (10,62), (17,53), (15,41), (6,48), (2,28), (13,14), (24,21), (40,1), (33,32), (50,27).
Exercice 1. Implanter une fonction de visualisation dans l'espace écran de polygones à N cotés définis dans l'espace euclidien.
La structure de données initiale d'un polygone doit comporter au minimum : le nombre de sommets, la liste des coordonnées des sommets et les couleurs de contour et de fond du polygone. Par convention, le premier sommet de la liste jouera le rôle d'origine locale.
Exercice 2. A partir de la définition d'un polygone donnée à l'exercice 1, construire la table des arêtes (TA), définie comme une liste de listes, et afficher une représentation de cette dernière dans un terminal.
Rappel : lors du parcours du polygone, il faut déterminer pour chaque sommet si l'on est en présence d'un sommet "haut" ou "bas" vis-à-vis du segment courant auquel il appartient.
Exercice 3. Après avoir établi la structure de données d'une table des arêtes active (TAA), écrire la fonction de mise à jour de la TAA en fonction des cas rencontrés par la ligne de balayage (sommet bas, sommet haut, point d'intersection).
Le calcul des points d'intersection de la demi-droite correspondant à la ligne de balayage et chaque arête du polygone peut reposer sur l'algorithme de Bresenham.
Une autre solution (non incrémentale) pour déterminer les intersections entre la ligne de balayage et les arêtes du polygone est d'utiliser la représentation de l'équation cartésienne d'une droite par un vecteur à 3 composantes. Le point d'intersection (s'il existe) se calcule par le produit vectoriel de leur vecteur respectif. On est certain d'avoir trouvé la solution tant que l'on n'a pas atteint le sommet haut d'une arête.
Exercice 4. Implanter l'algorithme de remplissage géométrique d'un polygone dans l'espace objet par ligne de balayage.
Remarque : lors du remplissage à proprement parler, on prendra garde à ne pas modifier la couleur du contour du polygone. Pour se faire, en fonction de la parité du nombre d'intersections, on commencera le remplissage à droite du contour et on le terminera à gauche du contour.