From: http://www.cgal.org/

 

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... More on the projects using CGAL web page.

The Computational Geometry Algorithms Library (CGAL), offers data structures and algorithms like triangulations (2D constrained triangulations and Delaunay triangulations in 2D and 3D, periodic triangulations in 3D), Voronoi diagrams (for 2D and 3D points, 2D additively weighted Voronoi diagrams, and segment Voronoi diagrams), polygons (Boolean operations, offsets, straight skeleton), polyhedra (Boolean operations), arrangements of curves and their applications (2D and 3D envelopes, Minkowski sums), mesh generation (2D Delaunay mesh generation and 3D surface and volume 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), 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.

License

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. For more details see the License page.

News

June 17-20, 2012
Follow CGAL during the CG Week in Chapel Hill, NC, USA. Two minisymposia: CGAL, an Open Gate to Computational Geometry and Publicly Available Geometric/Topological Software
March 16, 2012
The CGAL Project is a mentoring organization for the Google Summer of Code 2012. Have a look at our Project Ideas page.
March 12, 2012
CGAL-4.0 is released. Note that this is the first release of CGAL that is published under GPLv3+ license. Check the changes for details, the manual, and download!
February 13, 2012
A book entitled "CGAL Arrangements and Their Applications" has been published by Springer; see the publisher and the authors websites of the book.
January 16, 2012
The CGAL-bindings repository is now open to the public. This project provides an interface to some CGAL algorithms in other languages than C++ (Java, Python, ...) using the SWIG technology.
November 9, 2011
Jane Tournois, Pierre Alliez, Laurent Rineau, and Mariette Yvinec received the Meshing Maestro Award at the 20. International Meshing Roundtable for their poster Meshing with CGAL.
September 28, 2011
CGAL-3.9 is released. Check the changes, the manual, and download!
August 8-11, 2011
Visit the CGAL Project on Booth No. 170 at the exhibition of Siggraph 2011, Vancouver, 8-11 August 2011. (Add to Google Calendar)
April 19, 2011
CGAL-3.8 is released. Check the changes, the manual, and download!
April 1, 2011
On the new homepage the CGAL Project agressively uses Web 3.14 technology.
Older news and announcements

用户登录