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 backward-compatible with existing usages of CGAL CMake
scripts. The only non-compatible effect is that the
`CMAKE_BUILD_TYPE`

and compilation flags are no longer copied from the`CGAL_DIR`

to the project using it. Note also that the`CMAKE_BUILD_TYPE`

is no longer set to`Release`

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 build-system should set the`CMAKE_BUILD_TYPE`

to`Release`

manually.

### 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 user-defined 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 CGAL-4.12. Users of the package will have to keep using the source code available in CGAL-4.12 or earlier.

### 2D Arrangements

- When removing an edge from an arrangement and the user has requested to remove the end-vertices in case they become redundant (either isolated or approach infinity), defer the removal of the such end-vertices 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 (non-symmetric) 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 class`Triangulation_hierarchy_vertex_base_2`

, which is identical.**Breaking change**: The functions`circumcenter()`

,`side_of_oriented_circle()`

, and`is_extensible_in_1_sheet_h[12]()`

are related to Delaunay triangulations and have been moved from`Periodic_2_triangulation_2`

to`Periodic_2_Delaunay_triangulation_2`

.

### 2D Alpha Shapes

- It is now possible to use
`CGAL::Periodic_2_triangulation_2`

as underlying triangulation for`Alpha_shape_2`

.

### 3D Surface Mesh Generation

- Added the function
`facets_in_complex_2_to_triangle_mesh()`

that exports`Surface_mesh_complex_2_in_triangulation_3`

facets into a`MutableFaceGraph`

.

### 3D Mesh Generation

- Added the function
`facets_in_complex_3_to_triangle_mesh()`

that exports`Mesh_complex_3_in_triangulation_3`

facets into a`MutableFaceGraph`

. **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.- Added 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()`

, and`non_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 feature-guided
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.- Add a callback mechanism for both
`CGAL::Efficient_RANSAC`

and`CGAL::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 functions`METIS_PartMeshNodal`

and`METIS_PartMeshDual`

are offered.