### The CGAL Manual

- The documentation of CGAL is now generated with Doxygen.

### 2D Periodic Triangulations (new package)

- This package allows to build and handle triangulations of point sets in the two dimensional flat torus. Triangulations are built incrementally and can be modified by insertion or removal of vertices. They offer point location facilities. The package provides Delaunay triangulations and offers nearest neighbor queries and primitives to build the dual Voronoi diagrams.

### API Changes

#### 2D and 3D Geometry Kernel

- The intersection functions and functors used to return
a
`CGAL::Object`

in order to deal with the different possible return types. However, depending on the arguments it is possible to reduce the possible return types to a small set. For this reason and to take advantage of the type safety, we decided to use`boost::variant`

instead of`CGAL::Object`

. The`result_of`

protocol is now even more useful to determine the return type of the intersection functions and functors. The change should be relatively transparent to the user thanks to the implicit constructor added to`CGAL::Object`

. However, it is recommended to upgrade your code. The previous behavior can be restored by defining the macro`CGAL_INTERSECTION_VERSION`

to 1.

#### 2D Arrangements

- The type of the result of point location queries changed to
`boost::variant`

(from`CGAL::Object`

). For convenience, the previous behavior can be restored by defining the macro`CGAL_ARR_POINT_LOCATION_VERSION`

to 1. - Introduced an optimization for operations on large and dense arrangements.

#### 3D Fast Intersection and Distance Computation

- Following the intersection API
change,
`Object_and_primitive_id`

has been replaced by a template class`Intersection_and_primitive_id<Query>`

to determine the type depending on the query object type.

#### CGAL and Boost Property Maps

- The
`key_type`

of the property maps provided by CGAL used to be an iterator. In order to be more easily re-used, the`key_type`

has been changed to be the`value_type`

of the iterator. The packages that have been updated to match these changes are**Point Set Processing**and**Surface Reconstruction from Point Sets**. However, for most users this change should be transparent if the default property maps were used. For convenience, the former behavior can be enabled by defining the macro`CGAL_USE_PROPERTY_MAPS_API_V1`

.

### Algebraic Foundations

- For convenience, add an overload of
`make_rational()`

taking a pair of numbers.

### 2D and 3D Geometry Kernel

- A
`Iso_rectangle_2`

can now be constructed from a`Bbox_2`

and an`Iso_cuboid_3`

from a`Bbox_3`

. - The implementation of
`CGAL::Object`

has been updated and now uses`boost::shared_ptr`

and`boost::any`

. This implementation is faster. - Add to
`Bbox_2`

and`Bbox_3`

a`+=`

operator as well as free functions to get the bounding box of a range of geometric objects.

### Combinatorial Maps

- Two bug fixes: do not use the 2 least significant bits for cell attribute without dart support; share the mark when copying a CMap_cell_iterator.
- Add a constructor taking a given combinatorial map as argument, possibly with different dimension and/or different attributes. This allows to transform a combinatorial map.
- Add operator= and swap method.
- Add dynamic onmerge/onsplit functions that can be associated dynamically to i-attributes and which are automatically called when i-cells are split/merged.
- Add a function allowing to reverse the orientation of a combinatorial map, and another one to reverse one connected component of a combinatorial map.

### 3D Boolean Operations on Nef Polyhedra

- Bug-fix in IO when using
`Lazy_exact_nt`

as number type or`Exact_predicates_exact_constructions_kernel`

as kernel.

### 2D Triangulations

- Extend the concept
`TriangulationDataStructure_2`

to require a more general`copy_tds`

function that allows a copy between TDS of different types. The CGAL model has been updated. - Add a way to efficiently insert a range of points with information into the 2D constrained Delaunay triangulations.

### 3D Triangulations

- Extend the concept
`TriangulationDataStructure_3`

to require a more general`copy_tds`

function that allows a copy between TDS of different types. The CGAL model has been updated. - Add an advanced function to set the infinite vertex of the triangulation for low level operations
- Fix a bug in the function inserting a range of points with info
when the
`Fast_location`

tag is used

### 2D Segment Delaunay Graph

- Add functions
`insert_points`

and`insert_segments`

to insert a range of points and segments. These functions uses the spatial sorting in order to speed up the time needed for the insertion. The function`insert(Input_iterator first, Input_iterator beyond, Tag_true)`

has been updated to dispatch the input when possible to these functions.

### 2D Apollonius Graphs

- Modified insertion algorithm so that the code can handle pseudo-circles as well.
- Updated implementation of the vertex conflict predicate by a faster version.

### 3D Mesh Generation

- Speed-up
`Mesh_3`

and in particular the global optimizers (Lloyd and ODT) by introducing a parameter`do_freeze`

to prevent from moving vertices which would move of very small displacements. - Introduce new data structures and options for speed-up and
compacity. Note that
`Compact_mesh_cell_base_3`

and`Mesh_vertex_base_3`

are now our favoured implementations of the concepts MeshCellBase_3 and MeshVertexBase_3. - Introduce a new constructor
for
`Polyhedral_mesh_domain_3`

that takes a bounding polyhedron to be meshed along with a polyhedral surface entirely included in it. This allows the user to mesh a polyhedral domain with internal surface(s) which can be non-watertight and even non-manifold. - Several documentation bug fixes.
- Provide the ability to plug in custom cell_base/vertex_base classes into the Mesh_triangulation_3 class.

### Triangulated Surface Mesh Simplification

- Fix a segmentation fault that was happening when some edges of length 0 were in the input mesh.

### 3D Fast Intersection and Distance Computation

- Following the intersection API
change,
`Object_and_primitive_id`

has been replaced by a template class`Intersection_and_primitive_id<Query>`

to determine the type depending on the query object type. - Introduce the
class
`AABB_halfedge_graph_segment_primitive`

, which replaces the class`AABB_polyhedron_segment_primitive`

(which is now deprecated). The new class is more general and can be used with any model of`HalfedgeGraph`

. - Introduce the class
`AABB_face_graph_triangle_primitive`

which replaces the class`AABB_polyhedron_triangle_primitive`

(which is now deprecated). - Document the classes
`AABB_segment_primitive`

and`AABB_triangle_primitive`

that were already used in some examples. - Add a generic primitive class
`AABB_primitive`

that allows to define a primitive type by defining only two property maps. - Introduce a new concept of
primitive
`AABBPrimitiveWithSharedData`

. It allows to have some data shared between the primitives stored in a`AABB_tree`

. With this you can, for example have a primitive wrapping an integer which refers to the position of a geometric object in a`std::vector`

. Only one reference to this vector will be stored in the traits of the tree. The concept`AABBTraits`

, its model`AABB_traits`

and the class`AABB_tree`

have been updated accordingly. However, everything is backward compatible. - Fix a memory leak in the destructor of the
class
`AABB-tree`

### STL Extensions for CGAL

- Add to
`Dispatch_output_iterator`

and`Dispatch_or_drop_output_iterator`

an operator to accept and dispatch a tuple of values.

### Concurrency in CGAL

- Add a
`FindTBB`

CMake module so that one can easily link with TBB to write shared-memory parallel code. - Introduce two new tags: Sequential_tag and Parallel_tag