Planar Nef polyhedra and generic higher-dimensional geometry [Elektronische Ressource] / von Michael Seel

Sujets

• Informatik

Informations

• Publié par: universitat_des_saarlandes
• Publié le: 01 janvier 2004
• Nombre de lectures: 8
• Langue: English
• Poids de l'ouvrage: 1 Mo

Extrait

Planar Nef Polyhedra
and
Generic Higher-dimensional Geometry
Dissertation
zur Erlangung des Grades
des Doktors der Ingenieurswissenschaften (Dr.-Ing.)
der Naturwissenschaftlich-Technischen Fakultat¨ I
der Universitat¨ des Saarlandes
von
Michael Seel
Saarbruck¨ en
8. August 2001Abstract
We present two generic software projects that are part of the software library CGAL. The first part
describes the design of a geometry kernel for higher-dimensional Euclidean geometry and the inter-
action with application programs. We describe the software structure, the interface concepts, and
their models that are based on coordinate representation, number types, and memory layout. In the
higher-dimensional software kernel the interaction between linear algebra and the geometric objects
and primitives is one important facet. In the actual design our users can replace number types, re-
presentation types, and the traits classes that inflate kernel functionality into our current application
programs: higher-dimensional convex hulls and Delaunay tedrahedralisations.
In the second part we present the realization of planar Nef polyhedra. The concept of Nef polyhe-
dra subsumes all kinds of rectilinear polyhedral subdivisions and is therefore of general applicability
within a geometric software library. The software is based on the theory of extended points and
segments that allows us to reuse classical algorithmic solutions like plane sweep to realize binary
operations of Nef polyhedra.
Zusammenfassung
Wir prasentieren¨ zwei Softwareprojekte, die Teil der Softwarebibliothek CGAL sind. Der erste
Teil beschreibt den Entwurf eines Geometriekerns fur¨ hoherdimensionale¨ euklidische Geometrie
und dessen Interaktion mit Anwendungsprogrammen. Wir beschreiben die Softwarestruktur, die
auf der Herausarbeitung von Schnittstellenkonzepten und ihren Modellen hinsichtlich Koordinaten-
reprasentation,¨ Zahlentypen und Speicherablage beruht. Dabei spielt im Hoherdimensionalen¨ die
Interaktion zwischen linearer Algebra und den entsprechenden geometrischen Objekten und primi-
tiven Operationen eine wesentliche Rolle. Unser Entwurf erlaubt das Auswechseln von Zahlentypen,
Reprasentations-¨ und Traitsklassen bei der Berechnung von d-dimensionalen konvexen Hullen¨ und
Delaunay-Simplexzerlegungen.
Im zweiten Teil stellen wir die Realisierung von planaren Nef-Polyedern vor. Das Konzept der
Nef-Polyeder umfasst alle linear-polyedrisch begrenzten Unterteilungen. Wir beschreiben ein Soft-
waremodul das umfassende Funktionalitat¨ zur Verfugung¨ stellt. Als theoretische Grundlage des Ent-
wurfs dient die Theorie erweiterter Punkte und Segmente, die es uns erlaubt, vorhandene Algorithmen
wie z.B. Plane-Sweep zur Realisierung binarer¨ Operationen von Nef-Polyedern zu nutzen.Danke
Diese Arbeit ist das Ergebnis meiner Tatigk¨ eit in der Arbeitsgruppe von Kurt Mehlhorn am Max-
Planck-Institut fur¨ Informatik zwischen 1996 und 2001. Gigadank an Kurt Mehlhorn fur¨ seine Un-
terstutzung,¨ seine motivierende und menschliche Art und die Moglichk¨ eit an den Projekten LEDA
und CGAL aktiv teilzunehmen. Die Erfahrungen waren vielfaltig¨ und wertvoll: menschlich, inge-
nieurtechnisch und wissenschaftlich. Neben meinem Doktorvater habe ich auch Stefan Schirra als
meinem Zweitbetreuer zu danken. Er hat mir oft genug den C++ Standard interpretiert und mich bei
kritischen Fragen beraten.
Die Arbeit in beiden Projektgruppen war ambitioniert, und manchmal voller Emotionen. Die
Arbeit innerhalb der LEDA Gruppe mit Kurt, Stefan und Christian war mit ihren kurzen We-
gen und schnellen Entscheidungen produktiv und abwechslungsreich. Es war toll, LEDA als wis-
senschaftliches Projekt zu betreuen. In CGAL ging es mehr als einmal um die perfekte Software. Die
CGAL Entwicklertreffen mit Matthias, Herve, Andreas, Bernd, Geert-Jan, Susan, Shai, Michael, Lutz,
Dima, Eli, Sylvain, Sven, Monique und Mariette waren kreativ und spannend, wenn auch manch-
mal die Diskussionen unser aller Geduld strapaziert haben. Wir haben es — trotz Widrigkeiten —
geschafft, CGAL zu einem tollen Paket zu machen.
Die Nerds am MPI waren ein tolles Lunch- und Forschungsteam. Danke Andreas, Anker, Ernst,
Fritz, Knut, Mark, Stefan (der Schwabe), Sven, Uli, und all den anderen fur¨ die erquickliche Zeit.
Nicht zu vergessen sind auch all die Menschen in der RGB, Verwaltung und der Bibliothek. Beson-
deren Dank an Birgit, Bernd, Jor¨ g, Volker (den Grosswesir) und Wolfram. Danke auch Wolfgang, als
Quell mathematischer Weisheit bist du nicht zu schlagen.
Zuguter Letzt einen Megadank an Brinja und meine Familie, fur¨ all die Unterstutzung¨ und Hilfe
in den Situationen, als ich zweifelte und haderte. Es hat sich gelohnt.Contents
1 Introduction 1
1.1 Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Graphs and Plane Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.3 Programming Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.4 Unified Modeling Language . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Generic higher-dimensional geometry 19
2.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.2 Kernel Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 The Kernel Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2.5 Generic Programming Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.6 Discussion and Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3 Infimaximal Frames 43
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.2 Alternative Approaches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.3 Our approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.1 Frame Points and Extended Points . . . . . . . . . . . . . . . . . . . . . . . 46
3.3.2 The Endpoints of Segments, Rays, and Lines . . . . . . . . . . . . . . . . . 47
3.3.3 Predicates on Extended Points . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.3.4 Extended Segments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.3.5 Intersections of Extended Segments . . . . . . . . . . . . . . . . . . . . . . 49
3.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4.1 Polynomials in one variable . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4.2 Simple implementation - Standard kernel plus polynomial number type . . . 59
3.4.3 Filtered - Specialized kernel plus filtered inline . . . . . . . 68
i3.5 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4 Planar Nef Polyhedra 79
4.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.2 Previous Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
4.3 The Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
4.4 The Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
4.5 Top Level Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.5.1 The Polyhedron Class . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
4.5.2 Creating Polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
4.5.3 Unary Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
4.5.4 Binary Set Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
4.5.5 Binary Comparison Operations . . . . . . . . . . . . . . . . . . . . . . . . . 97
4.5.6 Point location and Ray shooting . . . . . . . . . . . . . . . . . . . . . . . . 97
4.5.7 Visualization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
4.5.8 Input and Output . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.5.9 Hiding extended geometry . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.6 Plane Map Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
4.7 Subdivision, Selection, and Simplification . . . . . . . . . . . . . . . . . . . . . . . 106
4.7.1 Notions and definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
4.7.2 The class design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4.7.3 Overlay calculation of a list of segments . . . . . . . . . . . . . . . . . . . . 109
4.7.4 Overlay of two plane maps . . . . . . . . . . . . . . . . . . . . . 111
4.7.5 Creating face objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
4.7.6 Selecting marks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.7.7 Simplification of attributed plane maps . . . . . . . . . . . . . . . . . . . . 123
4.8 A Generic Segment Sweep Framework . . . . . . . . . . . . . . . . . . . . . . . . . 126
4.8.1 Formalizing the sweep — Invariants . . . . . . . . . . . . . . . . . . . . . .