Robert Sedgewick: Algorithmen

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


27. Geometrischer Schnitt



Horizontale und vertikale Linien

Zunächst wollen wir voraussetzen, daß alle Linien entweder horizontal oder vertikal sind; die beiden Punkte, die eine solche Linie definieren, haben entweder gleiche x- oder gleiche y-Koordinaten, wie in den Beispielen, die Abbildung 27.1 zeigt. (Dies wird manchmal als Manhattan-Geometrie bezeichnet, da der Stadtplan von Manhattan in der Hauptsache aus horizontalen und vertikalen Linien besteht, abgesehen vom Broadway, der eine Ausnahme darstellt.) Die Forderung, daß die Linien horizontal oder vertikal sein müssen, ist sicherlich eine starke Einschränkung, doch dieses Problem ist bei weitem keine »Spielerei«. In Wirklichkeit wird diese Einschränkung in speziellen Anwendungsfällen oft auferlegt: Zum Beispiel werden VLSI-Schaltungen gewöhnlich unter dieser Einschränkung entworfen. In der rechten Abbildung sind die Linien relativ kurz, wie dies für viele Anwendungen typisch ist, obwohl man meist damit rechnen kann, daß einige sehr lange Linien auftreten.

Abbildung 27.1
Abbildung 27.1 Zwei Linienschnittprobleme (Manhattan).

Das allgemeine Prinzip des Algorithmus zum Auffinden eines Schnitts in solchen Linienmengen besteht darin, sich eine horizontale Durchmusterungslinie vorzustellen, die von unten nach oben verschoben wird. Auf diese Durchmusterungslinie projiziert sind vertikale Linien Punkte, und horizontale Linien sind Intervalle; wenn die Durchmusterungslinie sich von unten nach oben bewegt, erscheinen und verschwinden Punkte (die vertikale Linien darstellen), und horizontale Linien werden von Zeit zu Zeit angetroffen. Ein Schnitt ist gefunden, wenn eine horizontale Linie angetroffen wird, die auf der Durchmusterungslinie ein Intervall darstellt, welches einen Punkt enthält, der eine vertikale Linie darstellt. Die Existenz des Punktes bedeutet, daß die vertikale Linie die Durchmusterungslinie schneidet, und da die horizontale Linie auf der Durchmusterungslinie liegt, müssen sich die horizontale und die vertikale Linie schneiden. Auf diese Weise wird das zweidimensionale Problem des Auffindens eines sich schneidenden Linienpaars auf das eindimensionale Problem der Bereichssuche aus dem vorangegangenen Kapitel zurückgeführt.

Natürlich ist es nicht notwendig, wirklich eine horizontale Linie längs des ganzen Weges durch die Linienmenge nach oben zu verschieben; da wir nur dann handeln müssen, wenn Endpunkte von Linien angetroffen werden, können wir damit beginnen, daß wir die Linien nach ihren y-Koordinaten sortieren, und können danach die Linien in dieser Reihenfolge verarbeiten. Wenn der untere Endpunkt einer vertikalen Linie angetroffen wird, fügen wir die x-Koordinate dieser Linie zu dem binären Suchbaum (hier x-Baum genannt) hinzu; wenn der obere Endpunkt einer vertikalen Linie angetroffen wird, löschen wir die betreffende Linie aus dem Baum; wenn schließlich eine horizontale Linie angetroffen wird, führen wir unter Verwendung ihrer beiden x-Koordinaten eine Bereichssuche in diesem Intervall durch. Wie wir sehen werden, ist einige Sorgfalt erforderlich, um gleiche Koordinaten von Endpunkten von Linien zu behandeln (inzwischen dürfte der Leser daran gewöhnt sein, daß bei geometrischen Algorithmen derartige Schwierigkeiten auftreten).

Abbildung 27.2
Abbildung 27.2 Durchmusterung nach Schnitten: Anfangsschritte.

Abbildung 27.2 zeigt die ersten Schritte der Durchmusterung zum Auffinden der Schnitte in dem Beispiel von Abbildung 27.1 links. Die Durchmusterung beginnt bei dem Punkt mit der kleinsten y-Koordinate, dem unteren Endpunkt von C. Danach wird E angetroffen, dann D. Der Rest des Prozesses ist in Abbildung 27.3 dargestellt: Die nächste angetroffene Linie ist die horizontale Linie G, die hinsichtlich eines Schnitts mit C, D und E (den vertikalen Linien, die die Durchmusterungslinie schneiden) überprüft wird.

Abbildung 27.3
Abbildung 27.3 Durchmusterung nach Schnitten: Vollendung des Prozesses.

Um die Durchmusterung zu implementieren, brauchen wir nur die Endpunkte der Linien nach ihren y-Koordinaten zu sortieren. Für unser Beispiel ergibt dies die Liste

C E D G I B F C H B A I E D H F

Jede vertikale Linie erscheint in der Liste zweimal, jede horizontale Linie erscheint einmal. Für die Zwecke des Algorithmus kann man sich diese sortierte Liste als eine Folge von Befehlen Einfügen (vertikale Linien, wenn der untere Endpunkt angetroffen wird), Löschen (vertikale Linien, wenn der obere Endpunkt angetroffen wird) und Bereichssuche (für die Endpunkte horizontaler Linien) vorstellen. Alle diese »Befehle« sind einfach Aufrufe der Standardprogramme für Binärbäume aus den Kapiteln 14 und 26, bei Verwendung der x-Koordinaten als Schlüssel.

Abbildung 27.4 zeigt den Prozeß der Erzeugung des x-Baumes während der Durchmusterung. Jeder Knoten im Baum entspricht einer vertikalen Linie, doch der während der Erzeugung des Baumes verwendete Schlüssel ist die x-Koordinate. Da sich E rechts von C befindet, gehört es zum rechten Teilbaum von C usw. Die erste Reihe von Skizzen in Abbildung 27.4 entspricht Abbildung 27.2, der Rest entspricht Abbildung 27.3.

Abbildung 27.4
Abbildung 27.4 Datenstruktur während der Durchmusterung: Erzeugung des x-Baumes.

Wenn eine horizontale Linie angetroffen wird, so wird sie benutzt, um in dem Baum eine Bereichssuche durchzuführen: Alle vertikalen Linien in dem Bereich, der durch die horizontale Linie angegeben wird, entsprechen Schnitten. In unserem Beispiel wird der Schnitt zwischen E und G entdeckt, danach werden I, B und F eingefügt. Dann wird C gelöscht, H eingefügt und B gelöscht. Danach wird A angetroffen, und es wird eine Bereichssuche für das durch A definierte Intervall durchgeführt. Bei dieser Suche werden die Schnitte zwischen A und D, E sowie H entdeckt. Anschließend werden die oberen Endpunkte von I, E, D und F angetroffen und gelöscht, was zurück zu dem leeren Baum führt.


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