Triangulation de Delaunay & Polygones de Voronoï

Construction de la Triangulation de Delauney
 

La triangulation réalisée est telle que pour un set P de points du plan, aucun point de P n'est à l'intérieur de la circonférence d'un autre triangle. Cette opération permet d'éviter les triangles fins et maximise la valeur minimale des angles des triangles.

Ceux ci ont des formes irrégulières, ce qui donne en anglais pour ces ensembles le terme plus connu de Triangulated Irregular Network (Réseau de Triangles Irréguliers), raccourci en TIN.

Développé par Peucker, le modèle TIN prend en compte les variabilités des phénomènes, notamment l'altitude, avec un nombre minimal de points, densifiés aux endroits de brusque changement.

Son avantage est son faible encombrement (rendu en vecteur) et sa simplicité.

Fig. 1 : la figure (a) satisfait à ce critère, tandis que la (b) ne le respecte pas.

Construction des Diagrammes de Voronoï

Mathématiquement, ils sont définis par les bissectrices des angles perpendiculairement aux lignes des triangles de Delauney créés précédemment entre toutes les points.

Ces polygones sont aussi connus sous le nom de tesselation de Dirichlet.

Basée sur des critères de voisinages (partitionnment géométrique) simples elle construit une parcellisation du domaine d’étude. Chaque polygone (cellule) contient un et un seul point de l’échantillon, l’ensemble des points de l’espace appartenant à la cellule a pour plus proche voisin le point d’échantillonnage associé à la cellule. La valeur du point échantillonné est associée à tous les points de la parcelle ou cellule. Cette approche est semblable à la triangulation. Les limites sont évidentes, car il y a de brusques saut de discontinuité.

Fig. 2 : en noir les triangles de Delauney, en rouge les polygones de Voronoï.


Polygones de Thiessen 

Les diagrammes de Voronoï tiennent leur nom  du mathématicien Georgy F. Voronoï qui a définit et étudié le cas général sur n-dimensions en 1908. Ils sont aussi utilisés en géophysique et en météorologie pour analyser les données régionalisées comme les mesures de pluie, où ils sont alors appelés polygones de Thiessen, d'après l'américain Alfred H. Thiessen. On les retrouve dans d'autres domaines, comme la cristallographie ou la mesure des espaces, sous d'autres noms.