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

Question

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

L'exigence est que les arêtes/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 oubliez ça pour l'instant ;) ).

Le terme mathématique pour ce que je recherche est en fait décalage de polygone vers l'intérieur/l'extérieur.+1 à Balint pour l'avoir signalé.La dénomination alternative est 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
• Décalage du polygone, PROBLÈME
• Mise en mémoire tampon des données de polygones

Answer 1

Je pensais que je pourrais mentionner brièvement ma propre découpage de polygones et d'une bibliothèque de compensation - Clipper .

Alors que Clipper est principalement conçu pour les opérations de découpage de polygones, il ne polygone compensation aussi. La bibliothèque est open source freeware écrit Delphi, C ++ et C # . Il a une Boost licence lui permettant d'être utilisé dans des applications freeware et commerciales sans frais.

Polygon La compensation peut être effectuée en utilisant l'un des trois styles offset -. Carré, rond et mitre

Answer 2

Le polygone que vous recherchez s'appelle polygone décalé vers l'intérieur/l'extérieur en géométrie computationnelle et il est étroitement lié au squelette droit.

Voici 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, en fonction de la mesure dans laquelle vous envisagez de "gonfler/dégonfler" votre polygone, vous pouvez vous retrouver avec une connectivité différente pour la sortie.

Du point de vue calcul :une fois que vous avez le squelette droit, vous devriez pouvoir construire les polygones décalés relativement facilement.L'open source et (gratuit pour les non commerciaux) CGAL La bibliothèque 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'utilisez pas CGAL, et contient des références aux articles avec les définitions et propriétés mathématiques :

Manuel CGAL :Décalage du squelette droit et du polygone 2D

Answer 3

Sons pour moi comme ce que vous voulez est:

• À partir d'un sommet, le visage anti-horaire le long d'un bord adjacent.
• Remplacer le bord avec un nouveau bord parallèle placé à une distance d à la « gauche » de l'ancien.
• Répétez l'opération pour tous les bords.
• Rechercher les intersections des nouveaux bords pour obtenir les nouveaux sommets.
• Détecter si vous êtes devenu un polygone croisé et décider ce qu'il faut faire à ce sujet. ajouter probablement un nouveau sommet au point de passage et de se débarrasser de quelques anciens. Je ne sais pas s'il y a une meilleure façon de détecter ce que juste de comparer chaque paire de bords non adjacents 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 à une distance d de l'ancien polygone est, comme vous le dites, pas un polygone, de sorte que l'exigence ne peut pas être déclaré satisfait.

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

Answer 4

Pour ce genre de choses que j'utilise habituellement JTS. Pour des fins de démonstration, j'ai créé cette jsFiddle utilise JSTS (port JavaScript de JTS). Vous avez juste besoin de convertir les coordonnées que vous avez à 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 complémentaires : Je l'habitude d'utiliser ce type de gonflage / dégonflage (un peu modifié pour mes besoins) pour fixer des limites de rayon sur les polygones qui sont tracées sur une carte (avec des cartes Dépliant ou Google) . Vous convertissez juste paires (lat, lng) pour JSTS coordonnées et tout le reste est le même. Exemple:

Answer 5

Chaque ligne doit diviser le plan à « l'intérieur » et « grandes lignes »; vous pouvez le trouver en utilisant la méthode habituelle produit intérieur.

Déplacer toutes les lignes vers l'extérieur par une certaine distance.

Considérez toutes les paires de lignes voisines (lignes, non segment de ligne), trouver l'intersection. Ce sont les nouveaux sommets.

Nettoyage du nouveau sommet en supprimant les parties entrecroisés. - nous avons quelques cas ici

(a) Cas n ° 1:

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

si vous dépensez par un, vous avez 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 dépensez par 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 si elle se chevauchent avec des segments dernier.

(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

même que affaire3, mais dépenser par deux.

En fait, si vous pouvez gérer le cas 4. Tous les autres cas sont juste cas particulier de celui-ci avec un chevauchement de ligne ou un sommet.

Pour 4 cas, vous gardez une pile de sommet .. vous poussez quand vous trouvez des lignes qui se chevauchent avec cette dernière ligne, pop quand vous obtenez la dernière ligne. - tout comme ce que vous faites dans la coque convexe

.

Answer 6

Voici une solution de rechange, voir si vous aimez mieux cela.

1. Faites un de triangulation de, il ne doit pas être delaunay -. une triangulation ferait

2. Gonfler chaque triangle - cela devrait être trivial. si vous enregistrez le triangle dans l'ordre anti-horaire, il suffit de déplacer les lignes à main côté droit et faire intersection.

3. Fusionner les utiliser une version modifiée Weiler-Atherton algorithme d'écrêtage

Answer 7

Dans le monde du SIG on utilise tampon négatif pour cette tâche: http://www-users.cs.umn.edu/~npramod/enc_pdf .pdf

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

Pour un aperçu sommaire voir aussi le Guide du développeur: http://www.vividsolutions.com/jts/bin/JTS%20Developer % 20Guide.pdf

Answer 8

Un grand merci à Angus Johnson pour sa bibliothèque de tondeuse. Il y a de bons exemples de code pour faire les choses de découpage à la page d'accueil de tondeuse à http: // www .angusj.com / delphi / clipper.php # Code mais je ne vois pas un exemple de compensation polygone. Donc, je pensais que peut-être il est d'usage pour quelqu'un si je posterai 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;
    }

Answer 9

Une autre option est d'utiliser un polygone boost :: - la documentation manque un peu, mais vous devriez constater que les méthodes resize et bloat, ainsi que l'opérateur += surchargé, qui mettent en œuvre effectivement mise en mémoire tampon. Ainsi, par exemple augmenter la taille d'un polygone (ou un ensemble de polygones) par une valeur peut être aussi simple que:

poly += 2; // buffer polygon by 2

Answer 10

Sur la base des conseils de @ JoshO'Brian, il semble que le paquet rGeos dans la langue R implémente cet algorithme. Voir rGeos::gBuffer.

Answer 11

Il y a quelques bibliothèques, on peut utiliser (également utilisables pour des 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 correspondant à 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 les fichiers OBJ.

Les meilleurs voeux, Stephan

Answer 12

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

1. A chaque coin trouver le milieu vecteur, et l'angle moyen. vecteur d'âge est la moyenne arithmétique des deux vecteurs unitaires délimités par les bords du coin. Angle d'âge est la moitié de l'angle défini par les bords.

2. Si vous avez besoin d'élargir (ou contrat) polygone par la quantité de d de chaque bord; vous devriez sortir (en) par la quantité d / sin (midAngle) pour obtenir le nouveau point d'angle.

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

*** Faites attention à votre direction. Faire de test en utilisant les trois Sens contraire points définissant le coin; pour savoir de quelle manière est hors ou dans.