die Außenseite eines geometrischen Graphen zu finden

Question

ich eine Karte von Polygonen haben, zum Beispiel:

alt text http://img13.imageshack.us/img13/2808/output.png

(leider das Bild nicht so groß ist, ich werde versuchen und besser eine bekommen später)

Die grünen Linien sind der kürzeste Weg zwischen den verbundenen Formen. Was ich tun muss, ist die grünen Linien zu finden, die die äußere Kante bilden und in welche Richtung ich sie durchqueren muss, um den CCW zu umkreisen.

Die Polygone werden immer konvex sein und die Linien werden sich niemals kreuzen. Die Linien sind in Form von X-, Y-Endpunkten definiert. Ich habe einen Index von Polygonen zu verwandten Linien und es ist mit welchem ​​Ende angehängt.

Der Grund, warum ich das brauche, ist, weil ich die Kanten finden muss, die jede der inneren Sektion bilden und meine Wand folgende Lösung schlägt/stürzt für den äußeren Abschnitt ab.

Answer 1

0. Erläuterung: Ich bin nicht sicher, ob die grünen Verbindungen zwischen den konvexen Polygonen als Teil der Eingabe bereitgestellt werden oder ob das Programm die geeigneten grünen Verbindungen als kürzeste Pfade zwischen Polygonen selbst bestimmen muss. Ich habe gerade bemerkt, dass Ihr Bild eine grüne Kante in der oberen rechten Ecke fehlt (das wäre Teil der äußeren Grenze, wenn erlaubt).

1. Lösung: Wählen Sie immer die nächste Kante. Wenn Ihre Eingabe angibt, welche grünen Linien erlaubt sind und welche nicht, dann durchlaufen Sie einfach die Grenze der äußeren Komponente, indem Sie einen Startpunkt finden (z. B. indem Sie die Polygonecke mit der niedrigsten x-Koordinate nehmen) und die grünen Kanten anordnen das Polygon dieses aktuellen Punktes im Gegenuhrzeigersinn und die Wahl der Kante unmittelbar nach dem aktuellen Punkt in CCW-Reihenfolge. Nehmen Sie nun das andere Ende dieser Kante als "aktuellen Punkt" und wiederholen Sie die gleiche Methode, um die nächste Kante zu finden ... bis Sie zum ersten Polygon zurückkehren.

2. Lösung: Beginnen Sie mit der konvexen Hülle. Wenn Sie alle möglichen grünen Linien zulassen, brauchen Sie sie nicht als Eingabe. Die konvexe Hülle aller Polygonkanten ist eine erste Annäherung an Ihre Lösung (Details zum Finden --- siehe weiter unten): Die konvexe Hülle enthält echte Polygonkanten (stellen wir uns diese als "schwarz" vor: Sie sind Teil Ihrer endgültigen Lösung , bereits in der richtigen Reihenfolge) und Kanten, die Polygone verbinden (Betrachten wir sie als rot: Sie müssen durch grüne Kanten und möglicherweise Teile von anderen Polygonen ersetzt werden).

Abschluss der zweiten Lösung: teile und herrsche: Jetzt müssen wir jede rote Kante durch eine Kombination von grünen und schwarzen Kanten ersetzen. Wir konzentrieren uns nur auf jeweils eine rote Linie (und wenden dieselbe Methode für jede rote Linie an, die wir haben könnten).

Also haben wir eine rote Linie, die zwei Polygone enthält, die eine grüne Linie haben (die kürzeste Verbindung zwischen ihnen) --- die vier Kanten dieser zwei Linien definieren ein Viereck. Wenn keine der anderen Polygon-Ecken in diesem Viereck ist, sind Sie fertig: Ersetzen Sie die rote Kante durch die grüne Kante und alle schwarzen Kanten auf den Polygonen, um zu den Verbindungspunkten zu kommen.

Aber wenn Sie Polygon im Viereck finden, wählen Sie aus ihnen die am nächsten an der roten Kante. Bewege die rote Kante zu diesem Punkt - so dass der neue Punkt die rote Kante in zwei rote Kanten schneidet. Diese zwei neuen roten Kanten ersetzen die eine alte rote Kante: Wenden Sie diese Methode rekursiv auf beide an. Ihre entsprechenden Vierecke sind viel kleiner und enthalten weniger Polygonkanten.

Wenn Sie diese Divide and Conquer-Methode anwenden, werden Sie am Ende keine roten Ränder mehr haben (weil Sie jedes Mal, wenn Sie ein leeres Viereck finden, eine rote Kante verlieren).

Konvexe Hülle: Dies ist ein schwieriges Problem in n Dimensionen, aber einfach in zwei Dimensionen: Wenn Sie im Internet suchen oder SO durchsuchen, finden Sie sicherlich eine bessere Lösung als ich jetzt denken kann, aber hier ist einer das kommt mir in den Sinn (nochmal: teile und herrsche): Finde einen Punkt A mit maximaler x-Koordinate und einen Punkt B mit minimaler x-Koordinate, verbinde sie durch zwei gerichtete "blaue" Kanten: A-> B und B-> A . Teilen Sie Ihre Punkte in zwei Sätze: die auf der rechten Seite der Kante A-> B und diejenigen auf der linken Seite (die wirklich die rechte Seite von B-> A ist). Wir ersetzen wiederholen jeden blauen Rand, bis wir die konvexe Hülle finden:

Nehmen Sie eine blaue Kante A-> B und Blick auf den Punkten seine rechte Seite. Wenn es keine gibt, dann ist diese blaue Kante wirklich schwarz (Teil Ihrer Lösung). Andernfalls den Punkt C am weitesten rechts von der blauen Kante nehmen und die Kante A-> B durch zwei blaue Kanten A-> C und C-> B ersetzen. Teilen Sie die Punkte, die sich auf der rechten Seite von A-> B befanden, in die auf der rechten Seite von A-> C, die auf der rechten Seite von C-> B und die auf der rechten Seite von A-> B auf werden ignoriert). Wiederholen Sie dies, bis alle blauen Kanten ersetzt sind.