△ Delaunay & Voronoï

L'algorithme de Bowyer-Watson insère les points un par un dans une triangulation existante. Il commence avec un grand « super-triangle » qui contient tous les points d'entrée. Pour chaque nouveau point, il trouve tous les triangles dont le cercle circonscrit contient le point (les triangles « mauvais »), les supprime pour former une cavité polygonale en forme d'étoile, puis connecte le nouveau point à chaque arête de cette cavité pour créer de nouveaux triangles. Enfin, tous les triangles partageant un sommet avec le super-triangle sont écartés. L'algorithme s'exécute en temps attendu O(n log n) pour des ensembles de points aléatoires et O(n²) dans le pire cas.

Le diagramme de Voronoï partitionne le plan en régions, une par point d'entrée, où chaque région contient tous les emplacements plus proches de ce point que de tout autre. La triangulation de Delaunay et le diagramme de Voronoï sont des duaux géométriques : le centre du cercle circonscrit de chaque triangle de Delaunay devient un sommet de Voronoï, et connecter les centres circonscrits de triangles adjacents (triangles partageant une arête) trace les arêtes de Voronoï. Activez « Diagramme de Voronoï » dans la simulation pour superposer les deux structures simultanément et observer comment chaque sommet de Voronoï se situe exactement au centre du cercle circonscrit d'un triangle de Delaunay.

La triangulation de Delaunay sous-tend la génération de maillages par éléments finis dans les simulations structurelles et de dynamique des fluides, où des triangles bien formés améliorent la précision du solveur. Elle est utilisée dans les systèmes d'information géographique pour construire des réseaux irréguliers triangulés (TIN) pour les modèles d'élévation de terrain. Les pipelines d'infographie l'utilisent pour la reconstruction de surfaces à partir de nuages de points, les formes alpha et l'atlas de textures. La planification de réseaux sans fil et mobiles utilise les cellules de Voronoï (le dual) pour modéliser les zones de couverture et les frontières de transfert entre stations de base.

Pour des points en « position générale » — c'est-à-dire qu'aucun quatre points ne sont exactement cocirculaires — la triangulation de Delaunay est unique. Lorsque quatre points ou plus se trouvent sur un cercle commun (une configuration dégénérée), il n'y a pas de préférence stricte entre deux triangulations valides, donc le résultat dépend des règles de départage. La simulation gère cela en appliquant une légère perturbation aux coordonnées des points pendant le calcul de Bowyer-Watson, garantissant un résultat cohérent même pour des dispositions symétriques telles que des grilles régulières ou des cercles.

La triangulation porte le nom de Boris Nikolaïevitch Delaunay (également translittéré Delone), un mathématicien soviétique qui a formellement défini et démontré la construction dans son article de 1934 « Sur la sphère vide ». Gueorgui Voronoï avait déjà décrit le diagramme dual en 1908. L'algorithme incrémental de Bowyer-Watson, que cette simulation implémente, a été découvert indépendamment par Adrian Bowyer et David Watson en 1981, rendant la méthode suffisamment efficace pour une utilisation interactive pratique.

Les structures étroitement apparentées incluent l'enveloppe convexe (la frontière extérieure de la triangulation de Delaunay, affichée en activant « Enveloppe convexe » dans cette simulation), le graphe de Gabriel (un sous-graphe des arêtes de Delaunay où le cercle diamétral de chaque arête est vide), et l'arbre couvrant minimal (toujours un sous-graphe de la triangulation de Delaunay). Dans les dimensions supérieures, la triangulation de Delaunay se généralise en tétraédralisation de Delaunay en 3D, essentielle pour la génération de maillages volumétriques en ingénierie computationnelle.

En analyse par éléments finis (FEA), les triangles mal formés avec des angles très petits provoquent des matrices de rigidité mal conditionnées et une instabilité numérique ; le maillage de Delaunay suivi d'algorithmes de raffinement comme l'algorithme de Ruppert garantit une borne d'angle minimum (généralement supérieure à 20 degrés) sur tout le maillage. En vision par ordinateur, la triangulation de Delaunay de points de repère faciaux produit un maillage utilisé pour la déformation de visage, le morphing et les filtres de réalité augmentée. Les logiciels géospatiaux comme QGIS et ArcGIS l'utilisent pour interpoler les données d'élévation et générer des lignes de contour à partir de mesures d'enquête dispersées.

La recherche active inclut la construction de Delaunay parallèle et accélérée par GPU pour de très grands ensembles de points (milliards de points dans les simulations scientifiques), les structures de Delaunay dynamiques qui prennent en charge des insertions et suppressions de points efficaces dans des scénarios en flux continu ou de points mobiles, et le maillage anisotrope où la forme des triangles s'adapte à la directionnalité du domaine sous-jacent (comme les couches limites en dynamique des fluides). Des travaux sont également en cours sur les triangulations de Delaunay pondérées (diagrammes de puissance) et leurs applications en transport optimal et en géométrie de l'apprentissage automatique.