Wie kombiniere ich komplexe Polygone?

Das ist eine sehr gute Frage. Ich habe vor einiger Zeit denselben Algorithmus in c # implementiert. Der Algorithmus konstruiert eine gemeinsame Kontur aus zwei Polygonen (d. H. Konstruiert eine Vereinigung ohne Löcher). Hier ist es.

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

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

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

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

• Wenn Schnittpunkte gefunden werden, sortieren Sie diese nach Länge bis zum Startpunkt, fügen Sie alle Knoten (Start-, End- und Schnittpunkte) hinzu und verbinden Sie sie (bereits in der Reihenfolge ) Mit dem Edge .

Schritt 2. Überprüfen Sie die erstellte Grafik

Wenn beim Erstellen des Diagramms keine Schnittpunkte gefunden wurden, liegt eine der folgenden Bedingungen vor:

1. Polygon1 enthält Polygon2 - Rückgabepolygon1
2. Polygon2 enthält Polygon1 - Rückgabepolygon2
3. Polygon1 und Polygon2 schneiden sich nicht. Rückgabe polygon1 AND polygon2. 

Schritt 3. Finden Sie den linken unteren Scheitelpunkt.

Ermitteln Sie die minimalen x- und y-Koordinaten (minx, miny). Dann ermitteln Sie den Mindestabstand zwischen (Minx, Miny) und den Polygonpunkten. Dieser Punkt wird der Punkt ganz links sein. 

Schritt 4. Erstellen Sie eine gemeinsame Kontur.

Wir beginnen, den Graphen vom linken unteren Punkt aus zu durchqueren und fahren fort, bis wir wieder hinein kommen. Am Anfang markieren wir alle Kanten als nicht besucht. Bei jeder Wiederholung sollten Sie den nächsten Punkt auswählen und als besucht markieren. 

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

Ich berechne zwei Vektoren: vector1 für die aktuelle Kante und vector2 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 einen rechten Winkel in Entgegen dem Uhrzeigersinn. Sonst (z-Koordinate ist negativ), I Berechnen Sie den Winkel zwischen Vektoren als 360 - Winkel vom Skalar Produkt.

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

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

Bemerkungen

1. Mit diesem Algorithmus können wir mehrere Polygone zusammenführen, um sie iterativ mit den Polygonpaaren anzuwenden.
2. Wenn Sie einen Pfad haben, der aus vielen Bezier-Kurven und -Linien besteht, sollten Sie diesen Pfad zuerst reduzieren.

Dies ist ein herausforderndes, aber gut verstandenes Thema, das häufig unter dem Namen "Regularisierte Boolesche Operationen auf Polygonen" geführt wird. Sie können sich diese MathOverflow-Antwort ansehen, das die folgende Abbildung enthält (aus Alan Murtas Schnittbibliothek ), mit der pinkfarbenen Vereinigung der OPs kombinieren :

Sie müssen bestimmen, welche Punkte in liegen. Nach dem Entfernen dieser Punkte können Sie einen Satz "Außenpunkte" in den anderen einfügen. An den Einfügepunkten (z. B. wo sich der Pfeil rechts im Bild befindet) mussten Sie Punkte aus den Eingabesätzen entfernen.

Gute Frage! Ich habe das noch nie versucht, aber ich werde jetzt einen Riss darauf werfen.

Erstens: Sie müssen wissen, wo sich diese beiden Formen überlappen. Um dies zu tun, können Sie jede Kante in Polygon A und die Schnittpunkte und Kante in Polygon B sehen. In diesem Beispiel sollten zwei Schnittpunkte vorhanden sein.

Dann: Machen Sie die Vereinigungsform. Sie können alle Scheitelpunkte in A und B sowie die Schnittpunkte nehmen und dann die Scheitelpunkte ausschließen, die in der endgültigen Form enthalten sind. Um diese Punkte zu finden, sieht es so aus, als könnten Sie einfach einen Scheitelpunkt von A finden, der sich in B befindet, und einen Scheitelpunkt von B, der sich in A befindet.

Versuchen Sie gpc .

Eine Lösung, die ich mit BSP-Bäumen gesehen habe, ist hier .

Grundsätzlich beschreibt es den Schnittpunkt als Vereinigung der Kanten des Polygons A, die sich innerhalb des Polygons B befinden (einschließlich Teilkanten und mit einem BSP-Baum berechnet). Dann können Sie A/B als ~ (~) definierenEIN/\~B), wobei ~ die Wicklung des Polygons umkehrt,/die Vereinigung und/\ den Schnittpunkt.

Wenn Sie Länder gruppieren, hoffe ich, dass es keine Überschneidungen gibt. Sie könnten einen ziemlich naiven Algorithmus verwenden, der nach gemeinsam genutzten Scheitelpunkten sucht. Eine einfache Ansicht wäre, die Punkte eines Polygons zu durchlaufen und zu prüfen, ob sie sich auf einem der anderen Polygone befinden und teilt denselben nächsten oder vorherigen Punkt, um zu sehen, ob es eine Übereinstimmung gibt. Dann entfernen Sie einfach den gemeinsamen Scheitelpunkt, um Ihre Vereinigung zu erstellen

Ich musste dieses Problem heute lösen und fand die Lösung mit dieser lib: http://www.cs.man.ac.uk/~toby/alan/software/ .

Es gibt viele Sprachimplementierungen die Liste hier einschließlich Java, Obj-C, C #, Lua, Python und mehr.

Ich bin auf dasselbe Problem gestoßen und habe das Problem folgendermaßen gelöst

Cython-Wrapper für die C++ - Übersetzung der Angus Johnson's Clipper-Bibliothek (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)

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

Sehen Sie sich diesen Ausschnitt unten an:

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