3.1 Motivation

Geoinformationssysteme (Folien 3–6)

In einem GIS liegen Informationen in Ebenen (Layern) übereinander: Straßen, Flüsse, Bahnlinien, Orte. Will man z.B. alle Brücken finden, legt man die Layer „Straßen“ und „Flüsse“ übereinander und sucht alle Kreuzungen.

• Straßen und Flüsse werden durch Polygonzüge angenähert.
• Gesucht sind also Schnittpunkte von Liniensegmenten.
• Wer naiv jede Straße gegen jeden Fluss testet, überfordert das System schnell, weil Karten sehr viele Segmente haben.

Vereinfachung: Statt Polygonzügen betrachtet man nur einzelne Liniensegmente.

Vorgehen (Folie 6):

1. Alle Segmente aller Polygonzüge in eine Menge werfen und alle Schnitte berechnen.
2. Danach sortieren, welche Schnitte zu welchen Polygonzügen gehören.
3. Achtung: Zwei aufeinanderfolgende Segmente desselben Polygonzugs berühren sich immer in ihrem gemeinsamen Endpunkt. Dieser „Schnitt“ ist kein echter Schnitt. Ein echter Schnitt kann aber zufällig genau auf so einem Endpunkt liegen und muss dann trotzdem erkannt werden.

3.2 Naiver Ansatz (Folie 8)

Eingabe	Menge $S=\{s_1,\dots,s_n\}$ von $n$ Strecken in der Ebene
Ziel	alle Schnittpunkte von Strecken aus $S$
Lösung	alle $\binom n2$ Paare testen, bei Schnitt den Schnittpunkt ausgeben
Laufzeit	$\Theta(n^2)$

Ist das schlecht? Kommt drauf an:

• Wenn sich alle Paare schneiden, gibt es $\Theta(n^2)$ Schnittpunkte. Allein die Ausgabe kostet dann $\Theta(n^2)$, und der naive Algorithmus ist optimal.
• In der Praxis (Karten!) ist die Zahl der Schnitte aber viel kleiner, meist eher $O(n)$. Dann verschwendet der naive Algorithmus fast seine gesamte Zeit mit Paaren, die sich gar nicht schneiden.

Daraus folgt der Wunsch nach einem ausgabesensitiven Algorithmus, dessen Laufzeit von der Zahl $k$ der Schnitte abhängt. Dasselbe Motiv kennt man schon aus Kapitel 2 (Jarvis' March, $O(nh)$).

Schnitttest für zwei Strecken (Ergänzung)

Die Folien setzen den Test voraus. Mit dem Orientierungstest geht er ohne Division:

$\overline{ab}\text{ und }\overline{cd}\text{ schneiden sich echt} \iff \operatorname{orient}(c,d,a)\cdot\operatorname{orient}(c,d,b)<0 \ \land\ \operatorname{orient}(a,b,c)\cdot\operatorname{orient}(a,b,d)<0.$

In Worten: $a$ und $b$ liegen auf verschiedenen Seiten der Geraden durch $c,d$, und $c$ und $d$ liegen auf verschiedenen Seiten der Geraden durch $a,b$. Ist eines der Produkte $=0$, liegt ein Endpunkt auf der anderen Geraden (Berührung oder kollinear), das ist ein Sonderfall.

Den Schnittpunkt selbst bekommt man dann über den Parameter

$t=\frac{\operatorname{orient}(c,d,a)}{\operatorname{orient}(c,d,a)-\operatorname{orient}(c,d,b)},\qquad p = a + t\,(b-a).$