Ci-dessous, quelques définition relatives à la triangulation et à ses usages. La plupart des définitions sont tirées de wikipédia. Un prochain article comparera quelques outils proposant des triangulations de Delaunay et des diagrammes de Voronoï.
Triangulation : En géométrie, une triangulation est une façon de découper une forme géométrique (un plan, un polygone) en une collection de triangles (pour approfondir, voir wikipedia).
Triangulation de Delaunay : 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" (pour approfondir, voir wikipedia)
Utilisation : Pour modéliser un terrain ou d’autres objets à partir d’un ensemble de points donnés, la triangulation de Delaunay fourni un bon ensemble de triangles qui pourront ensuite être utilisés comme polygones dans le modèle.
Triangulation contrainte : lors de la construction d’un modèle de terrain par triangulation, on a souvent besoin d’introduire des contraintes sous forme de lignes ne devant pas être coupées par une arête de la triangulation. Les courbes de niveau et les lignes de rupture de pente sont généralement introduites comme lignes de contrainte.
Lignes de contraintes et critère de Delaunay : Il y a deux façons d’introduire des lignes de contraintes dans une triangulation de Delaunay. Dans la première, on perd localement la propriété de Delaunay aux alentours de la ligne de contrainte. Dans la deuxième, on introduit de nouveaux points le long des lignes de contrainte de manière à conserver le caractère de Delaunay.
Amélioration des MNT obtenus par triangulation : Lorsqu’on modélise un terrain par triangulation, on voit apparaître des triangles plats (horizontaux) qui ne devraient pas l’être :
triangle plats couvrant la courbe sommet lorsque le sommet n’est pas marqué par un point coté.
triangles plats au creux des talweg lorsque ceux-ci ne sont pas materialisés par une ligne de contrainte
triangles plats s’appuyant sur trois points consécutifs d’une courbe de niveau alors que tout triangle dont un coté suit une courbe de niveau devrait avoir sont sommet opposé à une altitude différente.
Différents moyens sont mis en oeuvre pour essayer de résoudre ces difficultés et d’affiner la représentation du terrain.
Diagramme de Voronoï : En mathématiques, un diagramme de Voronoï est une décomposition particulière d’un espace métrique déterminée par les distances à un ensemble discret d’objets de l’espace (pour approfondir, voir wikipedia).
On appelle région de Voronoï ou cellule de Voronoï associée à un élément p de S l’ensemble des points qui sont plus proches de p que de tout autre point de S.
La triangulation de Delaunay d’un ensemble discret P de points est le graphe dual du diagramme de Voronoï associé à P.
Les diagrammes de Voronoï sont utilisés, ou réinventés sous de nombreux noms, dans différents domaines. Ils interviennent souvent lorsque l’on cherche à partitionner l’espace en sphères d’influence.
RSS 2.0