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

201

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

Alt-Text

Die Anforderung besteht darin, dass die Kanten / Punkte des neuen (aufgeblasenen) Polygons alle den gleichen konstanten Abstand zu den alten (ursprünglichen) Polygonen haben (auf dem Beispielbild nicht), da dann Bögen für aufgeblasene Eckpunkte verwendet werden müssten, aber lassen Sie uns vergiss das erstmal;)).

Der mathematische Begriff für das, wonach ich suche, ist tatsächlich das Versetzen von Polygonen nach innen / außen . +1 auf balint, um darauf hinzuweisen. Die alternative Benennung ist die Polygonpufferung .

Ergebnisse meiner Suche:

Hier sind einige Links:

Igor Brejc
quelle
17
Dies ist überhaupt keine triviale Frage: Wenn die Deflation / Inflation gering ist, passiert nichts Ernstes, aber irgendwann verschwinden die Eckpunkte. Wahrscheinlich wurde dies schon einmal gemacht, also würde ich sagen: Verwenden Sie den Algorithmus eines anderen, bauen Sie keinen eigenen.
Martijn
1
Wenn Ihr Polygon zunächst konkav ist (wie im obigen Beispiel), müssen Sie entscheiden, was an dem Punkt geschehen soll, an dem der naive Algorithmus ein sich selbst überschneidendes 'Polygon'
erstellen
Ja, das Hauptproblem sind die konkaven Teile des Polygons. Hier liegt die Komplexität. Ich denke immer noch, dass es kein Problem sein sollte zu berechnen, wann ein bestimmter Scheitelpunkt eliminiert werden muss. Die Hauptfrage ist, welche Art von asymptotischer Komplexität dies erfordern würde.
Igor Brejc
Hallo, das ist auch mein Problem, außer ich muss dies in 3D tun. Gibt es eine Alternative zum Ansatz der geraden Skelette dreidimensionaler Polyeder, der im Artikel arxiv.org/pdf/0805.0022.pdf beschrieben ist ?
stephanmg

Antworten:

137

Ich dachte, ich könnte kurz meine eigene Bibliothek zum Ausschneiden und Versetzen von Polygonen erwähnen - Clipper .

Während Clipper hauptsächlich für das Beschneiden von Polygonen konzipiert ist, wird auch das Versetzen von Polygonen durchgeführt. Die Bibliothek ist Open Source Freeware, geschrieben in Delphi, C ++ und C # . Es hat einen sehr unbelasteten Boost Lizenz, mit der es sowohl in Freeware- als auch in kommerziellen Anwendungen kostenlos verwendet werden kann.

Das Versetzen von Polygonen kann mit einem von drei Versatzstilen durchgeführt werden - quadratisch, rund und auf Gehrung.

Polygon-Versatzstile

Angus Johnson
quelle
2
Sehr cool! Wo warst du vor 2 Jahren? :) Am Ende musste ich meine eigene Gegenlogik implementieren (und verlor dabei viel Zeit). Welchen Algorithmus verwenden Sie übrigens für die Polygonverschiebung? Ich habe Grasfeuer benutzt. Behandeln Sie Löcher in Polygonen?
Igor Brejc
2
Vor 2 Jahren suchte ich nach einer anständigen Lösung für das Ausschneiden von Polygonen, die nicht mit kniffligen Lizenzproblemen belastet war :). Der Kantenversatz wird erreicht, indem Einheitennormalen für alle Kanten erzeugt werden. Kantenverbindungen werden von meinem Polygon-Clipper aufgeräumt, da die Ausrichtungen dieser überlappenden Schnittpunkte der Ausrichtung der Polygone entgegengesetzt sind. Löcher werden mit Sicherheit genauso behandelt wie sich selbst schneidende Polygone usw. Es gibt keine Einschränkungen hinsichtlich ihres Typs oder ihrer Anzahl. Siehe auch "Polygonversatz durch Berechnung der Wicklungszahlen" hier: me.berkeley.edu/~mcmains/pubs/DAC05OffsetPolygon.pdf
Angus Johnson
Whoa! Denken Sie keine Sekunde lang, dass diese Frage "vergessen" ist! Ich habe letzte Woche hier gesucht - ich hatte nicht erwartet, darauf zurückzukommen! Vielen Dank!
Chris Burt-Brown
Clippers Dokumente zur Poly-Pufferung sind hier: angusj.com/delphi/clipper/documentation/Docs/Units/ClipperLib/…
Drew Noakes
5
Für alle, die dies tun möchten, ist die Verwendung von GEOS eine weitere Alternative. Wenn Sie Python verwenden, ist Shapely, der Wrapper von GEOS. Ein wirklich hübsches Beispiel: toblerity.github.com/shapely/manual.html#object.buffer
pelson
40

Das gesuchte Polygon wird in der Rechengeometrie als nach innen / außen versetztes Polygon bezeichnet und ist eng mit dem geraden Skelett verwandt .

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

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

Wie bereits in anderen Kommentaren erwähnt, kann es je nachdem, wie weit Sie Ihr Polygon "aufblasen / entleeren" möchten, zu unterschiedlichen Konnektivitäten für die Ausgabe kommen.

Aus rechnerischer Sicht: Sobald Sie das gerade Skelett haben, sollten Sie in der Lage sein, die versetzten Polygone relativ einfach zu konstruieren. Die Open Source und (kostenlos für nichtkommerzielle) CGAL- Bibliothek enthält ein Paket, das diese Strukturen implementiert. In diesem Codebeispiel können Sie versetzte Polygone mit CGAL berechnen.

Das Pakethandbuch 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-Versatz für gerades Skelett und Polygon

balint.miklos
quelle
11

Für diese Art von Dingen verwende ich normalerweise JTS . Zu Demonstrationszwecken habe ich diese jsFiddle erstellt , die JSTS (JavaScript-Port von JTS) verwendet. Sie müssen nur die Koordinaten, die Sie haben, 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:

Geben Sie hier die Bildbeschreibung ein

Zusätzliche Informationen : Normalerweise verwende ich diese Art des Aufblasens / Entleerens (für meine Zwecke etwas modifiziert), um Grenzen mit Radius für Polygone festzulegen, die auf einer Karte gezeichnet sind (mit Broschüre oder Google Maps). Sie konvertieren einfach (lat, lng) Paare in JSTS-Koordinaten und alles andere ist gleich. Beispiel:

Geben Sie hier die Bildbeschreibung ein

Marko Letic
quelle
9

Klingt für mich so, als ob Sie Folgendes wollen:

  • Beginnen Sie an einem Scheitelpunkt und zeigen Sie gegen den Uhrzeigersinn entlang einer angrenzenden Kante.
  • Ersetzen Sie die Kante durch eine neue, parallele Kante, die im Abstand d"links" von der alten platziert ist.
  • Wiederholen Sie dies für alle Kanten.
  • Suchen Sie die Schnittpunkte der neuen Kanten, um die neuen Scheitelpunkte zu erhalten.
  • Erkennen Sie, ob Sie ein gekreuztes Polygon geworden sind, und entscheiden Sie, was Sie dagegen tun möchten. Fügen Sie wahrscheinlich einen neuen Scheitelpunkt am Kreuzungspunkt hinzu und entfernen Sie einige alte. Ich bin mir nicht sicher, ob es einen besseren Weg gibt, dies zu erkennen, als jedes Paar nicht benachbarter Kanten zu vergleichen, um festzustellen, ob ihr Schnittpunkt zwischen beiden Scheitelpunktpaaren liegt.

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

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

Steve Jessop
quelle
5

Jede Linie sollte die Ebene in "innen" und "Umriss" aufteilen. 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 von Nachbarlinien (Linien, kein Liniensegment) und finden Sie den Schnittpunkt. Dies sind die neuen Eckpunkte.

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

(a) Fall 1:

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

Wenn Sie es um eins 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 zweit ausgeben, haben Sie Folgendes:

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

Um dies zu beheben, 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 um 1. Dies ist ein allgemeinerer Fall für Fall 1.

(d) Fall 4

wie Fall3, aber um zwei ausgeben.

Eigentlich, wenn Sie mit Fall 4 umgehen können. Alle anderen Fälle sind nur Sonderfälle mit einer Überlappung von Linien oder Scheitelpunkten.

Um Fall 4 auszuführen, behalten Sie einen Scheitelpunktstapel bei. Wenn Sie Linien finden, die sich mit der letzteren Linie überlappen, drücken Sie, wenn Sie die letztere Linie erhalten. - Genau wie bei einer konvexen Hülle.

J-16 SDiZ
quelle
Kennen Sie einen Psedo-Algorithmus dafür?
EmptyData
5

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

  1. Machen Sie eine Triangulation , es muss keine Verzögerung sein - jede Triangulation würde reichen.

  2. Blasen Sie jedes Dreieck auf - dies sollte trivial sein. Wenn Sie das Dreieck gegen den Uhrzeigersinn speichern, verschieben Sie die Linien einfach nach rechts und schneiden Sie sie.

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

J-16 SDiZ
quelle
Wie bläst man die Dreiecke genau auf? Hängt Ihre Ausgabe von der Triangulation ab? Können Sie mit diesem Ansatz den Fall behandeln, wenn Sie das Polygon verkleinern?
balint.miklos
Sind Sie sicher, dass dieser Ansatz wirklich für die Polygoninflation funktioniert? Was passiert, wenn die konkaven Teile des Polygons so weit aufgeblasen werden, dass einige Eckpunkte entfernt werden müssen? Die Sache ist: Wenn Sie schauen, was mit Dreiecken nach Poly passiert. Inflation werden die Dreiecke nicht aufgeblasen, sondern verzerrt.
Igor Brejc
1
Igor: Der Weiler-Atherton-Clipping-Algorithmus kann den Fall "Einige Eckpunkte müssen beseitigt werden" korrekt behandeln.
J-16 SDiZ
@balint: Ein Dreieck aufzublasen ist trivial: Wenn Sie den Vertrex in normaler Reihenfolge speichern, ist die rechte Seite immer "nach außen". Behandeln Sie diese Liniensegmente einfach als Linien, verschieben Sie sie nach außen und finden Sie die Interaktion - sie sind der neue Scheitelpunkt. Für die Triangulation selbst kann bei einem zweiten Gedanken die Delaunay-Triangulation ein besseres Ergebnis liefern.
J-16 SDiZ
4
Ich denke, dieser Ansatz kann leicht zu schlechten Ergebnissen führen. Auch für ein einfaches Beispiel als Quad mit einer Diagonale trianguliert. Für die beiden vergrößerten Dreiecke erhalten Sie: img200.imageshack.us/img200/2640/counterm.png und ihre Vereinigung ist einfach nicht das, wonach Sie suchen. Ich sehe nicht, wie nützlich diese Methode ist.
balint.miklos
3

Vielen Dank an Angus Johnson für seine Clipper-Bibliothek. Auf der Clipper-Homepage unter http://www.angusj.com/delphi/clipper.php#code gibt es gute Codebeispiele für das Clipping-Material, aber ich habe kein Beispiel für das Versetzen von Polygonen gesehen. Also dachte ich, dass es vielleicht für jemanden von Nutzen 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;
    }
PainElemental
quelle
2

Eine weitere Möglichkeit ist die Verwendung boost :: Polygon - die Dokumentation etwas fehlt, aber Sie sollten feststellen , dass die Methoden resizeund bloat, und auch der überladenen +=Operator, der tatsächlich Pufferung implementieren. So kann beispielsweise das Erhöhen der Größe eines Polygons (oder einer Reihe von Polygonen) um einen bestimmten Wert so einfach sein wie:

poly += 2; // buffer polygon by 2
Paul R.
quelle
Ich verstehe nicht, wie Sie etwas mit boost :: polygon machen sollen, da es nur ganzzahlige Koordinaten unterstützt? Angenommen, ich habe ein allgemeines Polygon (Gleitkommakoordinaten) und möchte es erweitern. Was würde ich tun?
David Doria
@DavidDoria: Dies hängt davon ab, welche Auflösung / Genauigkeit und welchen Dynamikbereich Sie für Ihre Koordinaten benötigen. Sie können jedoch auch ein 32-Bit- oder 64-Bit-Int mit einem geeigneten Skalierungsfaktor verwenden. Übrigens habe ich in der Vergangenheit (versehentlich) boost :: polygon mit Gleitkoordinaten verwendet und es scheint in Ordnung zu funktionieren, aber es ist möglicherweise nicht 100% robust (die Dokumente warnen davor!).
Paul R
Ich wäre in Ordnung mit "es wird die meiste Zeit funktionieren" :). Ich habe es versucht: ideone.com/XbZeBf, aber es wird nicht kompiliert - irgendwelche Gedanken?
David Doria
Ich sehe offensichtlich nichts Falsches, aber in meinem Fall habe ich die geradlinigen Spezialisierungen (polygon_90) verwendet, sodass ich nicht weiß, ob dies einen Unterschied macht. Es ist allerdings ein paar Jahre her, seit ich damit herumgespielt habe.
Paul R
OK - es kommt jetzt auf mich zurück - Sie können nur +=mit einem Polygonsatz verwenden , nicht mit einzelnen Polygonen. Versuchen Sie es mit einem std :: -Vektor von Polygonen. (Natürlich muss der Vektor nur ein Polygon enthalten).
Paul R
1

Basierend auf den Ratschlägen von @ JoshO'Brian scheint das rGeosPaket in der RSprache diesen Algorithmus zu implementieren. Siehe rGeos::gBuffer.

Carl Witthoft
quelle
0

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 Veröffentlichungen für diese Bibliotheken finden, um die Algorithmen genauer zu verstehen.

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

Beste Grüße, Stephan

stephanmg
quelle
0

Ich benutze einfache Geometrie: Vektoren und / oder Trigonometrie

  1. Finden Sie an jeder Ecke den mittleren Vektor und den mittleren Winkel. Der mittlere Vektor ist der arithmetische Durchschnitt der beiden Einheitsvektoren, die durch die Kanten der Ecke definiert sind. Der mittlere Winkel ist die Hälfte des durch die Kanten definierten Winkels.

  2. Wenn Sie Ihr Polygon von jeder Kante um den Betrag d 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. Führen Sie einen CounterClockWise-Test mit den drei Punkten durch, die die Ecke definieren. um herauszufinden, welcher Weg raus oder rein ist.

user2800464
quelle