View
214
Download
1
Category
Preview:
Citation preview
1
Seminar ApproximationstheorieLehrstuhl Mathematik IVG. Nürnberger, M. Matt, G. Schneider
Delauny Triangulierung
Abbas Yavuz 15.09.2011
2
Inhaltsverzeichnis
Polygon (n-Eck / Vieleck), Einfaches Polygon
Triangulierung einfacher Polygone
Anzahl von Dreicken in einem n-Eck für n≥3 * Beweis für [n-2 Dreiecke] in einem n-Eck für n≥3 durch vollständige Induktion
Triangulierung einer beliebigen Punktmenge
„Winkelvektor“ & „Winkeloptimal“
„Edge-Flip“ & „illegale Kanten“
Das Kreiskriterium
Die Delauny-Triangulierung* Ermittlung der Delauny-Triangulierung* Delauny-Triangulierung Algorithmus
LegalizeEdge Algorithmus
Die Arbeitsweise des „Delauny-Triangulierung“ anhand eines Applets
3
Polygon (=n-Eck, Vieleck)
Definiton Polygone:
Unter einem Polygon P versteht man ein Gebiet im ℝ², welches durch einen geschlossenen Polygonzug beschränkt wird.
Der Rand von P lässt sich also folgendermaßen darstellen:-> P= Z(t0,…, tn) wobei tn = t0
Die Punkte t0,…,tn-1 werden auch als Ecken des Polygons bezeichnet.
Dieses Polygon besitzt 9 Ecken.
Die Mengen nennt man Kanten von P
Und alle anderen Verbindungsstrecken bezeichnet man als Diagonalen:
4
Einfaches Polygon
Gehören zu jeder Ecke höchstens zwei Kanten und ergibt der Schnitt zweier Kanten die leere Menge oder einen Eckpunkt, so ist die Rede von einem „einfachen Polygon“.
Diagonale des Polygons.Kante des Polygons.
Diagonale des Polygons = Menge aller Strecken zwischen den Ecken, die nicht zum Rand gehören!
Ecke des Polygons.
5
Triangulierung einfacher Polygone
Sei P ein einfaches Polygon!
Triangulierung T(P) von P: Zerlegung von P in Dreiecke durch eine maximale Anzahl von Diagonalen, die sich nur in einem Eckpunkt oder überhaupt nicht schneiden.
n=3 3 Eckenn=4; 4 Ecken. Hier ist es möglich, dieses
einfache Polygon durch eine Diagonale in zwei Dreiecke zu zerlegen!
Triangulierung mit einem 6-Eck:
Möglichkeit1: 6 Ecken, 3 Diagonale und 4 Dreiecke
Möglichkeit2: 6 Ecken, 3 Diagonale und 4 Dreiecke
Wichtig:Bedingung = n≥3, sonst
kein geschlossener Polygonzug möglich!
Also mind. ein 3-Eck.
6
Anzahl von Dreicken für n≥3
Für jedes einfache Polygon mit n≥3 Ecken existiert eine Triangulierung, die aus genau n-2 Dreiecken besteht!
n=3 3-2 = 1, 1 Dreieck.
n=4 4-2 = 2, 2 Dreiecke.
n=5 5-2 = 3, 3 Dreiecke.
n=9 9-2 = 7, 7 Dreiecke.
7
Beweis für [n-2 Dreiecke] durch Vollständige Induktion
Für n=3 ist es offensichtlich erfüllt. (=> 3-2=1, ein Dreieck)
IA: Für alle n<m gilt: Es existiert ein T(P) mit genau „n-2“ Dreiecken.n: Anzahl der Eckenm: Anzahl eines beliebigen Polygons
Sei nun P ein Polygon mit m Ecken, z.B.
Diagonale D. (Kante D)P2
P1
Polygon PDurch Diagonale D ist P in 2 Teilpolygone zerlegt; P1 mit m1 Ecken und P2 mit m2 Ecken.
Nach Vss. können P1 und P2 trianguliert werden, und somit auch P. Da mind. 1 Ecke aus P1 nicht in P2 enthalten ist, folgt: m1 , m2 < m Für die Anzahl der Dreiecke in P gilt nun folgende Überlegung:
- Beide Teilpolygone P1 & P2 teilen sich NUR die Kante D.- Daher liegen auch NUR die 2 zugehörigen Ecken in dem Schnitt der beiden Eckmengen. Somit gilt: (m1 + m2 = m + 2) - Nach IV besteht P1 aus (m1 – 2) und P2 aus (m2 - 2) Dreiecken. Also besteht P aus (m1 – 2) + (m2 - 2) = (m +2) – 4 = m – 2 Dreiecken.
Dies entspricht der Behauptung!
8
Triangulierung einer beliebigen Punktmenge (1/2)
Höhe der Punkte aus der vorgegebenen Punktmenge (=Terrain/Landschaft) nur anbestimmten Messpunkten bekannt. Daher: Approximation/Interpolation der Zwischenräume erforderlich, um sich ein ein Bild von der Oberfläche zu verschaffen.
Durch die Triangulierung dieser Punktemenge entstehen Dreiecke! Diese Landschaft kann als ein Graph einer Funktion f: ℝ² ℝ formuliert werden, die jedem
Punkt der Ebene eine bestimmte Höhe zuweist.
9
Triangulierung einer beliebigen Punktmenge (2/2)
Def. Einer Triangulierung T einer Punktmenge P:
Eine Triangulierung T(P) ist eine planare Aufteilung der konvexen Hülle von P in Dreiecke mit Eckpunkten aus P. (planar = Keine Kanten schneiden sich)
Anzahl von Dreiecken und Kanten:
Jede beliebige Triangulierung T(P) mit Punkten P={p1,…,pn} hat (2n-2+k) Dreiecke
und (3n-3-k) Kanten. (k= Anzahl der Punkte, die auf dem Rand liegen.)
- Anzahl der Dreiecke m= 2n-2+k Somit hat T(P) m Dreiecke!- Anzahl der Kanten ne = 3n-3-k
10
„Winkelvektor“ & „Winkeloptimal“
Definition „Winkelvektor“:- Gegeben sei eine Triangulierung T(P) mit m Dreiecken. - Somit gibt es demnach 3m Winkel. - Alle Winkel einer Triangulierung T(P) sind in einem Vektor angelegt, die aufsteigend
sortiert sind nach der Größe: A(T) von T. A(T) = {a1,…, a3m}
Definition „Winkeloptimal“:- Eine Triangulierung T(P) ist winkeloptimal, wenn ihr Winkelvektor im vgl. zu allen
anderen möglichen Triangulierung T‘ der größte ist:
A(T(P)) ≥ A(T‘(P)) für alle T‘ von P gilt!
11
Edge-Flip & Illegale Kanten
Definition „Edge-Flip“:- Entfernen der Kante pipj und Hinzufügen der Kante plpk
Kante pipj
Kante plpk
Definition „Illegale Kante“:- Voraussetzung hierfür ist, wenn durch einen „Edge-Flip“ der minimale der 6 Winkel
vergrößert werden kann, also
12
Das Kreiskriterium
Sei nun C der Kreis durch pi,pj und pk. Die Kante pipj ist genau dann illegal, wenn der Punkt pl im Inneren von C liegt.
13
Die Delauny Triangulierung
Nun wird der Voronoi-Graph einer Punktmenge P betrachtet.- Der Delauny-Graph von P besitzt nun -- einen Knoten für jeden Punkt in P -- einen Bogen zwischen 2 Knoten, wenn die zugehörigen Voronoi-Zellen eine gemeinsame Kante besitzen.
Wenn die Bögen zu geraden Linien überführt werden, so entsteht der Delauny-Graph DG(P)
Wichtig: In einem Delauny-Graph kreuzen sich keine zwei Kanten! (Eine Triangulierung t ist legal, wenn T eine Delauny Triangulierung von P ist.
14
Ermittlung der Delauny-Triangulierung
„Randomized incremental“ – Algorithmus:
Punkte der Punktmenge P werden nacheinander in willkürlicher Reihenfolge dem Graphen hinzugefügt.
Hilfsdreieck durch die Punkte p0 p-1 p-2 zeichnen:
Durch dieses Hilfsdreieck werdenBegrenzungen erzeugt,
wobei das Dreieck alle Punkte von P im Innern haben muss.
15
Ermittlung der Delauny-Triangulierung
Ein Punkt pr wird hinzugefügt:
Der Punkt pr in einem Dreieck:
3 Kanten werden daher hinzugefügt.
Der Punkt pr auf einer Kante:
2 Kanten werden daher hinzugefügt.
GESUCHT: 1.) Das Dreieck, in das der Punkt fällt. 2.) Die Kante, auf die der Punkt fällt.
16
Delauny Triangulierung - Algorithmus
Algorithmus: Delauny Triangulierung (P)Input: Eine Punktemenge P in der Ebene.Output: Eine Triangulierung t von P
1 P0p-1p-2 seien Punkte derart, dass P im Dreieck p0p-1p-2 enthalten ist.
2 T als Triangulierung bestehend aus p0p-1p-2 initialisieren.
3 Berechne eine zufällige Reihenfolge der Punkte p1,p2,…,pn von P
4 for r=1 to n do5 Suche das Dreieck pipjpk das pr enthält.
6 Füge pr zu T hinzu.
7 If (pr liegt im Innern des Dreiecks pipjpk) then8 Füge die drei Kanten von pr zu pipjpk zu T hinzu.
9 LEGALIZEEDGE (pr,pipj,T)
10 LEGALIZEEDGE (pr,pjpk,T)
11 LEGALIZEEDGE (pr,pkpi,T)
12 else pr liegt auf einer Kante pi pj des Dreiecks.
13 Füge die zwei Kanten von pr zu pk und pl zu T hinzu
14 LEGALIZEEDGE (pr,pipl,T)
15 LEGALIZEEDGE (pr,plpj,T )
16 LEGALIZEEDGE (pr,pjpk,T)
17 LEGALIZEEDGE (pr,pkpi,T)
18 Entferne p0 p-1 p-2 und alle zugehörigen Kanten.
19 Return T
17
LegalizeEdge- Algorithmus
Die Triangulierung, die man nach Hinzufügen der Kanten erhalten hat, muss noch in eine Delauny-Triangulierung mit lediglich legalen Kanten umgewandelt werden.
Nur, wenn ein zugehöriges Dreieck verändert wurde, können legale Kanten illegal werden! DAHER: Nur die Kanten der neuen Dreiecke müssen überprüft werden!
JEDOCH: Wenn LEGALIZEEDGE einen Edge-Flip durchführt, können dann andere Kanten illegal werden!
Schlussfolgerung: Rekursiver Aufruf von LEGALIZEEDGE innerhalb der Prozedur!
Algorithmus: LEGALIZEEDGE (pr,pipj,T)1 pr ist hinzugefügter Punkt, pi pj ist Kante von T, die evtl. illegal ist
2 if (pi pj ist illegal) then3 Sei pipjpk das gegenüberliegende Dreieck zu prpipj bezüglich pipj
4 Ersetze pi pj mit pr pk (Edge-Flip!)
5 LEGALIZEEDGE (pr,pipk,T)
6 LEGALIZEEDGE (pr,pkpj,T)
18
LegalizeEdge- Algorithmus
Überprüfung, ob Kante illegal ist, kann durch die Anwendung des Kreiskriteriumsdurchgeführt werden!
Fazit: Da eine Kante nur dann illegal werden kann, wenn ein zugehöriges Dreieck verändert wird und da auch jedes pr zugehöriges Dreieck durch LEGALIZEEDGE überprüft wird, folgt
demnach die Korrektheit des Algorithmus!
Folge: Offensichtlich ist nun, dass neu hinzugefügte legale Kanten immer zu pr
zugehörig sind.
19
Arbeitsweise des „Delauny-Algorithmus“
Die Arbeitsweise des „Delauny-Algorithmus“ anhand eines Applets, das den Algorithmus schrittweise verdeutlicht!
http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/
20
Ich bedanke mich für eure Aufmerksamkeit!
21
Literaturverzeichnis
Mark de Berg, Otfried Cheong, Marc von Kreveld & Mark Overmars,
„Computational Geometry: Algorithms and Applications“ (2008)
http://www.cs.uu.nl/geobook/
http://www.pi6.fernuni-hagen.de/GeomLab/VoroGlide/ (Applet der Fernuni-Hagen)
Tom Dickmeiß (Uni-Bonn), „Zur graphtheoretischen Dilation der Delauny- Triangulation und verwandter Graphen“ (2005)
Matthias Lenga (Uni-Ulm), „Algorithmen: Delauny Triangulation“ (2010)
ttp:::www:un ulm: : l m n:w s t un ulm: u :: nst::::h i defie ad i eb i e_ i_ i ii
:L r :::::::::ros m n r:l o: us r eh e e i a g a a btun l un : Tr n ul t on n:pei g_De a a_i a g a i e df
Recommended