CGAL 4.12 offers the following improvements and new functionality over CGAL 4.11:
Changelog
Important Notice
 The CMake scripts used by CGAL have been changed to use modern patterns introduced by CMake 2.8.12 and CMake 3.0: instead of setting CMake variables, the script now defines imported targets and uses link interfaces.
 That is mostly backwardcompatible with existing usages of CGAL CMake
scripts. The only noncompatible effect is that the
CMAKE_BUILD_TYPE
and compilation flags are no longer copied from theCGAL_DIR
to the project using it. Note also that theCMAKE_BUILD_TYPE
is no longer set toRelease
by default. For a developer using the Visual Studio IDE or the Xcode IDE, the change should be transparent. Developers using makefiles or the Ninja buildsystem should set theCMAKE_BUILD_TYPE
toRelease
manually, to avoid using CGAL libraries without any compiletime optimization.
Headeronly mode
 Since CGAL4.9, it has been possible to use CGAL by configuring it using CMake, but without compiling the CGAL libraries. With CGAL4.12, it is now possible to use CGAL headeronly, without even configuring it. CMake is then used only to configure programs using CGAL.
2D Movable Separability of Sets (new package)
 A new package called “2D Movable Separability of Sets” has been introduced. It handles a class of problems that deal with moving sets of objects in the plane; the challenge is to avoid collisions between the objects while considering different kinds of motions and various definitions of separation.
 At this point this package consists of the implementations of various predicates and constructions related to castings of polygonal objects. In particular, it can be used to determine whether a feasible mold for a polygonal object does exist. If a mold exists, the package can also be used to compute all possible orientations of the feasible molds and the corresponding motions needed to remove the casted object from the mold.
Classification (new package)
 This package offers an algorithm that classifies a data set into a userdefined set of labels (such as ground, vegetation, buildings, etc.). A flexible API is provided so that users can classify any type of data, compute their own local features on the input data set, and define their own labels.
Kinetic Data Structures (removed package)
 This package has been removed from CGAL4.12. Users of the package will have to keep using the source code available in CGAL4.11 or earlier.
3D Convex Hull
 Breaking change: The header
<CGAL/convex_hull_3.h>
no longer includes<CGAL/Polyhedron_3.h>
, as the convex hull function works with any model of the conceptMutableFaceGraph
.
2D Arrangements

When removing an edge from an arrangement and the user has requested to remove the endvertices in case they become redundant (either isolated or approach infinity), defer the removal of the such endvertices to occur after the observer is notified that the edge has been removed. This is symmetric (opposite) to the order of notification when an edge is inserted.
The user can restore old (nonsymmetric) behaviour by defining the macro:
CGAL_NON_SYMETRICAL_OBSERVER_EDGE_REMOVAL_BACKWARD_COMPATIBILITY
2D Periodic Triangulations
 Breaking change: The class
Periodic_2_triangulation_hierarchy_vertex_base_2
(and its corresponding header) have been removed. Users should directly use the classTriangulation_hierarchy_vertex_base_2
, which is identical.  Breaking change: The functions
circumcenter()
,side_of_oriented_circle()
, andis_extensible_in_1_sheet_h[12]()
are related to Delaunay triangulations and have been moved fromPeriodic_2_triangulation_2
toPeriodic_2_Delaunay_triangulation_2
.
2D Alpha Shapes
 It is now possible to use
CGAL::Periodic_2_triangulation_2
as underlying triangulation forAlpha_shape_2
.
3D Surface Mesh Generation
 Add the function
facets_in_complex_2_to_triangle_mesh()
that exportsSurface_mesh_complex_2_in_triangulation_3
facets into aMutableFaceGraph
.
3D Mesh Generation
 Add the function
facets_in_complex_3_to_triangle_mesh()
that exportsMesh_complex_3_in_triangulation_3
facets into aMutableFaceGraph
.  Breaking change: The concept
MeshDomainWithFeatures_3
has been modified, to improve the performance and the reliability of the sampling of 1D curves of the domain.  Add the ability to ensure that the output mesh surface describes a
manifold, when the input surface is a manifold. New named parameters
manifold()
,manifold_with_boundary()
, andnon_manifold()
are added.
Optimal Transportation Curve Reconstruction
 New method
run_under_wasserstein_tolerance()
which allows the user to perform curve reconstruction by relying on a threshold on the Wasserstein distance. This is useful when the number of edges in the expected output reconstruction is not known.
Polygon Mesh Processing
 Added two functions for orienting connected components :
CGAL::Polygon_mesh_processing::orient()
CGAL::Polygon_mesh_processing::orient_to_bound_a_volume()
 Added a new function for intersection tests between triangle meshes
and/or polylines or range of polylines, and another one to report
all the pairs of meshes intersecting from a range of meshes:
CGAL::Polygon_mesh_processing::do_intersect()
CGAL::Polygon_mesh_processing::intersecting_meshes()
 Added new functions for feature detection and featureguided
segmentation:
CGAL::Polygon_mesh_processing::detect_sharp_edges()
CGAL::Polygon_mesh_processing::detect_vertex_incident_patches()
CGAL::Polygon_mesh_processing::sharp_edges_segmentation()
Point Set Shape Detection
 New algorithm:
CGAL::Region_growing
. This is a deterministic alternative to RANSAC for plane detection.  Breaking change: the API of
CGAL::regularize_planes()
is generalized to accept other types of input than the RANSAC output.  Added a callback mechanism for both
CGAL::Efficient_RANSAC
andCGAL::Region_growing
.
Point Set Processing
 Breaking change: the API of
CGAL::structure_point_set()
is generalized to accept other types of input than the RANSAC output.  Breaking change: the API of all functions of Point Set Processing is modified to use ranges (instead of iterators) and Named Parameters (similarly to the API of Polygon Mesh Processing). The old API is kept as deprecated.
CGAL and the Boost Graph Library (BGL)
 Added helper function
CGAL::expand_face_selection_for_removal
that expands a face selection to avoid creating a non manifold mesh when removing the selected faces.  Added support for dynamic property maps.
 Added an interface to the METIS library,
which allows to partition any mesh that is a model of
FaceListGraph
. Wrappers to the METIS functionsMETIS_PartMeshNodal
andMETIS_PartMeshDual
are offered.