Triangulation

Question 1

Welches Problem hat man oft mit Daten?

Answer 1

Oft werden Daten an den Vertices von unstrukturierten Punktwolken erfasst

Question 2

Was ist die Aufgabe der Triangulation?

Answer 2

Man muss eine topologische Struktur erzeugen, d.h. ein unstrukturiertes Grid, das in der Regel eine Triangulation ist

Question 3

Aus welchen Einheiten besteht eine Triangulation?

Answer 3

• Set von Vertices
• Set von Edges
• Faces bzw. Dreiecken
• Regularity

Question 4

Es gibt viele verschiedene Triangulationsmöglichkeiten, welche davon ist eine Gute bzw. die Beste?

Answer 4

Vermeidung von langen, dünnen Dreiecken, da diese zu sichtbaren Interpolationsartefakten führen

Question 5

Wie lautet die Faustformel für gute Dreiecke?

Answer 5

• Equilateral (dt. gleichseitige) Dreiecke sind optimal
• Kleinster Winkel sollte maximal sein
• Verhältnis von Innenkreis und Umkreis sollte maximal sein

Question 6

Was ist die Delaunay Triangulation?

Answer 6

Die Delaunay Triangulation ist die optimale Triangulation, d.h. diejenige mit insgesamt maximalen kleinsten Winkeln

Question 7

Wie lautet die Definition des Voronoi-Diagramms?

Answer 7

Bei einer Menge von Vertices ist ein Voronoi-Diagramm eine Unterteilung der Ebene in Regionen

Question 8

Wie lautet der Ausnamefall bei einem Voronoi-Diagramm und der Delaunay Triangulation?

Answer 8

Wenn vier Vertices auf einem Kreis liegen (und kein weiterer Vertex im Kreis liegt)

Question 9

Wie lautet das Ergebnis bei einem Ausnamefall des Voronoi-Diagramms und der Delaunay Triangulation?

Answer 9

Die Voronoi-zu-Delaunay Konstruktion ergibt ein Viereck und beide Diagonalen führen zu einer gültigen Delaunay Triangulation

Question 10

Welche zwei (gleichwertigen) Kriterien kennzeichnen Delaunay Triangulationen?

Answer 10

• Das globale Delaunay Kriterium oder global circumcircle
• Das lokale Delaunay Kriterium oder local circumcircle

Question 11

Was besagt das globale Delaunay Kriterium oder global circumcircle?

Answer 11

Eine Triangulation ist eine Delaunay Triangulation, wenn die Umkreise aller Dreiecke keinen anderen Vertex enthalten

Question 12

Was besagt das lokale Delaunay Kriterium oder local circumcircle?

Answer 12

Für jede innere Kante enthält der Umkreis eines Dreiecks nicht den dritten Vertex des anderen Dreiecks

Question 13

Wie lautet die Idee des Flipping Algorithmus?

Answer 13

• Erstelle eine anfängliche, regelmäßige Triangulation
• Kehre sukzessiv die inneren Kanten um, wenn das lokale Delaunay Kriterium nicht erfüllt ist

Question 14

Wie erstellt man eine initiale Triangulation?

Answer 14

• 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

Question 15

Wie lautet die Idee des Flip Inner Edges Algorithmus?

Answer 15

Vertausche alle inneren Kanten, die das lokale Delaunay Kriterium verletzen

Question 16

Wie lautet der Flip Inner Edges Algorithmus?

Answer 16

• 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

Question 17

Was ist der Vorteil und Nachteil des Flip Inner Edges Algorithmus und welche Laufzeit hat er?

Answer 17

• Pro: Einfache Implementierung
• Con: Rechenintensiv
• O(n^2)

Question 18

Wie lautet die Idee des Incremental Algorithmus?

Answer 18

Die Idee ist, mit einem beliebigen Dreieck zu beginnen, neue Vertices und Edges hinzuzufügen und das Delaunay Kriterium zu überprüfen

Question 19

Wie funktioniert der Incremental Algorithmus?

Answer 19

• 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

Question 20

Was macht man beim Incremental Algorithmus im ersten Fall, wenn der neue Vertex innerhalb eines existierenden Dreiecks liegt?

Answer 20

• 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

Question 21

Was macht man beim Incremental Algorithmus im zweiten Fall, wenn der neue Vertex außerhalb der aktuellen Triangulation liegt?

Answer 21

• 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

Question 22

Was ist der Vorteil und Nachteil des Incremental Algorithmus und welche Laufzeit hat er?

Answer 22

• Pro: Etwas komplexerer Algorithmus
• Con: Immernoch rechenintensiv
• O(n^2)

Question 23

Wie lautet die Idee des Divide and Conquer Algorithmus?

Answer 23

Ein schnellerer Algorithmus durch Erzeugung von Delaunay Triangulationen in Unterregionen (divide) und Kombination dieser in einem zweiten Schritt

Question 24

Wie lautet der Divide and Conquer Algorithmus?

Answer 24

• 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

Question 25

Was ist der Nachteil des Divide and Conquer Algorithmus und welche Lauzeit hat er?

Answer 25

Komplexer Algorithmus
O(nlog(n))

Question 26

Wie lautet der Spezialfall beim Divide and Conquer Algorithmus?

Answer 26

• Keine der zwei möglichen Optionen resultiert in einer validen Konfiguration
• Grund: Eine bereits existierende Kante verletzt das Delaunay Kriterium

Question 27

Wie kann man den Spezialfall beim Divide and Conquer Algorithmus lösen?

Answer 27

Entferne Kanten, die das Kriterium verletzen und fahre mit dem Algorithmus fort