Polygon-Polygon-Schnittpunkt schlägt im Spezialfall fehl

Question

Ich habe den Bentley-Ottmann-algorithm implementiert, um Polygon-Polygon-Schnittpunkte zu erkennen. Dies funktioniert normalerweise sehr gut: Da sich die Polygone nicht selbst schneiden, deutet jeder Liniensegmentschnitt in der Vereinigung der Liniensegmente beider Polygone an, dass sich beide Polygone schneiden.

Aber wenn ich in diesem Fall aussehen:

gibt es keine Segment-Kreuzung. Aber klar schneiden sich beide Polygone.

Wie kann ich diesen Fall ohne Verwendung des naiven Algorithmus erkennen, der für jeden Punkt jedes Polygons im anderen Polygon nach einem Punkt-in-Polygon sucht und daher in O (m * n) läuft.

Answer 1

Hint:

Die Handhabung von Sonderfällen, wie beispielsweise einen Scheitelpunkt auf einer Kante oder zwei überlappenden Kanten ist ein unbehagliches Thema als die Konfigurationen unterschiedlich sind und Fälle können Teleskop (mehrere kollinearen Kanten denken, die sie überlappen) .

Mein bester Rat ist, Kohärenz zu erzwingen, indem Sie jedem Eckpunkt einen inneren oder äußeren Zustand zuweisen (mit dem anderen Polygon). Wenn Sie dann eine Kante mit dem anderen Polygon schneiden, muss die Parität der Anzahl der Schnittpunkte mit der Änderung des Endpunktstatus übereinstimmen (gleicher Zustand => gerade Anzahl von Schnittpunkten).

Ich gebe nicht an, auf welche Weise Sie die Zustände zuweisen, dies hängt von Ihrem speziellen Algorithmus ab (in der Praxis werden Zustände zugewiesen, während Sie gehen). Was zählt ist, dass wenn ein Staat getestet wird, du ihn nicht mehr ändern kannst. Wenn eine Anomalie auftritt (Parität der Anzahl von Kreuzungen, die nicht mit der Zustandsänderung übereinstimmen), müssen Sie dies entweder durch Opfern einer Kreuzung oder durch Duplizieren einer (oder einer anderen Regel, die Sie für angemessen halten) beheben.

Beispiel:

In diesem Beispielfall werden die grünen Punkte Vertices bezeichnen betrachtet außerhalb des blauen polygon, und die Ziffern zeigen akzeptable Anzahl von an den entsprechenden Kanten zugeordnet Kreuzungen.

Der schwarze Umriss unten stellt das Union-Polygon dar, das sich aus dieser Zuweisung von Zuständen ergeben würde.