Un algorithme pour gonfler / dégonfler (compenser, tamponner) les polygones

Comment "gonfler" un polygone? Autrement dit, je veux faire quelque chose de similaire à ceci:

La condition est que les bords / points du nouveau polygone (gonflé) soient tous à la même distance constante de l'ancien polygone (d'origine) (sur l'image d'exemple, ils ne le sont pas, car il faudrait alors utiliser des arcs pour les sommets gonflés, mais disons oublie ça pour l'instant;)).

Le terme mathématique pour ce que je recherche est en fait un décalage de polygone vers l'intérieur / vers l'extérieur . +1 à balint pour l'avoir signalé. L'autre dénomination est la mise en mémoire tampon des polygones .

Résultats de ma recherche:

Voici quelques liens:

• Une enquête sur les stratégies de compensation des polygones
• Offset polygone, PROBLÈME
• Mise en mémoire tampon des données de polygone

J'ai pensé que je pourrais mentionner brièvement ma propre bibliothèque de découpage et de compensation de polygones - Clipper .

Alors que Clipper est principalement conçu pour les opérations de découpage de polygone, il effectue également la compensation de polygone. La bibliothèque est un logiciel gratuit open source écrit en Delphi, C ++ et C # . Il possède une licence Boost très libre qui lui permet d'être utilisé à la fois gratuitement et dans des applications commerciales.

Le décalage de polygone peut être effectué en utilisant l'un des trois styles de décalage - carré, rond et à onglet.

Le polygone que vous recherchez est appelé polygone de décalage vers l'intérieur / vers l'extérieur dans la géométrie 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, également, 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 point de 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 CGAL open source et (gratuite pour les non-commerciaux) dispose d'un package implémentant ces structures. Voir cet exemple de code pour calculer des polygones décalés à l'aide de CGAL.

Le manuel du paquet devrait vous donner un bon point de départ sur la façon de construire ces structures même si vous n'allez pas utiliser CGAL, et contient des références aux articles avec les définitions et propriétés mathématiques:

Manuel CGAL: Squelette droit 2D et décalage de polygone

Pour ces types de choses, j'utilise habituellement JTS . À 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é à mes fins) pour définir des limites de rayon sur des polygones dessinés sur une carte (avec Leaflet ou Google maps). Vous convertissez simplement les paires (lat, lng) en coordonnées JSTS et tout le reste est le même. Exemple:

Cela me semble être ce que vous voulez:

• En partant d'un sommet, faites face dans le sens inverse des aiguilles d'une montre le long d'un bord adjacent.
• Remplacez le bord par un nouveau bord parallèle placé à distance dà la "gauche" de l'ancien.
• Répétez pour tous les bords.
• Trouvez les intersections des nouvelles arêtes pour obtenir les nouveaux sommets.
• Détectez si vous êtes devenu un polygone croisé et décidez quoi faire à ce sujet. Ajoutez probablement un nouveau sommet au point de croisement et supprimez les anciens. Je ne sais pas s'il existe un meilleur moyen de détecter cela que de comparer chaque paire d'arêtes non adjacentes pour voir si leur intersection se situe entre les deux paires de sommets.

Le polygone résultant se trouve à la distance requise de l'ancien polygone "assez loin" des sommets. Près d'un sommet, l'ensemble des points à distance dde l'ancien polygone n'est pas, comme vous le dites, un polygone, de sorte que l'exigence telle qu'énoncée ne peut pas être remplie.

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

Dans le monde SIG, on utilise une mise en 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 un aperçu approximatif, voir également le Guide du développeur: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf

Chaque ligne doit diviser l'avion en "intérieur" et "contour"; vous pouvez le découvrir 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 segment de ligne), trouvez l'intersection. Ce sont le nouveau sommet.

Nettoyez le nouveau sommet en supprimant toutes les parties qui se croisent. - nous avons quelques cas ici

a) Cas 1:

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

si vous le dépensez par un, vous obtenez ceci:

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

7 et 4 se chevauchent .. si vous voyez cela, vous supprimez ce point et tous les points entre les deux.

b) cas 2

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

si vous le dépensez par deux, vous obtenez 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 avec ces derniers segments.

c) cas 3

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

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

d) cas 4

comme cas 3, mais dépenser par deux.

En fait, si vous pouvez gérer le cas 4. Tous les autres cas ne sont que des cas spéciaux avec un chevauchement de ligne ou de sommet.

Pour faire le cas 4, vous gardez une pile de vertex. - tout comme ce que vous faites en coque convexe.

Voici une solution alternative, voyez si vous préférez cela.

1. Faites une triangulation , cela n'a pas besoin d'être retardé - n'importe quelle triangulation ferait l'affaire.

2. Gonflez chaque triangle - cela devrait être trivial. si vous stockez le triangle dans le sens inverse des aiguilles d'une montre, déplacez simplement les lignes vers la droite et faites l'intersection.

3. Fusionnez-les en utilisant un algorithme de découpage Weiler-Atherton modifié

Un grand merci à Angus Johnson pour sa bibliothèque de tondeuses. Il existe de bons exemples de code pour effectuer les coupures sur la page d'accueil de clipper à http://www.angusj.com/delphi/clipper.php#code mais je n'ai pas vu d'exemple de décalage de polygone. J'ai donc pensé que cela pourrait être utile à quelqu'un si je poste mon code:

    public static List<Point> GetOffsetPolygon(List<Point> originalPath, double offset)
    {
        List<Point> resultOffsetPath = new List<Point>();

        List<ClipperLib.IntPoint> polygon = new List<ClipperLib.IntPoint>();
        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<List<ClipperLib.IntPoint>> solution = new List<List<ClipperLib.IntPoint>>();
        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;
    }

Une autre option consiste à utiliser boost :: polygon - la documentation fait quelque peu défaut, mais vous devriez trouver que les méthodes resizeet bloat, et également l' +=opérateur surchargé , qui implémentent en fait la mise en mémoire tampon. Ainsi, par exemple, augmenter la taille d'un polygone (ou d'un ensemble de polygones) d'une certaine valeur peut être aussi simple que:

poly += 2; // buffer polygon by 2

Sur la base des conseils de @ JoshO'Brian, il semble que le rGeospackage dans le Rlangage implémente cet algorithme. Tu vois rGeos::gBuffer.

Il existe quelques bibliothèques que l'on peut 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 ces bibliothèques pour comprendre les algorithmes plus en détail.

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

Meilleurs voeux, Stephan

J'utilise une géométrie simple: vecteurs et / ou trigonométrie

1. À chaque coin, trouvez le vecteur médian et l'angle médian. Le vecteur médian est la moyenne arithmétique des deux vecteurs unitaires définis par les bords du coin. L'angle moyen est la moitié de l'angle défini par les bords.

2. Si vous avez besoin d'agrandir (ou de contracter) votre polygone de la quantité de d de chaque bord; vous devez sortir (in) du montant d / sin (midAngle) pour obtenir le nouveau point de coin.

3. Répétez cette opération pour tous les coins

*** Faites attention à votre direction. Faites le test CounterClockWise en utilisant les trois points définissant le coin; pour savoir quelle voie est sortie ou vers l'intérieur.