CGAL: The Open Source Computational Geometry Algorithms Library

Google Tech Talks March, 3 2008 ABSTRACT Introduction Project mission statement, history, internal organization, partners, CGAL in numbers. What's in CGAL A survey on available data structures and algorithms, as well as examples how and by whom they are used. Topics include Triangulations, Voronoi diagrams, Boolean operations on polygons and polyhedra, arrangements of curves and their applications, Mesh generation, Geometry processing, Alpha shapes, Convex hull algorithms, Operations on polygons, Search structures, Interpolation, Shape analysis, fitting, and distances, Kinetic data structures... Generic Programming Paradigm CGAL data structures are C++ template classes and functions, usually taking several template parameters (with default values for ease of use). This gives developers an incredible flexibility to adapt the data structures to their needs, which is important internally for code reuse, and important for end users, as they typically integrate CGAL in already existing applications. Parts of CGAL are also interfaced with languages and software like Python, Java, Scilab, Qt and the Ipe drawing editor. Exact Geometric Computing Paradigm We present how to make geometric algorithms correct, robust, and nevertheless fast, by combining floating point arithmetic with exact arithmetic, and clever filtering mechanisms to switch between these two modes. These mechanisms can be used for geometric predicates, as well as for geometric constructions, which instead of a discrete return value generate new geometric entities. Conclusion and Outlook A wrapup, and a sneak preview on algorithms that might make it into future releases of CGAL. Speaker: Andreas Fabri, PhD, GeometryFactory As member of the initial development team of the CGAL project, Andreas is one of the architects of the CGAL software. For several years he chaired the CGAL Editorial Board. In 2003, Andreas founded the GeometryFactory as spin-off of the CGAL project, offering licenses, service and support to commercial users. Andreas received his PhD in 1994 from the Ecole des Mines de Paris, while working on geometric algorithms for parallel machines at INRIA. Speaker: Sylvain Pion, PhD, INRIA Sophia-Antipolis Sylvain got involved in the CGAL project during his PhD, which he received in 1999 at INRIA. He worked then on providing generic solutions to numerical robustness issues arising in geometric algorithms. Later on he worked on the efficiency of some fundamental geometric algorithms such as 3D Delaunay triangulations. He is now also involved in C++ standardization, and is working on parallel geometric algorithms. He is employed as researcher at INRIA, and is the current chair of the CGAL Editorial Board.