Welches Problem hat man oft mit Daten?
Oft werden Daten an den Vertices von unstrukturierten Punktwolken erfasst
Was ist die Aufgabe der Triangulation?
Man muss eine topologische Struktur erzeugen, d.h. ein unstrukturiertes Grid, das in der Regel eine Triangulation ist
Aus welchen Einheiten besteht eine Triangulation?
- Set von Vertices
- Set von Edges
- Faces bzw. Dreiecken
- Regularity
Es gibt viele verschiedene Triangulationsmöglichkeiten, welche davon ist eine Gute bzw. die Beste?
Vermeidung von langen, dünnen Dreiecken, da diese zu sichtbaren Interpolationsartefakten führen
Wie lautet die Faustformel für gute Dreiecke?
- Equilateral (dt. gleichseitige) Dreiecke sind optimal
- Kleinster Winkel sollte maximal sein
- Verhältnis von Innenkreis und Umkreis sollte maximal sein
Was ist die Delaunay Triangulation?
Die Delaunay Triangulation ist die optimale Triangulation, d.h. diejenige mit insgesamt maximalen kleinsten Winkeln
Wie lautet die Definition des Voronoi-Diagramms?
Bei einer Menge von Vertices ist ein Voronoi-Diagramm eine Unterteilung der Ebene in Regionen
Wie lautet der Ausnamefall bei einem Voronoi-Diagramm und der Delaunay Triangulation?
Wenn vier Vertices auf einem Kreis liegen (und kein weiterer Vertex im Kreis liegt)
Wie lautet das Ergebnis bei einem Ausnamefall des Voronoi-Diagramms und der Delaunay Triangulation?
Die Voronoi-zu-Delaunay Konstruktion ergibt ein Viereck und beide Diagonalen führen zu einer gültigen Delaunay Triangulation
Welche zwei (gleichwertigen) Kriterien kennzeichnen Delaunay Triangulationen?
- Das globale Delaunay Kriterium oder global circumcircle
- Das lokale Delaunay Kriterium oder local circumcircle
Was besagt das globale Delaunay Kriterium oder global circumcircle?
Eine Triangulation ist eine Delaunay Triangulation, wenn die Umkreise aller Dreiecke keinen anderen Vertex enthalten
Was besagt das lokale Delaunay Kriterium oder local circumcircle?
Für jede innere Kante enthält der Umkreis eines Dreiecks nicht den dritten Vertex des anderen Dreiecks
Wie lautet die Idee des Flipping Algorithmus?
- Erstelle eine anfängliche, regelmäßige Triangulation
- Kehre sukzessiv die inneren Kanten um, wenn das lokale Delaunay Kriterium nicht erfüllt ist
Wie erstellt man eine initiale Triangulation?
- Ordne die Vertices mit aufsteigender x Koordinate
- Das erste Dreieck ergibt sich aus den ersten drei Vertices
- Füge den nächsten Vertex hinzu und verbinde ihn mit den “sichtbaren” Vertices
Wie lautet die Idee des Flip Inner Edges Algorithmus?
Vertausche alle inneren Kanten, die das lokale Delaunay Kriterium verletzen
Wie lautet der Flip Inner Edges Algorithmus?
- Füge alle Kanten, die das lokale Delaunay Kriterium verletzen in eine Queue
- Dequeue erste Kante und drehe sie um
- Prüfe alle vier Begrenzungskanten des jeweiligen Vierecks und füge sie der Queue hinzu, falls sie sich nicht bereits in der Warteschlange befinden und wenn sie (jetzt) das lokale Delaunay Kriterium verletzen
Was ist der Vorteil und Nachteil des Flip Inner Edges Algorithmus und welche Laufzeit hat er?
- Pro: Einfache Implementierung
- Con: Rechenintensiv
- O(n^2)
Wie lautet die Idee des Incremental Algorithmus?
Die Idee ist, mit einem beliebigen Dreieck zu beginnen, neue Vertices und Edges hinzuzufügen und das Delaunay Kriterium zu überprüfen
Wie funktioniert der Incremental Algorithmus?
- Gegeben ist eine valide Delaunay Triangulation für die ersten k Vertices, wir fügen einen neuen Vertex hinzu
- Fall 1: Neuer Vertex ist innerhalb eines existierenden Dreiecks
- Fall 2: Neuer Vertex ist außerhalb der aktuellen Triangulation
Was macht man beim Incremental Algorithmus im ersten Fall, wenn der neue Vertex innerhalb eines existierenden Dreiecks liegt?
- Prüfung des lokalen Delaunay Kriteriums für alle benachbarten Dreiecke
- Entfernung aller Kanten, die das Kriterium verletzen
- Triangulieren der Region durch Verbinden ihrer Randpunkte mit dem neuen Vertex
Was macht man beim Incremental Algorithmus im zweiten Fall, wenn der neue Vertex außerhalb der aktuellen Triangulation liegt?
- Prüfe das circumcircle Kriterium für alle Dreiecke
- Entferne alle Kanten (bzw. Dreiecke), die das Kriterium verletzen
- Verbinde den neuen Vertex mit allen Vertices der entfernten Dreiecke
Was ist der Vorteil und Nachteil des Incremental Algorithmus und welche Laufzeit hat er?
- Pro: Etwas komplexerer Algorithmus
- Con: Immernoch rechenintensiv
- O(n^2)
Wie lautet die Idee des Divide and Conquer Algorithmus?
Ein schnellerer Algorithmus durch Erzeugung von Delaunay Triangulationen in Unterregionen (divide) und Kombination dieser in einem zweiten Schritt
Wie lautet der Divide and Conquer Algorithmus?
- Unterteilen der Ebene in (quadratische) Regionen mit 2 oder 3 Vertices und triangulieren der resultierenden Vertex-Sets
- Kombination von zwei Triangulationen: Man beginnt mit der unteren Kante und fügt ein Dreieck hinzu, das das Delaunay Kriterium erfüllt -> Bewege dich nach oben bis zur Spitze
