Triangulation d'un polygone

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En géométrie algorithmique, la triangulation d'un polygone consiste à décomposer ce polygone en un ensemble (fini) de triangles[1].

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 le cas le plus restrictif, on impose que les sommets des triangles ne soient que les sommets de P. Dans un cadre plus permissif, on peut rajouter des sommets à l'intérieur de P ou sur la frontière pour servir de sommets aux triangles.

Les triangulations sont des cas particuliers de graphes planaires rectilignes (i.e. dont les arêtes sont des segments).

La triangulation d'un polygone convexe est triviale et se calcule en un temps linéaire, par exemple en partant d'un sommet et en ajoutant des arêtes avec tous les autres sommets. En 1991, Bernard Chazelle montra que tout polygone simple peut être triangulé en un temps linéaire[2]. L'algorithme proposé est cependant très complexe, et des algorithmes plus simples sont toujours recherchés.

Méthodes de résolution[modifier | modifier le code]

Méthode "des oreilles"[modifier | modifier le code]

Une oreille d'un polygone
Une oreille d'un polygone

Une manière de trianguler un polygone simple est d'utiliser le fait que tout polygone simple sans trou possède au moins deux "oreilles"[3]. 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.

Cet algorithme est simple à implémenter, mais sous-optimal : une implémentation qui stocke des listes séparées de sommets pour les triangles et le polygone aura une complexité en O(n²). De plus, il ne fonctionne que sur des polygones sans trous.

Décomposition en chaînes monotones[modifier | modifier le code]

Décomposition d'un polygone en polygones monotones
Décomposition en polygones monotones

Un polygone monotone est tel que sa frontière peut être divisée en deux parties, chacune d'entre elle étant composée de points dont les coordonnées selon une dimension donnée ne font que croître : la frontière ne revient pas "en arrière". A. Fournier et D. Y. Montuno ont montré qu'un tel polygone peut être triangulé en temps linéaire[4].

Pour diviser un polygone en polygones monotones, on utilise une ligne verticale ou horizontale qui balaie les coordonnées dans une direction[1].

Cet algorithme a une complexité en O(n log n).

Notes et références[modifier | modifier le code]

Notes[modifier | modifier le code]

  1. a et b (en) Mark de Berg, Marc van Kreveld, Mark Overmars et Otfried Schwarzkopf, Computational Geometry, Springer Verlag,‎ 2000, 2e éd. (ISBN 3-540-65620-0), chap. 3 (« Polygon Triangulation »), p. 45-61
  2. (en) Bernard Chazelle, « Triangulating a Simple Polygon in Linear Time », Discrete & Computational Geometry, vol. 6,‎ 1991, p. 485–524 (ISSN 0179-5376, DOI 10.1007/BF02574703)
  3. (en) Gary Hosler Meisters, « Polygons have ears », American Mathematical Monthly, vol. 82,‎ 1975, p. 648-651 (lire en ligne)
  4. (en) A. Fournier et D. Y. Montuno, « Triangulating simple polygons and equivalent problems », ACM Transactions on Graphics, vol. 3, no 2,‎ avril 1984, p. 153–174 (ISSN 0730-0301, DOI 10.1145/357337.357341)

Références[modifier | modifier le code]

Articles connexes[modifier | modifier le code]