Triangulation de Delaunay contrainte
En géométrie algorithmique, une triangulation de Delaunay contrainte est une triangulation d'un ensemble de points qui généralise la triangulation de Delaunay par la donnée d'un ensemble de segments devant être inclus dans la triangulation[1],[2]. La triangulation de Delaunay standard ne prend en compte que la position des points à trianguler sans qu'on puisse spécifier quels points doivent être connectés. La triangulation contrainte permet de forcer la triangulation à contenir les segments prédéfinis.
Il existe des algorithmes efficaces pour calculer une triangulation de Delaunay contrainte, ce qui permet son utilisation notamment dans les systèmes d'information géographique ou la génération de maillages.
Définition
On suppose donnés un ensemble de points du plan et un ensemble de segments reliant deux a deux des points. L'ensemble forme un graphe planaire droit (c'est-à-dire dont les arêtes sont des segments de droite).
On souhaite trianguler ce graphe, c'est-à-dire relier les points par des arêtes de telle sorte à ce que l'enveloppe convexe des points soit partitionnée en triangles dont les sommets sont les points donnés. On souhaite de plus que cette triangulation contienne les arêtes du graphe initial.
La triangulation obtenue est une triangulation de Delaunay contrainte, si pour chaque segment ajouté (ne faisant pas partie de l'ensemble initial), il existe un cercle passant par les extrémités A et B du segment, tel que pour tout autre sommet P à l'intérieur du cercle, la visibilité de A ou B depuis P soit bloquée par l'un des segments initiaux. Autrement dit, pour chaque sommet P, on ne peut pas relier P à A et à B par une ligne droite sans croiser l'un des segments données en entrée.
Il s'agit de la généralisation de la propriété de Delaunay, dans laquelle chaque segment a un cercle passant par ses extrémités ne contenant aucun autre point.
On peut montrer qu'une telle triangulation contrainte existe toujours dans le plan[1], mais que si l'on généralise à la dimension 3 ce n'est pas toujours le cas [2].
Algorithmes
On connaît plusieurs algorithmes pour les triangulations de Delaunay contraintes dont la complexité en temps est en O(n log n) sont connus[3]. Dans le cas d'un polygone simple la triangulation contrainte peut être construite en temps linéaire[4].
Applications
En topographie, on construit une triangulation à partir des relevés obtenus par arpentage. Si l'un des segments mesurés traverse par exemple une rivière, la surface résultante ne pourra pas représenter le trajet de la rivière[pas clair]. On trace donc des lignes de contraintes supplémentaires qui sont utilisées comme contraintes lors de la construction de la triangulation[réf. nécessaire].
La triangulation de Delaunay contrainte peut également être utilisée dans les méthodes de raffinement pour la génération de maillage, pour forcer le maillage à se conformer aux bornes du domaine lors de son raffinement.
Références
- (en) L. Paul Chew, « Constrained delaunay triangulations », Algorithmica, vol. 4, nos 1-4, , p. 97–108 (ISSN 0178-4617 et 1432-0541, DOI 10.1007/BF01553881, lire en ligne, consulté le )
- (en) Jonathan Richard Shewchuk, « General-Dimensional Constrained Delaunay and Constrained Regular Triangulations, I: Combinatorial Properties », Discrete & Computational Geometry, vol. 39, nos 1-3, , p. 580–637 (ISSN 0179-5376 et 1432-0444, DOI 10.1007/s00454-008-9060-3, lire en ligne, consulté le )
- ↑ (en) C. Wang et L. Schubert, « An optimal algorithm for constructing the Delaunay triangulation of a set of line segments », CrossRef, ACM Press, , p. 223–232 (ISBN 978-0-89791-231-0, DOI 10.1145/41958.41982, lire en ligne, consulté le )
- ↑ (en) Francis Chin et Cao An Wang, « Finding the Constrained Delaunay Triangulation and Constrained Voronoi Diagram of a Simple Polygon in Linear Time », SIAM Journal on Computing, vol. 28, no 2, , p. 471–486 (ISSN 0097-5397 et 1095-7111, DOI 10.1137/S0097539795285916, lire en ligne, consulté le )
- Portail des mathématiques