Preface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
What This Book Contains . . . . . . . . . . . . . . . . . . . . . . . . . . . xi
What You Should Know before Reading This Book . . . . . . . . . . . . . . . . xi
How to Obtain and Install Cgal  . . . . . . . . . . . . . . . . . . . . . .  xii
License . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  xvi
Style Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  xvi
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii
Cover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii
Errata  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvii
1 Introduction  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  1
1.1 Arrangements  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  1
1.2 Generic Programming . . . . . . . . . . . . . . . . . . . . . . . . . . .  2
1.2.1 Concepts and Models . . . . . . . . . . . . . . . . . . . . . . . . . .  2
1.2.2 Traits Classes  . . . . . . . . . . . . . . . . . . . . . . . . . . . .  3
1.2.3 Generic and Object-Oriented Programming . . . . . . . . . . . . . . . .  5
1.2.4 Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  7
1.3 Geometric Computing . . . . . . . . . . . . . . . . . . . . . . . . . . .  7
1.3.1 Separation of Topology and Geometry . . . . . . . . . . . . . . . . . .  8
1.3.2 Exact Geometric Computation . . . . . . . . . . . . . . . . . . . . . .  8
1.3.3 Well-Behaved Curves . . . . . . . . . . . . . . . . . . . . . . . . . .  9
1.4 The Computational Geometry Algorithm Library  . . . . . . . . . . . . . . 10
1.4.1 Cgal Chronicles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.2 Cgal Content  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4.3 The Algebraic Foundations of Cgal . . . . . . . . . . . . . . . . . . . 11
1.4.4 The Geometry Kernel of Cgal . . . . . . . . . . . . . . . . . . . . . . 12
1.4.5 The State of Cgal . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.4.6 The Namespace of Cgal . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.5 Outline of the Book . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.6 Further Reading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2 Basic Arrangements  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.1 Representation of Arrangements: The Dcel  . . . . . . . . . . . . . . . . 19
2.2 The Main Arrangement Class  . . . . . . . . . . . . . . . . . . . . . . . 20
2.2.1 Traversing the Arrangement  . . . . . . . . . . . . . . . . . . . . . . 22
2.2.2 Modifying the Arrangement . . . . . . . . . . . . . . . . . . . . . . . 26
2.2.3 Input/Output Functions  . . . . . . . . . . . . . . . . . . . . . . . . 33
2.3 Application: Obtaining Silhouettes of Polytopes . . . . . . . . . . . . . 36
2.4 Bibliographic Notes and Remarks . . . . . . . . . . . . . . . . . . . . . 40
2.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3 Queries and Free Functions  . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1 Issuing Queries on an Arrangement . . . . . . . . . . . . . . . . . . . . 43
3.1.1 Point-Location Queries  . . . . . . . . . . . . . . . . . . . . . . . . 43
3.1.2 Vertical Ray Shooting . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.2 Two Algorithmic Frameworks: Plane Sweep and Zone Construction . . . . . . 48
3.3 Batched Point-Location  . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.4 Free Insertion Functions  . . . . . . . . . . . . . . . . . . . . . . . . 51
3.4.1 Incremental Insertion Functions . . . . . . . . . . . . . . . . . . . . 52
3.4.2 Aggregate Insertion Functions . . . . . . . . . . . . . . . . . . . . . 55
3.5 Removing Vertices and Edges . . . . . . . . . . . . . . . . . . . . . . . 57
3.6 Vertical Decomposition  . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.6.1 Application: Decomposing an Arrangement of Line Segments  . . . . . . . 59
3.7 Bibliographic Notes and Remarks . . . . . . . . . . . . . . . . . . . . . 63
3.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4 Arrangements of Unbounded Curves  . . . . . . . . . . . . . . . . . . . . . 67
4.1 Representing Arrangements of Unbounded Curves . . . . . . . . . . . . . . 67
4.1.1 Basic Manipulation and Traversal Methods  . . . . . . . . . . . . . . . 69
4.1.2 Free Functions  . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
4.2 Point-Line Duality  . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.2.1 Application: Minimum-Area Triangle  . . . . . . . . . . . . . . . . . . 74
4.2.2 A Note on the Input Precision . . . . . . . . . . . . . . . . . . . . . 79
4.3 Bibliographic Notes and Remarks . . . . . . . . . . . . . . . . . . . . . 81
4.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
5 Arrangement-Traits Classes  . . . . . . . . . . . . . . . . . . . . . . . . 83
5.1 The Hierarchy of Traits-Class Concepts  . . . . . . . . . . . . . . . . . 83
5.1.1 The Basic Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.1.2 Supporting Intersections  . . . . . . . . . . . . . . . . . . . . . . . 85
5.1.3 Supporting Arbitrary Curves . . . . . . . . . . . . . . . . . . . . . . 87
5.1.4 The Landmark Concept  . . . . . . . . . . . . . . . . . . . . . . . . . 88
5.1.5 Supporting Unbounded Curves . . . . . . . . . . . . . . . . . . . . . . 89
5.1.6 The Traits Adaptor  . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.2 Traits Classes for Line Segments and Linear Objects . . . . . . . . . . . 91
5.2.1 The Caching Segment-Traits Class  . . . . . . . . . . . . . . . . . . . 92
5.2.2 The Non-Caching Segment-Traits Class  . . . . . . . . . . . . . . . . . 92
5.2.3 The Linear-Traits Class . . . . . . . . . . . . . . . . . . . . . . . . 94
5.3 The Polyline-Traits Class . . . . . . . . . . . . . . . . . . . . . . . . 94
5.4 Traits Classes for Algebraic Curves . . . . . . . . . . . . . . . . . . . 97
5.4.1 A Traits Class for Circular Arcs and Line Segments  . . . . . . . . . . 98
5.4.2 A Traits Class for Conic Arcs . . . . . . . . . . . . . . . . . . . .  102
5.4.3 A Traits Class for Arcs of Rational Functions . . . . . . . . . . . .  105
5.4.4 A Traits Class for Planar Bézier Curves . . . . . . . . . . . . . . .  109
5.4.5 A Traits Class for Planar Algebraic Curves of Arbitrary Degree  . . .  111
5.5 Traits-Class Decorators . . . . . . . . . . . . . . . . . . . . . . . .  117
5.6 Application: Polygon Orientation  . . . . . . . . . . . . . . . . . . .  121
5.7 Bibliographic Notes and Remarks . . . . . . . . . . . . . . . . . . . .  124
5.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  126
6 Extending the Arrangement . . . . . . . . . . . . . . . . . . . . . . . .  129
6.1 The Notification Mechanism  . . . . . . . . . . . . . . . . . . . . . .  129
6.2 Extending the Dcel  . . . . . . . . . . . . . . . . . . . . . . . . . .  132
6.2.1 Extending the Dcel Faces  . . . . . . . . . . . . . . . . . . . . . .  132
6.2.2 Extending All the Dcel Records  . . . . . . . . . . . . . . . . . . .  134
6.2.3 Input/Output for Arrangements with Auxiliary Data . . . . . . . . . .  137
6.3 Overlaying Arrangements . . . . . . . . . . . . . . . . . . . . . . . .  138
6.4 Storing the Curve History . . . . . . . . . . . . . . . . . . . . . . .  146
6.4.1 Traversing an Arrangement with History  . . . . . . . . . . . . . . .  147
6.4.2 Modifying an Arrangement with History . . . . . . . . . . . . . . . .  148
6.4.3 Input/Output for Arrangements with Curve History  . . . . . . . . . .  151
6.5 Application: Polygon Repairing and Winding Numbers  . . . . . . . . . .  152
6.6 Bibliographic Notes and Remarks . . . . . . . . . . . . . . . . . . . .  157
6.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  158
7 Adapting to Boost Graphs  . . . . . . . . . . . . . . . . . . . . . . . .  161
7.1 The Primal Arrangement Representation . . . . . . . . . . . . . . . . .  161
7.2 The Dual Arrangement Representation . . . . . . . . . . . . . . . . . .  164
7.3 Application: Largest Common Point Sets under ε-Congruence . . . . . . .  166
7.4 Bibliographic Notes and Remarks . . . . . . . . . . . . . . . . . . . .  171
7.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  172
8 Operations on (Curved) Polygons . . . . . . . . . . . . . . . . . . . . .  175
8.1 Operations on Linear Polygons . . . . . . . . . . . . . . . . . . . . .  177
8.1.1 Polygons with Holes . . . . . . . . . . . . . . . . . . . . . . . . .  178
8.1.2 Operations on Polygons with Holes . . . . . . . . . . . . . . . . . .  181
8.1.3 Point Containment and Non-Regularized Operations  . . . . . . . . . .  183
8.1.4 Connecting Holes  . . . . . . . . . . . . . . . . . . . . . . . . . .  184
8.1.5 Operations on Polygon Sets  . . . . . . . . . . . . . . . . . . . . .  184
8.1.6 A Sequence of Set Operations  . . . . . . . . . . . . . . . . . . . .  185
8.1.7 Inserting Non-Intersecting Polygons . . . . . . . . . . . . . . . . .  187
8.1.8 Performing Multiway Operations  . . . . . . . . . . . . . . . . . . .  189
8.2 Operations on Curved Polygons . . . . . . . . . . . . . . . . . . . . .  189
8.2.1 The Traits-Class Concepts . . . . . . . . . . . . . . . . . . . . . .  190
8.2.2 Operations on Polygons with Circular Arcs . . . . . . . . . . . . . .  192
8.2.3 General-Polygon Set Traits-Adaptor  . . . . . . . . . . . . . . . . .  194
8.3 Application: Multiway Operations on General Polygons  . . . . . . . . .  198
8.4 Application: Obtaining Silhouettes of Polyhedra . . . . . . . . . . . .  203
8.5 Bibliographic Notes and Remarks . . . . . . . . . . . . . . . . . . . .  205
8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  207
9 Minkowksi Sums and Offset Polygons  . . . . . . . . . . . . . . . . . . .  209
9.1 Computing the Minkowski Sum of Two Polygons . . . . . . . . . . . . . .  209
9.1.1 Computing Minkowski Sum Using Convolutions  . . . . . . . . . . . . .  211
9.1.2 Decomposition Strategies  . . . . . . . . . . . . . . . . . . . . . .  213
9.2 Offsetting a Polygon  . . . . . . . . . . . . . . . . . . . . . . . . .  214
9.2.1 Approximating the Offset with a Guaranteed Error Bound  . . . . . . .  215
9.2.2 Computing the Exact Offset  . . . . . . . . . . . . . . . . . . . . .  217
9.3 Motion-Planning Applications  . . . . . . . . . . . . . . . . . . . . .  219
9.3.1 Application: A Translating Polygonal Robot  . . . . . . . . . . . . .  220
9.3.2 Application: Coordinating Two Disc Robots . . . . . . . . . . . . . .  227
9.4 Bibliographic Notes and Remarks . . . . . . . . . . . . . . . . . . . .  237
9.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  239
10 Envelopes  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  241
10.1 Envelopes of Curves in the Plane . . . . . . . . . . . . . . . . . . .  241
10.1.1 Representing the Envelope  . . . . . . . . . . . . . . . . . . . . .  241
10.1.2 Constructing the Envelope Diagram  . . . . . . . . . . . . . . . . .  242
10.1.3 The Envelope-Software Components . . . . . . . . . . . . . . . . . .  243
10.1.4 Using the Traits Classes . . . . . . . . . . . . . . . . . . . . . .  244
10.2 Application: Nearest Jeep over Time  . . . . . . . . . . . . . . . . .  248
10.3 Envelopes of Surfaces in 3-Space . . . . . . . . . . . . . . . . . . .  250
10.3.1 The Envelope-Traits Concept  . . . . . . . . . . . . . . . . . . . .  252
10.3.2 Using the Envelope-Traits Classes  . . . . . . . . . . . . . . . . .  254
10.4 Application: Locating the Farthest Point . . . . . . . . . . . . . . .  257
10.5 Bibliographic Notes and Remarks  . . . . . . . . . . . . . . . . . . .  259
10.6 Exercises  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  260
11 Prospects  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  263
11.1 Arrangements on Curved Surfaces  . . . . . . . . . . . . . . . . . . .  263
11.2 Higher-Dimensional Arrangements  . . . . . . . . . . . . . . . . . . .  265
11.3 Fixed-Precision Geometric Computing  . . . . . . . . . . . . . . . . .  267
11.4 More Applications  . . . . . . . . . . . . . . . . . . . . . . . . . .  268
11.5 Exercises  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  269
Bibliography  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  271
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  285