Delaunay-Triangulierung

Ithaqua
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 2. Apr 2005 20:59

Delaunay-Triangulierung

Beitrag von Ithaqua »

Hallo!

Wie erstellt ihr denn die Delaunay-Triangulierung?
Auf Wikipedia http://de.wikipedia.org/wiki/Delaunay-Triangulation hab ich den sog. "Flip-Algorithmus" gefunden, der scheint aber auch nicht so das Gelbe vom Ei zu sein.
Gibt es eine praktikable Methode, ohne mit Zirkel und Geodreieck aufwendig die Dreiecks-Umkreise konstruieren zu müssen?

Viele Grüße,
Sascha.

Benutzeravatar
buhrmi
Windoof-User
Windoof-User
Beiträge: 34
Registriert: 25. Okt 2004 01:48
Kontaktdaten:

Beitrag von buhrmi »

Sehr naiv:
1. Du machst eine beliebige Triangulierung Tri_0.
2. Finde in Tri_i alle benachbarten Dreiecke die das Delaunay Kriterium verletzen und flippe ihre gemeinsame Kante. Dann hast du Tri_i+1
3. Wiederhole Schritt 2 solange bis Delaunay Kriterium erfüllt ist.
Bild

Ithaqua
Mausschubser
Mausschubser
Beiträge: 65
Registriert: 2. Apr 2005 20:59

Beitrag von Ithaqua »

buhrmi hat geschrieben:Sehr naiv:
1. Du machst eine beliebige Triangulierung Tri_0.
2. Finde in Tri_i alle benachbarten Dreiecke die das Delaunay Kriterium verletzen und flippe ihre gemeinsame Kante. Dann hast du Tri_i+1
3. Wiederhole Schritt 2 solange bis Delaunay Kriterium erfüllt ist.
Jo, das ist der Algorithmus aus Wikipedia.
Probier den mal bei der Übungsaufgabe aus. Hab ich gemacht und festgestellt, dass ich irgendwann (bin von oben nach unten vorgegangen) nicht mehr weiterkam, weil weder die eine Variante noch die andere durch das Flippen ein korrektes Dreieck ergab.

Antworten

Zurück zu „Archiv“