Un algorithme pour gonfler / dégonfler (décalage, mise en mémoire tampon) des polygones

Je pensais pouvoir mentionner brièvement ma propre bibliothèque de coupures et de décalages de polygones – Clipper .

Bien que Clipper soit principalement conçu pour les opérations de découpage de polygones, il effectue également la compensation des polygones. La bibliothèque est un logiciel gratuit open source écrit en Delphi, C ++ et C # . Il possède une licence Boost très peu encombrée lui permettant d’être utilisé à la fois dans des applications gratuites et commerciales.

Le décalage des polygones peut être effectué en utilisant l’un des trois styles de décalage – carré, rond et à tabs.

Le polygone que vous recherchez est appelé polygone décalé vers l’intérieur / l’extérieur en géomésortinge de calcul et il est étroitement lié au squelette droit .

Ce sont plusieurs polygones décalés pour un polygone compliqué:

Et voici le squelette droit d’un autre polygone:

Comme indiqué dans d’autres commentaires, selon la mesure dans laquelle vous prévoyez de «gonfler / dégonfler» votre polygone, vous pouvez vous retrouver avec une connectivité différente pour la sortie.

Du sharepoint vue du calcul: une fois que vous avez le squelette droit, vous devriez pouvoir construire les polygones décalés relativement facilement. La bibliothèque open source et (gratuite pour les applications non commerciales) CGAL a un package mettant en œuvre ces structures. Voir cet exemple de code pour calculer les polygones de décalage à l’aide de CGAL.

Le manuel du package doit vous donner un bon sharepoint départ pour construire ces structures même si vous n’utilisez pas CGAL et contient des références aux articles avec les définitions et les propriétés mathématiques suivantes:

Manuel CGAL: Squelette 2D et décalage polygonal

J’ai l’impression que ce que vous voulez c’est:

• En partant d’un sumt, faites face au sens inverse des aiguilles d’une montre le long d’un bord adjacent.
• Remplacez le bord par un nouveau bord parallèle placé à la distance d sur la “gauche” de l’ancien.
• Répétez pour tous les bords.
• Trouvez les intersections des nouvelles arêtes pour obtenir les nouveaux sumts.
• Détecter si vous êtes devenu un polynôme croisé et décider quoi faire. Ajoutez probablement un nouveau sumt au sharepoint croisement et débarrassez-vous de certains anciens. Je ne suis pas sûr qu’il existe un meilleur moyen de détecter cela que de simplement comparer chaque paire d’arêtes non adjacentes pour voir si leur intersection se situe entre les deux paires de sumts.

Le polygone résultant se trouve à la distance requirejse de l’ancien polygone «assez loin» des sumts. Comme vous le dites, près d’un sumt, l’ensemble des points situés à une distance d de l’ancien polygone n’est pas un polygone. Par conséquent, l’exigence énoncée ne peut être satisfaite.

Je ne sais pas si cet algorithme a un nom, un exemple de code sur le Web, ou une optimisation diabolique, mais je pense que cela décrit ce que vous voulez.

Je n’ai jamais utilisé Clipper (développé par Angus Johnson), mais pour ce genre de choses, j’utilise généralement JTS . A des fins de démonstration, j’ai créé ce jsFiddle qui utilise JSTS (port JavaScript de JTS). Il vous suffit de convertir les coordonnées que vous avez en coordonnées JSTS:

 function vectorCoordinates2JTS (polygon) { var coordinates = []; for (var i = 0; i < polygon.length; i++) { coordinates.push(new jsts.geom.Coordinate(polygon[i].x, polygon[i].y)); } return coordinates; } 

Le résultat est quelque chose comme ceci:

Informations supplémentaires : j'utilise généralement ce type de gonflage / dégonflage (un peu modifié pour mes besoins) pour définir des limites avec un rayon sur des polygones dessinés sur une carte (avec Leaflet ou Google maps). Vous convertissez simplement (lat, lng) des paires en coordonnées JSTS et tout le rest est identique. Exemple:

Chaque ligne doit diviser le plan en “intérieur” et “contour”; vous pouvez le trouver en utilisant la méthode habituelle du produit interne.

Déplacez toutes les lignes vers l’extérieur d’une certaine distance.

Considérez toutes les paires de lignes voisines (lignes, pas le segment de ligne), trouvez l’intersection. Ce sont les nouveaux sumts.

Nettoyez le nouveau sumt en supprimant les parties qui se croisent. – nous avons quelques cas ici

a) Cas 1:

  0--7 4--3 | | | | | 6--5 | | | 1--------2 

si vous en dépensez un, vous avez ceci:

 0----a----3 | | | | | | | b | | | | | 1---------2 

7 et 4 se chevauchent .. si vous voyez ceci, vous supprimez ce point et tous les points intermédiaires.

b) cas 2

  0--7 4--3 | | | | | 6--5 | | | 1--------2 

si vous en dépensez deux, vous avez ceci:

 0----47----3 | || | | || | | || | | 56 | | | | | | | 1----------2 

pour résoudre ce problème, pour chaque segment de ligne, vous devez vérifier s’il chevauche les derniers segments.

c) cas 3

  4--3 0--X9 | | | 78 | | | 6--5 | | | 1--------2 

dépenser par 1. Ceci est un cas plus général pour le cas 1.

d) cas 4

comme cas3, mais dépenser deux.

En fait, si vous pouvez gérer le cas 4. Tous les autres cas ne sont que des cas particuliers avec un chevauchement des lignes ou des sumts.

Pour faire le cas 4, vous conservez une stack de sumts .. vous poussez lorsque vous trouvez des lignes qui se chevauchent avec la dernière ligne, faites-la apparaître lorsque vous obtenez la dernière ligne. – comme ce que vous faites en shell convexe.

Voici une solution alternative, voyez si cela vous convient mieux.

1. Faire une sortingangulation , il ne doit pas être delaunay – toute sortingangulation ferait.

2. Gonflez chaque sortingangle – cela devrait être sortingvial. Si vous stockez le sortingangle dans le sens contraire des aiguilles d’une montre, déplacez simplement les lignes vers la droite et faites une intersection.

3. Fusionnez-les à l’aide d’un algorithme de découpage de Weiler-Atherton modifié

Dans le monde des SIG, on utilise une mémoire tampon négative pour cette tâche: http://www-users.cs.umn.edu/~npramod/enc_pdf.pdf

La bibliothèque JTS devrait le faire pour vous. Voir la documentation de l’opération de tampon: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html

Pour une vue d’ensemble, voir également le Guide du développeur: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf

Un grand merci à Angus Johnson pour sa bibliothèque Clipper. Il y a de bons exemples de code pour faire les trucs sur la page d’accueil de clipper sur http://www.angusj.com/delphi/clipper.php#code mais je n’ai pas vu d’exemple de compensation de polygones. Alors j’ai pensé que peut-être que ça sert à quelqu’un si je poste mon code:

  public static List GetOffsetPolygon(List originalPath, double offset) { List resultOffsetPath = new List(); List polygon = new List(); foreach (var point in originalPath) { polygon.Add(new ClipperLib.IntPoint(point.X, point.Y)); } ClipperLib.ClipperOffset co = new ClipperLib.ClipperOffset(); co.AddPath(polygon, ClipperLib.JoinType.jtRound, ClipperLib.EndType.etClosedPolygon); List> solution = new List>(); co.Execute(ref solution, offset); foreach (var offsetPath in solution) { foreach (var offsetPathPoint in offsetPath) { resultOffsetPath.Add(new Point(Convert.ToInt32(offsetPathPoint.X), Convert.ToInt32(offsetPathPoint.Y))); } } return resultOffsetPath; } 

D’après les conseils de @ JoshO’Brian, il semble que le package rGeos du langage R implémente cet algorithme. Voir rGeos::gBuffer .

Une autre option consiste à utiliser boost :: polygon – la documentation manque quelque peu, mais vous devriez trouver que les méthodes resize et bloat , ainsi que l’opérateur surchargé += , qui implémente réellement la mise en mémoire tampon. Ainsi, par exemple, l’augmentation de la taille d’un polygone (ou d’un ensemble de polygones) peut être aussi simple que:

 poly += 2; // buffer polygon by 2 

Il existe plusieurs bibliothèques que vous pouvez utiliser (également utilisable pour les ensembles de données 3D).

1. https://github.com/otherlab/openmesh
2. https://github.com/alecjacobson/nested_cages
3. http://homepage.tudelft.nl/h05k3/Projects/MeshThickeningProj.htm

On peut également trouver des publications correspondantes pour que ces bibliothèques comprennent les algorithmes plus en détail.

Le dernier a les moins de dépendances et est autonome et peut lire dans les fichiers .obj.

Meilleurs voeux, Stephan