CGAL 2.3 differs from CGAL 2.2 in the platforms that are supported and in functionality:
- GNU g++ 3.0 on Solaris and Linux
- 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_homogeneousis available. It is equivalent to
Homogeneousbut without reference-counted objects.
- A new kernel called
Filtered_kernelis available that allows one to build kernel traits classes that use exact and efficient predicates.
- A new d-dimensional kernel,
Kernel_dis available. It provides diverse kernel objects, predicates and constructions in d dimensions with two representations based on the kernel families
- There are two classes,
Homogeneous_converterthat allows one to convert objects between different Cartesian and homogeneous kernels, respectively.
- 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_3now uses a new implementation of the quickhull algorithm and no longer requires LEDA.
- A new
convex_hull_incremental_3function based on the new d-dimensional convex hull class is available for comparison purposes.
- 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_2but 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
- 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 (
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.
- The polyhedral surface has been rewritten to work with the new
halfedge data structure design. The user level interface of the
CGAL::Polyhedron_3class 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_ONEmacro. The new design is selected with the
- 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…
- A new class
Triangulation_hierarchy_3that 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)
Triangulation_data_structurehave 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.
- 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.
In_place_listhas a new third template parameter (with a suitable default) for an STL-compliant allocator.
Unique_hash_mapis a new support class.
Union_findis a new support class.
Lazy_exact_nt<NT>is a new number type wrapper to speed up exact number types.
MP_Floatis a new multiprecision floating point number type. It can do exact additions, subtractions and multiplications over floating point values.
- Geomview version 1.8.1 is now required.
- no need to have a
- new output operators for triangulations.
- new output operators for
- various new manipulators…
- 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.