CGAL is a software project that provides 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 geographic information systems, computer aided design, molecular biology, medical imaging, computer graphics, and robotics.
The library offers data structures and algorithms like triangulations, Voronoi diagrams, Boolean operations on polygons and polyhedra, point set processing, arrangements of curves, surface and volume mesh generation, geometry processing, alpha shapes, convex hull algorithms, shape reconstruction, AABB and KD trees...

Homepage
Download

#### Recent Releases

5.513 Jan 2022 03:16
**minor feature:**
Release date: January 2022
### dD Spatial Searching.
Added the member function `write_graphviz()` to the class The Kd_tree` that writes the tree in a stream in the Graphviz format.
### 3D Convex Hulls.
Added an overload of the function `CGAL::convex_hull_3()`, which writes the result in an indexed triangle set.

5.420 Jul 2021 06:05
**minor feature:**
Release date: December 2021
### Polygon Mesh Processing.
Added the function `CGAL::Polygon_mesh_processing::match_faces()`, which, given two polygon meshes, identifies their common faces as well as as faces present in only either of them.

5.212 Sep 2020 03:16
**minor feature:**
Release date: December 2020
### CGAL and the Boost Graph Library (BGL).
Added the convenience header `CGAL/boost/graph/graph_traits_inheritance_macros.h` that allows to easily
make any class inheriting from a model of a face graph concept, a model of the same concept.
### 3D Convex Hulls.
Added the function `CGAL::halfspace_intersection_interior_point_3()` that can be used to retrieve
the point that is the most interior a convex volume defined by the intersection of a set of halfspaces.

5.116 Jan 2020 06:25
**minor feature:**
Release date: June 2020
### Surface Mesh Topology (new package).
- This package allows to compute some topological invariants of.
Surfaces. For now, it is possible to test if two () curves
on a combinatorial surface are homotopic. The user can choose.
Between free homotopy and homotopy with endpoints.
A contractibility test is also provided.
3D Fast Intersection and Distance Computation:
Breaking change: the internal search tree is now lazily constructed. To disable it, one must call.
The new function `do_not_accelerate_distance_queries()` before the first distance query.
Polygon Mesh Processing:
Introduced a new function, `CGAL::Polygon_mesh_processing::remove_connected_components_of_negligible_size()`.
Which can be used to remove connected components whose area or volume is under a certain threshold.
Area and volume thresholds are either specified by the user or deduced from the bounding box of the mesh.
Added a new named parameter for `keep_large_connected_components()` and `remove_connected_components_of_negligible_size`.
That can be used to perform a dry run of the operation, meaning that the function will return the number of connected
Components that would be removed with the specified threshold, but without actually removing them.
The function `CGAL::Polygon_mesh_processing::stitch_borders()` now returns the number
of halfedge pairs that were stitched.
2D Triangulations:
To an inconsistency between code and documentation and to clarify which types of intersections.
Are truly allowed in constrained Delaunay triangulations, the tag `CGAL::No_intersection_tag`
Has been deprecated in favor of two new tags `CGAL::No_constraint_intersection_tag`
And `CGAL::No_constraint_intersection_requiring_constructions_tag`.
The latter is equivalent to the now-deprecated `CGAL::No_intersection_tag`, and allows constraints
to intersect as long as no new point has to be created to represent that intersection (for example.
The intersection of two constrain

5.030 Sep 2019 16:45
**minor feature:**
https://github.com/CGAL/cgal/releases/tag/releases 2FCGAL-5.0