Wie man in Scheiben schneiden ein einfaches Polygon mit einer Linie

Question

Ich habe ein einfaches Polygon (konvex oder konkav, aber keine Löcher), die ich zur Scheibe muß in Teile mit einem Liniensegment. Ich bin mir nicht sicher, wie eigentlich bestimmen, wie viele Polygone nach der Scheibe führen, oder wie man Gruppe der Eckpunkte.

konvex Grund Fälle die immer Ergebnisse in 2 Subpolygone sind einfach, aber wie würde ich mit einer komplizierten konkaven Form umgehen? Nehmen Sie ein „E“ -Form Polygon zum Beispiel. Eine vertikale Scheibe 4 kann Polygone ergeben. Wie kann ich feststellen, welche Eckpunkte jeder dieser Subpolygone machen?

Definition der Polygon: Ich habe zwei Möglichkeiten. Mein Polygon kann eine geordnete Liste von Eckpunkten sein, oder es kann eine Reihe von Dreiecken sein. Ich würde eine Lösung bevorzugen, die die Anordnung von Dreiecken verwendet. Es sollte ziemlich einfach durch jedes Dreieck Schleife und schneiden Sie es mit der Linie, wenn sie sich schneiden. Aber dann habe ich keine Ahnung, wie man diese Gruppe Dreiecke in die Subpolygone das Ergebnis.

Pseudo-Code oder auch allgemeine Beratung ist gut; eine C # -Implementierung ist ideal.

Answer 1

Vor einer Weile gab ich diese Antwort auf eine etwas andere Frage.

Diese Antwort gibt einen Weg, um eine Kontur einer Form aufzubauen, da eine Dreieckszerlegung von dieser Form.

Die Grundidee ist es, die Kanten aller Dreiecken als gerichtete Vektoren zu betrachten, und dann heben sie gleiche, aber entgegengesetzte Kanten.

In Ihrem Fall würden Sie eine Reihe von Dreiecken haben die ursprüngliche Form darstellen. Sie würden die einzelnen Dreiecke mit der Linie schneiden. Sie würden dann regather die Dreiecke in Formen, das Verfahren unter Verwendung der oben beschriebenen, mit der Maßgabe, dass in Scheiben geschnittenen Kanten würde abbrechen nicht.

Es gibt Details und Bilder in der Antwort auf die oben Bezug genommen wird. Aber die Schritte zusammenfassen würde

1. Führen Sie die Dreieck-Splits

2. Für jedes resultierende Dreieck, fügen die drei gerichteten Kanten zu einem Satz. Um zu bestimmen, im Uhrzeigersinn um Besuche die die Antworten auf diese Frage .

3. Go durch den Rand Satz Paare von Kanten zu entfernen, die gleich sind, aber entgegengesetzt (es sei denn, sie sind slice Kanten)

4. Wählen Sie eine Kante in dem Satz, finden dann den Rand dessen Schwanz passt den Kopf der ersten Kante. Dann wiederholen Sie für die Kante, bis Sie an den Anfang Rand bekommen. Entfernen Sie jede Kante vom Rand gesetzt, wie Sie es. Jedes Mal, wenn Sie an den Anfang Rand bekommen haben Sie eine geschlossene Schleife eines des Ergebnis Polygone darstellen.

5. Führen Sie Schritt 4, bis es keinen linken Rand.

All dies bietet Platz für Ihren Wunsch nach einer Triangulation Ihres Polygon zu starten. Aber als einer der Kommentatoren auf Ihre ursprüngliche Frage hat darauf hingewiesen, sollten Sie die Alternativen unter neuen Polygone aus einem Schnitt Polygon (2D) .

Answer 2

Ich habe diesen Algorithmus in meiner Bibliothek PolyK . Hier ist href="http://polyk.ivank.net/?p=demos&d=slice">. Wenn Sie Javascript verstehen, ich bin sicher, dass es einfach sein, sie in den Programmiersprache neu zu schreiben.