Geometrische Algorithmen in der Flächenrückführung
Loading...
Date
2001-01-17
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universität Dortmund
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.
Description
Table of contents
Keywords
Algorithmische Geometrie, Aufzählungsalgorithmen, computational geometry, Delaunaydiagramme, delaunay diagrams, enumeration algorithms, Flächenrückführung, Polygonale Hüllen, polygonal hulls, reverse engineering, Sphärische konvexe Hüllen, spherical convex hulls, surface reconstruction, triangulation, Triangulierung