D -

•

Iiil

.

~

:.

,

\,

I

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

page x

1 I

11 16

24 27 32

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

44 44

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

63

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

47 51 56

58

64

66 68

69 72 87

88 91

96 101 101 109 117 146

149 150 153

Contents

Vl\l

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

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

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

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

294 294 295 300 302 313 322 339

9. Sources Bibliographies and FAQs 9.1 9.2 Textbooks Book Collections 9.3

347 347 347 348

Contents 9.4 9.5 9.6 9.7

Monographs Journals Conference Proceedings Software

IX

349 349

350 350

Bibliography

351

Index

361

Preface

Computational geometry broadly construed is the study of algorithms for solving geometric problems on a computer. The emphasis in this text is on the design of such algorithms, with somewhat less attention paid to analysis of performance. I have in several cases carried out the design to the level of working C programs, which are discussed in detail. There are many brands of geometry, and what has become known as "computational geometry," covered in this book, is primarily discrete and combinatorial geometry. Thus polygons playa much larger role in this book than do regions with curved boundaries. Much of the work on continuous curves and surfaces falls under the rubrics of "geometric modeling" or "solid modeling," a field with its