2D Maps in CGAL and Applications
CGAL
General
 The goal: make the large body of geometric algorithms developed in the field of computational geometry available for industrial applications.
 Reliable.
 Flexible.
 Efficient.
 Easy to use.
 Developed in C++ and follows the Generic Programming paradigm.
 Developed by a consortium consisting of a few institutions in Europe and Israel.
 Active institutions: (i) (ii) (iii) (iv) (v)
History
 Development started at 1995.
 First release appeared in June 1997.
 Work continued after the end of European support in 1999.
 Editorial Board created in 2001.
 Geometry Factory founded in January 2003.
 An INRIA startup.
 Sells commercial licenses, support, geometry ized development.
 Version 3.5.1 released in December 2009.
 Version 3.6 Beta release February 2010.
Numbers
900,000  lines of C++ code 
10,000  downloads per year not including Linux distributions 
3,500  pages manual 
3,000  subscribers to cgalannounce list 
1,000  subscribers to cgaldiscuss list 
120  packages 
60  commercial users 
25  active developers 
7  Google’s page rank for www.cgal.org 
6  months release cycle 
2  licenses: Open Source and commercial 
Customers
Reliability
 Addresses robustness problems
 Explicit degeneracy handling.
 Exact Geometric Computation.
Flexibility
 Open library
 Modular structure. Separation between to geometry and topology.
 Adaptable to user code.
 Extensible, e.g., data structures can be extended.
Ease of Use
 Didactic and exhaustive Manuals
 Follows standard concepts (e.g., C++ and STL)
 Smooth learningcurve
Efficiency
 Follows the genericprogramming paradigm.
 Polymorphism is resolved at compile time
 Has no runtime overhead cost.
 Large code footprint and long compilation processes.
Architecture
 Geometric Kernel
 Constantsize geometric objects (e.g., points, lines, and planes).
 Predicates and constructors of objects of these types.
 Basic Library
 Data structure and algorithms (e.g., Triangulations, Polyhedrons, and Arrangements).
 Support Library
 Number types.
 Geometricobject generators.
 Input/Output.
 Visualization.
 More none geometric types (e.g., Circulators).
Geometric Kernel Classification
 Dimension  2, 3, arbitrary
 Number types:
 Ring: +,,*
 Euclidean ring (adds integer division and gcd) (e.g., CGAL::Gmpz).
 Field:  +,,*,\ (e.g., CGAL::Quotient(CGAL::Gmpz)).
 Exact sign evaluation for expressions with roots (Field_with_sqr).
 Coordinate representation
 Cartesian  requires a field number type or Euclidean ring if no constructions are performed.
 Homogeneous  requires Euclidean ring.
 Reference Counting.
The Trouble with Double
[KMSY04]
p = (0.5 + x.u, 0.5 + y.u), 0 ≤ x, y < 256, u = 2^{−53}, q = (12, 12) r = (24, 24) orientation(p, q, r) evaluated with double 256 x 256 pixel image

→ Inconsistencies in predicate evaluations.
Orientation in Theory
orientation(p, q, r)  =  sign(det[ 

])  
=  sign((qx − px )(ry − py ) − (qy − py )(rx − px)) 
ccw(s, q, r) ∩ ccw(s, r , p) ∩ ccw(s, p, q) ⇒ ccw(p, q, r)
Exact Geometric Computation
Ensure that the control flow in the implementation corresponds to the control flow with exact arithmetic. [Yap]
 Evaluate predicate instantiated with limited precision.
 If uncertain ⇒ evaluate predicate instantiated multiple precision.
Geometric Kernel (easy) Choices
CGAL::Exact_predicates_inexact_constructions_kernel CGAL::Exact_predicates_exact_constructions_kernel CGAL::Exact_predicates_exact_constructions_kernel_with_sqrt
Orientation of a triple: Version 1
 Computing the orientation of 3 points in the plane.
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel typedef Kernel::Point_2 Point_2 int main() { Point_2 p(0,0), q(10,3), r(12,19); return (CGAL::orientation(q,p,r) == CGAL::LEFT_TURN) ? 0 : 1; }
Orientation of a triple: Version 2
 Increasing flexibility.
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> typedef CGAL::Exact_predicates_inexact_constructions_kernel Kernel typedef Kernel::Point_2 Point_2 typedef Kernel::Orientation_2 Orientation_2; int main() { Kernel kernel; Orientation_2 orientation = Kernel.orientation_2_object(); Point_2 p(0,0), q(10,3), r(12,19); return (orientation(q,p,r) == CGAL::LEFT_TURN) ? 0 : 1; }
Basic Library
 Generic data structures are parameterized with Traits
 Separates algorithms and data structures from the geometric kernel.
 Generic algorithms are parameterized with iterator ranges
 Decouples the algorithm from the data structure.
Convex Hull
 A subset S ⊆^{d} is convex if for any two points p and q in the set the line segment with endpoints p and q is contained in S.
 The convex hull of a set S is the smallest convex set containing S.
 The convex hull of a set of points P is a convex polygon with vertices in P.
Demonstration of Upper Convex Hull
 Using Random Access Iterator. [C++]
 Provides both increment and decrement.
 Constanttime methods for moving forward and backward in arbitrarysized steps ('[]' operator).
 Maintaining the current point separately. [C++]
 Maintaining an iterator that points to the current point separately. [C++]
 More generic  can be used for computing the lower hull. [C++]
Miscellaneous
 CGAL Version
 Latest public version 3.6.
 Latest internal version is 3.7I8.
 Latest public version 3.6.
 CGAL is built with cmake.
 Dependencies
 Linux  there are Debian and Fedora packages.
CGAL Arrangements on Surfaces
Two Dimensional Arrangements
Definition: Given a collection C of curves on a surface, the arrangement A(C) is the partition of the surface into vertices, edges, and faces induced by the curves of C.
An arrangement of circles in the plane. 
An arrangement of lines in the plane. 
An arrangement of greatcircle arcs on a sphere. 
The CGAL Arrangement Package
 Constructs, maintains, modifies, traverses, queries, and presents arrangements on twodimensional parametric surfaces.
 Robust and exact.
 All inputs are handled correctly (including degenerate input).
 Exact number types are used to achieve exact results.
 Generic – easy to interface, extend, and adapt
 Modular – geometric and topological aspects are separated
 Supports among the others:
 various point location strategies
 zoneconstruction paradigm
 sweepline paradigm
 overlay computation
 Part of the CGAL basic library
CGAL Arrangements in Numbers
137,080  lines of C++ code (headers) 
527  pages of manual 
265  files of C++ code (headers) 
9  commercial users 
7  packages (AOS/SL, BSO, MS, 2D & 3D Env., SR, LER) 
AOS   2D Arrangements on Surfaces 
SL   2D Intersection of Curves (Sweep Line) 
BSO   2D Regularized Boolean Set Operations 
MS   2D Minkowski Sums 
SR   SR 2D Snap Rounding 
LER   LER 2D Largest Empty Iso Rectangle 
Arrangement Data Structure
template <typename GeomTraits, typename TopTraits> Arrangement_on_surface { ... }
Geometry Traits
 Is a parameter of the data structures and algorithms.
 Defines the family of curves that induce the arrangement.
 Aggregates
 Geometric types (point, curve).
 Operations over types (accessors, predicates, constructors).
 Subdivides input curves into umonotone subcurves.
 Most operations involve points and umonotone curves.
Curve Family  Degree  Surface  Boundness  Arithmetic  Author 

linear segment  1  plane  bounded  rational  
linear segments, rays, lines  1  plane  unbounded  rational  
piecewise linear curves  ∞  plane  bounded  rational  
circular arcs, linear segments  ≤2  plane  bounded  rational  
algebraic curves  ≤2 ≤n 
plane  bounded unbounded 
algebraic  
quadric projections  ≤2  plane  unbounded  algebraic  
planar Bézier curves  ≤n  plane  unbounded  algebraic  
univariate polynomials  ≤n  plane  unbounded  algebraic  
rational function arcs  ≤n  plane  unbounded  algebraic  
geodesics in sphere 
≤2  sphere  bounded  rational  
quadric intersection arcs 
≤2  quadric  unbounded  algebraic  
Dupin cyclide intersection arcs 
≤2  Dupin cyclide 
bounded  algebraic 
Point Location
Given a subdivision A of the space into cells and a query point q, find the cell of A containing q

Naive  Walk  RIC  Landmarks  

Preprocessing time  none  none  O(n log n) 
O(k log k) 
Memory space  none  none  O(n)  O(k) 
Query time  bad  reasonable  good  good 
Applicability  all  limited  limited  limited 
Walk — Walk along a line
RIC — Random Incremental Construction based on trapezoidal decomposition
k — number of landmarks
Map Overlay
Definition: The overlay of two planar subdivisions S_{1} and S_{2} is a planar subdivision S such that there is a face f in S if and only if there are faces f_{1} and f_{2} in S_{1} and S_{2} respectively such that f is a maximal connected subset of f_{1} ∩ f_{2}.
The overlay of two subdivisions embedded on a surface in ^{3} is defined similarly.
Map Overlay Implementation
template <typename GeomTraitsA, typename GeomTraitsB, typename GeomTraitsRes, typename TopTraitsA, typename TopTraitsB, typename TopTraitsRes, typename OverlayTraits> void overlay(Arrangement_2<GeomTraitsA, TopTraitsA> arr1, Arrangement_2<GeomTraitsB, TopTraitsB> arr2, Arrangement_2<GeomTraitsRes, TopTraitsRes>& arr_res, OverlayTraits& ovl_tr)
The overlay traits handles the following possible 10 cases:
 A new vertex v is induced by coinciding vertices v_{r} and v_{b}.
 A new vertex v is induced by a vertex v_{r} that lies on an edge e_{b}.
 An analogous case of a vertex _{b} that lies on an edge e_{r}.
 A new vertex v is induced by a vertex v_{r} that is contained in a face f_{b}.
 An analogous case of a vertex v_{b} contained in a face f_{r}.
 A new vertex v is induced by the intersection of two edges e_{r} and e_{b}.
 A new edge e is induced by the overlap of two edges e_{r} and e_{b}.
 A new edge e is induced by the an edge e_{r} that is contained in a face f_{b}.
 An analogous case of an edge e_{b} contained in a face f_{r}.
 A new face f is induced by the overlap of two faces f_{r} and f_{b}.
Parametric Surfaces
Definition: A parametric surface S of two parameters is a surface defined by parametric equations involving two parameters u and v:
f_{S}(u, v) = (x(u, v), y(u, v), z(u, v))
Thus, f_{S} : → ^{3} and S = f_{S}(), where is a continuous and simply connected twodimensional parameter space.We deal with orientable parametric surfaces.
2D Arrangement on Surfaces in 3D
Cylinder 
Sphere

S(u, v) = (r cos u, r sin u, v) u ∈ [−π,π), v ∈ 
S(u, v) = (r cos u cos v, r sin u cos v, r sin v) u ∈ [−π, π), v ∈ [−π/2, π/2] 
3D Collision Detection
Minkowski Sums
P and Q are two polyhedra in ^{d}.
M = P ⊕ Q = {p + q  p ∈ P, q ∈ Q}.
Collision Detection using Minkowski Sums
P and Q are two polyhedra in ^{d}.
P ∩ Q ≠ ∅ ⇔ Origin ∈ M = P ⊕ (−Q).
Polytope
Definition: A polytope is a bounded convex polyhedron P ⊆^{d}.
Gaussian Maps
Definition: The Gaussian map G(P) of a polytope P ⊆^{3 }is the decomposition of ^{2} into maximal connected regions so that the extremal point is the same for all directions within one region.
G is a setvalued function from ∂P to ^{2}.
G(p ∈ ∂P) = the set of outward unit normals to support planes to P at p.
v, e, f — a vertex, an edge, a facet of P.
 G(f) = outward unit normal to f.
 G(e) = geodesic segment.
 G(v) = spherical polygon.
Extended Gaussian Maps
 G(P) is an arrangement embedded on ^{2}, where each face G(v) of the arrangement is extended with v.
 G(P) is unique ⇒ G^{−1}(G(P)) = P.
Gaussian Maps of Minkowski Sums
The overlay of the Gaussian maps of two polytopes P and Q is the Gaussian map of the Minkowski sum of P and Q.
 It identifies all the pairs of features of P and Q, respectively, that have common supporting planes.
 These common features occupy the same space on ^{2}.
 They identify the pairwise features that contribute to ∂(P ⊕ Q).
Cube  Tetrahedron  Minkowski Sum 
2D Motion Planing
Summary
 Arrangements are versatile.
 Arrangements are used as foundation for higher level geometric data structures.
 Arrangements are not bound to the plane.
Literature
Books and Book Chapters
[FWH10]  Efi Fogel, Dan Helperin, and Ron Wein.
CGAL Arrangements and Their Applications, A StepbyStep Guide, to be published. 

[FHKTWW07]  Efi Fogel, Dan Halperin, Lutz Kettner, Monique Teillaud, Ron Wein, and Nicola Wolpert.
Arrangements. In J.D. Boissonnat and M. Teillaud, editors, Effective Computational Geometry for Curves and Surfaces, chapter 1, pages 1–66. 2007. 

[FT07]  Efi Fogel and Monique Teillaud. Generic programming and the CGAL library. In J.D. Boissonnat and M. Teillaud, editors, Effective Computational Geometry for Curves and Surfaces, chapter 8, pages 313–320. 2007. 
Journal Articles
[FH07]  Efi Fogel and Dan Halperin.
Exact and efficient construction of Minkowski sums of convex polyhedra with applications. ComputerAided Design, 39(11):929–940, 2007. 

[WFZH07] 
Ron Wein, Efi Fogel, Baruch Zukerman, and Dan Halperin.
Advanced programming techniques applied to CGAL’s arrangement package. Computational Geometry: Theory and Applications, 38(1–2):37–63, 2007. Special issue on CGAL. 

[BFHMW10] 
Eric Berberich, Efi Fogel, Dan Halperin, Kurt Melhorn, and Ron Wein.
Arrangements on Parametric Surfaces I: General Framework and Infrastructure. Accepted for publication in Mathematics in Computer Science, 2010. 

[BFHKS10] 
Eric Berberich, Efi Fogel, Dan Halperin, Michael Kerber, and Ophir Setter,
Arrangements on Parametric Surfaces II: Concretizations and Applications. Accepted for publication in Mathematics in Computer Science, 2010. 

[KMSY04]  Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and Chee Yap.
Classroom Examples of Robustness Problems in Geometric Computations. Computational Geometry: Theory and Applications, 40(1):6178, 2007. 
Symposium, Workshop Papers, and Manuscripts
[MFH10]  Naama Mayer, Efi Fogel, and Dan Halperin.
Dynamically Maintaining the Exact Minkowski Sums of Rotating Polytopes. Submitted to Solid and Physical Modeling, 2010. 