Algorithmes de décompositions convexes de polygones
La classe PolygonMeshBuilder contient l’ensemble des fonctions permettant d’effectuer une décomposition en parties convexes (majoritairement des triangles) d’un polygone 2D (avec ou sans parties évidées). Les fonctionnalités les plus avancées de cette classe utilisent les algorithmes de triangulation de la librairie JTS.
Les entrées/sorties génériques des fonctions de décomposition sont :
- Entrée : IGeometry
- Sortie : IMultiSurface<GM_Polygon>
1) TRIANGULATE : ‘’triangulation’’ simple sans ajouter de vertices
2) MAKECONVEX : partitionnement en ensembles convexes (majoritairement
à base de triangles (triangulation jusqu’à ce que la surface résultante
soit convexe)
3) GENERATEMESH : partitionnements paramétrables à l’aide des
triangulations contraintes de JTS
 |
 |
IMultiSurface<GM_Polygon> partitionConvexe = makeConvex(polygon);Cet algorithme simple et fonctionnel (à base de décomposition à partir des “oreilles” du polygone) présente l’avantage de ne pas être dépendant de la triangulation contrainte de JTS, instable dès lors que le nombre de sommets et relativement élevé et donc inutilisable sur des polygones complexes. En revanche, l’irrégularité des triangles de la décomposition (parfois quasi-plats) peut poser des problèmes de stabilité numérique dans la suite des traitements, auquel cas il faudra préférentiellement utiliser les algorithmes plus évolués décrits ci-dessous.
 |
 |
// Pas de sur-échantillonnage des vertices du maillage
PolygonMeshBuilder.setOverSampling(false);
// Calcul de la partition
IMultiSurface<GM_Polygon> partitionConvexe = generateMesh(polygon);La “régularité” du partitionnement est assurée par une triangulation de Delaunay contrainte des sommets du polygone.
 |
 |
// Sur-échantillonnage des vertices du maillage
PolygonMeshBuilder.setOverSampling(true);
// Paramètres : grille régulière / résolution 5 m
PolygonMeshBuilder.setGridGeneration(PolygonMeshBuilder.REGULAR_GRID);
PolygonMeshBuilder.setSamplingResolution(5.0);
// Calcul de la partition
IMultiSurface<GM_Polygon> partitionConvexe = generateMesh(polygon); |
 |
// Sur-échantillonnage des vertices du maillage
PolygonMeshBuilder.setOverSampling(true);
// Paramètres : grille irrégulière aléatoire / résolution 5 m
PolygonMeshBuilder.setGridGeneration(PolygonMeshBuilder.RANDOM_GRID);
PolygonMeshBuilder.setSamplingResolution(5.0);
// Calcul de la partition
IMultiSurface<GM_Polygon> partitionConvexe = generateMesh(polygon);Dans cet algorithme, la paramètre de “résolution” est telle que la
densité de sur-échantillonnage globale est identique à celle d’un
maillage régulier de même résolution.
Par exemple, une résolution de 1 m appliquée à un sur-échantillonnage
aléatoire d’un polygone carré de côté 10 m produira un maillage de
partitionnement contenant 100 points.
 |
 |
// Sur-échantillonnage des vertices du maillage
PolygonMeshBuilder.setOverSampling(true);
// Paramètres : grille irrégulière adaptative / résolution 5 m
PolygonMeshBuilder.setGridGeneration(PolygonMeshBuilder.ADAPTIVE_GRID);
PolygonMeshBuilder.setSamplingResolution(5.0);
// Calcul de la partition
IMultiSurface<GM_Polygon> partitionConvexe = generateMesh(polygon);Cet algorithme est requis lorsque l’on désire une modélisation fine des
frontières du polygones sans accroître inutilement le nombres de parties
de la décomposition.
Le paramètre “résolution” correspond à la résolution de niveau moyen :
résolution max = 0.5 x samplingResolution (sur les bords) et résolution
min = 1.5 x samplingResolution (au centre).
 |
 |
Le paramètre de tolérance (réel entre 0 et 1, par défaut égal à 0.001) permet d’éviter les problèmes d’erreurs numériques lors des tests d’inclusion des parties issues de la décomposition dans le polygone d’origine au niveau des frontières. A titre d’exemple, une valeur de 0.001 indique une incertitude numérique sur l’erreur de calcul d’aire de l’ordre de 0.1% de la surface totale du polygone à décomposer. Dans l’éventualité où un résultat incorrect soit obtenu en sortie de l’algorithme, il est important de tester d’augmenter légèrement cette valeur de tolérance.
