CGAL

Computational Geometry Algorithms Library

The goal of the CGAL Open Source Project is to provide easy access to efficient and reliable geometric algorithms in the form of a C++ library. CGAL is used in various areas needing geometric computation, such as: computer graphics, scientific visualization, computer aided design and modeling, geographic information systems, molecular biology, medical imaging, robotics and motion planning, mesh generation, numerical methods.

The Computational Geometry Algorithms Library offers data structures and algorithms like triangulations (2D constrained triangulations and Delaunay triangulations in 2D and 3D), Voronoi diagrams (for 2D and 3D points, 2D additively weighted Voronoi diagrams, and segment Voronoi diagrams), Boolean operations on polygons and polyhedra, arrangements of curves and their applications (2D and 3D envelopes, Minkowski sums), mesh generation (2D Delaunay mesh generation and 3D surface mesh generation, skin surfaces), geometry processing (surface mesh simplification, subdivision and parameterization, as well as estimation of local differential properties, and approximation of ridges and umbilics), alpha shapes, convex hull algorithms (in 2D, 3D and dD), operations on polygons (straight skeleton and offset polygon), search structures (kd trees for nearest neighbor search, and range and segment trees), interpolation (natural neighbor interpolation and placement of streamlines), shape analysis, fitting, and distances (smallest enclosing sphere of points or spheres, smallest enclosing ellipsoid of points, principal component analysis), and kinetic data structures.

All these data structures and algorithms operate on geometric objects like points and segments, and perform geometric tests on them. These objects and predicates are regrouped in CGAL Kernels.

Finally, the Support Library offers geometric object generators and spatial sorting functions, as well as a matrix search framework and a solver for linear and quadratic programs. It further offers interfaces to third party software such as the GUI libraries Qt, Geomview, and the Boost Graph Library.

CGAL is distributed under a dual-license scheme. CGAL can be used together with Open Source software free of charge. Using CGAL in other contexts can be done by obtaining a commercial license from GeometryFactory

License: special.

Tags: geometry, computational geometry, library.

Interface: library.

Source language: C++.

Supported language: C++.

Staff

Developers: Fernando Cacciola, Frédéric Cazals, Raphaëlle Chaine, Pavel Emeliyanenko, Marc Glisse, Luc Habert, Peter Hachenberger, Thomas Herrmann, Samuel Hornus, Michael Kerber, Nico Kruithof, Sebastian Limbach, Sébastien Loriot, Pedro Machado Manhães de Castro, Andreas Meyer, Thanh-Trung Nguyen, Luis Peñaranda, Joachim Reichel, Laurent Rineau, Daniel Russel, Laurent Saboret, Ophir Setter, George Tzoumas.

Sponsors: ETH Zürich, FORTH IACM, Freie Universität Berlin, GeometryFactory, INRIA, Max-Planck-Institut für Informatik, National and Kapodistrian University of Athens, Stanford University, Tel-Aviv University, The University of Groningen, Universiteit Utrecht.

Links

Homepage: http://www.cgal.org/.

Documentation: http://www.cgal.org/FAQ.html, http://www.cgal.org/Manual/.

Mailing lists

Support: http://www.cgal.org/mailing_list.html.