Implementierung einer Datenstruktur für simpliziale 3D-Netze

Natalya Obydenna, Leibniz Universität Hannover, Studienarbeit
04/2009

Heutzutage treten in verschiedensten Anwendungen häufig sehr große dreidimensio-
nale simpliziale Netze auf. Deren Sicherung ist speicherintensiv und beeinträchtigt
daher die Berechnungsgeschwindigkeit. Aus diesem Grund ist eine Datenstruktur ge-
wünscht, die möglichst kompakt ist.

In einer Arbeit von 2003 stellten D. K. Blandford et al. eine Datenstruktur für simpliziale Netze vor, die geeignet ist, um Dreiecks- oder Tetraedernetze zu verwalten. Sie zeichnet sich durch eine einfach zu benutzende Schnittstelle aus und ist in der Lage, die Daten bei geringer Beeinträchtigung der Laufzeit zu komprimieren. Die Datenstruktur speichert eine Auswahl repräsentativer Kanten mit dazugehörigen Adjazenzlisten. Die Anzahl der repräsentativen Kanten beträgt dabei nur ein Viertel der gesamten Kanten.

Diese Datenstruktur ist effizient in Hinblick auf ihren Speicherbedarf und Zugriffszeiten; siegestattet  wichtige Zugriffe in konstanter Zeit, sofern die Knoten (bei Dreiecksnetzen), bzw. Kanten (bei Tetraedernetzen) beschränkten Grad haben.

Als erste Anwendung wurde die Delaunay-Tesselation mit dem Bowyer-Watson-Algorithmus implementiert.

Kontakt: Philipp Blanke