Geometrische Algorithmen in der Flächenrückführung

Abstract

Gegenstand der Flächenrückführung ist, aus einer gegebenen Menge von Abtastpunkten einer Fläche eine Näherung zu rekonstruieren, die die Fläche möglichst gut repräsentiert. Ein weit verbreiteter Ansatz ist, die rekonstruierte Fläche durch ein Netz aus Polygonen, meist Dreiecken, zu beschreiben. Die Schwierigkeit besteht darin, unter den kombinatorisch vielen Möglichkeiten eine "gute" Rekonstruktion zu erhalten, insbesondere für den Fall, dass die ursprünglich gegebene Fläche nicht bekannt ist. Im Zusammenhang mit Verfahren zur Flächenrückführung treten vielfältige geometrische Teilprobleme auf, die für sich gesehen interessant sind. In dieser Arbeit werden für eine Reihe solcher Probleme effiziente Algorithmen entwickelt. Zu nennen sind Korrektheitsbetrachtungen für den gebräuchlichen Oriented-Walk-Algorithmus, Triangulierung innerhalb frei wählbarer, nicht konvexer Gebiete in der Ebene, Berechnung konvexer Hüllen von Polygonen auf Sphären mit linearem Zeitaufwand, Stabilität von Delaunay-Facetten mit Anwendung auf die Rekonstruktion geschlossener Flächen sowie effiziente Aufzählung polygonaler Hüllen.