Infographie 2D - TP 4

mer. 16 septembre 2009

Géométrie algorithmique

Dichotomie et polygones

Exercice 1. Construire 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. 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 3. 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 ?