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