WIXLIB

Generic programming([E. Fogel, TAU, IL, 2012])ConceptA concept is a set of requirements divided into four categories:Associated Types — auxiliary types, for exampleP o i n t 2 — a type that represents a two-dimensional point.Valid Expressions — C expressions that must compile successfully, forexamplep q, where p and q are objects of type P o i n t 2 .ComputationalGeometryAlgorithmLibraryFUBerlin, GeometricComputing:Introductionto CGAL, WS 2012/1327,13

Generic programming([E. Fogel, TAU, IL, 2012])ConceptA concept is a set of requirements divided into four categories:Associated Types — auxiliary types, for exampleP o i n t 2 — a type that represents a two-dimensional point.Valid Expressions — C expressions that must compile successfully, forexamplep q, where p and q are objects of type P o i n t 2 .Runtime Characteristics — characteristics of the variables involved inthe valid expressions that apply during the variables’ yAlgorithmLibraryFUBerlin, GeometricComputing:Introductionto CGAL, WS 2012/1328,13

Generic programming([E. Fogel, TAU, IL, 2012])ConceptA concept is a set of requirements divided into four categories:Associated Types — auxiliary types, for exampleP o i n t 2 — a type that represents a two-dimensional point.Valid Expressions — C expressions that must compile successfully, forexamplep q, where p and q are objects of type P o i n t 2 .Runtime Characteristics — characteristics of the variables involved inthe valid expressions that apply during the variables’ lifespans,pre/post-conditions.Complexity Guarantees — maximum limits on the computing resourcesconsumed by the valid UBerlin, GeometricComputing:Introductionto CGAL, WS 2012/1329,13

Generic programming([E. Fogel, TAU, IL, 2012])Generic Programming & the Stl BibliographyAndrei Alexandrescu.Modern C Design: Generic Programming And Design Patterns Applied.Addison-Wesley, Boston, MA, USA, 2001.Matthew H. Austern.Generic Programming and the Stl.Addison-Wesley, Boston, MA, USA, 1999.Erich Gamma, Richard Helm, Ralph Johnson, and John M. Vlissides.Design Patterns — Elements of Reusable Object-Oriented Software.Addison-Wesley, Boston, MA, USA, 1995.David R. Musser, Gillmer J. Derge, and Atul Saini.Stl tutorial and reference guide: C programming with the standard template library.Addison-Wesley, Boston, MA, USA, 2nd edition, Professional Computing Series, 2001.David Vandevoorde and Nicolai M. Josuttis.C Templates: The Complete Guide,Addison-Wesley, Boston, MA, USA, 2002.Jeremy G. Siek, Lie-Quan Lee, and Andrew Lumsdaine.The Boost Graph Library,Addison-Wesley, Boston, MA, USA, 2002.David A. Musser and Alexander A. Stepanov.Generic programming.In Proceedings of International Conference on Symbolic and Algebraic Computation, volume 358 of LNCS, pages 13–25.Springer, 1988.The planned new standard for the C programming language.http://en.wikipedia.org/wiki/C 0x#References .The Sgi STL.http://www.sgi.com/tech/stl/ .,ComputationalGeometryAlgorithmLibraryFUBerlin, GeometricComputing:Introductionto CGAL, WS 2012/133013

CGAL([E. Fogel, TAU, IL, 2012])Cgal: Mission“Make the large body of geometric algorithms developed in the field ofcomputational geometry available for industrial applications”Cgal Project Proposal, 1996Computational Geometry Algorithm LibraryFU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/133114,

CGAL([E. Fogel, TAU, IL, 2012])Some of Cgal ContentBounding VolumesPolyhedral cationArrangementsBoolean OperationsVoronoi DiagramsParametrisationStreamlinesMesh GenerationRidge Detection Neighbor SearchIntersection Detection Minkowski SumsComputational Geometry Algorithm LibraryFU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/13PCAKinetic Data StructuresPolytope DistanceQP Solver3214,

CGAL([E. Fogel, TAU, IL, 2012])Cgal FactsWritten in C Follows the generic programming paradigmDevelopment started in 1995Active European sites:1INRIA Sophia Antipolis2MPII Saarbrücken3Tel Aviv University4ETH Zürich (Plageo)5University of Crete and FO.R.T.H.6INRIA Nancy7Université Claude Bernard de Lyon8ENS Paris9University of Eindhoven10University of California, San Francisco11University of AthensComputational Geometry Algorithm LibraryFU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/133414,

CGAL([E. Fogel, TAU, IL, 2012])Cgal in Numbers900,00010,0003,5003,0001,0001206025672lines of C codedownloads per year not including Linux distributionsmanual pagessubscribers to cgal-announce listsubscribers to cgal-discuss listpackagescommercial usersactive developersmonths release cycleGoogle’s page rank for cgal.org.comlicenses: Open Source and commercialComputational Geometry Algorithm LibraryFU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/133614,

CGAL([E. Fogel, TAU, IL, 2012])Cgal PropertiesReliabilityExplicitly handles degeneraciesFollows the Exact Geometric Computation (EGC) paradigmFlexibilityIs an open libraryDepends on other libraries (e.g., Boost, Gmp, Mpfr, Qt, & Core)Has a modular structure, e.g., geometry and topology are separatedIs adaptable to user codeIs extensible, e.g., data structures can be extendedEase of UseHas didactic and exhaustive ManualsFollows standard concepts (e.g., C and Stl)Characterizes with a smooth learning-curveEfficiencyAdheres to the generic-programming paradigm Polymorphism is resolved at compile timeComputational Geometry Algorithm Library38,FU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/1314

CGAL([E. Fogel, TAU, IL, 2012])Cgal StructureBasic LibraryAlgorithms and Data Structurese.g., Triangulations, Surfaces, and ArrangementsVisualizationFilesI/OKernelElementary geometric objectsElementary geometric computations on themNumber TypesGenerators.Support LibraryConfigurations, Assertions,.,FU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/13Computational Geometry Algorithm Library1439

CGAL([E. Fogel, TAU, IL, 2012])Cgal Kernel ConceptGeometric objects of constant size.Geometric operations on object of constant size.Primitives 2D, 3D, dDpointvectortriangleiso omparisonintersectionorientationsquared distancecontainment . . .,FU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/13Computational Geometry Algorithm Library1540

CGAL([E. Fogel, TAU, IL, 2012])Cgal Kernel Affine Geometrypoint - originpoint - pointpoint vector vector vector pointpoint point Illegalmidpoint(a, b) a 1/2 (b a),FU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/13Computational Geometry Algorithm Library1641

CGAL([E. Fogel, TAU, IL, 2012])Cgal Kernel ClassificationDimension: 2, 3, arbitraryNumber types:Ring: , , Euclidean ring (adds integer division and gcd) (e.g., CGAL : : Gmpz).Field: , , ,/ (e.g., CGAL : : Q u o t i e n t (CGAL : : Gmpz ) ).Exact sign evaluation for expressions with roots ( F i e l d w i t h s q r ).Coordinate representationCartesian — requires a field number type or Euclidean ring if noconstructions are performed.Homegeneous — requires Euclidean ring.Reference countingExact, Filtered,FU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/13Computational Geometry Algorithm Library1642

CGAL([E. Fogel, TAU, IL, 2012])Cgal Kernels and Number TypesCartesian representationHomogeneous representationhxhxx hwhypointpointhyy hwhwIntersectionoftwolines a1 x b 1 y c 1 0a1 hx b1 hy c1 hw 0a2 x b 2 y c 2 0a2 hx b2 hy c2 hw 0(x, y ) b1 b2 a1a2c1c2b1b2a1a2, a1a2c1c2b1b2Field operations (hx, hy , hw ) b1b2c1c2, a1a2c1c2,a1a2b1b2 Ring operations,FU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/13Computational Geometry Algorithm Library1643

CGAL([E. Fogel, TAU, IL, 2012])Example: K e r n e l s NumberType C a r t e s i a n FieldNumberType t y p e d e f CGAL : : C a r t e s i a n Gmpq K e r n e l ;t y p e d e f CGAL : : S i m p l e c a r t e s i a n d o u b l e K e r n e l ; No reference-counting, inexact instantiationHomogeneous RingNumberType t y p d e f CGAL : : Homogeneous Core : : B i g I n t K e r n e l ;d-dimensional C a r t e s i a n d and Homogeneous dTypes OperationsK e r n e l : : P o i n t 2 , K e r n e l : : Segment 3Kernel : : Less xy 2, Kernel : : Construct bisector 3,FU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/13Computational Geometry Algorithm Library1644

CGAL([E. Fogel, TAU, IL, 2012])Cgal Numerical Issues t y p e d e f CGAL : : C a r t e s i a n NT K e r n e l ;NT s q r t 2 s q r t (NT ( 2 ) ) ;Kernel : : Point 2 p (0 ,0) , q( sqrt2 , sqrt2 ) ;K e r n e l : : C i r c l e 2 C( p , 4 ) ; a s s e r t (C . h a s o n b o u n d a r y ( q ) ) ;OK if NT supports exact sqrt.Assertion violation otherwise.,FU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/13Computational Geometry Algorithm Library1645

CGAL([E. Fogel, TAU, IL, 2012])Computing the Intersection typedef Kernel : : Line 2 Line 2 ;i n t main ( ) {Kernel kernel ;P o i n t 2 p ( 1 , 1 ) , q ( 2 , 3 ) , r ( 12 ,19);Line 2 l1 (p , q ) , l2 ( r , p ) ;i f ( d o i n t e r s e c t ( l1 , l 2 )) {CGAL : : O b j e c t o b j CGAL : : i n t e r s e c t i o n ( l 1 , l 2 ) ;i f ( c o n s t P o i n t 2 p o i n t o b j e c t c a s t P o i n t 2 (&o b j ) ) {/ do s o m e t h i n g w i t h p o i n t /} e l s e i f ( c o n s t Segment 2 s e g m e n t o b j e c t c a s t Segment 2 (&o b j ) ) {/ do s o m e t h i n g w i t h s e g m e n t /}}return 0;},FU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/13Computational Geometry Algorithm Library1649

CGAL([E. Fogel, TAU, IL, 2012])Cgal Basic LibraryGeneric data structures are parameterized with TraitsSeparates algorithms and data structures from the geometric kernel.Generic algorithms are parameterized with iterator rangesDecouples the algorithm from the data structure.,FU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/13Computational Geometry Algorithm Library1650

CGAL([E. Fogel, TAU, IL, 2012])Cgal BibliographyA. Fabri, G.-J. Giezeman, L. Kettner, S. Schirra, and S. Schönherr.On the design of Cgal a computational geometry algorithms library.Software — Practice and Experience, 30(11):1167–1202, 2000. Special Issue on Discrete Algorithm Engineering.A. Fabri and S. Pion.A generic lazy evaluation scheme for exact geometric computations.In 2nd Library-Centric Software Design Workshop, 2006.M. H. Overmars.Designing the computational geometry algorithms library Cgal.In Proceedings of ACM Workshop on Applied Computational Geometry, Towards Geometric Engineering, volume 1148,pages 53–58, London, UK, 1996. Springer.The Cgal Project.Cgal User and Reference Manual.Cgal Editorial Board, 3.9 edition, 2010. http://www.cgal.org/Manual/3.9/doc html/cgal manual/contents.html .Efi Fogel, Ron Wein, and Dan Halperin.Cgal Arrangements and Their Applications, A Step-by-Step Guide.Springer, 2012.,FU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/13Computational Geometry Algorithm Library1651

Exercise 11. Install CGAL: www.cgal.org(Installation tips also on the course’s website)2. Read CGAL’s manual: Chapters 1 (Introduction), 2 (Preliminaries),3 (Installation), 5 (Number Types), 11 (2D and 3D Geometry Kernel)3. For the following use the Cartesian kernel with number type double.Use only geometric primitives from the kernel. Do not use any kerneloperation (predicate or construction).ÉÉÉÉWrite a function that takes two segments in the plane asarguments and returns: 1 if the segments intersect, 0 if theydon’t.Write a function that takes two segments in the plane asarguments and computes their intersection (if it exists).Write a function that takes a point and a segment in the plane asarguments and returns 1 if the point lies on the segment and 0otherwise.Test your functions.4. Suggested reading: Computational Geometry in C (Second Edition), J.O’Rourke. Cambridge University Press, 1998.,FU Berlin, Geometric Computing: Introduction to CGAL, WS 2012/1317

This course is about É Computing with geometric objects (points, lines, segments, curves, planes, etc.) É Implementing and using geometric algorithms and data structures (efficiently and correctly) É Using the Computational Geometry Algorithms Library (CGAL) (together with STL, Boost, Qt, etc.) É Basic packages: Convex Hull, Arrangements, Triangulations, Voronoi Diagrams, etc.