Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


27. Geometrischer Schnitt



Allgemeiner Schnitt von Strecken

Wenn Geradenabschnitte mit beliebiger Steigung zugelassen sind, kann die Situation komplizierter werden, wie Abbildung 27.6 veranschaulicht. Erstens machen es die verschiedenen möglichen Richtungen der Linien notwendig, explizit zu testen, ob bestimmte Paare von Linien sich schneiden; ein einfacher Bereichstest für ein Intervall genügt nicht. Zweitens sind die Ordnungsbeziehungen zwischen den Linien für den binären Baum komplizierter als zuvor, da sie von dem aktuell interessierenden y-Bereich abhängen. Drittens führen beliebige auftretende Schnitte dazu, daß neue »interessierende« y-Werte hinzukommen, die sich von der Menge der y-Werte unterscheiden dürften, die wir aus den Endpunkten der Linien erhalten.

Abbildung 27.6
Abbildung 27.6 Zwei Probleme des allgemeinen Schnitts von Strecken.

Es erweist sich, daß diese Probleme mit einem Algorithmus behandelt werden können, dessen Grundstruktur der oben angegebenen gleicht. Um die Untersuchung zu vereinfachen, betrachten wir einen Algorithmus, mit dem festgestellt werden kann, ob in einer Menge von N Strecken ein sich schneidendes Paar existiert oder nicht, und erörtern dann, wie er dahingehend erweitert werden kann, daß alle Schnitte zurückgegeben werden.

Wie zuvor sortieren wir zuerst nach y, um den Raum in Streifen zu unterteilen, in denen sich keine Endpunkte von Linien befinden. Wie zuvor gehen wir dann die sortierte Liste von Punkten durch, wobei wir jede Linie einem binären Suchbaum hinzufügen, wenn ihr unterer Endpunkt angetroffen wird, und sie wieder löschen, wenn ihr oberer Endpunkt angetroffen wird. Wie zuvor gibt der binäre Baum die Reihenfolge an, in der die Linien in dem horizontalen »Streifen« zwischen zwei aufeinanderfolgenden y-Werten erscheinen. Zum Beispiel sollten in dem Streifen zwischen dem unteren Endpunkt von D und dem oberen Endpunkt von B in Abbildung 27.6 die Linien in der Reihenfolge F B D H G erscheinen. Wir nehmen an, daß in dem aktuellen horizontalen Streifen keine Schnitte vorhanden sind; unser Ziel ist es, diese Baumstruktur laufend zu aktualisieren und sie zu benutzen, um das Auffinden des ersten Schnittes zu ermöglichen.

Um den Baum zu erzeugen, können wir nicht einfach die x-Koordinaten der Endpunkte der Linien als Schlüssel verwenden (wenn wir das tun würden, würden zum Beispiel in dem obigen Beispiel B und D in der falschen Reihenfolge angeordnet). Stattdessen verwenden wir eine allgemeinere Ordnungsbeziehung: Eine Linie x wird als rechts von einer Linie y befindlich definiert, falls beide Endpunkte von x sich auf der gleichen Seite von y befinden wie ein unendlich weit rechts befindlicher Punkt, oder falls y sich links von x befindet, wobei »links« analog definiert ist. Demzufolge befindet sich in der obigen Skizze B rechts von A, und B befindet sich rechts von C (da C sich links von B befindet). Falls x sich weder links noch rechts von y befindet, müssen sich die Linien schneiden. Diese verallgemeinerte Operation des »Linienvergleichs« kann unter Benutzung der Prozedur ccw aus Kapitel 24 implementiert werden. Abgesehen von der Benutzung dieser Funktion jedesmal dann, wenn ein Vergleich erforderlich ist, können die Standardprozeduren für binäre Suchbäume verwendet werden (sogar für ausgeglichene Bäume, wenn es gewünscht wird). Abbildung 27.7 zeigt die Behandlung des Baumes für unser Beispiel zwischen dem Zeitpunkt, zu dem die Linie C angetroffen wird, und dem Zeitpunkt, zu dem die Linie D angetroffen wird. Jeder »Vergleich«, der während der Prozeduren für die Operationen am Baum ausgeführt wird, ist in Wirklichkeit ein Test bezüglich des Schnitts von Linien: Falls die Prozedur des binären Suchbaumes keine Entscheidung treffen kann, ob nach rechts oder links zu gehen ist, müssen sich die zwei fraglichen Linien schneiden, und wir sind fertig.

Abbildung 27.7
Abbildung 27.7 Datenstruktur (x-Baum) für das allgemeine Problem.

Doch damit ist noch nicht alles erledigt, weil diese verallgemeinerte Vergleichsoperation nicht transitiv ist. Im obigen Beispiel befindet sich F links von B (da B sich rechts von F befindet), und B befindet sich links von D, doch F befindet sich nicht links von D. Es ist wichtig, dies zu bemerken, da für die Prozedur des Löschens in einem binären Baum vorausgesetzt wird, daß die Operation des Vergleichs transitiv ist: Wenn B aus dem letzten Baum in der obigen Folge gelöscht wird, wird der in Abbildung 27.7 dargestellte Baum gebildet, ohne daß irgendein expliziter Vergleich zwischen F und D erfolgt. Damit unser Algorithmus für die Prüfung auf Schnitte einwandfrei arbeitet, müssen wir jedesmal, wenn wir die Struktur des Baumes ändern, explizit testen, ob die Beziehungen noch gültig sind. Insbesondere führen wir jedesmal, wenn wir die linke Verbindung des Knotens x auf den Knoten y zeigen lassen, einen expliziten Test durch, ob die x entsprechende Linie sich links von der y entsprechenden Linie befindet, und analog für eine rechte Verbindung. Natürlich könnte dieser Vergleich zur Entdeckung eines Schnitts führen, wie dies in unserem Beispiel der Fall ist.

Zusammenfassend kann gesagt werden, daß wir, um eine Menge von N Strecken auf das Vorliegen eines Schnitts zu testen, das obige Programm benutzen, jedoch den Aufruf der Bereichssuche entfernen und die Routinen für binäre Bäume dahingehend erweitern, daß der verallgemeinerte Vergleich in der oben beschriebenen Weise benutzt wird. Wenn kein Schnitt vorhanden ist, beginnen wir mit einem Null-Baum und enden mit einem Null-Baum, ohne nicht vergleichbare Linien zu finden. Wenn ein Schnitt existiert, dann müssen die zwei sich schneidenden Linien an einer bestimmten Stelle während des Prozesses der Durchmusterung miteinander verglichen werden, und der Schnitt wird entdeckt.

Nachdem wir jedoch einen Schnitt gefunden haben, können wir nicht einfach rasch fortfahren und hoffen, noch weitere zu finden, da die beiden sich schneidenden Linien unmittelbar nach dem Schnittpunkt ihre Plätze in der Folge der Linien vertauschen müßten. Eine Möglichkeit, diese Frage zu lösen, wäre die Verwendung einer Prioritätswarteschlange anstelle eines binären Baumes für das Sortieren nach y: Am Anfang werden die Linien entsprechend den y-Koordinaten ihrer Endpunkte in der Prioritätswarteschlange angeordnet. Dann wird die Durchmusterungslinie eingesetzt, indem sukzessive die kleinste y-Koordinate aus der Prioritätswarteschlange entnommen wird und ein Einfügen oder Löschen im binären Baum wie oben vorgenommen wird. Wenn ein Schnitt gefunden wird, werden für jede Linie neue Eintragungen zur Prioritätswarteschlange hinzugefügt, wobei der Schnittpunkt als der untere Endpunkt dieser Linien benutzt wird.

Ein anderer Weg zum Auffinden aller Schnitte, der geeignet ist, wenn nicht zu viele Schnitte zu erwarten sind, besteht einfach darin, eine der sich schneidenden Linien zu entfernen, wenn ein Schnitt gefunden wird. Nachdem die Durchmusterung beendet ist, wissen wir, daß bei allen sich schneidenden Paaren eine dieser Linien beteiligt sein muß, und wir können eine grobe Methode anwenden, um alle Schnitte anzugeben.

Eigenschaft 27.2 Alle Schnitte von N Linien können in einer zu (N + I) log N proportionalen Zeit gefunden werden, wobei I die Anzahl der Schnitte ist.

Dies folgt unmittelbar aus den obigen Erläuterungen. w.z.b.w.

Ein interessantes Merkmal der obigen Prozedur ist, daß sie einfach durch Änderung der Prozedur des verallgemeinerten Vergleichs dahingehend angepaßt werden kann, daß die Existenz eines sich schneidenden Paares innerhalb einer Menge von allgemeineren geometrischen Formen geprüft wird. Wenn wir zum Beispiel eine Prozedur implementieren wollen, die zwei Rechtecke mit horizontalen und vertikalen Seiten entsprechend der trivialen Regel vergleicht, daß das Rechteck x sich links vom Rechteck y befindet, wenn sich die rechte Seite von x links von der linken Seite von y befindet, so können wir das obige Verfahren benutzen, um zu prüfen, ob innerhalb einer Menge solcher Rechtecke ein Schnitt vorliegt. Für Kreise können wir die x-Koordinaten der Mittelpunkte zum Ordnen benutzen und explizit auf einen Schnitt testen (zum Beispiel vergleiche man den Abstand zwischen den Mittelpunkten mit der Summe der Radien). Auch hier erhalten wir, wenn diese Vergleichsprozedur in dem obigen Verfahren verwendet wird, einen Algorithmus zur Überprüfung einer Menge von Kreisen auf das Vorhandensein von Schnitten. Das Problem der Ermittlung aller Schnitte ist in solchen Fällen wesentlich komplizierter, obwohl die im vorangegangenen Absatz erwähnte grobe Methode stets anwendbar ist, wenn wenige Schnitte zu erwarten sind. Ein anderer Ansatz, die für viele Anwendungen ausreichend ist, besteht einfach darin, komplizierte Objekte als Mengen von Linien zu betrachten und die Prozedur für den Schnitt von Linien zu benutzen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]