Infographie 2D - TP 4

ven. 16 septembre 2016

Géométrie algorithmique

Dichotomie et polygones

Exercice 1. Implanter une fonction de construction de polygones à N cotés, puis une fonction de visualisation. La structure de données d'un polygone doit comporter au minimum : le nombre de sommets, la liste des coordonnées des sommets (ordonnés dans le sens trigonométrique) et la couleur du contour du polygone. Par convention, le premier sommet de la liste jouera le rôle d'origine locale.

Exercice 2. Offrir la possibilité de définir et d'afficher plusieurs polygones à l'écran, puis implanter une fonction de sélection d'un polygone quelconque (i.e convexe ou concave mais sans trou et non auto-intersectant). On supposera pour cet exercice qu'aucun polygone ne se recouvre (i.e pas de gestion de liste de priorité).

Exercice 3. Implanter l'algorithme de remplissage de polygones dans l'espace écran (pensez à tester chaque point avant l'appel récursif). Implanter l'algorithme de remplissage de polygones dans l'espace objet (remplissage géométrique). Comparez leur coût. Dans les deux cas, est-il plus efficace de traiter le cas d'un polygone coloré au niveau de sa fonction de visualisation plutôt qu'à posteriori ? Si c'est le cas, prévoyez une fonction de visualisation de polygone coloré.

Exercice 4. Soit un nuage de N points. Ecrire le programme naïf de recherche du couple de points les plus proches l'un de l'autre. Ecrire un programme supposé non naïf qui effectue le même travail. Comparez les temps d'exécution des deux programmes (commande time). A partir de combien de points l'algorithme non naïf est-il plus performant ?