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 <b>...</b>