zur Institutsseite   
Geoinformatik-Service

Lexikon | Wörterbuch | Vorlesung | Links | Produkte | Literatur | Ausbildung | Schriften

 zur Universitätsseite
 

Delaunay-Triangulation 


Themengebiet: Digitales Geländemodell

Delaunay-Prinzip  
Delaunay-Prinzip
Bedeutung:
Eine Methode zur Erstellung eines Dreiecknetzes aus einem Satz von Punkten. Die Dreiecke sind mit der Bedingung definiert, dass innerhalb eines Umkreises um drei Punkte, die ein Dreieck bilden, kein weiterer Punkt liegt (Kriterium des leeren Umkreises). Dies ist eine Methode, die wohlgeformte Dreiecke (nahe an gleichseitigen Dreiecken) produziert. Die resultierenden Dreiecke überlappen sich nicht und vermaschen eine beliebig große Punktmenge flächendeckend und einheitlich. Ein wichtiger rechentechnischer Aspekt ist, dass sich die Delaunay-Triangulation in der Ordnung O(n log(n)) erzeugen lässt. Die Delaunay-Triangulation findet Anwendung bei Digitalen Geländemodellen und bildet dort die TIN-Datenstruktur (Triangular Irregular Network) im Gegensatz zur Grid- bzw. Rasterdatenstruktur. Sie stellt den dualen Graphen zum Voronoi-Diagramm bzw. Thiessen-Diagramm dar, der das Problem der nächsten Nachbarschaft beschreibt.

Zum Begriff:
Korrekturen/Ergänzungen schreiben
Letzte Änderung: 22.12.2003



zurück nach obenProfessur für Geodäsie und Geoinformatik (GG) AUF Universität Rostock
© 2001-2016 GG - All Rights Reserved - Kontakt - Webmaster