Zunächst können wir davon ausgehen, dass alle Schnittpunkte vorhanden sind? Es ist leicht, Polygone zu finden, die sich auf interessante Weise schneiden. Mit etwas wie http://en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm sollten Sie in der Lage sein, alle Kreuzungen zu finden und hinzuzufügen.
Als nächstes werde ich die vereinfachende Annahme machen, dass wir niemals ein Liniensegment zurückfahren. (Sie können mit diesem pathologischen Fall auf verschiedene Arten umgehen.)
Mit diesem Detail erledigt, als nächstes müssen wir alle minimalen Polygone lokalisieren, die durch diese Punkte definiert werden können, ob sie schließlich gezählt werden oder nicht drinnen oder draußen. (Der Einfachheit halber werden wir einen "Punkt" im Unendlichen hinzufügen und die Außenseite als ein Polygon zählen.) Dazu nehmen wir zuerst jeden Punkt und listen die Punkte auf, mit denen er sich direkt im Gegenuhrzeigersinn verbindet. (Die Parallele zur x-Achse beträgt 0 Grad, zur y-Achse 90 Grad, die negative x-Achse 180 Grad, und dann wickeln wir um, wenn Sie weiter nach unten gehen.) Für Ihr Beispiel würden wir etwas bekommen dies wie:
(0, 0): (2, 0), (0, 2)
(2, 0): (10, 0), (2, 2), (0, 2), (0, 0)
(10, 0): (10,10), (2, 0)
(0, 2): (0, 0), (2, 0), (2, 2), (0,10)
(2, 2): (2, 0), (0, 2)
(0, 10): (0, 2), (10,10)
(10, 10): (10, 0), (0,10)
Nun jedes einfaches Polygon wird jeder Punkt zwischen zwei dieser Punkte treffen, und umgekehrt kann man einen dieser Lücken nehmen (einschließlich der Wrap-around) und leicht den zugehörigen Polygon erzeugen, bei jede Ecke macht die kleinstmögliche Drehung gegen den Uhrzeigersinn (dh von dem Punkt, zu dem wir gekommen sind, zu dem einen nach dem Wickeln). Für jedes Liniensegment befindet sich das Polygon auf der rechten Seite. Wir wissen, dass wir alle haben, wenn wir jeden einzelnen Punkt und jede Lücke haben. So im obigen Fall wir mit einem Punkt wie (0, 0) und die folgenden Punkt beginnen würden (2, 0), dann schauen wir uns (2, 0) und feststellen, dass (0, 0) von (10, 0) gefolgt wird, gehen Sie zu (10, 0) und feststellen, dass (2, 0) von (10,10) gefolgt und geht auf diese Weise nachzuspüren:
(0, 0), (2, 0), (10, 0), (10,10), (0,10), (0, 2), (0, 0)
(. Beachten Sie, dass aufgrund der Ausrichtung dieses die außerhalb Bereich verfolgt)
Jetzt beginnen wir mit (0, 0) und die alternativen Ausgangspunkt (0, 2) und die gleiche Operation zu erhalten:
(0, 0), (0, 2), (2, 0), (0, 0)
(Dies ist das kleine innere Dreieck.)
Für (2, 0) sind wir noch nicht zu (2, 2) gereist. Also lass uns das tun.
(2, 0), (2, 2), (0, 2), (0,10), (10,10), (10,0), (2, 0)
(Dies ist der große unregelmäßige Polygon.)
Für (2, 0) haben wir noch nicht gereist, um (0, 2) so lassen wir das tun: (. Dies ist das kleine weiße Dreieck)
(2, 0), (0, 2), (2, 2), (2, 0)
Und dann eine Aufzählung aller möglichen gerichteten Liniensegmente, die wir reisen möchten, finden wir, dass wir sie alle abgedeckt haben. Das sind unsere Polygone. Jetzt müssen wir herausfinden, was drin ist und was draußen ist. Dafür gibt es einen einfachen Trick. Finde einen Punkt mit dem niedrigsten möglichen Wert von y (wenn es ein Gleichstand gibt, wird jeder tun). Zum Beispiel angenommen, wir haben (2, 0) ausgewählt. Die gegen den Uhrzeigersinn angeordneten Verbindungsstellen waren (10, 0), (2, 2), (0, 2), (0, 0). Diese sind jeweils außen, innen, außen, innen ... und außerdem, sobald eine Kante eines gegebenen Polygons als außen oder innen markiert ist, sind alle ihre gerichteten Kanten gleich. So bekommen wir leicht:
outside:
- (10, 0), (2, 2), (0, 2), (0, 0)
- (2, 0), (0, 2), (2, 2), (2, 0)
inside:
- (2, 0), (2, 2), (0, 2), (0,10), (10,10), (10, 0), (2, 0)
- (0, 0), (0, 2), (2, 0), (0, 0)
Und Ihre Antwort wird nur die inneren Polygone sein.
(Kleine Optimierung, wir müssen die äußeren Polygone überhaupt nicht zeichnen. Wir können das erste Liniensegment nehmen, dessen Orientierung wir entdecken, einen inneren heraussuchen, dann zu einer seiner Ecken gehen, die Orientierung identifizieren Wenn wir den Überblick behalten, erhalten wir sie alle.)
Alle Punkte haben eine ganze Zahl? –
Wie ist C2 einer der Ausgänge? Es ist das Loch im ursprünglichen Polygon, nicht ein Teil davon. Außerdem wird Ihr ursprüngliches Polygon durch den Startpunkt und den Endpunkt dargestellt, die gleich sind, während Ihre Ausgabe-Polygone den Startpunkt nicht wiederholen (was eine angenommene Kante vom letzten Punkt zum ersten erfordert). Schließlich müssen Sie sich mit sich überschneidenden Kanten befassen, oder nur Kanten, die sich an Scheitelpunkten treffen? –
@ saeed Amiri: Nein, sie können float – csuo