CGAL 3.9 released

Changelog

General

• The class Root_of_2 is now deprecated. It is recommended to use the class Sqrt_extension instead.
• The class Sqrt_extension is now used everywhere in CGAL where an algebraic number of degree 2 is needed. This change has been done in the Root_of_traits mechanism (indirectly packages 2D Circular kernel and 3D Spherical kernel) and the packages 2D Segment Delaunay Graphs and 2D Arrangements.
• Various fixes in the manual.

Combinatorial Maps (new package)

• This package provides a new combinatorial data structure allowing to describe any orientable subdivided object whatever its dimension. It describes all cells of the subdivision and all the incidence and adjacency relations between these cells. For example it allows to describe a 3D object subdivided in vertices, edges, faces and volumes. This data structure can be seen as the generalization in dD of the halfedge data structure.

3D Convex Hull (major performance improvement)

• The quickhull implementation of CGAL (CGAL::convex_hull_3) has been worked out to provide very better performances.
• The function CGAL::convex_hull_3 no longer computes the plane equations of the facets of the output polyhedron. However an example is provided to show how to compute them easily.
• A global function convex_hull_3_to_polyhedron_3 is now provided to extract the convex hull of a 3D points set from a triangulation of these points.

dD Spatial Searching (major new feature added)

• A traits-class and distance adapter that together with a point property map, allow to make nearest neighbor queries on keys instead of points have been added.
• Few bug fixes in the documentation have revealed some inconsistencies that have been corrected. Two traits class concept are now documented (RangeSearchTraits and SearchTraits). Most other changes concerns only classes documented as advanced. One issue that user can encounter is due to an additional requirement on the nested class Construct_cartesian_const_iterator_d defined in the concept SearchTraits that must provide a nested type result_type.

Spatial Sorting (major new feature added)

• General dimension is now supported.
• Hilbert sorting admits now two policies: splitting at median or at middle (see user manual).
• Using a property map, sorting on keys instead of points is now easier

dD Kernel

• The d-dimensional kernel concept and models have been modified to additionally provide two new functors Less_coordinate_d and Point_dimension_d.

2D Arrangements

• A new geometry-traits class that handles rational arcs, namely Arr_rational_function_traits_2, has been introduced. It replaced an old traits class, which handled the same family of curves, but it was less efficient. The new traits exploits CGAL algebraic kernels and polynomials, which were not available at the time the old traits class was developed.
• A new geometry traits concept called ArrangementOpenBoundaryTraits_2 has been introduced. A model of this concept supports curves that approach the open boundary of an iso-rectangular area called parameter space, which can be unbounded or bounded. The general code of the package, however, supports only the unbounded parameter space. We intend to enhance the general code to support also bounded parameter spaces in a future release.
• The deprecated member function is_at_infinity() of Arrangement_2::Vertex has been removed. It has been previously replaced new function is_at_open_boundary().
• The tags in the geometry traits that indicate the type of boundary of the embedding surface were replaced by the following new tags: Left_side_category, Bottom_side_category, Top_side_category, and Right_side_category.
• It is still possible not to indicate the tags at all. Default values are assumed. This however will produce warning messages, and should be avoided.