Triangulations
Définition et premiers exemples
Dans toute cette page, lorsqu'il sera question d'un ensemble de points $E$ du plan, on supposera que $E$ contient au moins 3 points, et qu'ils ne sont pas tous alignés.
Une triangulation d'un polygone est un découpage de
ce polygone en triangles. Une triangulation d'un ensemble de points $E$
est une triangulation de l'enveloppe convexeL'ensemble des barycentres à coefficients positifs de points de $E$. de $E$ pour
laquelle les sommets des triangles sont exactement les
points de $E$.
Calculer une telle triangulation est un problème important en informatique - il permet par exemple d'obtenir des maillages de surfaces, outil de base en modélisation (où l'on approche une surface continue par un ensemble fini de triangles, permettant d'utiliser des méthodes de type «éléments finis»), ou encore en infographie. On trouve également des applications en robotiquePour décomposer l'espace dans lequel se déplace un robot par exemple. ou en vision par ordinateur.
Nous nous placerons dans le plan dans cette page, même si certains des concepts dont il sera question se généralisent sur des surfaces, ou en dimension supérieure.
Voici un premier algorithme naïf, et illustré ci-dessous, calculant une triangulation d'un $E$ ensemble de points.
On commence par trianguler les points situés sur le bord de
l'enveloppe convexe Il y a de nombreux algorithmes pour trouver ces points - par exemple l'algorithme de Jarvis. Les trianguler est ensuite algorithmiquement simple..
Puis on rajoute séquentiellement les autres points de
l'ensemble $E$ - dans un ordre aléatoire. Pour chaque
ajout d'un nouveau point $p$, on cherche le triangle de la
triangulation précédente contenant $p$. Pour construire la
nouvelle triangulation, on relie alors simplement $p$ aux
3 sommets de ce triangle.
Pour voir cet
algorithme en action, cliquez sur le bouton ci-dessous, et
observer la «mauvaise triangulation».
Points à trianguler
Mauvaise triangulation
Bonne triangulation
Comme on peut l'observer, la triangulation obtenue est mauvaise, surtout comparée à la bonne. Mais comme nous faisons de l'informatique, et non pas de la chasse à la Galinette cendrée, il va falloir expliquer un peu plus précisément la différence entre une bonne et une mauvaise triangulation...
Bonnes et mauvaises triangulations
Une triangulation est généralement faite pour approcher de façon discrète une figure polygonale du plan. Dans de nombreuses applications, il est nécessaire de préserver une certaine notion de localité : deux points reliés dans la triangulation ne devraient pas être trop éloignés spatialement.De plus, en simulation, la présence d'angles très obtus dans la triangulation peut poser des problèmes numériques.
L'ennemi est désigné : il s'agit des triangles trop «aplatis», i.e. contenant des angles trop obtus ou trop aigus. C'est ici qu'intervient la triangulation de Delaunay.
Une triangulation de $E$ est dite de
Delaunay si pour tout triangle $t$ de la triangulation,
aucun point de $E$ n'est (strictement) à l'intérieur du
cercle circonscrit à $t$
C'est une façon de garantir qu'il n'y aura pas d'angles
trop obtus dans la triangulation. Considérons les figures
suivantes (sur lesquelles vous pouvez déplacer les
points). La triangulation dans la figure de gauche n'est
pas de Delaunay. Un peu de
géométrieL'argument clef consiste à montrer que le fait que les 2 sommets soient à l'intérieur du cercle circonscrit du triangle en vis-à-vis (comme sur la figure de gauche) est équivalent au fait que la somme des angles des triangles en ces 2 points soit supérieure à $\pi$. montre que l'on peut la transformer en une
triangulation de Delaunay en basculant l'arête centrale -
on obtient alors la triangulation de droite. On remarque
égalementC'est encore de la géométrie du triangle ! que, ce faisant, l'angle minimal présent dans la
triangulation a augmenté.
Non-Delaunay
Arête basculée : Delaunay
Finesse d'une triangulation
On définit la finesse d'une triangulation $\mathcal{T}$ comme le vecteur $(a_1\dots a_{3t})$, où les $a_i$ sont les angles des triangles de $\mathcal{T}$, classés par ordre croissant.
On peut alors montrer à partir des remarques précédentes
la propriété suivante.
On définit la finesse d'une triangulation $\mathcal{T}$ comme le vecteur $(a_1\dots a_{3t})$, où les $a_i$ sont les angles des triangles de $\mathcal{T}$, classés par ordre croissant.
Soit $E$ un ensemble de points. Alors,
parmi toutes les triangulations possibles, une
triangulation qui maximise la finesse (pour l'ordre
lexicographique) est une triangulation de Delaunay.
Ceci a des conséquences importantes:
- Une triangulation de Delaunay maximise les angles en un certain sens : c'est une «bonne» triangulation, qui va éviter les angles trop aigus (et donc trop obtus également).
- Pour tout ensemble de points $E$ (non tous alignés), une triangulation de Delaunay existeEn effet, il n'y a qu'un nombre fini de triangulations d'un ensemble de points donné. Il en existe donc au moins une qui maximise la finesse, et c'est une triangulation de Delaunay d'après la proposition précédente..
- On dispose d'un algorithme pour la calculer. Partant d'une triangulation quelconque, on bascule ses arêtes tant que c'est possible, jusqu'à obtention d'une triangulation de DelaunayLe même argument que dans la remarque précédente prouve que cela termine. .
On commence par trianguler les points situés sur le bord de
l'enveloppe convexe.
Puis on rajoute séquentiellement les autres points de l'ensemble $E$ - dans un ordre aléatoire. Pour chaque ajout d'un nouveau point $p$, on cherche le triangle de la triangulation précédente contenant $p$. Pour construire la nouvelle triangulation, on relie alors $p$ aux 3 sommets de ce triangle, puis l'on bascule des arêtes tant que c'est possible pour construire une triangulation Delaunay.
On peut montrer que cela conduit à un algorithme de complexité $O(n\log(n))$ avec une implémentation soigneuseSur cette page, je me suis contenté de O(n^2)..
Puis on rajoute séquentiellement les autres points de l'ensemble $E$ - dans un ordre aléatoire. Pour chaque ajout d'un nouveau point $p$, on cherche le triangle de la triangulation précédente contenant $p$. Pour construire la nouvelle triangulation, on relie alors $p$ aux 3 sommets de ce triangle, puis l'on bascule des arêtes tant que c'est possible pour construire une triangulation Delaunay.
À noter que l'on peut également prouver l'unicité de la triangulation de Delaunay, dans le cas où les points sont en position généraleC'est-à-dire s'il n'y a pas 4 points cocycliques - sinon, essayez de comprendre ce qui peut se passer en vous aidant de l'application ci-dessus.. Dans ce cas, la triangulation de Delaunay produite par l'algorithme ci-dessus ne dépend donc pas de l'ordre dans lequel sont rajoutés les points.
L'application ci-dessous permet de visualiser des triangulations de Delaunay.
- Cliquez pour ajouter ou enlever un sommet
- Cliquez/tirer pour déplacer un sommet existant
Diagramme de Voronoi
Partant d'une triangulation de Delaunay d'un ensemble de points $E$, plaçons les centres des cercles circonscrits de chaque triangle, et relions par des arêtes ceux qui sont dans des triangles adjacents de la triangulation. On obtient ainsi le diagramme de Voronoi de l'ensemble de points - que vous pouvez visualiser dans l'application ci-dessus.Il s'agit d'un ensemble de cellules, contenant chacune exactement un point de l'ensemble $E$, qui vérifient les deux propriétés suivantes.
- Les bords des cellules sont constitués de segments inclus dans des médiatrices de points de $E$ voisins dans la triangulation de Delaunay. Les points des bords des cellules sont donc équidistants d'au moins 2 points de $E$.
- L'intérieur de la cellule contenant $s\in E$ est l'ensemble des points du plan strictement plus proche de $s$ que de tout autre point de $E$.
Elles permettent également de modéliser des phénomènes de croissances spatiale : si l'on considère $E$ comme un ensemble de «graines» qui s'étendent (à même vitesse dans toutes les directions), les points de rencontre des graines seront leur diagramme de Voronoi. C'est ce que l'on observe par exemple sur le pelage de la Girafe réticulée.
Pour aller plus loin
- Géométrie algorithmique (Boissonnat et Yvinec) - Ediscience, 2002. Cet excellent livre présente toutes les notions fondamentales de géométrie algorithmique de façon précise. Une large partie est consacrée aux triangulations de Delaunay et aux diagrammes de Voronoi.
- La page wikipedia sur les triangulations de Delaunay.
- La page wikipedia sur les diagrammes de Voronoï.