wake-up-neo.com

Ein Algorithmus zum Aufblasen/Entleeren (Versetzen, Puffern) von Polygonen

Wie würde ich ein Polygon "aufblasen"? Das heißt, ich möchte etwas Ähnliches machen: 

alt text

Die Anforderung ist, dass die Kanten/Punkte des neuen (aufgeblasenen) Polygons alle im gleichen konstanten Abstand zu den alten (ursprünglichen) Polygonen liegen (im Beispielbild sind sie dies nicht, da dann Bögen für aufgeblasene Scheitelpunkte verwendet werden müssten, aber lass uns vergiss das erstmal;)). 

Der mathematische Begriff für das, wonach ich suche, ist eigentlich innen/außen Polygonversatz. +1, um dies zu zeigen. Die alternative Benennung ist Polygon-Pufferung.

Ergebnisse meiner Suche:

Hier sind einige Links:

179
Igor Brejc

Ich dachte, ich könnte kurz meine eigene polygon-Clipping- und Offset-Bibliothek - Clipper erwähnen.

Während Clipper hauptsächlich für Polygon-Clipping-Operationen konzipiert ist, werden auch Polygon-Offsets ausgeführt. Die Bibliothek ist Open Source Freeware, die in Delphi, C++ und C # geschrieben ist. Es verfügt über eine sehr unbeschränkte Boost - Lizenz, die es erlaubt, sowohl in Freeware als auch in kommerziellen Anwendungen kostenlos zu verwenden. 

Der Polygonversatz kann mit einem von drei Versatzstilen durchgeführt werden - quadratisch, rund und mit Gehrung.

Polygon offsetting styles

125
Angus Johnson

Das Polygon, nach dem Sie suchen, wird in der Berechnungsgeometrie nach innen/außen versetztes Polygon genannt und steht in enger Beziehung zum straight-Skelett .

Dies sind mehrere versetzte Polygone für ein kompliziertes Polygon:

Und das ist das gerade Skelett für ein anderes Polygon:

Wie bereits in anderen Kommentaren dargelegt, können Sie abhängig davon, wie weit Sie Ihr Polygon "aufpumpen/entlüften" möchten, unterschiedliche Konnektivität für die Ausgabe haben. 

Aus rechnerischer Sicht: Sobald Sie das gerade Skelett haben, sollten Sie die versetzten Polygone relativ leicht konstruieren können. Die Open Source- und (für nicht-kommerzielle) Bibliothek CGAL enthält ein Paket, das diese Strukturen implementiert. Siehe dieses Codebeispiel , um Offset-Polygone mit CGAL zu berechnen.

Das package-Handbuch sollte Ihnen einen guten Ausgangspunkt für die Erstellung dieser Strukturen geben, auch wenn Sie CGAL nicht verwenden, und enthält Verweise auf die Artikel mit den mathematischen Definitionen und Eigenschaften:

CGAL-Handbuch: 2D-Skelett- und Polygon-Offset

37
balint.miklos

Klingt für mich wie das, was Sie wollen:

  • Beginnen Sie an einem Scheitelpunkt und blicken Sie entlang einer angrenzenden Kante gegen den Uhrzeigersinn.
  • Ersetzen Sie die Kante durch eine neue, parallele Kante, die sich im Abstand d von der "linken" der alten befindet.
  • Wiederholen Sie dies für alle Kanten.
  • Suchen Sie die Schnittpunkte der neuen Kanten, um die neuen Scheitelpunkte zu erhalten.
  • Finden Sie heraus, ob Sie ein gekreuztes Polynom geworden sind und entscheiden Sie, was Sie dagegen tun sollen. Fügen Sie wahrscheinlich an der Kreuzungsstelle einen neuen Scheitelpunkt hinzu und entfernen Sie einige alte. Ich bin nicht sicher, ob es einen besseren Weg gibt, dies zu erkennen, als nur jedes Paar nicht benachbarter Kanten zu vergleichen, um zu sehen, ob deren Schnittpunkt zwischen beiden Scheitelpaaren liegt.

Das resultierende Polygon liegt im erforderlichen Abstand vom alten Polygon "weit genug" von den Scheitelpunkten entfernt. In der Nähe eines Scheitelpunkts ist die Menge der Punkte in einem Abstand d vom alten Polygon, wie Sie sagen, kein Polygon, daher kann die angegebene Anforderung nicht erfüllt werden.

Ich weiß nicht, ob dieser Algorithmus einen Namen, Beispielcode im Web oder eine teuflische Optimierung hat, aber ich denke, er beschreibt, was Sie wollen.

8
Steve Jessop

Für diese Art von Dingen benutze ich normalerweise JTS . Zu Demonstrationszwecken habe ich dieses jsFiddle erstellt, das JSTS (JavaScript-Port von JTS) verwendet. Sie müssen nur die Koordinaten in JSTS-Koordinaten konvertieren:

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;
}

Das Ergebnis ist ungefähr so:

 enter image description here

Zusatzinfo: Normalerweise verwende ich diese Art des Aufblasens/Entlüftens (ein wenig modifiziert für meine Zwecke), um Grenzen mit dem Radius von Polygonen festzulegen, die auf einer Karte (mit Leaflet- oder Google-Karten) gezeichnet sind. Sie konvertieren (lat, lng) -Paare einfach in JSTS-Koordinaten und alles andere ist gleich. Beispiel:

 enter image description here

7
Marko Letic

Jede Linie sollte die Ebene in "Innen" und "Umriss" teilen. Sie können dies mit der üblichen Methode des inneren Produkts herausfinden.

Bewegen Sie alle Linien um ein Stück nach außen. 

Betrachten Sie alle Paare benachbarter Linien (Linien, nicht Liniensegment) und suchen Sie den Schnittpunkt. Dies ist der neue Scheitelpunkt.

Bereinigen Sie den neuen Scheitelpunkt, indem Sie sich überschneidende Teile entfernen. - Wir haben hier ein paar Fälle

a) Fall 1:

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

wenn Sie es nach dem anderen ausgeben, haben Sie Folgendes:

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

7 und 4 überlappen sich. Wenn Sie dies sehen, entfernen Sie diesen Punkt und alle Punkte dazwischen.

(b) Fall 2

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

wenn Sie es zu zwei ausgeben, haben Sie Folgendes:

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

um dies aufzulösen, müssen Sie für jedes Liniensegment prüfen, ob es sich mit letzteren Segmenten überschneidet.

(c) Fall 3

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

ausgaben bis 1. Dies ist ein allgemeinerer Fall für Fall 1.

(d) Fall 4

wie bei case3, aber mit zwei ausgeben.

Eigentlich, wenn Sie mit Fall 4 umgehen können. Alle anderen Fälle sind nur ein Sonderfall, bei dem sich einige Linien oder Scheitelpunkte überschneiden.

Für Fall 4 behalten Sie einen Stapel Scheitelpunkt. Sie drücken, wenn Sie Linien finden, die sich mit letzterer Linie überlappen, und platzieren Sie ihn, wenn Sie die letzte Zeile erhalten. - so wie Sie es im konvexen Rumpf machen.

5
J-16 SDiZ

Hier ist eine alternative Lösung, um zu sehen, ob Ihnen das besser gefällt.

  1. Machen Sie eine Triangulation , es muss kein Delaunay sein - jede Triangulation würde es tun.

  2. Blase jedes Dreieck auf - das sollte trivial sein. Wenn Sie das Dreieck im Gegenuhrzeigersinn speichern, verschieben Sie die Linien einfach nach rechts und machen einen Schnittpunkt.

  3. Füge sie mit einem modifizierten Weiler-Atherton-Clipping-Algorithmus zusammen

5
J-16 SDiZ

In der GIS-Welt wird für diese Aufgabe eine negative Pufferung verwendet: http://www-users.cs.umn.edu/~npramod/enc_pdf.pdf

Die JTS-Bibliothek sollte dies für Sie tun. Informationen zur Pufferoperation finden Sie in der Dokumentation: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html

Einen groben Überblick finden Sie auch im Developer Guide: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf

5
stryeko

Ein großes Dankeschön geht an Angus Johnson für seine Clipper-Bibliothek ... Es gibt gute Codebeispiele für das Clipping auf der Clipper-Homepage unter http://www.angusj.com/delphi/clipper.php#code Ich habe jedoch kein Beispiel für das Versetzen von Polygonen gesehen. Also dachte ich, dass es für jemanden nützlich ist, wenn ich meinen Code poste:

    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;
    }
3
PainElemental

Basierend auf den Empfehlungen von @ JoshO'Brian scheint das rGeos-Paket in der R-Sprache diesen Algorithmus zu implementieren. Siehe rGeos::gBuffer.

1
Carl Witthoft

Eine weitere Option ist die Verwendung von boost :: polygon - die Dokumentation fehlt etwas, aber Sie sollten feststellen, dass die Methoden resize und bloat sowie der überladene +=-Operator, der die Pufferung implementiert. Das Erhöhen der Größe eines Polygons (oder einer Gruppe von Polygonen) um einen bestimmten Wert kann beispielsweise so einfach sein:

poly += 2; // buffer polygon by 2
1
Paul R

Es gibt einige Bibliotheken, die verwendet werden können (auch für 3D-Datensätze verwendbar).

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

Man kann auch entsprechende Publikationen für diese Bibliotheken finden, um die Algorithmen genauer zu verstehen.

Der letzte hat die geringsten Abhängigkeiten und ist in sich abgeschlossen und kann OBJ-Dateien einlesen.

Beste Wünsche, Stephan

0
Stephan M. G.

Ich benutze einfache Geometrie: Vektoren und/oder Trigonometrie

  1. Suchen Sie an jeder Ecke den mittleren Vektor und den mittleren Winkel. Der mittlere Vektor ist das arithmetische Mittel der beiden Einheitsvektoren, die durch die Eckenränder definiert sind. Mittelwinkel ist die Hälfte des Winkels, der durch die Kanten definiert wird.

  2. Wenn Sie Ihr Polygon um den Betrag von d von jeder Kante aus erweitern (oder verkleinern) müssen; Sie sollten um den Betrag d/sin (midAngle) hinausgehen, um den neuen Eckpunkt zu erhalten.

  3. Wiederholen Sie dies für alle Ecken

*** Sei vorsichtig mit deiner Richtung. Machen Sie CounterClockWise Test mit den drei Punkten, die die Ecke definieren; herauszufinden, welcher Weg raus oder rein ist.

0
user2800464