Ein einfacher Algorithmus für Polygonschnitt

Question

Ich bin auf der Suche nach einem sehr einfachen Algorithmus zur Berechnung der Schnittmenge/des Clusters des Polygons ..__ Das heißt, angesichts der Polygone P, Q möchte ich das Polygon T finden, das in P und Q enthalten ist, und ich möchte T maximal unter allen möglichen Polygonen.

Ich kümmere mich nicht um die Laufzeit (ich habe ein paar sehr kleine Polygone), ich kann mir auch eine Annäherung an die Schnittmenge der Polygone leisten (dh ein Polygon mit weniger Punkten, das aber immer noch in der Schnittmenge der Polygone enthalten ist) ).

Für mich ist es jedoch sehr wichtig, dass der Algorithmus einfach ist (günstigeres Testen) und vorzugsweise kurz ist (weniger Code).

edit: Bitte beachten Sie, ich möchte ein Polygon erhalten, das die Schnittmenge darstellt. Ich brauche nicht nur eine boolesche Antwort auf die Frage, ob sich die beiden Polygone schneiden.

Angus Johnson · Accepted Answer

Ich verstehe, dass das Originalposter nach einer einfachen Lösung suchte, aber leider gibt es keine einfache Lösung.

Trotzdem habe ich vor kurzem eine Open-Source-Freeware-Clipping-Bibliothek (in Delphi, C++ und C # geschrieben) erstellt, die alle Arten von Polygonen (einschließlich sich selbst überschneidender) ausschneidet. Diese Bibliothek ist ziemlich einfach zu verwenden: http://sourceforge.net/projects/polyclipping/ .

Doug Ferguson · Answer

Sie können einen Polygon Clipping - Algorithmus verwenden, um den Schnittpunkt zwischen zwei Polygonen zu finden. Dies ist jedoch in der Regel ein komplizierter Algorithmus, wenn alle Edge-Fälle berücksichtigt werden.

Eine Implementierung von Polygon-Clipping, nach der Sie mit Ihrer bevorzugten Suchmaschine suchen können, ist Weiler-Atherton. Wikipedia-Artikel zu Weiler-Atherton

Alan Murta hat eine vollständige Implementierung eines Polygonschneiders GPC .

Bearbeiten:

Ein anderer Ansatz besteht darin, zunächst jedes Polygon in eine Reihe von Dreiecken zu unterteilen, die einfacher zu handhaben sind. Der Two-Ears-Theorem von Gary H. Meisters macht den Trick. Diese Seite bei McGill erklärt die Unterteilung der Dreiecke gut.

Barend · Answer

Wenn Sie C++ verwenden und den Algorithmus nicht selbst erstellen möchten, können Sie Boost.Geometry verwenden. Es verwendet eine angepasste Version des oben erwähnten Weiler-Atherton-Algorithmus.

Aryabhatta · Answer

Sie haben uns Ihre Darstellung eines Polygons nicht gegeben. Also wähle ich (eher als Vorschlag) einen für dich :)

Stellen Sie jedes Polygon als ein großes konvexes Polygon dar und eine Liste kleinerer konvexer Polygone, die von diesem großen konvexen Polygon "abgezogen" werden müssen.

Wenn Sie nun zwei Polygone in dieser Darstellung angeben, können Sie die Schnittmenge wie folgt berechnen:

Berechnen Sie den Schnittpunkt der großen konvexen Polygone, um das große Polygon des Schnittpunkts zu bilden. Subtrahieren Sie dann die Schnittpunkte aller kleineren von beiden, um eine Liste der abgezogenen Polygone zu erhalten.

Sie erhalten ein neues Polygon, das der gleichen Darstellung folgt.

Da der konvexe Polygonschnitt einfach ist, sollte auch diese Schnittpunktsuche problemlos sein.

Es scheint, als sollte es funktionieren, aber ich habe nicht tiefer über die Korrektheit/Zeit/Raumkomplexität nachgedacht.

Eric · Answer

Hier ist ein auf Triangulation basierender Ansatz, der ziemlich einfach zu implementieren ist und in O ausgeführt werden kann (N²).

Übrigens, O (N²) ist für dieses Problem optimal. Stellen Sie sich zwei Polygone vor, die wie Pitchfork-Klingen geformt sind und sich im rechten Winkel schneiden. Jedes hat eine Anzahl von Segmenten, die proportional zur Anzahl der Zinken ist. Die Anzahl der Polygone im Schnittpunkt ist proportional zum Quadrat der Anzahl der Zinken.

Triangulieren Sie zunächst jedes Polygon.
Vergleichen Sie alle Dreiecke von P paarweise mit allen Dreiecken von Q, um Schnittpunkte zu ermitteln. Jedes Paar von sich kreuzenden Dreiecken kann in kleinere Dreiecke unterteilt werden, von denen jedes in P, in Q oder im Schnittpunkt liegt. (Was auch immer Sie in Schritt 1 verwendet haben, kann hier wieder verwendet werden.) Behalten Sie nur Dreiecke bei, die sich im Schnittpunkt befinden.
Berechnen Sie die Nachbarn jedes Dreiecks, indem Sie sie paarweise vergleichen, und erstellen Sie einen Nachbarschaftsgraphen. Dieser Graph enthält ein verbundenes Untergraph für jedes Polygon im Schnittpunkt von P und Q.
Wählen Sie für jede dieser Unteransichten ein Dreieck aus, gehen Sie zum Rand und gehen Sie dann um den Rand herum, wobei Sie die Segmente erzeugen, die das entsprechende Ausgabe-Polygon begrenzen.

Darius Bacon · Answer

Hier ist ein einfacher und dummer Ansatz: diskretisieren Sie Ihre Polygone bei der Eingabe in eine Bitmap. Überkreuzen UND die Bitmaps zusammen. Um Ausgabepolygone zu erzeugen, müssen Sie die zackigen Ränder der Bitmap nachzeichnen und die Zacken mit einem Polygon-Näherungsalgorithmus glätten. (Ich kann mich nicht erinnern, ob dieser Link die geeignetsten Algorithmen enthält, es ist nur der erste Google-Treffer. Sie können eines der Tools ausprobieren, um Bitmap-Bilder in Vektordarstellungen zu konvertieren. Möglicherweise können Sie diese verwenden, ohne den Algorithmus neu zu implementieren ?)

Der komplexeste Teil wäre die Grenzen ausfindig machen , denke ich.

In den frühen 90ern war ich übrigens bei der Arbeit so etwas wie dieses Problem. Ich muffelte es: Ich entwickelte einen (völlig anderen) Algorithmus, der mit reellen Zahlenkoordinaten arbeiten würde, schien aber angesichts der Realitäten von Fließkommazahlen (und Rauschen) eine völlig unfixierbare Fülle degenerierter Fälle zu finden. . Vielleicht hätte ich es mit Hilfe des Internets besser gemacht!

Ansh David · Answer

Die Art, wie ich an demselben Problem gearbeitet habe

brechen des Polygons in Liniensegmente
schnittlinie mit IntervalTrees oder LineSweepAlgo finden
suchen eines geschlossenen Pfads mithilfe von GrahamScanAlgo zum Suchen eines geschlossenen Pfads mit benachbarten Scheitelpunkten
Querverweis 3. mit DinicAlgo, um sie aufzulösen

hinweis: Mein Szenario war anders, da die Polygone einen gemeinsamen Knoten hatten. Aber hoffe das kann helfen

Dom · Answer

Ich habe keine sehr einfache Lösung, aber hier sind die Hauptschritte für den Algorithmus real:

Führen Sie eine benutzerdefinierte doppelt verknüpfte Liste für die Polygonscheitelpunkte und Kanten aus. Die Verwendung von std::list ist nicht sinnvoll, da Sie die nächsten und __. Vorherigen Zeiger/Offsets selbst gegen eine spezielle Operation auf den Knoten austauschen müssen. Dies ist der einzige Weg, um einfachen Code zu erhalten, und dies ergibt eine gute Leistung.
Finden Sie die Schnittpunkte, indem Sie jedes Kantenpaar vergleichen. Beachten Sie, dass der Vergleich jedes Edge-Paares O (N²) Zeit ergibt, die Verbesserung des Algorithmus auf O (N · logN) ist jedoch danach einfach. Für einige Paare von Kanten (etwa a → b und c → d) wird der Schnittpunkt gefunden, indem Der Parameter (von 0 bis 1) an Kante a → b verwendet wird, der durch .__ gegeben ist. = d₀/(d₀-d₁), wobei d₀ (ca) × (ba) ist und d₁ (da) × (ba) ist. X ist das 2D-Kreuzprodukt, wie z. B. p × q = p · q · - p · q ·. Nachdem Sie tₐ gefunden haben, wird das Finden des Schnittpunkts als linearer Interpolationsparameter auf dem Segment a → b verwendet: P = a + tₐ (b-a)
Teilen Sie jede Kante und fügen Sie Scheitelpunkte (und Knoten in Ihrer verknüpften Liste) Wo sich die Segmente schneiden.
Dann müssen Sie Kreuz die Knoten an den Kreuzungspunkten. Dies ist die Operation, für die Sie eine benutzerdefinierte doppelt verknüpfte Liste erstellen mussten. Sie müssen ein Paar next-Zeiger austauschen (und die vorherigen-Zeiger entsprechend aktualisieren).

Dann haben Sie das rohe Ergebnis des Polygonschnitt-Auflösungsalgorithmus. Normalerweise möchten Sie eine Region entsprechend der Wicklungsnummer jeder Region auswählen. Suchen Sie nach Polygonwicklungsnummer für eine Erklärung dazu.

Wenn Sie aus diesem O (N²) -Algorithmus einen O (N · logN) -Algorithmus erstellen möchten, müssen Sie genau dasselbe tun, außer dass Sie ihn innerhalb eines Line-Sweep-Algorithmus ausführen. Suchen Sie nach Bentley-Ottman-Algorithmus . Der innere Algorithmus ist derselbe, mit dem einzigen Unterschied, dass die Anzahl der zu vergleichenden Kanten innerhalb der Schleife reduziert wird.