Générateur de triangulation de Delaunay

Le Générateur de Triangulation de Delaunay transforme n'importe quel ensemble de points 2D en l'unique triangulation qui maximise le plus petit angle intérieur — la référence absolue pour la modélisation de terrain, le maillage par éléments finis, l'interpolation par plus proche voisin et les cours de géométrie algorithmique. Collez des coordonnées (ou choisissez un motif de démarrage rapide), et l'outil exécute l'algorithme de Bowyer-Watson côté serveur, colore chaque triangle selon sa qualité et affiche la propriété du cercle circonscrit vide, l'enveloppe convexe et le duel de Voronoi à la demande.

Comment lire le maillage généré

Ce qui rend ce triangulateur de Delaunay différent

Qu'est-ce qu'une triangulation de Delaunay ?

Pour un ensemble de points 2D donné, il existe généralement plusieurs manières de les relier pour former une triangulation (un pavage complet de leur enveloppe convexe par des triangles sans chevauchement ni espace). La triangulation de Delaunay, nommée d'après le mathématicien russe Boris Delaunay (1934), est celle qui satisfait la propriété du cercle circonscrit vide : pour chaque triangle du maillage, le cercle qui passe par ses trois sommets ne contient aucun autre point d'entrée. Cette unique propriété a une conséquence remarquable : parmi toutes les triangulations d'un même ensemble de points, celle de Delaunay maximise le plus petit angle intérieur. En clair, elle produit des triangles les plus « larges » et « équilibrés » possibles.

Comment fonctionne l'algorithme de Bowyer-Watson

1. Entourer tous les points d'entrée avec un très grand super-triangle.
2. Insérer un point d'entrée à la fois. Pour chaque nouveau point, trouver chaque triangle existant dont le cercle circonscrit contient le nouveau point — ce sont les « mauvais » triangles.
3. Supprimer les mauvais triangles. Le trou qu'ils laissent derrière eux possède une bordure polygonale.
4. Relier le nouveau point à chaque arête de cette bordure, formant ainsi de nouveaux triangles.
5. Une fois tous les points insérés, retirer tout triangle touchant encore un sommet du super-triangle. Ce qui reste est la triangulation de Delaunay de l'ensemble de points initial.

Où la triangulation de Delaunay est-elle utilisée ?

• Modélisation de terrain (SIG) : les échantillons d'altitude (généralement espacés de manière irrégulière, comme les stations de terrain) sont reliés en un réseau de triangles irréguliers (TIN) pour les requêtes d'altitude, l'ombrage et la visualisation 3D.
• Analyse par éléments finis : les triangles de Delaunay bien formés permettent d'obtenir des solutions numériques stables pour les équations aux dérivées partielles en mécanique, transfert de chaleur et électromagnétisme.
• Infographie : génération de maillage pour le rendu, l'animation de personnages (rigging) et les terrains procéduraux — la garantie « sans triangles étirés » de Delaunay évite les artefacts d'étirement des textures.
• Interpolation par voisins naturels : des surfaces lisses sont reconstruites à partir d'échantillons dispersés en calculant les voisins naturels de chaque point de requête via le duel de Voronoi.
• Cours de géométrie algorithmique : un algorithme canonique ayant des liens profonds avec les enveloppes convexes, les diagrammes de Voronoi, la localisation de points et le principe diviser pour régner.
• Trancheurs d'impression 3D et parcours d'outils CNC : la méthode Delaunay 2D (et sa variante 3D, la tétraédrisation de Delaunay) sous-tend de nombreuses stratégies de tranchage et de remplissage.

Delaunay vs Voronoi : deux faces d'une même pièce

Le diagramme de Voronoi divise le plan en une cellule par point d'entrée, où chaque cellule contient tout ce qui est plus proche de son point que de n'importe quel autre. Reliez les points dont les cellules partagent une frontière commune, et vous obtenez exactement la triangulation de Delaunay. Inversement, les centres des cercles circonscrits des triangles de Delaunay adjacents, reliés par des segments de droite, forment les arêtes de Voronoi. Activez le « duel de Voronoi » sur cet outil pour voir les lignes pointillées orange superposées sur le même graphique — chaque arête de Delaunay croise exactement une arête de Voronoi à angle droit.

Qualité, triangles étirés et raffinement de maillage

Delaunay maximise l'angle intérieur minimal global, mais il ne peut pas corriger une distribution de points fondamentalement mauvaise. Si vos points d'entrée sont presque colinéaires, regroupés ou laissent de larges régions vides, certains triangles resteront étirés (angle minimal inférieur à 20°). La solution consiste en l'insertion de points de Steiner : des algorithmes tels que l'algorithme de Ruppert et le second algorithme de Chew ajoutent de manière itérative de nouveaux points au centre du cercle circonscrit des triangles étirés, en recalculant la triangulation à chaque fois, jusqu'à ce que chaque triangle respecte une limite de qualité cible. Ce générateur vous montre quels triangles sont étirés afin que vous sachiez où ajouter des points de Steiner si vous souhaitez obtenir un maillage plus précis.

Exemple concret

Cliquez sur le préréglage « Cercle + moyeu ». L'outil place 18 points autour d'un cercle et 1 point au centre, puis les triangule. Le résultat est un éventail parfait de 18 triangles isocèles se rejoignant au moyeu — chacun ayant des angles de 10° sur le bord et de 80°–80° au centre. Le pire angle minimal est de 10°, tous les triangles sont signalés comme étirés et l'histogramme affiche l'ensemble dans la tranche 0°–10°. Cet exemple constitue un excellent cas d'école : même la triangulation optimale de Delaunay peut comporter des triangles étirés lorsque les données d'entrée les imposent. Cliquez maintenant sur « Nuage aléatoire » — le même algorithme produit des triangles bien formés car les points sont répartis uniformément, et l'histogramme se déplace vers la droite.

Idées reçues courantes

• « La triangulation de Delaunay est unique » : généralement oui, mais si quatre points d'entrée sont cocycliques (ils se situent tous sur le même cercle), il existe deux triangulations de Delaunay valides pour ce groupe. Le générateur en choisit une de manière cohérente.
• « Plus de points signifie toujours une meilleure qualité » : ajouter des points mal placés peut introduire de nouveaux triangles étirés. Les algorithmes de points de Steiner passent les nouveaux points avec soin — aux centres des cercles circonscrits — de sorte que la qualité s'améliore à coup sûr.
• « Delaunay est identique à une enveloppe convexe » : non. L'enveloppe convexe est la bordure extérieure ; la triangulation de Delaunay remplit l'intérieur avec des triangles.
• « Toutes les triangulations se ressemblent à peu près » : la différence est flagrante. Un simple basculement d'arête (edge flip) par rapport à une arête de Delaunay peut transformer un triangle de 25° en un triangle de 5°. La carte de chaleur de qualité de l'outil rend cette différence bien visible.

Foire aux questions