[Compgeom-discuss] CGAL 3.2 Released, Computational Geometry Algorithms Library

[Andreas Fabri]

The CGAL Open Source Project is pleased to announce the release 3.2 of
CGAL, the Computational Geometry Algorithms Library.


Besides improvements of existing packages this release offers
the following new algorithms and data structures.

  o 2D Regularized Boolean Set-Operations

    This package consists of the implementation of Boolean
    set-operations on point sets bounded by weakly x-monotone curves in
    2-dimensional Euclidean space. In particular, it contains the
    implementation of regularized Boolean set-operations, intersection
    predicates, and point containment predicates.

  o 2D Straight Skeleton and Polygon Offsetting

    This package implements an algorithm to construct a halfedge data
    structure representing the straight skeleton in the interior of 2D
    polygons with holes and an algorithm to construct inward offset
    polygons at any offset distance given a straight skeleton.


  o 2D Voronoi Diagram

    The 2D Voronoi diagram package provides an adaptor that adapts a
    2-dimensional triangulated Delaunay graph to the corresponding
    Voronoi diagram, represented as a doubly connected edge list (DCEL)
    data structure. The adaptor has the ability to automatically
    eliminate, in a consistent manner, degenerate features of the
    Voronoi diagram, that are artifacts of the requirement that
    Delaunay graphs should be triangulated even in degenerate
    configurations. Depending on the type of operations that the
    underlying Delaunay graph supports, the adaptor allows for the
    incremental or dynamic construction of Voronoi diagrams and can
    support point location queries.


  o 3D Surface Mesher

    This package provides functions to generate surface meshes that
    interpolate smooth surfaces. The meshing algorithm is based on
    Delaunay refinement and provides some guarantees on the resulting
    mesh: the user is able to control the size and shape of the mesh
    elements and the accuracy of the surface approximation. There is no
    restriction on the topology and number of components of input
    surfaces. The surface mesher may also be used for non smooth
    surfaces but without guarantee.

    Currently, implementations are provided for implicit surfaces
    described as the zero level set of some function and surfaces
    described as a gray level set in a three-dimensional image.


  o 3D Surface Subdivision Methods

    Subdivision methods recursively refine a control mesh and generate
    points approximating the limit surface. This package consists of
    four popular subdivision methods and their refinement hosts.
    Supported subdivision methods include Catmull-Clark, Loop, Doo-Sabin
    and sqrt(3) subdivisions. Their respective refinement hosts are
    PQQ, PTQ, DQQ and sqrt(3) refinements. Variations of those methods
    can be easily extended by substituting the geometry computation of
    the refinement host.


  o Planar Parameterization of Triangulated Surface Meshes

    Parameterizing a surface amounts to finding a one-to-one mapping
    from a suitable domain to the surface. In this package, we focus
    on triangulated surfaces that are homeomorphic to a disk and on
    piecewise linear mappings into a planar domain. This package
    implements some of the state-of-the-art surface mesh
    parameterization methods, such as least squares conformal maps,
    discrete conformal map, discrete authalic parameterization,
    Floater mean value coordinates or Tutte barycentric mapping.


  o Principal Component Analysis

    This package provides functions to compute global informations on
    the shape of a set of 2D or 3D objects such as points. It provides
    the computation of axis-aligned bounding boxes, centroids of point
    sets, barycenters of weighted point sets, as well as linear least
    squares fitting for point sets in 2D, and point sets as well as
    triangle sets in 3D.


  o 2D Placement of Streamlines

    Visualizing vector fields is important for many application domains.
    A good way to do it is to generate streamlines that describe the
    flow behavior. This package implements the "Farthest Point Seeding"
    algorithm for placing streamlines in 2D vector fields. It generates
    a list of streamlines corresponding to an input flow using a
    specified separating distance. The algorithm uses a Delaunay
    triangulation to model objects and adress different queries, and
    relies on choosing the centers of the biggest empty circles to start
    the integration of the streamlines.


  o  Kinetic Data Structures

    Kinetic data structures allow combinatorial structures to be
    maintained as the primitives move. The package provides
    implementations of kinetic data structures for Delaunay
    triangulations in two and three dimensions, sorting of points in
    one dimension and regular triangulations in three dimensions.
    The package supports exact or inexact operations on primitives
    which move along polynomial trajectories.


  o Kinetic Framework

    Kinetic data structures allow combinatorial geometric structures
    to be maintained as the primitives move. The package provides a
    framework to ease implementing and debugging kinetic data
    structures. The package supports exact or inexact operations on
    primitives which move along polynomial trajectories.


  o  Smallest Enclosing Ellipsoid

    An approximative algorithm for constructing the smallest enclosing
    ellipsoid in d-dimensional Euclidean space.



See http://www.cgal.org/releases_frame.html for a complete list of changes.



The CGAL project is a collaborative effort to develop a robust,
easy-to-use, and efficient C++ software library of geometric data
structures and algorithms, like
- triangulations (2D constrained triangulations and Delaunay
   triangulations in 2D and 3D),
- Voronoi diagrams (for 2D and 3D points, 2D additively weighted
   Voronoi diagrams, and segment Voronoi diagrams),
- Boolean operations on polygons and polyhedra,
- arrangements of curves,
- mesh algorithms (2D Delaunay mesh generation and 3D surface mesh
   generation, surface mesh subdivision and parameterization),
- alpha shapes,
- convex hull algorithms (in 2D, 3D and dD),
- operations on polygons (straight skeleton and offset polygon),
- search structures (kd trees for nearest neighbor search, and
   range and segment trees),
- interpolation (natural neighbor interpolation and placement of
   streamlines),
- optimisation algorithms (smallest enclosing sphere of points or
   spheres, smallest enclosing ellipsoid of points, principal
   component analysis),
- kinetic data structures.




Some modules are distributed under the terms of the LGPL Open Source
license(GNU Lesser General Public License v2.1).
Most modules are distributed under the terms of the QPL Open Source
license (Q Public License v1.0).
If your intended usage does not meet the criteria of the
aforementioned licenses, a commercial license must be purchased from
GeometryFactory (www.geometryfactory.com).


For further information and for downloading the library and its
documentation, please visit the CGAL web site: http://www.cgal.org/