Prüfungsfrage 03 – incremental insertion Algorithmus, Delaunay

 

Eine Punktwolke wurde durch den incremental insertion Algorithmus Delaunay-dreiecksvernetzt. Dabei wurde der gerichtete azyklische Dalaunay-Graph aufgebaut. Geben Sie an, wie unter Benützung dieser Datenstruktur möglichst effizient bestimmt werden kann, in welchem Dreieck sich ein neuer, beliebiger Punkt befindet!

Lösung

Die Aufgabenstellung ist es, eine Menge P an Punkten zu einer dreidimensionalen Oberfläche zu verbinden. Zu diesem Zweck könnte man die Fläche um je einen Punkt auf die Höhe des Punktes heben. Dadurch würde das Terrain allerdings diskret werden, es gäbe zwischen den Höhenstufen senkrechte Absätze, was nicht besonders realistisch ist. Stattdessen sollen die Punkte zu Dreiecken verbunden werden. Das Problem löst man durch eine Delaunay-Triangulierung in der Ebene, anschließend werden die Punkte auf ihre jeweilige Höhe gehoben, wobei die Verbindungslinien erhalten bleiben. So entsteht ein vielflächiges Terrain, der Graph einer stetigen stückweise linearen Funktion.
Die Frage ist nun, wie in der Ebene die Punkte am günstigsten zu Dreiecken verbunden werden können. Welche Art der Verbindung am realistischsten ist, kann nicht festgestellt werden, da wir nur die gemessenen Punkte, nicht aber das wirkliche Terrain als Vergleich kennen. Trotzdem wirken manche Triangulierungen natürlicher als andere:

inf-incremental-insertion-algorithmus-beispiel

Von den Werten her könnten die schwarzen Punkte einen Bergrücken beschreiben. Triangulierung a unterstützt diese Vorstellung, da der neue Punkt etwa die gleiche Höhe hat. Bei Triangulierung b gibt es einen scharfen Schnitt in der Kette, der neue Punkt ist auf dem Niveau der äußeren Punkte, was unnatürlich wirkt. Das hier auftretende Problem ist, dass die Höhe des neuen Punktes im Fall b von zwei weit entfernten Punkten bestimmt wird. Das wird dadurch deutlich, dass die Winkel der beiden neuen Dreiecke klein sind.
Es gibt eine endliche Anzahl an Möglichkeiten zur Triangulierung, wobei die Anzahl m der Dreiecke immer gleich ist. Gesucht ist die optimale Triangulierung. Diese zeichnet sich dadurch aus, dass der Winkelvektor A\left( \mathcal{T} \right) = {\left( {{\alpha _1},{\alpha _2},...,{\alpha _{3m}}} \right)^T} maximal ist.
Ein beliebiges Viereck kann auf genau zwei Arten in Dreiecke zerlegt werden (zwei Diagonalen). Die optimale Variante zeichnet sich dadurch aus, dass der kleinste auftretende Winkel größer ist als in der alternativen Triangulierung:

inf-incremental-insertion-edge-flip

Die Kante e = {p_i}{p_j} ist illegal, da die „geflippte“ Kante zu einem größeren kleinsten Winkel führt. Um zu vermeiden, für jede Version sechs Winkel messen zu müssen, nutzen wir ein Kriterium, dass uns direkt sagt ob eine Kante illegal ist, ohne dass wir die alternative Triangulierung bilden müssen. Hierzu nutzen wir den Satz von Thales in der allgemeinen Form:

Sei K ein Kreis, l eine Sekante und a,b die Schnittpunkte. Dann ist der sich an einem dritten Punkt c ergebene Winkel des Dreiecks abhängig von der Position von c:

({c_1} innerhalb des Kreises, {c_2},{c_3} auf dem Kreis, {c_4} außerhalb des Kreises)

\measuredangle ab{c_1} > \measuredangle ab{c_2} = \measuredangle ab{c_3} > \measuredangle ab{c_4}

Das Kriterium ist also, dass bei einer legalen Triangulierung kein Punkt im Umkreis eines Dreiecks anderer Punkte liegen darf. Der Algorithmus zu Delaunay-Triangulierung funktioniert wie folgt: Alle Punkte werden zunächst zufällig permutiert. Anschließend wird der höchste Punkt (z.B. größte y-Koordinate) ermittelt und mit zwei weit entfernten, nicht in der Menge der Punkte enthaltenen Hilfspunkten verbunden, so dass die gesamte Punktwolke innerhalb des entstandenen Dreiecks liegt. Dadurch werden Probleme am Außenrand der Triangulierung verhindert.
Die Punkte werden dann nacheinander dem Graph hinzugefügt, wobei das Delaunay-Kriterium immer aufrecht erhalten wird. Abschließend werden die beiden Hilfsknoten einschließlich aller inzidenten Kanten aus dem Graph gelöscht.

Algorithmus in Pseudocode:

für r = 1 bis n
	Finde das Dreieck p_ijk, das p_r enthält.
	wenn p_r im Inneren des Dreiecks p_ijk liegt
		dann füge die Kanten von p_r zu p_i, p_j und p_k dem Graphen hinzu,
		so dass das alte Dreieck in drei neue aufgeteilt wird.
		LegalizeEdge(p_r, p_ij)
		LegalizeEdge(p_r, p_jk)
		LegalizeEdge(p_r, p_ki)
	sonst // Punkt liegt auf Kante von Dreieck
		teile beide an die Kante angrenzenden Dreiecke in zwei neue.
		LegalizeEdge(p_r, p_il)
		LegalizeEdge(p_r, p_lj)
		LegalizeEdge(p_r, p_jk)
		LegalizeEdge(p_r, p_ki)

inf-quad-edge-datenstruktur-nutzung-beispiel

Es gibt mehrere Möglichkeiten, den ersten Befehl („finde das Dreieck“) zu implementieren.

1. Nutzung einer QuadEdge Datenstruktur

Vom zuletzt eingefügten Punkt aus wird zunächst ein Orientierungstest gemacht, um im Beispiel links das Dreieck sab zu bestimmen. Anschließend wird die Kante ermittelt, die von line geschnitten wird. Mit Hilfe der QuadEdge Datenstruktur wird der Algorithmus mit dem Dreieck f1 fortgesetzt. In f1 werden die Kanten traversiert, bis erneut eine Kante line schneidet. Dies geht rekursiv weiter, bis ein Dreieck nur eine Kante hat, die line schneidet. Dieses Dreieck enthält dann den Punkt dest.

2: Nutzung des gerichteten azyklischen Dalaunay-Graphen

inf-azyklischer-delaunay-graph-algorithmus

Um mit der gegebenen Struktur einen Punkt zu lokalisieren, starten wir mit dem aus dem höchsten Punkt und den beiden Hilfspunkten bestehenden Dreieck, das die gesamte Punktwolke enthält.
Von dort aus prüfen wir die drei Nachfolger, die beim Einfügen des zweiten Punktes entstanden sind. Nur einer der Nachfolger kann den neuen Punkt enthalten. Das Dreieck selbst existiert allerdings schon nicht mehr, da auch die Nachfolger des Startknotens im Laufe des Hinzufügens neuer Punkte in kleinere Dreiecke unterteilt wurden. Wir können uns aber an der Struktur des Baumes entlanghangeln und finden so irgendwann ein Blatt im Baum. Dieses repräsentiert ein noch existierendes Dreieck im Delaunay-Graph, das den neu eingefügten Punkt enthält.