Triangulation
En géométrie algorithmique, la triangulation d’un polygone consiste à décomposer ce polygone en un ensemble (fini) de triangles. Une triangulation d’un polygone P est une partition de P en un ensemble de triangles qui ne se recouvrent pas, et dont l’union est P.
Dans ce TP, on se limitera à des polygones simples. En géométrie, un polygone est dit simple si deux cotés non consécutifs ne se rencontrent pas et deux cotés consécutifs n’ont en commun que l’un de leurs sommets.
Les polygones sont 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. Structure de données
Utiliser la structure de données d’une liste double-chaînée mise à disposition et l’appliquer à la définition d’un polygone simple.
Exercice 2. Convexité
Implanter une fonction qui détermine si une suite de trois sommets consécutifs d’un polygone constitue un angle ouvert (supérieur à 180°) ou fermé (inférieur ou égal à 180°).
Tester cette fonction sur le polygone de test.
Exercice 3. Triangulation d’un polygone simple
Une manière de trianguler un polygone simple est d’utiliser le fait que tout polygone simple à au moins quatre sommets possède au moins deux “oreilles”.
Une oreille est un triangle avec deux arêtes appartenant à la frontière du polygone, et la troisième située à l’intérieur du polygone.
L’algorithme consiste à trouver une telle oreille, à la retirer du polygone, ce qui donne un nouveau polygone qui répond toujours aux conditions, et à répéter l’opération jusqu’à ce qu’il n’y ait plus qu’un seul triangle.
Implanter la fonction de triangulation par la méthode des “oreilles” (ear-clipping) et l’appliquer au polygone test. Donner son temps d’exécution (voir pour cela perf_counter() du module time).
Exercice 4. Décomposition d’un polygone simple en sous polygones monotones
Implanter une fonction qui détermine, pour chaque sommet d’un polygone, si celui-ci est de type start, end, split, merge ou regular.
A la suite de cette détermination, implanter l’algorithme de décomposition d’un polygone simple en sous-polygones monotones. On utilisera avec profit un tas (module heapq) pour gérer les arêtes.
Exercice 5. Triangulation d’un polygone monotone
Pour chaque sous-polygone monotone, appliquer l’algorithme de triangulation par la méthode des “oreilles”. Comparez le temps d’exécution total (exercices 4 et 5) avec celui de l’exercice 3.