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

Wie würde ich das "aufblasen" eines Polygons? Das heißt, ich will etwas tun, ähnlich wie diese:

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

Voraussetzung ist, dass die neue (aufgeblasen) polygon-Kanten/Punkte sind alle mit der gleichen Konstanten Abstand von der alten (original -) polygon (auf dem Beispiel-Bild sind Sie nicht, denn dann müsste es arcs für überhöhten Ecken, aber vergessen wir das für jetzt 😉 ).

Der mathematische Begriff für das, was ich Suche, ist eigentlich nach innen/nach außen polygon offseting. +1 balint für den Hinweis. Die alternative Benennung ist polygon Pufferung.

Ergebnisse meiner Suche:

Hier sind einige links:

InformationsquelleAutor der Frage Igor Brejc | 2009-07-10

116

Dachte ich, ich könnte kurz erwähnen, meine eigene polygon-clipping und Verrechnung Bibliothek - Clipper.

Während Clipper ist in Erster Linie für polygon-clipping-Operationen, es tut polygon Aufrechnung zu. Die Bibliothek ist open-source-freeware geschrieben Delphi, C++ und C#. Es hat eine sehr unbelastet Steigern Lizenz ermöglicht es, verwendet werden, in beiden freeware-und kommerzielle Anwendungen ohne Gebühr.

Polygon Aufrechnung durchgeführt werden kann mit einem von drei offset-Stile - Quadrat -, rund-und Gehrung.

InformationsquelleAutor der Antwort Angus Johnson
34

Des Polygons, die Sie suchen, heißt inward/outward offset polygon in der "computational geometry" und es ist eng mit der straight-skeleton.

Diese werden mehrere offset-Polygone für eine komplizierte polygon:

- Und dies ist der gerade das Gerüst für ein weiteres polygon:

Wie bereits in anderen Kommentaren, als auch, je nachdem, wie weit Sie planen, "inflate/deflate" das polygon können Sie am Ende mit unterschiedlichen Anschlüssen für die Ausgabe.

Berechnung von point-of-view: hat man einmal den straight-skeleton-man sollte in der Lage sein zu konstruieren, die offset-Polygone relativ leicht. Die open-source und (kostenlos für nicht-kommerzielle) CGAL Bibliothek hat ein Paket der Umsetzung dieser Strukturen. Sehen dieses code-Beispiel zu berechnen offset-Polygone mit CGAL.

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

CGAL-Handbuch: 2D-Straight-Skeleton-und Polygon Offsetting

InformationsquelleAutor der Antwort balint.miklos
7

Klingt für mich wie das, was Sie wollen, ist:
- Beginnend an einer Ecke, das Gesicht gegen den Uhrzeigersinn entlang einer angrenzenden Kante.
- Ersetzen Sie die Kante mit einer neuen, parallelen Kante platziert im Abstand d auf die "Links" des alten.
- Wiederholen Sie dies für alle Kanten.
- Finden die Schnittpunkte der neuen Kanten, um die neuen vertices.
- Erkennen, wenn Sie sich schon gekreuzt Polynom und entscheiden, was zu tun ist. Wahrscheinlich fügen Sie einen neuen Eckpunkt an der Kreuzung-Punkt und loszuwerden, einige alte. Ich bin mir nicht sicher, ob es einen besseren Weg, um dies zu erkennen, als nur zu vergleichen zu jedem paar von nicht benachbarten Kanten, um zu sehen, wenn Ihre Schnittmenge liegt zwischen den beiden Paaren der Scheitelpunkte.
Das resultierende polygon liegt auf den erforderlichen Abstand von der alten polygon "weit genug" von den vertices. In der Nähe einer Ecke, die Menge aller Punkte im Abstand d von der alten polygon ist, wie Sie sagen, nicht ein polygon, also die Voraussetzung, wie gesagt, kann nicht erfüllt werden.

Ich weiß nicht, ob dieser Algorithmus hat einen Namen, Beispiel-code auf dem web, oder eine teuflische Optimierung, aber ich denke, es beschreibt das, was Sie wollen.

InformationsquelleAutor der Antwort Steve Jessop
7

Ich nie benutzt Clipper (entwickelt von Angus Johnson), aber für diese Arten von Dinge, die ich in der Regel verwenden JTS. Zur demonstration habe ich diesen jsFiddle verwendet JSTS (JavaScript-port von JTS). Sie müssen nur konvertieren der Koordinaten, die Sie haben, um JSTS Koordinaten:
```
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 so etwas wie dieses:

Zusätzliche info: ich verwende in der Regel diese Art von aufblasen/ablassen der Luft (ein wenig modifiziert für meine Zwecke) für Grenzen setzen, mit radius auf Polygonen, die gezeichnet werden auf einer Karte (mit Leaflet oder Google maps). Sie einfach konvertieren (lat,lng) - Paare JSTS Koordinaten und alles andere ist gleich. Beispiel:

InformationsquelleAutor der Antwort Marko Letic
5

Jeder Zeile sollten, teilen Sie die Ebene "innen" und "Gliederung"; Sie finden diese unter Verwendung der üblichen inneren-Produkt-Methode.

Verschieben Sie alle Zeilen, die nach außen mit Abstand.

Berücksichtigen Sie alle paar von benachbarten Linien (die Linien, nicht die Linie, segment) finden Sie die Kreuzung. Das sind die neuen vertex.

Bereinigung der neue Eckpunkt entfernen Sie alle Schnitt-Teile. - wir haben ein paar hier

(a) Fall 1:
```
 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2
```
wenn Sie verbrauchen es durch, du hast diese:
```
0----a----3
|    |    |
|    |    |
|    b    |
|         |
|         |
1---------2
```
7 und 4 überschneiden sich.. wenn Sie sehen, entfernen Sie diesen Punkt und alle Punkte zwischen.

(b) Fall 2
```
 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2
```
wenn Sie aufwenden, es von beiden, Sie haben diese:
```
0----47----3
|    ||    |
|    ||    |
|    ||    |
|    56    |
|          |
|          |
|          |
1----------2
```
diese zu lösen, für jedes segment der Linie, die Sie haben zu prüfen, ob es überschneidungen mit den letzteren Segmenten.

(c) Fall 3
```
       4--3
 0--X9 |  |
 |  78 |  |
 |  6--5  |
 |        |
 1--------2
```
aufwenden, um 1. dies ist ein allgemeiner Fall für Fall 1.

(d) Fall 4

gleiche wie case3, sondern verbrauchen durch zwei.

Eigentlich, wenn Sie behandeln können, Fall 4. Alle anderen Fälle sind nur spezielle Fall mit irgendeiner Linie oder einer Ecke überschneiden.

Tun Fall 4 halten Sie einen Stapel von vertex.. Sie schieben, wenn Sie finden, die Linien überschneiden sich mit letzterer Linie, pop es, wenn Sie die vorige Zeile. -- gerade wie, was Sie tun, convex-hull.

InformationsquelleAutor der Antwort J-16 SDiZ
5

Hier ist eine alternative Lösung finden Sie, wenn Sie dieses besser.
1. Tun triangulationes nicht zu delaunay-jede triangulation tun würde.
2. Aufblasen jedes Dreieck-das sollte trivial sein. wenn Sie speichern Sie das Dreieck in der anti-Uhrzeigersinn, bewegen Sie einfach die Linien auf der rechten Seite und tun Schnittpunkt.
3. Mischen Sie Sie mit einem modifizierten Weiler-Atherton-clipping-Algorithmus
InformationsquelleAutor der Antwort J-16 SDiZ
5

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

Den JTS-Bibliothek sollte dies für Sie tun. Finden Sie in der Dokumentation für die Puffer-Betrieb: http://tsusiatsoftware.net/jts/javadoc/com/vividsolutions/jts/operation/buffer/package-summary.html

Für eine übersicht, siehe auch die Handbuch für Entwickler:
http://www.vividsolutions.com/jts/bin/JTS%20Developer%20Guide.pdf

InformationsquelleAutor der Antwort stryeko

Großen Dank an Angus Johnson für seine clipper-Bibliothek.
Es gibt gute code-Beispiele für das tun des clipping-Zeug auf die clipper-homepage http://www.angusj.com/delphi/clipper.php#code
aber ich wollte nicht sehen, ein Beispiel für die polygon offsetting. Also ich dachte, dass vielleicht es ist von nutzen für jemanden, wenn ich mein 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;
    }

InformationsquelleAutor der Antwort PainElemental

1

Basierend auf den Rat von @JoshO ' Brian, es erscheint die rGeos Paket in der R Sprache implementiert diesen Algorithmus. Sehen rGeos::gBuffer .

InformationsquelleAutor der Antwort Carl Witthoft
1

Eine weitere option ist die Verwendung boost::polygon - die Dokumentation ist etwas fehlt, aber Sie sollten feststellen, dass die Methoden resize und bloatund auch die überladene += Betreiber, welche auch tatsächlich umzusetzen Pufferung. So zum Beispiel die Erhöhung der Größe der ein polygon (oder einen Satz von Polygonen), die von einigen Wert kann so einfach sein wie:
```
poly += 2; //buffer polygon by 2
```
InformationsquelleAutor der Antwort Paul R
0

Gibt es ein paar Bibliotheken, die man nutzen kann (Auch verwendbar für 3D-Datensätze).
Findet man auch entsprechende Publikationen für die Bibliotheken zu verstehen, die algorithmen im detail.

Den letzten hat man die wenigsten Abhängigkeiten und ist in sich abgeschlossen und kann Lesen .obj-Dateien.

Die besten Wünsche,
Stephan

InformationsquelleAutor der Antwort Stephan M. G.

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.