Delaunay-Triangulierungen in zwei und drei Dimensionen

Diplomarbeit von Jörg Krämer

Einleitung:

Das Voronoi-Diagramm und sein Dual, die Delaunay-Triangulierung, haben in vielen Gebieten der Naturwissenschaft und der Technik Anwendung gefunden, wie z.B. in der Kristallographie, in der Geographie und in der Metallurgie. Nachdem am Anfang dieses Jahrhunderts der russische Mathematiker Georges Voronoi Veröffentlichungen über die nach ihm benannte Struktur schrieb, verwendete in den 30er Jahren der Kristallograph Delaunay diese Struktur für die Simulation von Kristallwachstum sowie zur Beschreibung und Untersuchung von Kristallstrukturen. Weitere geographische Anwendungen finden sich in der Kartographie und in der Stadtplanung.

Heute sind das Voronoi-Diagramm und die Delaunay-Triangulierung grundlegende Strukturen in der algorithmischen Geometrie (Computational Geometry). Eine naheliegende geometrische Anwendung des Voronoi-Diagramms besteht im Post-Office-Problem d.h. im Beantworten von Anfragen der Form, welcher Punkt einer Punktmenge in der Ebene oder im Raum zu einem vorgegebenen Punkt der nächste ist. Bei vielen Anfragen lohnt es sich, das Voronoi-Diagramm für die Bestimmung der nächsten 'Postämter' zu benutzen.

Die geometrische Struktur des Voronoi-Diagramms kann schnell konstruiert werden (O(n log n) Zeit und enthält alle wichtigen Informationen über Nachbarschaften (O(n) Speicherplatzbedarf), aus denen sich in linearer Zeit wichtige Probleme der algorithmischen Geometrie berechnen lassen. Zu diesen zählen u.a. der euklidische minimale Spannbaum (EMST), der größte leere Kreis und die zwei nächsten Nachbarpunkte. Eine Näherungslösung für ein NP-vollständiges, graphentheoretisches Problem, das Problems des Handlungsreisenden, kann mit Hilfe der zweidimensionalen Delaunay-Triangulierung bzw. des EMST gewonnen werden. Das Problem des Handlungsreisenden besteht aus dem Bestimmen einer optimalen Rundtour durch n vorgegebene Punkte (Städte), ohne einen Punkt zweimal zu besuchen.

In der Computer-Graphik eignet sich die Delaunay-Triangulierung besonders gut für die Visualisierung und Modellierung von geometrischen Objekten, wie z.B. Freiformflächen. Eine wichtige Eigenschaft der Delaunay-Triangulierung, dass die Winkel unter allen möglichen Triangulierungen optimal sind, rechtfertigt die Verwendung der Delaunay-Triangulierung bei der Netzgenerierung. Zur Visualisierung werden geometrische Objekte durch Dreiecksnetze approximiert, die dann mittels Hardware-Unterstützung schnell schattiert und dargestellt werden können. Weitere Anwendungen zwei- und dreidimensionaler Delaunay-Triangulierungen finden sich in der Stereolithographie und in der Methode der Finiten Elemente.

Wegen der Dualität zwischen Voronoi-Diagramm und Delaunay-Triangulierung kann in einer zur Größe der Struktur proportionalen Zeit aus der einen die jeweils duale Struktur berechnet werden. Im wesentlichen existieren zur Berechnung der Delaunay-Triangulierung einfachere Algorithmen als zur Berechnung des Voronoi-Diagramms. Aus diesem Grund empfiehlt es sich zur Berechnung des Voronoi-Diagramms, zunächst die Delaunay-Triangulierung und anschließend das Voronoi-Diagramm zu bestimmen.

In dieser Diplomarbeit werden eine Reihe von Algorithmen zur Berechnung der Delaunay-Triangulierung mit oder ohne Beschleunigungsstrukturen auf die Eignung für die Computer-Graphik und Netzgenerierung untersucht und miteinander verglichen. Im ersten Kapitel der Arbeit werden die Eigenschaften von Voronoi-Diagrammen und Delaunay-Triangulierungen zusammengestellt. Sie bilden die Grundlage für die im zweiten Kapitel vorgestellten Algorithmen zur Berechnung von zwei- und dreidimensionalen Delaunay-Triangulierungen. Am Ende des zweiten Kapitels befinden sich die ermittelten Laufzeiten der Algorithmen in Form von Tabellen und Graphiken. Das nächste Kapitel gibt einen Überblick über die verwendeten Datenstrukturen und deren Realisierung in Klassen. Das vierte Kapitel beschäftigt sich mit der Visualisierung von dreidimensionalen Triangulierungen. Dort werden einfache Methoden vorgestellt, wie z.B. das Auseinanderziehen der Tetraeder oder das Entfernen einzelner Tetraedern, die die Visualisierung erheblich erleichern. Im letzten Kapitel sind einige Algorithmen für die Netzgenerierung zusammengestellt, die auf den in dieser Arbeit vorgestellten Algorithmen aufbauen. Diese Algorithmen berechnen die bedingte Delaunay-Triangulierung (CDT), die Delaunay-Triangulierung von Polygonen (PDT) und verfeinerte Netze bzw. Triangulierungen durch Einfügen von Punkten. Anschließend wird erklärt, welche Bedeutung die Netzgenerierung für die Stereolithographie, die Modellierung und Visualisierung von Freiformflächen und die Methode der Finiten Elemente besitzt.

Inhaltsverzeichnis:

1.	Grundlagen	6
1.1	Definitionen	6
1.1.1	Graph	6
1.1.2	Simplex, Facette und Kugel	6
1.1.3	Polygon, Polygonnetz und Polyeder	7
1.1.4	Konvexe Hülle	8
1.1.5	Triangulierung	9
1.1.6	Voronoi-Diagramm	10
1.1.7	Delaunay-Triangulierung	12
1.1.8	Delaunay-Triangulierung im R²	13
1.1.9	Delaunay-Tetraedrisierung im R³	13
1.1.10	Zusammenhang mit konvexen Polyedern	14
1.2	Berechnung der Umkugel	15
1.2.1	Umkugel-Kriterium	15
1.2.2	Berechnung der Umkugel	16
1.3	Numerische Probleme	17
2.	Die Algorithmen	19
2.1	Der Flipping-Algorithmus	20
2.2	Der Plane-Sweep-Algorithmus	23
2.3	Der Einfüge-Algorithmus	30
2.3.1	Der randomisierte inkrementelle Algorithmus	34
2.3.2	Strukturen zum Lokalisieren für den Einfüge-Algorithmus	35
2.3.3	Der Einfüge-Algorithmus im R³	41
2.4	Algorithmen mit Suchstrukturen	44
2.4.1	Das reguläre Gitter	44
2.4.2	Die spärliche Matrix	45
2.4.3	Die Berechnung des Startdreiecks	45
2.4.4	Die Berechnung des dritten Punktes	46
2.4.5	Die Shelling-Methode	49
2.4.6	Der Algorithmus im R³	51
2.5	Der Divide-and-Conquer-Algorithmus	56
2.6	Der Delaunay-Wall-Algorithmus	58
2.7	Vergleich der Algorithmen	63
3.	Datenstrukturen und Klassen	74
3.1	Polygonale Netze	74
3.2	Tetraedrisierungen	77
4.	Visualisierung	81
4.1	Die Schichten-Methode	81
4.2	Die Ebenenmethode	82
4.3	Die Strahlmethode	83
4.4	Die Picking-Methode	84
4.5	Die Explosionsmethode	84
4.6	Das Visualisierungsprogramm showTetra	85
5.	Anwendungen	87
5.1	Netzgenerierung	87
5.1.1	Bedingte Delaunay-Triangulierung	87
5.1.2	Delaunay-Triangulierung von Polygonen	89
5.1.3	Algorithmus zum Verfeinern von Netzen	90
5.2	Die Methode der Finite Elemente	91
5.3	Modellierung und Visualisierung von Flächen	91
5.4	Stereolithographie	92