CGAL 2.3 released

Changelog

Supported platforms

• GNU g++ 3.0 on Solaris and Linux

Kernel

• The 2D and 3D kernels now serve as models of the new kernel concept described in the recent paper, An Adaptable and Extensible Geometry Kernel by Susan Hert, Micheal Hoffmann, Lutz Kettner, Sylvain Pion, and Michael Seel to be presented at WAE 2001 (and soon available as a technical report). This new kernel is completely compatible with the previous design but is more flexible in that it allows geometric predicates as well as objects to be easily exchanged and adapted individually to users’ needs.
• A new kernel called Simple_homogeneous is available. It is equivalent to Homogeneous but without reference-counted objects.
• A new kernel called Filtered_kernel is available that allows one to build kernel traits classes that use exact and efficient predicates.
• A new d-dimensional kernel, Kernel_d is available. It provides diverse kernel objects, predicates and constructions in d dimensions with two representations based on the kernel families Cartesean_d and Homogeneous_d.
• There are two classes, Cartesian_converter and Homogeneous_converter that allows one to convert objects between different Cartesian and homogeneous kernels, respectively.

Basic Library

• Almost all packages in the basic library have been adapted to the new kernel design to realize the flexibility this design makes possible. In several packages, this means that the traits class requirements have changed to conform to the function objects offered in the kernels so the kernels themselves can be used as traits classes in many instances.

2D Convex Hull

• The traits requirements have changed slightly to bring them in line with the CGAL kernels.

3D Convex Hull

• The function convex_hull_3 now uses a new implementation of the quickhull algorithm and no longer requires LEDA.
• A new convex_hull_incremental_3 function based on the new d-dimensional convex hull class is available for comparison purposes. Convex_hull_d, Delaunay_d
• Two new application classes offering the calculation of d-dimensional convex hulls and delaunay triangulations

Polygons and Polygon Operations

• The traits class requirements have been changed.
• The simplicity test has a completely new implementation.
• Properties like convexity, simplicity and area can now be cached by polygons. You need to set a flag to select this behaviour.

Planar Nef Polyhedra

• A new class (Nef_polyhedron_2) representing planar Nef polyhedra = rectilinearly bounded points sets that are the result of binary and topological operations starting from halfplanes.
• A new package offering functions to partition planar polygons into convex and y-monotone pieces is available.

Planar Maps and Arrangements

• A new class Planar_map_with_intersections_2<Planar_map> for planar maps of possibly intersecting, possibly non-x-monotone, possibly overlapping curves (like Arrangement_2 but without the hierarchy tree).
• I/O utilities for planar maps and arrangements for textual and graphical streams. (It is possible to save and later reload built planar maps or arrangements.)
• New arrangement traits class for line segments and circular arcs (Arr_segment_circle_traits<NT>).
• New faster traits for polylines specialized for using the LEDA rational kernel (Arr_leda_polylines_traits). The LEDA traits for segments was also made faster.
• A new point location strategy (Pm_simple_point_location<Planar_map>).

Halfedge Data Structure

• The halfedge data structure has been completely revised. The new design is more in line with the STL naming scheme and it provides a safe and coherent type system throughout the whole design (no void* pointers anymore), which allows for better extendibility. A user can add new incidences in the mesh easily. The new design also uses standard allocators with a new template parameter that has a suitable default.
• The old design is still available, but its use is deprecated, see the manual of deprecated packages for its documentation. Reported bugs in copying the halfedge data structure (and therefore also polyhedral surfaces) have been fixed in both designs. Copying a list-based representation is now based on hash maps instead of std::map and is therefore considerably faster.

Polyhedral Surface

• The polyhedral surface has been rewritten to work with the new halfedge data structure design. The user level interface of the CGAL::Polyhedron_3 class is almost backwards compatible with the previous class. The exceptions are the template parameter list, everything that relies on the flexibility of the underlying halfedge data structure, such as a self-written facet class, and that the distinction between supported normals and supported planes has been removed. Only planes are supported. See the manuals for suggestions how to handle normals instead of planes.
• More example programs are provided with polyhedral surfaces, for example, one about Euler operator and one computing a subdivision surface given a control mesh as input.
• The old design is still available for backwards compatibility and to support older compiler, such as MSVC++6.0. For the polyhedral surface, old and new design cannot be used simultaneously (they have identical include file names and class names). The include files select automatically the old design for MSVC++6.0 and the new design otherwise. This automatism can be overwritten by defining appropriate macros before the include files. The old design is selected with the CGAL_USE_POLYHEDRON_DESIGN_ONE macro. The new design is selected with the CGAL_USE_POLYHEDRON_DESIGN_TWO macro.

2D Triangulation

• The geometric traits class requirements have been changed to conform to the new CGAL kernels. CGAL kernel classes can be used as traits classes for all 2D triangulations except for regular triangulations.
• Dual method for regular triangulations (to build a power diagram).
• Unified names and signatures for various “find_conflicts()”. member functions in Delaunay and constrained Delaunay triangulation.
• As an alternative to the simple insert() member function, insertion of points in those triangulation can be performed using the combination of find_conflicts() and star_hole() which eventually allows the user to keep track of deleted faces.
• More demos and examples…

3D Triangulation

• A new class Triangulation_hierarchy_3 that allows a faster point location, and thus construction of the Delaunay triangulation.
• A new method for removing a vertex from a Delaunay triangulation that solves all degenerate cases
• Running time of the usual location and insertion methods improved.
• New geomview output.
• Dual methods in Delaunay triangulations to draw the Voronoi diagram.
• Traits classes requirements have been modified
• The kernel can be used directly as a traits class (except for regular triangulation)
• insert methods in Triangulation_data_structure have a new interface.
• More demos and examples…

3D Alpha Shapes

• A new class (Alpha_shapes_3) that computes Alpha shapes of point sets in 3D is available.
• The traits requirements for matrix search and minimum quadrilaterals have been changed to bring them in line with the CGAL kernels.

Point_set_2

• Now independent from LEDA and based on the CGAL Delaunay triangulation.
• Traits class requirements adapted to new kernel concept.
• Function template versions of the provided query operations are available.

Support Library

General

• In_place_list has a new third template parameter (with a suitable default) for an STL-compliant allocator.
• Unique_hash_map is a new support class.
• Union_find is a new support class.

Number types:

• Lazy_exact_nt<NT> is a new number type wrapper to speed up exact number types.
• MP_Float is a new multiprecision floating point number type. It can do exact additions, subtractions and multiplications over floating point values.

Geomview_stream

• Geomview version 1.8.1 is now required.
• no need to have a ~/.geomview file anymore.
• new output operators for triangulations.
• new output operators for Ray_2, Line_2, Ray_3, Line_3, Sphere_3.
• various new manipulators…

Window stream

• In cooperation with Algorithmic Solutions, GmBH (distributors of the LEDA library), we can now offer a visualization package downloadable in binary form that supports visualization on a ported version of the LEDA window lib.