3.3.2 Beliebige Segmente (Bentley–Ottmann)

Der Algorithmus stammt von Bentley und Ottmann (1979) [3] und heißt meist nach ihnen.

Problem und allgemeine Lage (Folie 26)

Eingabe	$n$ beliebige Strecken in der Ebene
Ziel	alle echten Schnittpunkte, d.h. Schnitte, die keine Endpunkte sind

Annahme: allgemeine Lage (general position):

1. Kein Segment ist senkrecht.
2. Zwei Segmente schneiden sich in höchstens einem Punkt (keine Überlappung).
3. In einem Punkt schneiden sich höchstens zwei Segmente.
4. Alle End- und Schnittpunkte haben paarweise verschiedene $x$-Koordinaten.

Die Annahmen schließen genau die Fälle aus, in denen die Reihenfolge auf der Sweep-Line nicht eindeutig wäre. In der Prüfung lohnt es sich, zu jeder Annahme sagen zu können, welches Problem sie verhindert (siehe Sonderfälle).

Zwei Beobachtungen (Folien 28–31)

Beobachtung 2. Schneiden sich $s_i$ und $s_j$ im Punkt $p_{ij}=(x,y)$, dann sind $s_i$ und $s_j$ auf der Sweep-Line benachbart, wenn sie bei $x-\varepsilon$ steht (für hinreichend kleines $\varepsilon>0$).

Warum? Zwischen $s_i$ und $s_j$ könnte kurz vor dem Schnitt nur ein drittes Segment liegen, wenn es durch den Schnittpunkt ginge (verboten: höchstens zwei Segmente pro Punkt) oder vorher endet bzw. beginnt (dann wählt man $\varepsilon$ kleiner als den Abstand zu diesem Ereignis).

Folgerung: Es genügt, benachbarte Segmente auf Schnitt zu testen. Jeder Schnitt wird dabei irgendwann gefunden, nämlich spätestens wenn die beiden zuletzt benachbart werden.

Beobachtung 3. An einem Schnittpunkt tauschen die beiden Segmente ihre Reihenfolge auf der Sweep-Line.

Folgerung:

• Auch Schnittpunkte sind Ereignisse, denn dort ändert sich der Status.
• Sie sind vorher nicht bekannt und müssen zur Laufzeit in die Ereignisstruktur eingefügt werden.

Ereignisse und Datenstrukturen (Folien 32–36)

Ereignistypen

Typ	bekannt	gespeichert
Startpunkt eines Segments	von Anfang an	$x$, eine Segment-ID
Endpunkt eines Segments	von Anfang an	$x$, eine Segment-ID
Schnittpunkt zweier Segmente	erst zur Laufzeit	$x$, zwei Segment-IDs (SegUp, SegLow)

Ereignisstruktur ES

• NextEvent(): Ereignis mit kleinstem $x$ zurückgeben und entfernen.
• AddEvent(E): neues Ereignis nach $x$ einsortieren.
• Umsetzung: Heap oder balancierter Baum, beide Operationen $O(\log|ES|)$.

Statusstruktur SSS (Scan-Line-State-Structure)

Speichert die aktiven Segmente, sortiert nach dem $y$-Wert ihres Schnitts mit der Sweep-Line.

Operation	Bedeutung
AddSegment(s)	$s$ einfügen
RemoveSegment(s)	$s$ entfernen
Pred(s)	Segment direkt unter $s$
Succ(s)	Segment direkt über $s$
Swap(s1, s2)	Reihenfolge von $s_1,s_2$ tauschen

Umsetzung (Folie 35): blattorientierter, balancierter binärer Suchbaum mit zusätzlichen Vorgänger- und Nachfolger-Zeigern. Die Segmente stehen in den Blättern, die inneren Knoten dienen nur der Suche.

Warum funktioniert ein Suchbaum, obwohl sich die $y$-Werte ständig ändern?

Der Schlüssel eines Segments ist sein $y$-Wert an der aktuellen Position der Sweep-Line, er ist also nicht fest. Trotzdem bleibt der Baum gültig: Zwischen zwei Ereignissen ändert sich die Reihenfolge der aktiven Segmente nicht (sonst gäbe es dazwischen einen Schnitt, also ein Ereignis). Beim Vergleich rechnet man den $y$-Wert einfach für die aktuelle $x$-Position aus.

Hilfsfunktion TestIntersectionGenerateEvent(s1, s2)

Nimmt zwei benachbarte Segmente, testet sie auf Schnitt und erzeugt bei Erfolg ein Schnittereignis mit dessen $x$-Koordinate und beiden IDs. Sonst kommt das leere Ereignis zurück.

Algorithmus 3 (Folien 37–39)

 1: Initialisiere ES und SSS;
 2: Sortiere die 2n Endpunkte nach x;
 3: Speichere die Ereignisse in ES;
 4: while (ES nicht leer) {
 5:   E = ES.NextEvent();
 6:   if (E ist Start eines Segments) {
 7:     SSS.AddSegment(E.Segment);
 8:     PredS = SSS.Pred(E.Segment);
 9:     E' = TestIntersectionGenerateEvent(E.Segment, PredS);
10:     if (E' ≠ ∅) ES.AddEvent(E');
11:     SuccS = SSS.Succ(E.Segment);
12:     E' = TestIntersectionGenerateEvent(E.Segment, SuccS);
13:     if (E' ≠ ∅) ES.AddEvent(E');
14:   }
15:   if (E ist Ende eines Segments) {
16:     PredS = SSS.Pred(E.Segment);
17:     SuccS = SSS.Succ(E.Segment);
18:     SSS.Remove(E.Segment);
19:     E' = TestIntersectionGenerateEvent(PredS, SuccS);
20:     if (E' ≠ ∅) ES.AddEvent(E');
21:   }
22:   if (E ist Schnittpunkt) {
23:     Melde Schnitt von E.SegUp und E.SegLow;
24:     SSS.Swap(E.SegUp, E.SegLow);
25:     PredS = SSS.Pred(E.SegUp);     // SegUp liegt jetzt unten
26:     E' = TestIntersectionGenerateEvent(E.SegUp, PredS);
27:     if (E' ≠ ∅) ES.AddEvent(E');
28:     SuccS = SSS.Succ(E.SegLow);    // SegLow liegt jetzt oben
29:     E' = TestIntersectionGenerateEvent(E.SegLow, SuccS);
30:     if (E' ≠ ∅) ES.AddEvent(E');
31:   }
32: }

Die Logik in einem Satz pro Fall: Immer wenn zwei Segmente neu benachbart werden, testet man sie.

Ereignis	neu benachbarte Paare
Start von $s$	$(s,\text{Pred}(s))$ und $(s,\text{Succ}(s))$
Ende von $s$	$(\text{Pred}(s),\text{Succ}(s))$, die vorher durch $s$ getrennt waren
Schnitt von $s_\text{up},s_\text{low}$	nach dem Tausch: das jetzt untere mit seinem neuen Vorgänger, das jetzt obere mit seinem neuen Nachfolger

Zum Durchklicken:

Schritt 1/17: Zeilen 1–3: die 12 Endpunkte nach x sortiert in ES. SSS = ∅.

langsamnormalschnellsehr schnell

Endpunkte lassen sich ziehen.

in SSSaktuelles Ereignisgetestete Nachbarn○ Schnitt-Ereignis in ESgemeldeter Schnitt

Zwei Details, die auf den Folien fehlen

1. Nur Schnitte rechts von der Sweep-Line einplanen. Zwei Segmente können mehrmals benachbart werden (z.B. wenn ein drittes Segment zwischen ihnen beginnt und wieder endet). Liegt ihr Schnitt links von $L$, ist er schon gemeldet.
2. Doppelte Ereignisse vermeiden. Liegt der Schnitt rechts, kann er trotzdem schon in ES stehen. Vor AddEvent also prüfen, ob es das Ereignis schon gibt (z.B. Paar-ID in einem std::set), sonst wird derselbe Schnitt zweimal gemeldet und zweimal getauscht.

Laufzeit (Folien 42–43)

• Sortieren der $2n$ Endpunkte: $O(n\log n)$.
• Ereignisse insgesamt: $2n+k$ ($k$ = Anzahl der Schnitte). Die while-Schleife läuft also $O(n+k)$-mal.
• Pro Durchlauf höchstens sechs Operationen auf ES und SSS.
• ES-Operationen: In ES stehen höchstens $O(n^2)$ Ereignisse, also kostet jede Operation $O(\log n^2) = O(2\log n) = O(\log n)$.
• SSS-Operationen: In SSS stehen höchstens $n$ Segmente, also $O(\log n)$.

Ergebnis

Gesamtlaufzeit $O((n+k)\log n)$, Speicher $O(n^2)$ (wegen bis zu $O(n^2)$ Schnittereignissen in ES).

Ist das gut? (Ergänzung)

• Für kleines $k$ (z.B. $k=O(n)$) ergibt sich $O(n\log n)$, viel besser als $\Theta(n^2)$.
• Für großes $k$ (z.B. $k=\Theta(n^2)$) ergibt sich $O(n^2\log n)$, schlechter als der naive Algorithmus! Der Sweep lohnt sich also nur, wenn $k = o(n^2/\log n)$.
• Die Laufzeit ist nicht optimal: Untere Schranke ist $\Omega(n\log n + k)$. Chazelle und Edelsbrunner (1992) erreichen $O(n\log n + k)$, der Algorithmus ist aber deutlich komplizierter.
• Speicher verbessern: Behält man in ES nur Schnittereignisse von aktuell benachbarten Paaren (und löscht das Ereignis wieder, wenn die beiden getrennt werden), stehen nie mehr als $O(n)$ Schnittereignisse in ES. Speicher $O(n)$ (so macht es de Berg et al.).

Sonderfälle (Ergänzung)

verletzte Annahme	Problem	Lösung
senkrechtes Segment	$y$-Wert auf $L$ nicht eindeutig	wie iso-orientiert behandeln oder Koordinatensystem minimal drehen (lexikographische Ordnung)
Überlappende Segmente	unendlich viele Schnittpunkte	gesondert erkennen (kollinear + Intervalle überlappen)
$\ge3$ Segmente durch einen Punkt	Swap tauscht nur zwei	alle Segmente durch den Punkt sammeln und die ganze Teilfolge umdrehen
gleiche $x$-Koordinaten	Reihenfolge der Ereignisse unklar	lexikographisch nach $(x,y)$ sortieren
Rundungsfehler	Schnittpunkt minimal links von $L$ berechnet	robuste Prädikate, exakte Arithmetik oder Toleranzen