Wie würde ich ein Polygon "aufblasen"? Das heißt, ich möchte etwas Ähnliches tun:
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:
Antworten:
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.
quelle
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
quelle
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:
Das Ergebnis ist ungefähr so:
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:
quelle
Klingt für mich so, als ob Sie Folgendes wollen:
d
"links" von der alten platziert ist.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 Entfernung
d
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.
quelle
In der GIS-Welt verwendet man für diese Aufgabe eine negative Pufferung: http://www-users.cs.umn.edu/~npramod/enc_pdf.pdf
Die JTS-Bibliothek sollte dies für Sie tun. Weitere Informationen zum Puffervorgang finden Sie in der Dokumentation: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html
Eine grobe Übersicht finden Sie auch im Entwicklerhandbuch: http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf
quelle
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:
Wenn Sie es um eins ausgeben, haben Sie Folgendes:
7 und 4 überlappen sich. Wenn Sie dies sehen, entfernen Sie diesen Punkt und alle Punkte dazwischen.
(b) Fall 2
Wenn Sie es zu zweit ausgeben, haben Sie Folgendes:
Um dies zu beheben, müssen Sie für jedes Liniensegment prüfen, ob es sich mit letzteren Segmenten überschneidet.
(c) Fall 3
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.
quelle
Hier ist eine alternative Lösung, um zu sehen, ob Ihnen das besser gefällt.
Machen Sie eine Triangulation , es muss keine Verzögerung sein - jede Triangulation würde reichen.
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.
Führen Sie sie mit einem modifizierten Weiler-Atherton-Clipping-Algorithmus zusammen
quelle
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:
quelle
Eine weitere Möglichkeit ist die Verwendung boost :: Polygon - die Dokumentation etwas fehlt, aber Sie sollten feststellen , dass die Methoden
resize
undbloat
, 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:quelle
+=
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).Basierend auf den Ratschlägen von @ JoshO'Brian scheint das
rGeos
Paket in derR
Sprache diesen Algorithmus zu implementieren. SieherGeos::gBuffer
.quelle
Es gibt einige Bibliotheken, die verwendet werden können (auch für 3D-Datensätze verwendbar).
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
quelle
Ich benutze einfache Geometrie: Vektoren und / oder Trigonometrie
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.
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.
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.
quelle