Wie kombiniere ich komplexe Polygone?

81

Gegeben zwei Polygone:

POLYGON((1 0, 1 8, 6 4, 1 0))
POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5))

Wie kann ich die Vereinigung berechnen (kombiniertes Polygon)?

Geben Sie hier die Bildbeschreibung ein

Daves Beispiel verwendet SQL Server, um die Union zu erstellen, aber ich muss dasselbe im Code erreichen. Ich suche nach einer mathematischen Formel oder einem Codebeispiel in einer beliebigen Sprache, die die tatsächliche Mathematik verfügbar macht. Ich versuche Karten zu erstellen, die Länder dynamisch zu Regionen zusammenfassen. Ich habe hier eine verwandte Frage gestellt: Gruppieren von geografischen Formen

Granate
quelle

Antworten:

67

Das ist eine sehr gute Frage. Ich habe vor einiger Zeit den gleichen Algorithmus auf c # implementiert. Der Algorithmus konstruiert eine gemeinsame Kontur aus zwei Polygonen (dh konstruiert eine Vereinigung ohne Löcher). Hier ist es.


Tor

Schritt 1. Erstellen Sie ein Diagramm, das die Polygone beschreibt.

Eingabe: erstes Polygon (n Punkte), zweites Polygon (m Punkte). Ausgabe: Grafik. Scheitelpunkt - Polygonpunkt des Schnittpunkts.

Wir sollten Kreuzungen finden. Durchlaufen Sie alle Polygonseiten in beiden Polygonen [O (n * m)] und finden Sie alle Schnittpunkte.

  • Wenn keine Kreuzung gefunden wird, fügen Sie einfach Scheitelpunkte hinzu und verbinden Sie sie mit der Kante.

  • Wenn Schnittpunkte gefunden werden, sortieren Sie sie nach Länge bis zu ihrem Startpunkt, fügen Sie alle Scheitelpunkte (Start, Ende und Schnittpunkte) hinzu und verbinden Sie sie (bereits in sortierter Reihenfolge) mit der Kante. Graph

Schritt 2. Überprüfen Sie das konstruierte Diagramm

Wenn wir beim Erstellen des Diagramms keine Schnittpunkte gefunden haben, haben wir eine der folgenden Bedingungen:

  1. Polygon1 enthält Polygon2 - Rückgabe von Polygon1
  2. Polygon2 enthält Polygon1 - Polygon2 zurückgeben
  3. Polygon1 und Polygon2 schneiden sich nicht. Rückgabe von Polygon1 UND Polygon2.

Schritt 3. Suchen Sie den Scheitelpunkt unten links.

Finden Sie die minimalen x- und y-Koordinaten (minx, miny). Finden Sie dann den Mindestabstand zwischen (minx, miny) und den Punkten des Polygons. Dieser Punkt ist der Punkt unten links.

Punkt unten links

Schritt 4. Konstruieren Sie eine gemeinsame Kontur.

Wir beginnen, den Graphen vom linken unteren Punkt aus zu durchlaufen und fahren fort, bis wir wieder darin sind. Zu Beginn markieren wir alle Kanten als nicht besucht. Bei jeder Iteration sollten Sie den nächsten Punkt auswählen und als besucht markieren.

Um den nächsten Punkt auszuwählen, wählen Sie eine Kante mit einem maximalen Innenwinkel gegen den Uhrzeigersinn.

Ich berechne zwei Vektoren: Vektor1 für die aktuelle Kante und Vektor2 für jede nächste nicht besuchte Kante (wie im Bild dargestellt).

Für Vektoren berechne ich:

  1. Skalarprodukt (Punktprodukt). Es gibt einen Wert zurück, der sich auf einen Winkel zwischen Vektoren bezieht.
  2. Vektorprodukt (Kreuzprodukt). Es wird ein neuer Vektor zurückgegeben. Wenn die Z-Koordinate dieses Vektors positiv ist, gibt mir das Skalarprodukt den rechten Winkel gegen den Uhrzeigersinn. Andernfalls (Z-Koordinate ist negativ) berechne ich den Abrufwinkel zwischen Vektoren als 360 - Winkel vom Skalarprodukt.

Als Ergebnis erhalte ich eine Kante (und einen entsprechenden nächsten Scheitelpunkt) mit dem maximalen Winkel.

Ich füge jeden übergebenen Scheitelpunkt zur Ergebnisliste hinzu. Ergebnisliste ist das Vereinigungspolygon. Vektoren

Bemerkungen

  1. Dieser Algorithmus ermöglicht es uns, mehrere Polygone zusammenzuführen, um sie iterativ mit Polygonpaaren anzuwenden.
  2. Wenn Sie einen Pfad haben, der aus vielen Bezierkurven und -linien besteht, sollten Sie diesen Pfad zuerst reduzieren.
xtmq
quelle
2
Ich denke, es sollte erwähnt werden, dass zum Vergleichen der Skalarprodukte die Vektoren normalisiert werden sollten, bevor ihr Skalarprodukt berechnet wird (dh die Vektorkoordinaten durch ihre Längen dividieren). Trotzdem danke für diese Antwort.
Eyalzba
Hat dieser Algorithmus einen Namen oder ist es Ihre eigene Kreation?
Andrés Oviedo
Ich habe es irgendwo gelesen, aber jetzt erinnere ich mich nicht, wo und wann =)
xtmq
HINWEIS: Siehe Polygonvereinigung ohne Löcher , die ein anderes Diagramm zeigt: Zwei Polygone überlappen sich, ABER es gibt ein "Loch", das keines von beiden abdeckt. Gemäß dem dortigen Kommentar von @ xtmq "füllt" dieser Algorithmus dieses Loch (obwohl er nicht Teil eines der Eingabepolygone ist). Wenn Sie diese Löcher stattdessen als Löcher "beibehalten" möchten, berechnen Sie (a) die Löcher und (b) geben Sie den "Satz von Löchern" zurück. [Bei einigen Grafiksystemen / -modi können diese Löcher in den Ausgangspolygonsatz aufgenommen werden und führt
ToolmakerSteve
2
... Um "(a) die Löcher zu berechnen", suchen Sie nach Punkten, die von "Schritt 4, Kontur konstruieren" nie besucht werden. Verwenden Sie einen dieser Punkte, um das Loch zu "starten". Führen Sie einen ähnlichen "Kontur" -Algorithmus aus, wobei Sie alle Punkte ausschließen, die bereits vom Hauptausgabepolygon verwendet werden. Das resultierende Polygon ist ein "Loch". Wiederholen Sie diesen Vorgang, bis ALLE Punkte in einem Polygon oder Loch enthalten sind.
ToolmakerSteve
11

Dies ist ein herausforderndes, aber gut verstandenes Thema, das häufig unter dem Namen "regulierte boolesche Operationen für Polygone" geführt wird. Sie können sich diese MathOverflow-Antwort ansehen , die die folgende Abbildung enthält (aus Alan Murtas Clipping-Bibliothek ), mit der rosa Union, die der OP kombiniert :


      BooleanOps


Joseph O'Rourke
quelle
2
Dieser Typ hat buchstäblich das Buch darüber geschrieben;)
Constantin
6

Sie müssen bestimmen, welche Punkte darin liegen . Nachdem Sie diese Punkte entfernt haben, können Sie einen Satz "äußerer" Punkte in den anderen einfügen. In Ihren Einfügepunkten (z. B. wo Sie den Pfeil im Bild rechts haben) mussten Sie Punkte aus den Eingabesätzen entfernen.

Benjamin Bannier
quelle
1
+1 für die Verknüpfung mit Bourke. Dreißig Sekunden langsamer und ich hätte dich geschlagen :)
David Seiler
4

Gute Frage! Ich habe das noch nie versucht, aber ich werde es jetzt ausprobieren.

Erstens: Sie müssen wissen, wo sich diese beiden Formen überlappen. Zu diesem Zweck können Sie jede Kante in Polygon A betrachten und sehen, wo sie sich schneidet, und jede Kante in Polygon B. In diesem Beispiel sollten zwei Schnittpunkte vorhanden sein.

Dann: Machen Sie die Verbindungsform. Sie können alle Scheitelpunkte in A und B sowie die Schnittpunkte übernehmen und dann die Scheitelpunkte ausschließen, die in der endgültigen Form enthalten sind. Um diese Punkte zu finden, könnten Sie einfach jeden Scheitelpunkt von A innerhalb von B und jeden Scheitelpunkt von B innerhalb von A finden.

FrustratedWithFormsDesigner
quelle
Ja, die eigentliche Frage ist, wie berechnen wir diese zwei hinzugefügten Schnittpunkte ?
Pacerier
2

Eine Lösung, die ich bei der Verwendung von BSP-Bäumen gesehen habe, wird hier beschrieben .

Grundsätzlich wird der Schnittpunkt als Vereinigung der Kanten des Polygons A beschrieben , die sich innerhalb des Polygons B befinden (einschließlich Teilkanten und unter Verwendung eines BSP-Baums berechnet ). Dann können Sie A  /  B als ~ (~ A  / \ ~ B ) definieren, wobei ~ das Umkehren der Wicklung des Polygons bezeichnet, / die Vereinigung bezeichnet und / \ den Schnittpunkt bezeichnet.

Nornagon
quelle
1

Wenn Sie Länder gruppieren, würde ich hoffen, dass es keine Überlappung gibt - Sie könnten einen ziemlich naiven Algorithmus verwenden, der nach gemeinsamen Scheitelpunkten sucht - eine einfache Ansicht wäre, durch die Punkte auf einem Polygon zu iterieren und zu prüfen, ob es sich um eines Ihrer anderen Polygone handelt und teilt den gleichen nächsten oder vorherigen Punkt, um festzustellen, ob eine Übereinstimmung vorliegt. Entfernen Sie dann einfach den gemeinsamen Scheitelpunkt, um Ihre Union zu erstellen

Rowland Shaw
quelle
2
"Bei der Gruppierung von Ländern würde ich hoffen, dass es keine Überschneidungen gibt" ... nicht alle Länder sind sich über ihre eigenen Grenzen oder die ihrer Nachbarn einig, obwohl es schön wäre, wenn sie dies tun würden.
FrustratedWithFormsDesigner
2
@FrustratedWithFormsDesigner in der Tat, aber die meisten Kartographen werden entweder die umstrittene Region ihrem politischen Verbündeten oder als eigenständige Einheit zuweisen - deshalb beschreibe ich meinen Algorithmus auch als naiv ...
Rowland Shaw
1

Dies ist eine sehr alte Frage, aber die Union_- Funktion von Boost hat für mich funktioniert.

Siehe diesen Ausschnitt unten:

#include <iostream>
#include <vector>

#include <boost/geometry.hpp>
#include <boost/geometry/geometries/point_xy.hpp>
#include <boost/geometry/geometries/polygon.hpp>

#include <boost/foreach.hpp>


int main()
{
    typedef boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > polygon;

    polygon green, blue;

    boost::geometry::read_wkt(
        "POLYGON((0 0, 0 10, 10 10, 10 0, 0 0))", green);

    boost::geometry::read_wkt(
        "POLYGON((5 5, 5 15, 15 15, 15 5, 5 5))", blue);

    std::vector<polygon> output;
    boost::geometry::union_(green, blue, output);

    int i = 0;
    std::cout << "green || blue:" << std::endl;
    BOOST_FOREACH(polygon const& p, output)
    {
        std::cout << i++ << ": " << boost::geometry::area(p) << std::endl;

        for (int i = 0; i < p.outer().size(); i++)
        {
            std::cout << p.outer().at(i).x() << " " << p.outer().at(i).y() << std::endl;
        }
    }



    return 0;
}
Yonatan
quelle
Denken Sie daran, Ihre Polygone bei Bedarf zu "korrigieren". Siehe stackoverflow.com/questions/22258784/…
anumi
1

Ich habe das gleiche Problem festgestellt und das Problem auf folgende Weise gelöst

Cython-Wrapper für die C ++ - Übersetzung der Clipper-Bibliothek von Angus Johnson (Version 6.4.2) https://github.com/fonttools/pyclipper

pc = pyclipper.Pyclipper()
def get_poly_union(polygons):
    pc.AddPaths(polygons, pyclipper.PT_SUBJECT, True)
    solution = pc.Execute(pyclipper.CT_UNION, pyclipper.PFT_NONZERO, pyclipper.PFT_NONZERO)
    return solution[0]

print_image = image.copy()
solution = get_poly_union(polygons_array) 
#polygons_array=[polygon,polygon,polygon, ...,polygon] and polygon=[point,point,point...,point]

cv2.drawContours(print_image, [np.asarray(solution)], -1, (0, 255, 0), 2)

plt.imshow(print_image)
Rabindra Nath Nandi
quelle
Clipper ist direkt in c ++ hier verfügbar: angusj.com/delphi/clipper.php
Catskul