Triangulation d'un polygone

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]^,^[3]. L'algorithme proposé est cependant très complexe, et des algorithmes plus simples sont toujours recherchés.

Méthodes de résolution

Méthode des oreilles

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 »^[4], résultat démontré initialement par Max Dehn en 1899 puis oublié jusqu'à être redémontré en 1975^[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^[5], à 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²)^[3].

Décomposition en chaînes monotones

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

Un polygone monotone (en) est tel que sa frontière peut être divisée en deux parties, chacune d'entre elles é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 ». Fournier (en) et Montuno ont montré qu'un tel polygone peut être triangulé en temps linéaire^[6].

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

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Polygon triangulation » (voir la liste des auteurs).

↑ ^{a et b} (en) Mark de Berg, Marc van Kreveld, Mark Overmars et Otfried Schwarzkopf, Computational Geometry, Springer Verlag, 2000, 2^e éd. (ISBN 3-540-65620-0, lire en ligne), chap. 3 (« Polygon Triangulation »), p. 45-61.
↑ (en) Bernard Chazelle, « Triangulating a simple polygon in linear time », Discrete Comput. Geom., vol. 6,‎ 1991, p. 485-524 (DOI 10.1007/BF02574703, lire en ligne).
↑ ^{a b et c} Yves Coudène, La géométrie élémentaire d'Euclide à aujourd'hui, Calvage & Mounet, coll. « Mathématiques en devenir », 2022, 451 p. (ISBN 978-2-49-323001-0), VIII. Géométrie et topologie, chap. 2 (« Triangulation des polygones »)
↑ Et même, deux oreilles qui ne se chevauchent pas : (en) Gary Hosler Meisters, « Polygons have ears », Amer. Math. Monthly, vol. 82,‎ 1975, p. 648-651 (lire en ligne).
↑ (en) Hossam ElGindy, Hazel Everett et Godfried Toussaint (en), « Slicing an ear using prune-and-search », Pattern Recognition Letters, vol. 14, n^o 9,‎ 1993, p. 719-722 (DOI 10.1016/0167-8655(93)90141-Y, lire en ligne).
↑ (en) A. Fournier et D. Y. Montuno, « Triangulating simple polygons and equivalent problems », ACM Transactions on Graphics, vol. 3, n^o 2,‎ avril 1984, p. 153-174 (DOI 10.1145/357337.357341).

Voir aussi

Articles connexes

Bibliographie

(en) Nancy M. Amato, Michael T. Goodrich (en) et Edgar A. Ramos, « A randomized algorithm for triangulating a simple polygon in linear time », Discrete Comput. Geom., vol. 26, n^o 2,‎ 2000, p. 245-265 (DOI 10.1007/s00454-001-0027-x, lire en ligne)
(en) Godfried Toussaint, « Anthropomorphic polygons », Amer. Math. Monthly, vol. 98, n^o 1,‎ 1991, p. 31-35 (DOI 10.2307/2324033, lire en ligne)

Liens externes

(en) « Polygons and meshes », sur paulbourke.net, mars 1998 (consulté le 3 janvier 2016)

[CompGeo-1] {a et b} (en) Mark de Berg, Marc van Kreveld, Mark Overmars et Otfried Schwarzkopf, Computational Geometry, Springer Verlag, 2000, 2^e éd. (ISBN 3-540-65620-0, lire en ligne), chap. 3 (« Polygon Triangulation »), p. 45-61.

[2] (en) Bernard Chazelle, « Triangulating a simple polygon in linear time », Discrete Comput. Geom., vol. 6,‎ 1991, p. 485-524 (DOI 10.1007/BF02574703, lire en ligne).

[coudene-3] {a b et c} Yves Coudène, La géométrie élémentaire d'Euclide à aujourd'hui, Calvage & Mounet, coll. « Mathématiques en devenir », 2022, 451 p. (ISBN 978-2-49-323001-0), VIII. Géométrie et topologie, chap. 2 (« Triangulation des polygones »)

[meisters-4] Et même, deux oreilles qui ne se chevauchent pas : (en) Gary Hosler Meisters, « Polygons have ears », Amer. Math. Monthly, vol. 82,‎ 1975, p. 648-651 (lire en ligne).

[5] (en) Hossam ElGindy, Hazel Everett et Godfried Toussaint (en), « Slicing an ear using prune-and-search », Pattern Recognition Letters, vol. 14, n^o 9,‎ 1993, p. 719-722 (DOI 10.1016/0167-8655(93)90141-Y, lire en ligne).

[6] (en) A. Fournier et D. Y. Montuno, « Triangulating simple polygons and equivalent problems », ACM Transactions on Graphics, vol. 3, n^o 2,‎ avril 1984, p. 153-174 (DOI 10.1145/357337.357341).

[1]

[2]

[3]

[4]

[5]

[6]