Triangulation de Delaunay

Triangulation de Delaunay
Page d'aide sur l'homonymie Pour les articles homonymes, voir Delaunay.
Une triangulation de Delaunay avec les cercles circonscrits en gris.

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

Sommaire

Relation avec les diagrammes de Voronoï

Superposition d'un diagramme de Voronoï et de sa triangulation de Delaunay (associée
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. Les arêtes du diagramme de Voronoï sont sur les médiatrices des arêtes de la triangulation de 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 cocycliques et, en dimension d, il suffit 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 | 2, 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 trouvent sur la même hypersphère et donc que les points ne sont 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 simplexes 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 2n - 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 : 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 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 ne respectent pas la condition de Delaunay, remplacer 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:

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^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{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. Cette méthode peut nécessiter O(n2) 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(n2).

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[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, 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 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 et 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 fournit 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. Jonathan Shewchuk a publié une bibliothèque libre sur les triangles.

Notes et références

  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, Otfried Cheong, Marc van Kreveld, Mark Overmars, Computational Geometry: Algorithms and Applications, Berlin, Springer-Verlag, 2008, 3e éd. (ISBN 978-3-540-77973-5) (LCCN 2008921564) [lire en ligne] 
  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

Voir aussi

Articles connexes

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Triangulation de Delaunay de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Triangulation de delaunay — Pour les articles homonymes, voir Delaunay. Une triangulation de Delaunay avec les cercles circonscrits visibles …   Wikipédia en Français

  • Delaunay triangulation — Triangulation de Delaunay Pour les articles homonymes, voir Delaunay. Une triangulation de Delaunay avec les cercles circonscrits visibles …   Wikipédia en Français

  • Delaunay Triangulation — Delaunay Triangulation, oft auch nur Triangulation oder Triangulierung genannt, ist ein gebräuchliches Verfahren, um aus einer Punktemenge ein Dreiecksnetz zu erstellen. Sie ist nach dem russischen Mathematiker Boris Nikolajewitsch Delone… …   Deutsch Wikipedia

  • Delaunay triangulation — A Delaunay triangulation in the plane with circumcircles shown In mathematics and computational geometry, a Delaunay triangulation for a set P of points in the plane is a triangulation DT(P) such that no point in P is inside the circumcircle of… …   Wikipedia

  • Triangulation de Pitteway — À gauche: Une triangulation de Pitteway. Chaque arrête de la triangulation de Delaunay, en noir, coupe son dual associé dans le diagramme de Voronoi, en pointillé bleu. À droite : une triangulation de Delaunay qui n est pas une triangulation …   Wikipédia en Français

  • Triangulation — En géométrie et trigonométrie, la triangulation est une technique permettant de déterminer la position d un point en mesurant les angles entre ce point et d autres points de référence dont la position est connue, et ceci plutôt que de mesurer… …   Wikipédia en Français

  • Triangulation d'un ensemble de points — Une triangulation d un ensemble de points P dans le plan est une triangulation de l’enveloppe convexe de P, tous les points de P formant alors des sommets de cette triangulation. Les triangulations sont un sous ensemble de graphes planaires… …   Wikipédia en Français

  • Delaunay — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.  Pour l’article homophone, voir Launay. Delaunay est un nom de famille notamment porté par : Albert Delaunay (1828 1892), auteur d une méthode… …   Wikipédia en Français

  • Triangulation (géométrie) — En géométrie, une triangulation est une partition d un objet en un ensemble de simplexes. En particulier dans le plan, une triangulation est composée de triangles. Une triangulation est un complexe simplicial. Une triangulation T d un ensemble X… …   Wikipédia en Français

  • 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… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”