Die Berechnung der Triangulation eines Polygons in fast-linearer Zeit.

s s a b a_y b_y 1 1 2 3 4 2 3 4 Abbildung 7: Trapezzerlegung für das Liniensegment s und die dazugehörige Suchstruktur Q({s}). wie folgt: Wir beginnen an der Wurzel von Q(S) und bewegen uns entlang eines Pfades bis zu einer
Senke, die bekanntlich einem Trapez aus T (S) entspricht. An jedem Knoten auf dem Pfad erfolgt ein
Vergleich mit dem Schlüssel des Knotens. An einem X-Knoten stellen wir fest, ob q sich links oder
rechts von dem Liniensegment befindet, welches der Schlüssel dieses Knotens ist. Liegt q links davon,
folgen wir der linken Kante. Wenn q rechts vom Schlüsselsegment liegt, folgen wir der rechten Kante.
Der Fall, dass  q  auf dem Schlüsselsegment liegt kann vernachlässigt werden, da dieser für unsere
Zwecke nicht relevant ist. Kommen wir an einem Y -Knoten an, vergleichen wir die y-Koordinate von
q  mit dem Schlüssel des Knotens, der bekanntlich eine horizontale Erweiterung eines Endpunktes
aus S repräsentiert. Liegt q oberhalb der horizontalen Erweiterung, wird der rechten Kante gefolgt.
Wenn q unterhalb der horizontalen Erweiterung liegt, wird der linken Kante gefolgt. Da wir ein nicht-
degeneriertes System vorfinden (laut Annahme) ist der Fall, dass q auf der horizontalen Erweiterung
liegt, irrelevant.     Weiterhin nehmen wir an, dass die Trapeze in T (S) mit den Senken in Q(S) fest verdrahtet sind,
d. h. für jedes Trapez aus  T (S) können wir in konstanter Zeit die entsprechende Senke in  Q(S)
bestimmen. Gleiches gilt für die und umgekehrte Richtung.     Sei nun  s  ein nicht-horizontales Liniensegment mit dem oberen Endpunkt  a  und dem unteren
Endpunkt b, das keine Liniensegmente aus S  kreuzt. Sei S ′ = S {s}. Im Folgenden möchten wir T (S ′ ) und Q(S ′ ) berechnen, wenn T (S) und Q(S) gegeben sind.     Falls der obere Endpunkt a kein Endpunkt der Liniensegmente aus S ist, benutzen wir Q(S) um
das Trapez t_a, welches a enthält, zu lokalisieren. Das Trapez t_a wird mit einer horizontalen Linie, die
durch a verläuft, geteilt und wir erhalten damit eine neue Trapezzerlegung T ′ . Die Senke aus Q(S), die t_a entspricht, verwandelt sich zu einem Y -Knoten, dessen Schlüssel die y-Koordinate von a ist.
Die Kinderknoten sind die zwei neuen Trapeze, die wir durch Teilung des Trapezes t_a erzeugt haben.
Damit haben wir die Strukturen T ′ und Q ′                                                                     .
Ist a ein Endpunkt eines Liniensegments aus S, setzt man T ′ = T  und Q ′ = Q.