Delaunay triangulation

Triangulation de Delaunay

Pour les articles homonymes, voir Delaunay.

Une triangulation de Delaunay avec les cercles circonscrits visibles

En mathématiques et plus particulièrement en géométrie algorithmique, la triangulation de Delaunay d'un ensemble P de points du plan est une triangulation DT(P) telle qu'aucun point de P n'est à l'intérieur du cercle circonscrit d'un des triangles de DT(P). Les triangulations de Delaunay maximisent le plus petit angle de l'ensemble des angles des triangles, évitant ainsi les triangles "allongés". Cette triangulation a été inventée par le mathématicien russe Boris Delaunay (1890 - 1980) en 1934 ^[1].

D'après la définition de Delaunay^[1], le cercle circonscrit d'un triangle constitué de trois points de l'ensemble de départ est vide s'il ne contient pas d'autres sommets que les siens. Ainsi, les autres points sont autorisés sur le périmètre en lui-même mais pas à l'intérieur strict du triangle.

La condition de Delaunay affirme qu'un réseau de triangles est une triangulation de Delaunay si tous les cercles circonscrits des triangles du réseau sont vides. Ceci constitue la définition originale en deux dimensions. En remplaçant les cercles par des sphères circonscrites, il est possible d'étendre la définition à la dimension trois.

Il n'existe pas de triangulation de Delaunay pour un ensemble de points alignés. De toute manière, la triangulation n'est dans ce cas pas définie.

Pour 4 points concentriques, tels que les sommets d'un rectangle, la triangulation de Delaunay n'est pas unique. Trivialement, les triangulations utilisant chacune des deux diagonales satisfont la condition de Delaunay.

Il est possible de généraliser cette notion pour des mesures non euclidiennes, sans garanti de l'existence ou de l'unicité de la triangulation.

Relation avec les diagrammes de Voronoï

Superposition d'un diagramme de Voronoï (en rouge) et de sa triangulation de Delaunay (en noir)

La triangulation de Delaunay d'un ensemble discret P de points est le graphe dual du diagramme de Voronoï associé à P. A chaque cellule du diagramme de Voronoï est associé un sommet dans la triangulation de Delaunay. Ces sommets sont reliés entre eux par une arête si les cellules sont voisines. On remarquera que les arêtes du diagramme de Voronoï sont sur les médiatrices des arêtes de la triangulation de Delaunay.

Delaunay en dimension quelconque

Pour un ensemble P de points dans l'espace Euclidien en n dimensions, une triangulation de Delaunay est une triangulation DT(P) telle qu'aucun point de P ne se trouve dans l'hypersphère circonscrite d'un simplexe de DT(P).

Une triangulation de Delaunay dans le plan est unique si les points sont dans une position générale, c'est-à-dire, en dimension 2, s'il n'y a pas trois points alignés ou quatre points concentriques, et en dimension d, il faut qu'il n'y ait pas d + 1 points dans le même hyperplan et d+2 sur la même hypersphère.

Le problème de la construction de la triangulation de Delaunay d'un ensemble de points en dimension n dans un espace Euclidien peut être ramené au problème de la construction de l'enveloppe convexe d'un ensemble de points en dimension n+1. Pour ce faire, on attribue à chaque point p une coordonnée supplémentaire, que l'on fixe à | p | ², on prend le fond de l'enveloppe convexe et on retourne en dimension n en supprimant la dernière coordonnée. Comme l'enveloppe convexe est unique, la triangulation l'est aussi tant que toutes les faces de l'enveloppe convexe sont des simplexes. Si une face n'est pas un simplexe, cela signifie que n + 2 points se trouvaient sur la même hypersphère et donc que les points n'étaient pas en position générale.

Propriétés

Soient n le nombre de points et d le nombre de dimensions.

• L'union de tous les simplex d'une triangulation constitue l'enveloppe convexe des points.
• La triangulation de Delaunay contient au plus $O(n^{\lceil d/2 \rceil})$ simplexes.
• Dans le plan, c'est-à-dire pour d=2, s'il y a b sommets dans l'enveloppe convexe, alors toute triangulation a au plus 2b - 2 - b triangles, plus un sur la face extérieure (voir la caractéristique d'Euler).
• Dans le plan, chaque sommet est en moyenne entouré de six triangles.
• Si un cercle passant par deux des points de l'ensemble n'en contient aucun autre dans son intérieur, alors le segment reliant les deux points est un segment de la triangulation de cet ensemble.
• La triangulation de Delaunay d'un ensemble de points dans un espace de dimension d est la projection de l'enveloppe convexe des projections des points sur une paraboloïde de dimension d+1.

Une définition visuelle de la triangulation de Delaunay : le basculement

D'après les propriétés précédentes, on peut remarquer qu'avec deux triangles ABD et BCD donnés (voir figure), si la somme des angles α et γ est inférieure ou égale à 180° alors cela signifie que ces triangles respectent la condition de Delaunay.

C'est une propriété importante car elle permet de déterminer une technique construisant une triangulation de Delaunay. Si deux triangles ne respectent pas la condition de Delaunay, on remplace l'arête commune BD par l'arête commune AC (ce qui constitue le basculement), génèrant ainsi deux triangles qui respectent la condition de Delaunay:

Cette triangulation ne respecte pas la propriété précédente : la somme de α et γ vaut plus que 180°.

La nouvelle triangulation ne vérifie pas la condition de Delaunay : les cercles circonscrits ne sont pas vides.

Le basculement d'arête produit une triangulation de Delaunay.

Algorithmes

Tous les algorithmes pour construire une triangulation de Delaunay reposent sur des opérations rapides permettant de détecter lorsqu'un point est à l'intérieur d'un triangle circonscrit et de structures de données efficaces pour conserver les triangles et les sommets. Dans le plan, une manière de détecter si un point D se trouve dans le cercle circonscrit de A, B et C est d'évaluer le déterminant de la matrice suivante :

$\begin{vmatrix} A_x & A_y & A_x^2 + A_y^2 & 1\\ B_x & B_y & B_x^2 + B_y^2 & 1\\ C_x & C_y & C_x^2 + C_y^2 & 1\\ D_x & D_y & D_x^2 + D_y^2 & 1 \end{vmatrix} = \begin{vmatrix} A_x - D_x & A_y - D_y & (A_x - D_x)^2 + (A_y - D_y)^2 \\ B_x - D_x & B_y - D_y & (B_x - D_x)^2 + (B_y - D_y)^2 \\ C_x - D_x & C_y - D_y & (C_x - D_x)^2 + (C_y - D_y)^2 \\ \end{vmatrix} > 0$

En supposant que A, B et C sont placés dans le sens anti-horaire, ce nombre est positif si et seulement si D se trouve dans le cercle circonscrit.

Algorithmes de basculement

Comme mentionné ci-dessus, si un triangle n'est pas de Delaunay, il est possible de basculer l'un de ses côtés. On construit ainsi un algorithme direct : on génère d'abord une triangulation quelconque, puis on bascule les arêtes jusqu'à ce que tous les triangles soient de Delaunay. Malheureusement, cette méthode peut nécessiter O(n²) basculements d'arêtes et ne peut se généraliser en dimension 3 ou supérieure. ^[2].

Incrémentation

La manière la plus directe de générer efficacement une triangulation de Delaunay est d'ajouter les sommets un par un en recalculant la triangulation des parties du graphe affectées par cet ajout. Lorsqu'un sommet s est ajouté, le triangle contenant s est séparé en trois puis on leur applique l'algorithme de basculement. Fait de manière naïve, cela se fera en temps 0(n) : il faut chercher parmi tous les triangles pour trouver celui qui contient s et tous les triangles vont ensuite potentiellement basculer. Comme il faut faire cela pour chaque sommet, le temps total d'exécution est en O(n²).

Si les sommets sont insérés dans un autre aléatoire, chaque insertion ne va faire basculer, en moyenne, que O(1) triangles, même si parfois beaucoup plus vont basculer.^[3].

Pour améliorer la recherche de la position du point, il est possible de stocker l'historique des partitionnements et des basculements effectués : chaque triangle garde en mémoire un pointeur vers les deux ou trois triangles qui l'ont remplacé. Pour trouver le triangle qui contient s, on commence à un triangle racine, puis on suit les pointeurs jusqu'à arriver à un triangle qui n'a pas été remplacé. En moyenne, cela se fera en temps 0(log n). Ainsi, pour rechercher le triangle conteneur de chaque sommet, cela se fera en temps O(n log n)^[2]. La technique peut être généralisée à des espaces de dimension quelconque, comme l'ont prouvé Edelsbrunner and Shah^[4], mais la complexité temporelle peut être exponentielle, y compris si la triangulation finale est petite.

Diviser pour régner

Lee et Schachter ont mis au point un algorithme diviser pour régner appliqué à la triangulation en deux dimensions qui a ensuite été amélioré par Guibas et Stolfi^[5] puis par Dwyer. Dans cet algorithme, une ligne est récursivement dessinée pour séparer les points en deux ensembles. La triangulation de Delaunay est calculée pour chacun des ensembles puis ils sont fusionnés. Avec quelques astuces, la fusion peut se faire en O(n). Ainsi, le temps total de calcul est en O(n log n).^[6]

Applications

L'arbre euclidien couvrant de poids minimum d'un ensemble de points est un sous-ensemble de la triangulation de Delaunay de ces mêmes points. Ce résultat permet de calculer efficacement cet arbre.

Pour modéliser un terrain ou d'autres objets à partir d'un ensemble de points donnés, la triangulation de Delaunay fourni un bon ensemble de triangles qui pourront ensuite être utilisés comme polygones dans le modèle.

La triangulation de Delaunay d'une centaine de points aléatoires du plan

Les triangulations de Delaunay sont souvent utilisées pour construire les mailles de la méthode des éléments finis à cause de la garantie sur les angles et grâce à la vitesse des algorithmes. Typiquement, le domaine dont on veut construire les mailles est décrit comme un gros complexe simplicial. Pour que le maillage soit stable numériquement, il faut qu'il soit raffiné, par exemple en utilisant l'algorithme de Ruppert. Cela a été fait par Jonathan Shewchuk dans la librairie libre sur les triangles.

Voir aussi

• Diagramme de Voronoï
• Graphe de Gabriel
• Triangulation de Pitteway

References

1. ↑ ^{a  et b} B. Delaunay: Sur la sphère vide, Izvestia Akademii Nauk SSSR, Otdelenie Matematicheskikh i Estestvennykh Nauk, 7:793-800, 1934
2. ↑ ^{a  et b} (en) Mark de Berg, Computational Geometry: Algorithms and Applications, Springer-Verlag (ISBN 978-3-540-77973-5) 
3. ↑ L. Guibas, « Randomized incremental construction of Delaunay and Voronoi diagrams », dans Algorithmica, vol. 7, 1992, p. 381-413 [texte intégral] 
4. ↑ Herbert Edelsbrunner, « Incremental Topological Flipping Works for Regular Triangulations », dans Algorithmica, vol. 15, 1996, p. 223–241 [texte intégral] 
5. ↑ Computing Constrained Delaunay Triangulations
6. ↑ G. Leach: Improving Worst-Case Optimal Delaunay Triangulation Algorithms. June 1992

Ce document provient de « Triangulation de Delaunay ».