Teilen Sie ein Rechteck basierend auf Punktepaaren auf
Beispiel http://xthlegion.co.uk/images/dividerectangle.png Beispiel http://xthlegion.co.uk/images/dividerectangle2.png
Wenn Sie die obigen Bilder betrachten, sehen Sie, dass sie aus einem einzelnen großen Rechteck bestehen, das durch Paare benutzerdefinierter Koordinaten in kleinere Rechtecke unterteilt ist (jedes Paar in den Beispielbildern ist mit einer anderen Farbe gekennzeichnet).
Ich versuche, die Koordinaten dieser Rechtecke zu erhalten, indem ich nur die Joins definiere. Kanten werden als explizite Joins behandelt. Ordnung spielt keine Rolle.
Kennt jemand den Namen des Algorithmus, der das tut (ich bin sicher, dass es einen mit einem fantastischen Namen gibt!) oder haben Sie einen Beispiel-C # -Code? Ich habe mich schon eine Weile bemüht, das selbst zu schaffen, habe aber wenig Erfolg. Noch eine weitere totale Mathematik scheitert!
Aktualisierung:
Ich dachte nur, ich würde diese Frage aufgrund der Kommentare, die ich erhalten habe, schnell aktualisieren.
- Linien müssen gerade sein, damit jedes Koordinatenpaar auf einer Achse ausgerichtet wird
- Koordinaten müssen entweder von einer Kante oder der Schnittmenge eines anderen Paares ausgehen. Die zweite Koordinate muss in ähnlicher Weise enden. Irgendwelche "Waisenkinder" -Koordinaten, die sich nicht gegenseitig starten / beenden, sind illegal und ich sollte sie für jetzt ignorieren, Snaping sollte möglich sein, sobald ich endlich meinen Kopf in Gang setze.
- Obwohl in diesem Beispiel alle Paare mehr oder weniger sauber das Rechteck teilen, wird dies in der Praxis nicht der Fall sein, und es könnte viele Linien geben, die Rechtecke vieler Größen erzeugen.
2. Update - es funktioniert:)
Beispiel http://xthlegion.co .de / images / dividectangle3.png
3 Antworten
Was Sie zu berechnen versuchen, ist eine Anordnung von Liniensegmenten . (Es ist kein besonders guter Name, aber es scheint der Name zu sein, mit dem wir feststecken!) Um es zu berechnen:
-
Suchen Sie die Schnittmenge (alle Punkte, an denen sich zwei Liniensegmente treffen oder kreuzen). Dies kann durch den Bentley-Ottmann-Algorithmus berechnet werden. Wenn es n -Zeilensegmente und k -Zuweisungen gibt, ist O (( n + k ) log n ). (Aber wenn Sie nur ein paar Liniensegmente haben, ist es wahrscheinlich besser, den einfachen O ( n 2 ) Algorithmus zu verwenden.)
-
Mit ein wenig extra Buchführung können Sie aufzeichnen, welche Kanten an jeder Kreuzung auftraten, und so das lineares lineares Diagramm (PSLG), das Ihrer Gruppe von Liniensegmenten entspricht.
-
Konvertieren Sie die PSLG in eine Quad-Edge-Datenstruktur . Dies geschieht in zwei Schritten. Suchen Sie zuerst nach Kanten-Kanten-Verbindungen in der Datenstruktur, indem Sie die auf jeden Knoten fallenden Kanten nach Winkel ordnen.
-
Wählen Sie eine Kante, die noch nicht mit zwei Flächen verbunden ist, erstellen Sie eine Fläche auf der nicht verbundenen Seite und gehen Sie um die Grenze der Fläche herum, die sie mit jeder Kante verbindet. Wiederholen Sie dies, bis jede Kante mit zwei Flächen verbunden ist.
Im Allgemeinen führt dies zu anderen Flächen als Rechtecken (auch wenn alle Liniensegmente achsenbündig ausgerichtet sind und alle Schnittpunkte ganzzahlige Koordinaten haben), aber in Ihrer Anwendung passiert dies möglicherweise nicht oder Sie können die nicht vorhandenen Elemente verwerfen. rechteckige Gesichter.
Die Antwort geht von folgender Regel aus, die ich für notwendig halte:
Der Benutzer darf nur ein vorhandenes Rechteck unter Verwendung einer horizontalen oder vertikalen Linie unterteilen.
Dies bedeutet, dass in Ihrem ersten Beispiel die Reihenfolge der Unterteilung sein müsste:
Braun, gelb, blau grün.
Definieren Sie für jede Rechteckklasse, die Sie verwenden, zwei Erweiterungsmethoden: SubdivideHorizontal und SubdivideVertical , die die Koordinate der Unterteilung übernehmen und die zwei resultierenden Rechtecke der Unterteilung zurückgeben.
Für jedes Rechteck, das du unterteilst, ersetze es durch die zwei resultierenden Unterteilungsrechtecke und wiederhole es rekursiv für alle Unterteilungen.
Ich würde Folgendes tun.
- Erstellen Sie einen Punkt an jeder der vier äußeren Ecken.
- Erstellen Sie einen Punkt für jeden benutzerdefinierten Punkt.
- Erstellen Sie einen Punkt, wenn eine Linie einen leeren Punkt überquert.
- Laufen Sie durch jedes Quadrat und prüfen Sie, ob sich an allen vier Ecken ein Punkt befindet.