Zerlegt ein schwach-einfaches Polygon in ein echtes einfaches Polygon oder Polygon
Ich möchte schwach einfache Polygone in einfache Polygone aufteilen.
Hintergrund
Der Anwendungsfall besteht darin, vereinfachte Polygone (Unioned) mit Javascript Clipper zu vereinfachen. Javascript Clippers sowie Original-Clippers SimplifyPolygon() -Funktion entfernt Selbstüberschneidungen und kombiniert gemeinsame Kanten, aber es kann nicht produzieren wahre einfache Polygone. Die Ausgabe wird in three.js verwendet, die TriangulateShapes() hat, was Polygone einfach macht. Three.js akzeptiert Polygon-Strukturen, die eine Kontur und null oder mehrere Löcher haben.
Eingabe, schwach einfache Polygone
Schwach einfache Polygone können keine sequentiell-duplizierten Scheitelpunkte (echte doppelte Punkte), keine Löcher (Inseln) oder Selbstüberschneidungen (Kantenüberquerung über andere Kanten) aufweisen, sondern es können nicht sequentiell-mehrfache Scheitelpunkte (Scheitelpunkte) sein die genau die gleiche Koordinate haben, aber nicht so sequentiell). Das Eingangspolygon kann entweder CW- oder CCW-Wicklungsreihenfolge haben, was bedeutet, dass der CW-Eingang ein äußeres Polygon und CCW ein Loch ist. Die Eingabe ist entweder CW oder CCW Polygon.
Die Eingabe ist ein Array von Polygonpunkten, zB:
%Vor% Dies ist das obige input Polygon als Bild:
Und hier sind die Punkte nummeriert, wo Sie leicht sehen können, welche Punkte Duplikate sind:
Wie Sie sehen, kann das obige Polygon auf verschiedene Arten unterteilt werden, zB .:
- Ein äußeres Polygon mit fünf Löchern
- fünf äußere Polygone, von denen eines ein Loch hat
Ausgabe einfacher Polygone als exPolygon-Struktur
Einfaches Polygon ist ein Polygon, das keine Selbstüberschneidungen aufweist, keine doppelten Koordinaten, unabhängig davon, ob sie sequenziell oder nicht sequenziell waren, keine Löcher. Das einfache Polygon des Ausgangs kann eine CW- oder CCW-Wicklungsreihenfolge haben. CW bedeutet äußere und CCW Löcher.
Der Ausgang kann Löcher haben (und in vielen Fällen wird es Löcher geben), aber in bestimmten Fällen hat der Ausgang keine Löcher. Die Ausgabe hat immer mindestens ein äußeres Polygon, aber es kann auch mehrere äußere Polygone geben, die null oder mehr Löcher haben.
Die Ausgabe sollte ein Array von exPolygon-Objekten mit den Eigenschaften "outer" und "holes" sein. "äußere" ist eine Anordnung von Punktobjekten, "Löcher" ist eine Anordnung von Anordnungen von Punktobjekten. Wenn "Löcher" gefüllt sind, müssen die Löcher Löcher des "äußeren" Polygons im exPolygon-Objekt sein.
Das Beispiel der Ausgabe:
%Vor%Die "äußeren" Polygone der Ausgabe sind CW, und "Löcher" sind CCW.
Es gibt keine Begrenzung für die Anzahl der Punkte in Polygonen, die Anzahl der exPolygon-Objekte oder die Anzahl der Löcher.
Hier sind weitere Beispiele für schwach einfache Polygone:
Beispiel für die Teilung
Hier ist ein Beispiel für ein Eingabepolygon:
Hier ist, wie es geteilt werden könnte:
Einige andere Polygone können mehrere mögliche Alternativen für den Ausgang haben, abhängig davon, wo die Pseudodoppelpunkte liegen.
Meine Frage
Wie können die Polygone auf diese Weise geteilt und die gewünschte Ausgabestruktur erreicht werden? Ich frage nicht den vollen Code (aber wenn Sie etwas Freizeit haben und zeigen wollen, dass es möglich ist). Gedanken zu möglichen Algorithmen sind ebenfalls willkommen.
Ich habe Stunden eine Lösung gesucht und versucht, einen Algorithmus zu finden.
Falls Sie eine Lösung ausprobieren wollen, habe ich hier einen Code, mit dem ich die Duplikate gefunden habe: Ссылка . Es zeigt das Polygon in SVG und zeigt die Punkte als rote Kreise und einen Array-Index für jeden Punkt (nach dem Drücken der Schaltfläche "Run with JS").
Hier ist das gleiche, aber mit 12 Beispielpolygonen (ändern Sie pindex im JavaScript-Fenster, um das Polygon zu ändern):
Ссылка
BEARBEITEN: Javascript Clipper 6 ist jetzt verfügbar und es gibt Unterstützung für StrictlySimple . Aber laut der Dokumentation "gibt es derzeit keine Garantie, dass Polygone streng einfach sein werden, da die 'Vereinfachung' noch in Arbeit ist." Ich habe StrictlySimple getestet und es schlägt in bestimmten Fällen fehl: Orientierungsprobleme und unsere Rotationsinvarianz . Wir hoffen, dass diese bald behoben werden und StrictlySimple funktioniert wie erwartet.
1 Antwort
Es mag etwas geben, was ich vermisse, aber das sieht wie ein klassisches Problem aus, den Artikulationsknoten eines Graphen zu finden. Im Wesentlichen versuchen Sie, den schwächsten Punkt in einem Graphen zu finden, sodass Sie, wenn Sie den Graphen an diesem Punkt schneiden, zwei separate Graphen erhalten. Wenn Sie in Ihrem Beispiel das Polygon an diesem Scheitelpunkt ausschneiden, erhalten Sie mehrere Polygone. Sie können Ihre Polygone relativ einfach als Graph darstellen, wobei jeder Knoten einen Graphenscheitel und die Polygonkanten als Graphenkanten darstellen.
Wenn ich das Problem lösen müsste, wäre dies der Ansatz, den ich wählen würde. Sie können die folgenden Ressourcen auschecken:
- Artikulationsvertices aus dem Algorithm Design Manual - Das ist Ihre beste Wette. Er erklärt den Algorithmus in einfachen Worten und gibt Ihnen auch C-Code, den Sie einfach in JavaScript übersetzen können. Wenn ich anfangen müsste, einen Algorithmus zu schreiben, würde ich hier anfangen.
- Bikonnected-Komponente
- Erkennung von Artikulationspunkten (Suche nach "Artikulation")
AKTUALISIEREN
Ich werde versuchen, Ihnen einen kurzen Überblick über das Problem und die Lösung zu geben, um Sie in die richtige Richtung zu weisen. Eine Implementierung dieses Algorithmus unter Verwendung von Graphen wird notwendigerweise in Graphalgorithmus-Terminologien eingehen. Wenn Sie also mit Graphen nicht vertraut sind, möchten Sie vielleicht nachlesen.
Der Brute-Force-Ansatz würde in Ihrem Fall sein, den Graphen zu durchlaufen, jeden Veteran vorübergehend zu löschen und dann zu sehen, ob der Graph verbunden ist, wenn eine DFS / BFS-Traversierung auf dem modifizierten Graphen durchgeführt wird. Dies ist nicht sehr effizient und wird in quadratischer Zeit O(n(m + n)) ausgeführt. Aber es gibt einen linearen Zeitalgorithmus, der auf der Klassifizierung der Kanten des resultierenden DFS-Baums basiert, der aus einer DFS-Traversierung gebildet wird.
In einem DFS-Baum, der keine Rückkanten enthält (Kanten verbinden einen "unteren" Knoten mit einem Knoten "höher" im Baum [unter der Annahme, dass "höhere" Knoten diejenigen sind, die näher an der Wurzel sind)) keine Artikulationsknoten, da das Löschen eines jeden von ihnen den Graphen weiterhin verbunden lässt. Wenn Sie jedoch einen der internen Knoten löschen, werden alle nachfolgenden Knoten vom Stamm getrennt.
Das Löschen des Stammverzeichnisses hängt davon ab, ob es ein oder mehrere untergeordnete Elemente enthält. Wenn es nur ein Kind hat, dann ist es mehr oder weniger ein Blatt und somit hat das Löschen keinen Effekt. Wenn Sie jedoch einen Stammknoten löschen, der mehrere untergeordnete Elemente enthält, wird das Diagramm getrennt.
In einem allgemeinen Diagramm können Sie jedoch Rückränder haben. Wenn Sie also einen der Knoten dazwischen löschen, wird das Diagramm nicht getrennt. Das Herausrechnen der Artikulationsknoten führt dazu, herauszufinden, welche Abschnitte des Baums durch Hinterkanten mit Vorfahrknoten verbunden sind (d. H., Den "erreichbaren Vorfahren" eines Eckpunkts herauszufinden).
Auf der Seite, mit der ich aus dem Algorithm Design Manual verlinkt bin, beschreibt Skiena drei Fälle, in denen ein Vertex ein Artikulationsknoten sein kann (root, bridge und parent cut-nodes). Mit dem Algorithmus, den er beschreibt, können Sie herausfinden, ob der Vertex, den Sie verarbeiten, eine dieser Bedingungen erfüllt. Wenn dies der Fall ist, handelt es sich um einen Artikulationsknoten.
Hoffentlich hilft dir das beim Einstieg!
Tags und Links javascript svg graph polygon