Computational Geometry in C (2nd ed.) [O'Rourke 1998-10-13].pdf

(15880 KB) Pobierz
D
•
:.
I
,
,
,
"
,
-
Iiil
.
.:
~
,
\
,
j
.
,.'
,
,
,
-
-
•
-
•
,
lI!"
_11:-
JOSEPH
O'ROURKE
COMPUTATIONAL
GEOMETRY
IN C
SECOND EDITION
JOSEPH O'ROURKE
Contents
Preface
1. Polygon 1iiangulation
1.1
Art Gallery Theorems
1.2
Triangulation: Theory
1.3
Area of Polygon
1.4
Implementation Issues
1.5
Segment Intersection
1.6
Triangulation: Implementation
2. Polygon Partitioning
2.1
Monotone Partitioning
2.2
Trapezoidalization
2.3
Partition into Monotone Mountains
2.4
Linear-Time Triangulation
2.5
Convex Partitioning
3. Convex Hulls in Two Dimensions
3.1
Definitions of Convexity and Convex Hulls
3.2
Naive Algorithms for Extreme Points
3.3
Gift Wrapping
3.4
QuickHull
3.5
Graham's Algorithm
3.6
Lower Bound
3.7
Incremental Algorithm
3.8
Divide and Conquer
3.9
Additional Exercises
4. Convex Hulls in Three Dimensions
4.1
Polyhedra
4.2
Hull Algorithms
4.3
Implementation of Incremental Algorithm
4.4
Polyhedral Boundary Representations
4.5
Randomized Incremental Algorithm
4.6
Higher Dimensions
4.7
Additional Exercises
page
x
1
I
11
16
24
27
32
44
44
47
51
56
58
63
64
66
68
69
72
87
88
91
96
101
101
109
117
146
149
150
153
Vl\l
Contents
s.
Voronoi Diagrams
5. I
5.2
5.3
5.4
5.5
5.6
5.7
5.8
Applications: Preview
Definitions and Basic Properties
Delaunay Triangulations
Algorithms
Applications in Detail
Medial Axis
Connection to Convex Hulls
Connection to Arrangements
155
155
157
161
165
169
179
182
191
193
193
194
199
201
201
205
209
218
220
220
220
226
239
245
252
263
266
269
272
285
294
294
295
300
302
313
322
339
347
347
347
348
6.
Arrangements
6.1
Introduction
6.2
Combinatorics of Arrangements
6.3
6.4
6.5
6.6
6.7
6.8
Incremental Algorithm
Three and Higher Dimensions
Duality
Higher-Order Voronoi Diagrams
Applications
Additional Exercises
7.
Search and Intersection
7.1
7.2
7.3
7.4
7.5
7.6
7.7
7.8
7.9
7.10
7.11
Introduction
Segment-Segment Intersection
Segment-Triangle Intersection
Point in Polygon
Point in Polyhedron
Intersection of Convex Polygons
Intersection of Segments
Intersection of Nonconvex Polygons
Extreme Point of Convex Polygon
Extremal Polytope Queries
Planar Point Location
8.
Motion Planning
8.1
Introduction
8.2
Shortest Paths
8.3
Moving a Disk
Translating a Convex Polygon
8.4
8.5
Moving a Ladder
8.6
Robot Arm Motion
8.7
Separability
9.
Sources
Bibliographies and FAQs
9.1
9.2
Textbooks
Book Collections
9.3
Contents
9.4
9.5
9.6
9.7
Monographs
Journals
Conference Proceedings
Software
IX
349
349
350
350
351
361
Bibliography
Index

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin