Geometric approximations in 2- and 3-dimensional space

Abstract

The goal of geometric approximation is to replace a given complex geometric object by a simpler object while capturing the significant features of the original. In the first part of the thesis we deal with approximating polygonal curves in 2-dimensional space. For a polygonal curve this approximation can be done either by a simpler polygonal curve (a curve with less segments) or by a higher order curve. We were able to compute an approximation of open polygonal curves with the minimum number of circular arcs (chapter 1) and also with the minimum number of biarcs (chapter 2) for a given upper error bound epsilon. In the second part of the thesis we move on the 3-dimensional space and to polytope approximations. We initiate the study of this problem by considering convex surfaces only, for simplicity, before moving on to non convex surfaces. A first natural step to higher order approximation of convex polytopes is the approximation with spheres or spherical patches. In chapter 3 we can show that deciding the existence of an approximation of a convex polytope with a given upper error bound epsilon and not more than a given number of spherical patches is NP-hard. In chapter 4 we present a new technique for constructing a curved surfaces based on inscribed polytopes resulting in a convex surface consisting of spherical patches. To tackle the approximation problem for non- convex polytopes we pick up the idea of an incremental approximation algorithm introduced in chapter 4. This induces the problem of finding a simple and topological correct start polytope, the seed polytope, for non-convex polytopes. In chapter 5 we describe how to construct for a surface in 3D space, given by sample points S, a coarse approximating polytope P that uses a subset of the points as vertices and preserves the topology. In contrast to surface reconstruction we do not use all sample points, but we try to use as few points as possible. We also give a short introduction how to use the results for the seed polytope generation for surface reconstruction.

Die Approximation eines geometrischen Objektes hat zum Ziel, ein komplexes Objekt durch ein vereinfachtes zu ersetzen, ohne die Charakteristika des ursprünglichen Objektes zu verlieren. In der Dissertation werden Approximationsalgorithmen für polygonale Kurven im 2-dimensionalen Raum und für Flächen im 3-dimensionalen Raum vorgestellt. Im ersten Teil behandeln wir die Approximation von polygonalen Kurven. Die Approximation einer polygonalen Kurve kann durch eine ebenfalls polygonale, aber nun einfachere, Kurve (eine Kurve mit weniger Segmenten), oder durch eine Kurve höherer Ordnung erfolgen. Man verbindet typischer Weise zwei Optimierungsprobleme mit der Approximation von polygonalen Kurven. Man möchte entweder die Anzahl der verwendeten Teilstücke der approximierenden Kurve zu einer gegebenen Fehlertoleranz minimieren oder man versucht den Approximationsfehler der approximierenden Kurve zu minimieren, hierbei wird die Anzahl der zu verwendeten Teilstücke vorgegeben. Während zahlreiche Algorithmen in der Literatur bekannt sind, die diese Optimierungsprobleme für die Approximation mit polygonalen Kurven lösen, so stellen sich die gleichen Fragen auch für die Approximation mit Kurven höheren Grades. Wir stellen in dieser Arbeit sowohl einen Algorithmus vor, der eine polygonale Kurve mit einer minimalen Anzahl and Kreisbögen, als auch einen Algorithmus der eine polygonale Kurve mit der minimalen Anzahl Biarcs (zwei glatt miteinander verbundene Kreisbögen) approximiert. Im zweiten Teil der Arbeit wenden wir uns der Approximation von Flächen im 3-dimensionalen Raum zu. Wir stellen zwei Algorithmen vor, die aus einer gegebenen Punktmenge die Oberfläche eines Objektes rekonstruieren. Zuerst betrachten wir nur Punktemengen in konvexer Lage und zeigen, dass die Approximation dieser Punktmengen mit einer minimalen Anzahl an Kugelkappen NP-schwer ist. Da dieses Problem vermutlich nicht optimal zu lösen ist, präsentieren wir einen inkrementellen Greedy-Algorithmus, der eine gegebene Punktemenge in konvexer Lage mit einer gekrümmten Fläche aproximiert. Als letztes betrachten wir die Rekonstruktion einer Fläche aus einer Punktmenge in nicht konvexer Lage. Hierbei nehmen wir die Idee des inkrementellen Ansatzes auf. Um eine Startkonfiguration für einen inkrementellen Algorithmus zu haben, stellen wir einen Algorithmus vor, der aus einer Punktprobe einer nicht konvexen Fläche ein möglichst kleines (aber nicht garantiert das kleinste) Polytop erzeugt, das folgende Eigenschaften hat: die Mittelachse der ursprünglichen Fläche ist im Polytop enthalten, das Polytop verläuft durch eine Teilmenge der Probenpunkte und die ursprüngliche Topologie bleibt erhalten. Wie zeigen wie dieser Algorithmus nicht nur für die Erzeugung eines Startpolytops genutzt werden kann, sondern auch um skalierbare Rekonstruktionen der Fläche zu erzeugen.