Triangulation de Delaunay

En mathématiques et plus particulièrement en géométrie algorithmique, une triangulation de Delaunay d'un ensemble Modèle:Mvar de points du plan est une triangulation Modèle:Math telle qu'aucun point de Modèle:Mvar n'est à l'intérieur du cercle circonscrit d'un des triangles de Modèle:Math. 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, dans un article publié en 1924^[1].

Définition

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 cercle circonscrit.

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 cocycliques, 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 garantie de l'existence ou de l'unicité de la triangulation.

Relation avec les diagrammes de Voronoï

Une triangulation de Delaunay d’un ensemble discret Modèle:Mvar de points peut être vu comme un graphe non orienté : les sommets sont les points de Modèle:Mvar et les côtés des triangles sont les arêtes du graphe. Il y a une relation entre les triangulations de Delaunay et les diagrammes de Voronoï : une triangulation de Delaunay d’un ensemble discret Modèle:Mvar de points est le graphe dual du diagramme de Voronoï associé à Modèle:Mvar^[2].

Diagramme de Voronoï

Modèle:Article détaillé

Un diagramme de Voronoï est un pavage du plan composée de cellules défini à partir d'un ensemble $P$ de points, aussi appelé germes. La figure de gauche montre un diagramme de Voronoï. A tout germe $a$ , on associe une cellule, formée exactement des points du plan dont le germe le plus proche est $a$ . On note $V o r_{P} (a)$ la cellule associée au germe $a$ .

Passage d'une triangulation de Delaunay au diagramme de Voronoï

Étant donné une triangulation de Delaunay, on peut construire un diagramme de Voronoï de la façon suivante :

Les germes du diagramme de Voronoï sont les centres des cercles circonscrits des triangles de la triangulation de Delaunay.
Les arêtes du diagramme de Voronoï sont sur les médiatrices des arêtes de la triangulation de Delaunay (cependant les arêtes de Voronoï sont des segments ou demi-droites qui n'ont pas nécessairement d'intersection sur le centre de ces médiatrices, comme on peut le voir sur la figure ci-contre).

Passage d'un diagramme de Voronoï à une triangulation de Delaunay

Modèle:Section à vérifier Étant donné un diagramme de Voronoï, on peut construire une triangulation de Delaunay de la façon suivante. Chaque germe du diagramme de Voronoï constitue un sommet dans la triangulation de Delaunay. Ces sommets sont reliés entre eux par une arête si et seulement si les cellules sont adjacentes.

D E L (P) = {(a, b) \in P^{2} ∣ V o r_{P} (a) \cap V o r_{P} (b) \neq \emptyset}

.

En dimension quelconque

Pour un ensemble Modèle:Mvar de points dans l'espace Euclidien en n dimensions, une triangulation de Delaunay est une triangulation Modèle:Math telle qu'aucun point de Modèle:Mvar ne se trouve dans l'hypersphère circonscrite d'un simplexe de Modèle:Math.

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 cocycliques et, en dimension Modèle:Mvar, il suffit qu'il n'y ait pas Modèle:Math points dans le même hyperplan et Modèle:Math sur la même hypersphère.

Le problème de la construction de la triangulation de Delaunay d'un ensemble de points en dimension Modèle:Mvar dans un espace euclidien peut être ramené au problème de la construction de l'enveloppe convexe d'un ensemble de points en dimension Modèle:Math. Pour ce faire, on attribue à chaque point Modèle:Mvar une coordonnée supplémentaire, que l'on fixe à Modèle:Math, on prend le fond de l'enveloppe convexe et on retourne en dimension Modèle:Mvar 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 Modèle:Math points se trouvent sur la même hypersphère et donc que les points ne sont pas en position générale.

Propriétés

Soient Modèle:Mvar le nombre de points et Modèle:Mvar le nombre de dimensions.

L'union de tous les simplexes d'une triangulation constitue l'enveloppe convexe des points.
La triangulation de Delaunay contient au plus $O (n^{⌈ d / 2 ⌉})$ simplexes.
Dans le plan, c'est-à-dire pour Modèle:Math, s'il y a Modèle:Mvar sommets dans l'enveloppe convexe, alors toute triangulation a exactement Modèle:Math triangles (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 : 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), la somme des angles α et γ est inférieure ou égale à 180° si et seulement si ces triangles respectent la condition de Delaunay.

C'est une propriété importante car elle permet de déterminer une technique de construction. Si deux triangles ABD et CBD ne respectent pas la condition de Delaunay, il faut remplacer l'arête commune BD par l'arête commune AC (ce qui constitue le basculement), pour obtenir deux triangles ABC et ACD 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 : les cercles circonscrits sont vides.

Algorithmes

Tous les algorithmes de construction d'une triangulation de Delaunay reposent sur des opérations rapides permettant de déterminer la position d'un point par rapport à un cercle circonscrit à un triangle, et de structures de données efficaces pour conserver les triangles et les sommets.

Dans le plan, pour vérifier si un point D se trouve dans le cercle circonscrit aux points A, B et C, il suffit d'évaluer le déterminant de la matrice suivante :

$| \begin{matrix} 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{matrix} | = | \begin{matrix} A_{x} - D_{x} & A_{y} - D_{y} & (A_{x}^{2} - D_{x}^{2}) + (A_{y}^{2} - D_{y}^{2}) \\ B_{x} - D_{x} & B_{y} - D_{y} & (B_{x}^{2} - D_{x}^{2}) + (B_{y}^{2} - D_{y}^{2}) \\ C_{x} - D_{x} & C_{y} - D_{y} & (C_{x}^{2} - D_{x}^{2}) + (C_{y}^{2} - D_{y}^{2}) \end{matrix} |$

Si A, B et C sont placés dans le sens anti-horaire, le déterminant 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. Cette méthode peut nécessiter Modèle:Math basculements d'arêtes et ne peut se généraliser en dimension 3 ou supérieure^[3].

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. Implémenté de manière naïve, cela se fera en temps O(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 Modèle:Math.

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

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, commencer à un triangle racine, puis suivre les pointeurs jusqu'à arriver à un triangle qui n'a pas été remplacé. En moyenne, cela se fera en temps O(log n). Ainsi, pour rechercher le triangle conteneur de chaque sommet, cela se fera en temps O(n log n)^[3]. La technique peut être généralisée à des espaces de dimension quelconque, comme l'ont prouvé Edelsbrunner et Shah^[5], mais la complexité temporelle peut être exponentielle, y compris si la triangulation finale est petite.

Afin d'éviter la recherche de triangles, une autre manière vise à introduire les points suivant l'ordre lexicographique. On associe le nouveau point à son prédécesseur ensuite on parcourt de part et d'autre l'enveloppe convexe pour former et légaliser les nouveaux triangles qui sont relatifs à ce nouveau point. Cette méthode est limitée car pour introduire un nouveau point qui n'est pas lexicographiquement supérieur aux autres, il faudra tout reconstruire. Elle requiert la connaissance parfaite de l'ensemble de points.

L'algorithme de Bowyer-Watson est une autre approche de construction incrémentale. Il donne une alternative au basculement en supprimant les triangles (ou simplexes) dont les cercles (ou hypersphère) circonscrits contiennent le nouveau point et en re-triangulant la cavité en étoile ainsi formée.

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^[6] 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 Modèle:Nobr

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 fournit un bon ensemble de triangles qui pourront ensuite être utilisés comme polygones dans le modèle.

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'Modèle:Lien. Jonathan Shewchuk a publié une bibliothèque libre sur les triangles^[7].

Les triangulations de Delaunay sont également utilisés en volumes finis, notamment en mécanique des fluides, pour générer des maillages non structurés sur des géométries complexes^[8].

Notes et références

Modèle:Traduction/Référence Modèle:Références

Voir aussi

Articles connexes

Modèle:Portail

↑ ^1,0 et ^1,1 B. Delaunay, « Sur la sphère vide », Proceedings du Congrès international des mathématiciens de 1924, Modèle:P..
↑ Modèle:Lien archive
↑ ^3,0 et ^3,1 Modèle:Ouvrage.
↑ Modèle:Article.
↑ Modèle:Article.
↑ Voir référence dans Modèle:Lien web.
↑ Modèle:En Triangle.
↑ Modèle:Article

[Delaunay1924-1] 1,0 et ^1,1 B. Delaunay, « Sur la sphère vide », Proceedings du Congrès international des mathématiciens de 1924, Modèle:P..

[2] Modèle:Lien archive

[deBerg-3] 3,0 et ^3,1 Modèle:Ouvrage.

[4] Modèle:Article.

[5] Modèle:Article.

[6] Voir référence dans Modèle:Lien web.

[7] Modèle:En Triangle.

[8] Modèle:Article

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Triangulation de Delaunay

Sommaire

Définition