# 24 Geometrie II - Segmentschnitt

[TOC]

[comment]: # (Zuerst ein paar LaTeX-Makros:)

$\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\lc}{\left\lceil}
\newcommand{\rc}{\right\rceil}
\newcommand{\lf}{\left\lfloor}
\newcommand{\rf}{\right\rfloor}
\newcommand{\ra}{\rightarrow}
\newcommand{\Ra}{\Rightarrow}
\newcommand{\O}{\mathcal{O}}$

*Disclaimer:* Diese Mitschrift ist als Ergänzung zur Vorlesung gedacht. Wir erheben keinen Anspruch auf Vollständigkeit und Korrektheit. Wir sind jederzeit froh um Hinweise zu Fehlern oder Unklarheiten an [e-mail].

Wenn Sie an dieser Mitschrift mitarbeiten möchten, melden Sie sich [hier](http://doodle.com/poll/hkiky233kxp7rr8n).

## Einführung
Letztes Mal haben wir zwei Dinge gesehen:
* Die konvexe Hülle von $n$ Punkten können wir in Zeit $\O(n \log n)$ berechnen. Zum Beispiel mittels Induktion von links nach rechts, also einer sogenannten Scanline
* Den Schnitt von orthogonalen Liniensegmenten (Entscheiden, ob es einen gibt und auch Zählen der Anzahl Schnitte) können wir auch in Zeit $\O(n \log n)$ mit einem Scanline-Ansatz.

Heute wollen wir zwei Dinge tun:
* Wir wollen weitere, kniffligere Beispiele für Scanline-Algorithmen anschauen.
* Wir wollen Datenstrukturen entwerfen, die uns bei diesen komplexeren Anfragen behilflich sind.

## Schnitt von Liniensegmenten


Wir betrachten nun beliebige Liniensegmente, jeweils definiert durch die beiden Endpunkte $A = (x_1, y_1)$ und $B = (x_2,y_2)$. Für nur zwei gegebene Liniensegmente $(A,B)$ und $(C,D)$ können wir in konstanter Zeit bestimmen, ob sie sich schneiden: Wir bilden die Geradengleichungen durch $(A,B)$ und durch $(C,D)$. Durch gleichsetzen und auflösen dieses $2x2$ Gleichungssystemes finden wir den Schnittpunkt $P$ der beiden Geraden. Nun müssen wir nur noch prüfen ob $P$ innerhalb von $(A,B)$ und $(C,D)$ liegt, um zu entscheiden ob sich die Liniensegmente (und nicht nur ihre Geradenverlängerungen) kreuzen.

**Allgemeine Lage:** Wir wollen alle Randfälle vermeiden. Wir nehmen dazu an, dass die Liniensegmente in allgemeiner Lage sind, was so viel heisst, wie dass keine zwei Linien parallel sind und dass kein Segment senkrecht steht. Ferner seien alle $x$- und $y$-Koordinaten eindeutig und kein Schnittpunkt genau am Rand eines Segmentes. Wir nehmen auch an, dass nicht drei Punkte auf einer Linie liegen und sich nicht mehrere Segmentpaare bei der selben $x$-Koordinate kreuzen.^[Sind diese Annahmen vernünftig? Können wir sie leicht garantieren indem wir die Endpunkte minimal bewegen und die Ebene minimal rotieren?]

### Detektionsproblem
Zuerst wollen wir nur entscheiden ob es einen Schnitt gibt: Dazu lassen wir eine Scanlinie von links nach rechts auf der obigen Skizze laufen. Sobald wir einen Schnittpunkt finden brechen wir alles ab. Wir wollen also (noch) nicht sämtliche Schnittpunkte finden.

Für eine bestimmte Scanlineposition gibt es wie letztes Mal schlafende, aktive und tote Segemente. Betrachten wir die aktiven Segement entlang der Scanline von unten nach oben: Wir sagen zwei Segmente sind *benachbart*, wenn sie in dieser Reihenfolge aufeinanderfolgend auftreten.


Für zwei sich schneidende Segmente gibt es nun einen $x$-Bereich für welchen die Scanline so liegt, dass die beiden Segmente benachbart sind.


Wenn wir die Scanlinie ganz wenig nach rechts verschieben, was passiert dann mit den Nachbarschaften? Die $y$-Koordinaten der aktiven Segmente ändern sich, aber solange wir keinen Schnittpunkt oder Segmentendpunkt überstreichen, ändert sich nichts an der Segmentreihenfolge entlang der Scanline.

Wir testen also alle benachbarten aktiven Segmente und finden so einen allfälligen Schnittpunkt. Sobald es beim Weiterführen der Scanline neue Nachbarschaften gibt, prüfen wir die neuen Nachbarpaare auch. Also alles was jemals benachbart wird, prüfen wir.

Wo ändert sich etwas? An den Anfangs- und Endpunkten der Segmente. Das sind also unsere Haltepunkte für die Scanline. Wenn wir die aktiven Segmente nach $y$-Koordinate sortiert halten, dann hat ein neues Segment beim Einfügen zwei neue Nachbarn, die wir prüfen, und beim Entfernen entsteht ein neues benachbartes Paar, das wir auch prüfen.

**Anfangshaltepunkte: Einfügen**
Die grünen Pfeile markieren die getesteten, neu benachbarten Segmentpaare.

**Endhaltepunkte: Entfernen**

Wie halten wir die aktiven Segmente sortiert? Müssen wir die Segmente umsortieren, wenn die Scanline vorwärts bewegt wird? Wir beobachten: liegt Segment $A$ unterhalb von Segment $B$, so bleibt dies unverändert solange sich die beiden Segmente nicht kreuzen. Wenn die Scanline wandert bleibt unsere Datenstruktur also unverändert zwischen den Haltepunkten. Und auch an den Haltepunkten ändert sich die Ordnung der anderen Segmente nicht.

Wir verwenden einen AVL-Baum als Scanline-Datenstruktur, also zur Verwaltung der aktiven Segmente. In den Schlüsseln des AVL-Baums speichern wir die komplette Information zu den Segmenten, also die Endpunkte und Geradengleichungen. Damit können wir Schlüsselvergleiche als "Liegt Segment $A$ oberhalb von $B$?" in konstanter Zeit beantworten.

Die Schnittests beim Einfügen funktionieren dann so: Wir fügen das neue Segment in den AVL-Baum ein und testen es dann mit seinem symmetrischen Vorgänger und symmetrischen Nachfolger.

Beim Entfernen testen wir zuerst die symmetrischen Vorgänger und symmetrischen Nachfolger (da sie neu benachbart sein werden) und entfernen dann das Segment aus dem AVL-Baum.

Beachte: Unser Algorithmus findet die Schnittpunkte nicht in der Reihenfolge von links nach rechts. Es kann auch sein, dass wir ein und denselben Schnittpunkt mehrfach entdecken.

#### Laufzeitanalyse

Wir betrachten $2n$ Haltepunkte, welche wir zuerst in Zeit $\O(n \log n)$ in aufsteigender $x$-Richtung sortieren.
Für jeden Anfangspunkt führen wir eine Einfügeoperation in einen AVL-Baum und zwei Schnitt-Tests durch. Für jeden Endpunkt braucht es eine Entferneoperation auf dem AVL-Baum und einen Schnitt-Test. Da die Vergleiche innerhalb des AVL-Baumes nur konstante Zeit brauchen, kostet jeder Haltepunkt also nur Zeit $\O(\log n)$.
Insgesamt sind wir also bei der Laufzeit $\O(n \log n)$.

### Alle Schnittpunkte bestimmen
Was tun wir nun, wenn wir sämtliche Schnittpunkte ausgeben wollen? Dann können wir nicht einfach abbrechen beim ersten gefundenen Schnittpunkt.

Streicht die Scanline über einen Schnittpunkt, so sind die beiden sich kreuzenden Segemente benachbart in der Scanlinereihenfolge, sowohl unmittelbar vor als auch unmittelbar nach dem Schnittpunkt. Es ändert sich also nur die Reihenfolge der beiden sich schneidenden Segmente. Ein solches Tauschen von Nachbarn können wir auch leicht in unserem AVL-Baum implementieren.

Detektieren wir einen Schnittpunkt, so müssen wir uns diesen nicht nur für die Ausgabe merken, sondern auch einen neuen Haltepunkt bei diesem Schnittpunkt einplanen. Denn die beiden Segmente tauschen ihre Reihenfolge ja noch nicht gleich beim Haltepunkt, wo wir den Schnitt detektieren, sondern erst später, dann wenn die Scanline den Schnittpunkt überstreicht.

Wie merken wir uns so eine dynamische Menge von Haltepunkten? Zuerst haben wir nur die $2n$ Endpunkte der Segmente und während der Scanline kommen weitere Haltepunkte hinzu, einen für jeden Segmentschnittpunkt. Wir brauchen also eine Einfügeoperation und wollen fortlaufend den linkesten eingeplanten Haltepunkt entfernen. Ein Min-Heap kann dies grundsätzlich schnell (in $\O(\log n)$ pro Operation), aber ist etwas problematisch, da wir unter Umständen den selben Schnittpunkt mehrfach entdecken, den Haltepunkt aber nur einmal einplanen wollen. Ein AVL-Baum unterstützt auch eine solche Duplikatsvermeidung (mittels Suchen vor dem Einfügen) in Zeit $\O(\log n)$. Wir halten unsere dynamischen Haltepunkte also in einem AVL-Baum.

Was tun wir nun an den Haltepunkten?

**Anfang eines Segmentes (linkes Ende)**
- Einfügen in die Scanline-Datenstruktur
- $\leq 2$ Nachbarn auf Schnitt prüfen
- Alle gefundenen Schnitte als Haltepunkte einplanen

**Ende eines Segmentes (rechtes Ende)**
- Entfernen aus der Scanline-Datenstruktur
- allfälliges neues Nachbarpaar auf Schnitt prüfen
- allfälliger gefundener Schnitte als Haltepunkte einplanen

**Kreuzungspunkt**
- Berichte den Schnitt
- Tausche die zwei symmetrischbenachbarten Schlüssel im AVL-Baum.
- Prüfe die $\leq 2$ neuen Nachbarschaften auf Schnitt
- Alle gefundenen Schnitte als Haltepunkte einplanen


In der Praxis gilt es die vielen Spezialfälle, die wir mit unserer allgemeinen Lage unter den Teppich gekehrt haben, genau zu analysieren. Software-Libraries für Geometrie tun dies und müssen sich neben den degenerierten Fällen auch mit der Präzision der Berechnungen herumschlagen.^[Ein wenig in die Tiefe dieses spannenden Bereiches geht die Mastervorlesung [Algolab](http://www.cadmo.ethz.ch/education/lectures/HS15/algolab/index.html), wo die Geometrie-Library [CGAL](http://www.cgal.org) benutzt wird.]

#### Laufzeitanalyse
Sei $k$ die Anzahl Schnittpunkte. Jede Operation an einem Haltepunkt können wir in logarithmischer Zeit durchführen. Die Anzahl Haltepunkte hängt nun aber von der Eingabe ab, ist nämlich $2n+k$. Dank des AVL-Baumes für die Haltepunkte ist auch der Aufwand für deren Verwaltung nur logarithmisch pro Haltepunkt. Die Gesamtlaufzeit summiert sich also auf $\O((n+k) \cdot \log n)$.

Ist das schnell? Erwarten wir nur wenige Schnittpunkte, dann sind wir damit sicher sehr zufrieden. Doch maximal kann es $n^2$ Schnittpunkte geben, was dann in Laufzeit $\O(n^2 \log n)$ resultiert. Das wäre gar (leicht) langsamer als der naive Ansatz, der in $\O(n^2)$ alle Paare testet! Es gibt kompliziertere Verfahren, die den $\log$-Faktor vom $k$ entkoppeln, aber die betrachten wir in dieser Vorlesung nicht. Was unser Verfahren zusätzlich liefert, ist die Schnittpunkte in sortierter Reihenfolge. Das haben wir zwar nicht verlangt, aber erklärt etwas den $\log$-Faktor gegenüber der naiven Lösung.

Nun wollen wir noch ein weiteres Beispiel anschauen - auch um zu demonstrieren wie allgemein und mächtig diese induktive Herangehensweise für Geometrieprobleme ist. Erneut werden wir dabei sehen, dass die recht spezifischen Datenstrukturen, wie der AVL-Baum, die wir im Verlaufe des Semesters entworfen haben, in solchen Aufgaben extrem nützliche Anwendungen finden.

## Schnitt orthogonaler Rechtecke

Im Chipdesign sind nicht nur die Leiterbahnen kritisch, sondern auf einer Platine werden unzählige Komponenten verbaut und wir wollen sicherstellen, dass wir den selben Platinenbereich nicht für mehrere Komponenten eingeplant haben. Vereinfacht kann jede Komponente als ein achsenparalleles Rechteck dargestellt werden.


### Detektionsproblem
Wir nehmen uns zuerst wieder dem Detection Problem an: Gegeben $n$ Rechtecke wollen wir entscheiden, ob es zwei sich überlappende Rechtecke gibt oder nicht. Jedes Rechteck beschreiben wir als $4$-Tupel der Koordinaten $(x^A_l, x^A_r, y^A_l, y^A_r)$.

Auch hier können wir eine Scanline von links nach rechts fahren lassen. Für zwei sich schneidende Rechtecke gibt es immer einen linkesten Punkt im Schnittbereich. Dies entspricht der $x$-Position des linken Endes einer der beiden Rechtecke. Genau dort wollen wir mit unserer Scanline den Schnitt detektieren.

Als Haltepunkte nehme wir also die linken und rechten Rand-$-x-Koordinaten der Rechtecke. Für alle aktiven Rechtecke müssen wir uns ihren $y$-Bereich merken, um für neue Rechteck auf Überlappung prüfen zu können. Wir wir das tun, wollen wir uns gleich überlegen, aber bauen wir uns zuerst den Scanline-Algorithmus fertig mit einer "Überlappungsanfragen-Blackbox".

Bei den Haltepunkten machen wir folgendes: Bei einem linken Ende führen wir eine Überlappungsanfrage durch. Überlappt sich das $y$-Interval des neuen Rechtecks mit einem Interval eines bereits aktiven Rechtecks, so detektieren wir den Schnitt. Sonst fügen wir das Interval des neuen Rechtecks in die Scanline-Datenstruktur ein und fahren fort. An rechten Enden von Rechtecken entfernen wir das Interval aus der Scanline-Datenstruktur und tun sonst nichts. Das ist alles.

Nun bleibt nur noch zu klären wie wir eine Datenstruktur bauen können, welche diese Intervall-Überlappungsanfragen unterstützt. Schauen wir uns die Intervall entlang der Scanline an. Wir drehen gedanklich die Scanline um 90 Grad und legen sie waagrecht vor uns hin:


Jedes Interval wird beschrieben durch seine beiden Grenzen $(l_i, r_i)$. Für eine Anfrage-Intervall $(l,r)$ können wir nun leicht auf Überlappung testen:
$$\text{$(l,r)$ überlappt mit $(l_i,r_i)$ genau dann wenn $(l_i \leq r) \wedge (l \leq r_i)$}$$

Betrachten wir die Intervalle als Punkte im zweidimensionalen Raum (eine Dimension für die linke Grenze, eine Dimension für die rechte), so entspricht die Schnittmenge mit einem Anfrageinterval einer Bereichsanfrage wie folgt:


Wie wir eine Datenstruktur entwerfen, welche diese Bereichsanfragen effizient unterstützt, werden wir morgen sehen.