 
IntroductionCGAL Editorial Board  
This chapter explains how the manual is organized, presents a ``Hello World''
program, and gives recommendations for further readings.

Introduced in: Cgal 1.0 Citation Entry User Manual Reference Manual 

PreliminariesCGAL Editorial Board  
This chapter lists the licenses
under which the Cgal datastructures and algorithms are distributed,
and the third party libraries on which Cgal depends, or for which
Cgal provides interfaces. The chapter further explains how to control
inlining, thread safety, code deprecation, checking of pre and postconditions,
and how to alter the failure behavior.
Finally, if you want to download and run any of the precompiled demos, here you can find the dlls that are shared by all of them. Note that on computer that does not have Visual C++ 2005 installed, you probably also need the Microsoft Visual C++ 2005 SP1 Redistributable Package (x86).

Introduced in: Cgal 1.0 Citation Entry Demo: dlls used by all demos User Manual Reference Manual 

InstallationJoachim Reichel and Fernando Cacciola  
This chapter describes how to install CGAL.

Introduced in: Cgal 3.6 Citation Entry User Manual Reference Manual 

 
Algebraic FoundationsMichael Hemmer  
This package defines what algebra means for Cgal, in terms of
concepts, classes and functions. The main features are:
(i) explicit concepts for interoperability of types
(ii) separation between algebraic types (not necessarily embeddable
into the reals), and number types (embeddable into the reals).

Introduced in: Cgal 3.3 License: LGPL Citation Entry User Manual Reference Manual 

Number TypesMichael Hemmer, Susan Hert, Sylvain Pion, and Stefan Schirra  
This package provides number type concepts as well as number type
classes and wrapper classes for third party number type libraries.

Introduced in: Cgal 1.0 License: LGPL Citation Entry User Manual Reference Manual 

Modular ArithmeticMichael Hemmer  
This package provides arithmetic over finite fields.
The provided tools are in particular useful for filters based on
modular arithmetic and algorithms based on Chinese remainder.

Introduced in: Cgal 3.4 License: LGPL Citation Entry User Manual Reference Manual 

PolynomialMichael Hemmer  
This package introduces a concept Polynomial_d, a concept for multivariate
polynomials in d variables. Though the concept is written for an arbitrary
number of variables, the number of variables is considered as fixed for a
particular model of Polynomial_d. The concept covers univariate
polynomials as well.

Introduced in: Cgal 3.3 License: LGPL Citation Entry User Manual Reference Manual 

Algebraic KernelEric Berberich, Michael Hemmer, Sylvain Lazard, Luis Peñaranda, and Monique Teillaud  
Real solving of polynomials is a fundamental problem with a wide application range.
This package is targeted to provide blackbox implementations of stateoftheart
algorithms to determine, compare and approximate real roots of univariate polynomials
and bivariate polynomial systems. Such a blackbox is called an Algebraic Kernel.
So far the package only provides models for the univariate kernel. Nevertheless,
it already defines concepts for the bivariate kernel, since this settles the interface
for upcoming implementations.

Introduced in: Cgal 3.6 Depends on: Some models depend on RS. License: LGPL Citation Entry User Manual Reference Manual 

 
Monotone and Sorted Matrix SearchMichael Hoffmann  
This package provides a matrix search framework, which is
the underlying technique for the computation of all furthest neighbors for the vertices of a convex polygon,
maximal kgons inscribed into a planar point set, and computing rectangular pcenters.

Introduced in: Cgal 1.1 License: QPL Citation Entry User Manual Reference Manual 

Linear and Quadratic Programming SolverKaspar Fischer, Bernd Gärtner, Sven Schönherr, and Frans Wessendorp  
This package contains algorithms for minimizing linear and
convex quadratic functions over polyhedral domains, described by linear
equations and inequalities. The algorithms are exact, i.e. the solution
is computed in terms of multiprecision rational numbers.
The resulting solution is certified: along with the claims that the problem under consideration has an optimal solution, is infeasible, or is unbounded, the algorithms also deliver proofs for these facts. These proofs can easily (and independently from the algorithms) be checked for correctness. The solution algorithms are based on a generalization of the simplex method to quadratic objective functions.

Introduced in: Cgal 3.3 License: QPL Citation Entry User Manual Reference Manual 

 
2D and 3D Linear Geometry KernelHervé Brönnimann, Andreas Fabri, GeertJan Giezeman, Susan Hert, Michael Hoffmann, Lutz Kettner, Sylvain Pion, and Stefan Schirra  
This package contains kernels each containing objects of
constant size, such as point, vector, direction, line, ray, segment, circle
as well as predicates and constructions for these objects. The kernels
mainly differ in the way they handle robustness issues.

Introduced in: Cgal 0.9 License: LGPL Citation Entry Demo: Robustness User Manual Reference Manual 

dD Geometry KernelMichael Seel  
The dD Kernel contains objects of constant size, such as point,
vector, direction, line, ray, segment, circle in d dimensional Euclidean space,
as well as predicates and constructions for these objects.

Introduced in: Cgal 1.1 License: LGPL Citation Entry User Manual Reference Manual 

2D Circular Geometry KernelPedro Machado Manhães de Castro, Sylvain Pion, and Monique Teillaud  
This package is an extension of the linear Cgal kernel. It offers
functionalities on circles, circular arcs and line segments in the
plane.

Introduced in: Cgal 3.2 License: QPL Citation Entry Demo: Arrangement of Circular Arcs User Manual Reference Manual 

3D Spherical Geometry KernelPedro Machado Manhães de Castro, Frédéric Cazals, Sébastien Loriot, and Monique Teillaud  
This package is an extension of the linear Cgal Kernel. It offers
functionalities on spheres, circles, circular arcs and line segments,
in the 3D space or restricted on a reference sphere.

Introduced in: Cgal 3.4 License: QPL Citation Entry User Manual Reference Manual 

 
2D Convex Hulls and Extreme PointsSusan Hert and Stefan Schirra  
This package provides functions
for computing convex hulls in two dimensions as well as functions for
checking if sets of points are strongly convex are not. There are also
a number of functions described for computing particular extreme
points and subsequences of hull points, such as the lower and upper
hull of a set of points.

Introduced in: Cgal 1.0 License: QPL Citation Entry Demo: 2D Convex Hull User Manual Reference Manual 

3D Convex HullsSusan Hert and Stefan Schirra  
This package provides functions
for computing convex hulls in three dimensions as well as functions
for checking if sets of points are strongly convex or not. One can
compute the convex hull of a set of points in three dimensions in one
of three ways: using a static algorithm, using an incremental
construction algorithm, or using a triangulation to get a fully
dynamic computation.

Introduced in: Cgal 1.1 Depends on: All algorithms produce as output a 3D Polyhedron. The dynamic algorithms depend on 3D Triangulations License: QPL Citation Entry Demo: See Polyhedral Surface User Manual Reference Manual 

dD Convex Hulls and Delaunay TriangulationsSusan Hert and Michael Seel  
This package provides functions for computing convex hulls and
Delaunay triangulations in ddimensional Euclidean space.

Introduced in: Cgal 2.3 License: QPL Citation Entry User Manual Reference Manual 

 
2D PolygonGeertJan Giezeman and Wieger Wesselink  
This package provides a 2D polygon class and operations on sequences of points, like bounding box, extremal points, signed area, simplicity and convexity test, orientation, and point location. The demo includes operations on polygons, such as computing a convex partition, and the straight skeleton.

Introduced in: Cgal 0.9 License: LGPL Citation Entry Demo: Operations on Polygons User Manual Reference Manual 

2D Regularized Boolean SetOperationsEfi Fogel, Ron Wein, Baruch Zukerman, and Dan Halperin  
This package consists of the implementation of Boolean setoperations
on point sets bounded by weakly xmonotone curves in 2dimensional
Euclidean space. In
particular, it contains the implementation of regularized Boolean
setoperations, intersection predicates, and point containment predicates.

Introduced in: Cgal 3.2 Depends on: 2D Arrangements License: QPL Citation Entry Demo: Boolean operations User Manual Reference Manual 

2D Boolean Operations on Nef PolygonsMichael Seel  
A Nef polygon is any set that can be obtained from a
finite set of open halfspaces by set complement and set intersection
operations. Due to the fact that all other binary set operations like
union, difference and symmetric difference can be reduced to
intersection and complement calculations, Nef polygons are also closed
under those operations. Apart from the set complement operation there
are more topological unary set operations that are closed in the
domain of Nef polygons interior, boundary, and closure.

Introduced in: Cgal 2.3 License: QPL Citation Entry Demo: 2D Nef Polygons User Manual Reference Manual 

2D Boolean Operations on Nef Polygons Embedded on the SpherePeter Hachenberger, Lutz Kettner, and Michael Seel  
This package offers the equivalent to 2D Nef Polygons in the plane.
Here halfplanes correspond to half spheres delimited by great circles.

Introduced in: Cgal 3.1 Depends on: 2D Nef Polygon License: QPL Citation Entry User Manual Reference Manual 

2D Polygon PartitioningSusan Hert  
This package provides functions
for partitioning polygons in monotone or convex polygons.
The algorithms can produce results with the minimal number of
polygons, as well as approximations which have no more than four
times the optimal number of convex pieces but they differ in
their runtime complexities.

Introduced in: Cgal 2.3 License: QPL Citation Entry Demo: 2D Polygon Partition Demo: Operations on Polygons User Manual Reference Manual 

2D Straight Skeleton and Polygon OffsettingFernando Cacciola  
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.

Introduced in: Cgal 3.2 Depends on: Halfedge Data Structure License: QPL Citation Entry Demo: 2D Straight Skeleton Demo: Operations on Polygons User Manual Reference Manual 

2D Minkowski SumsRon Wein  
This package consists of functions that compute the Minkowski sum
of two simple straightedge polygons in the plane. It also contains
functions for computing the Minkowski sum of a polygon and a disc,
an operation known as offsetting or dilating a polygon.
The package can compute the exact representation of the offset
polygon, or provide a guaranteed approximation of the offset.

Introduced in: Cgal 3.3 Depends on: 2D Arrangements License: QPL Citation Entry User Manual Reference Manual 

 
3D Polyhedral SurfaceLutz Kettner  
Polyhedral surfaces in three dimensions are composed of
vertices, edges, facets and an incidence relationship on them. The
organization beneath is a halfedge data structure, which restricts the
class of representable surfaces to orientable 2manifolds  with and
without boundary. If the surface is closed we call it a polyhedron.

Introduced in: Cgal 1.0 Depends on: Halfedge Data Structure License: QPL Citation Entry Demo: Operations on Polyhedra User Manual Reference Manual 

Halfedge Data StructuresLutz Kettner  
A halfedge data structure is an edgecentered data structure
capable of maintaining incidence information of vertices, edges and
faces, for example for planar maps, polyhedra, or other orientable,
twodimensional surfaces embedded in arbitrary dimension. Each edge is
decomposed into two halfedges with opposite orientations. One incident
face and one incident vertex are stored in each halfedge. For each
face and each vertex, one incident halfedge is stored. Reduced
variants of the halfedge data structure can omit some of these
information, for example the halfedge pointers in faces or the
storage of faces at all.

Introduced in: Cgal 1.0 License: LGPL Citation Entry User Manual Reference Manual 

3D Boolean Operations on Nef PolyhedraPeter Hachenberger, Lutz Kettner, and Michael Seel  
3D Nef polyhedra, are a
boundary representation for cellcomplexes bounded by halfspaces that
supports Boolean operations and topological operations in full
generality including unbounded cells, mixed dimensional cells (e.g.,
isolated vertices and antennas). Nef polyhedra distinguish between
open and closed sets and can represent nonmanifold geometry.

Introduced in: Cgal 3.1 Depends on: 2D Nef Polygons, Nef Polygons on the Sphere License: QPL Citation Entry Demo: Operations on Polyhedra User Manual Reference Manual 

Convex Decomposition of PolyhedraPeter Hachenberger  
This packages provides a function for decomposing a bounded polyhedron
into convex subpolyhedra. The decomposition yields O(r^{2}) convex
pieces, where r is the number of edges, whose adjacent facets form
an angle of more than 180 degrees with respect to the polyhedron's
interior. This bound is worstcase optimal.

Introduced in: Cgal 3.5 Depends on: 2D Nef Polygons, Nef Polygons on the Sphere 3D Nef Polyhedra, License: QPL Citation Entry User Manual Reference Manual 

3D Minkowski Sum of PolyhedraPeter Hachenberger  
This package provides a function, which computes the Minkowski sum of
two point sets in ℝ^{3}. These point sets may consist of
isolated vertices, isolated edges, surfaces with convex facets without
holes, and open and closed solids. Thus, it is possible to compute
the configuration space of translational robots (even in tight passage
scenarios) as well as several graphics operations, like for instance
the glide operation, which computes the point set swept by a
polyhedron that moves along a polygonal line.

Introduced in: Cgal 3.5 Depends on: 2D Nef Polygons, Nef Polygons on the Sphere 3D Nef Polyhedra, Convex Decomposition of Polyhedra License: QPL Citation Entry Demo: Operations on Polyhedra User Manual Reference Manual 

 
2D ArrangementRon Wein, Efi Fogel, Baruch Zukerman, and Dan Halperin  
This package can be used to construct, maintain, alter, and display
arrangements in the plane. Once an arrangement is constructed, the
package can be used to obtain results of various queries on the
arrangement, such as point location. The package also includes generic
implementations of two algorithmic frameworks, that are, computing the
zone of an arrangement, and linesweeping the plane, the arrangements
is embedded on. These frameworks are used in turn in the
implementations of other operations on arrangements. Computing the
overlay of two arrangements, for example, is based on the sweepline
framework.
Arrangements and arrangement components can also be extended to store additional data. An important extension stores the construction history of the arrangement, such that it is possible to obtain the originating curve of an arrangement subcurve.

Introduced in: Cgal 2.1 License: QPL Citation Entry User Manual Reference Manual 

2D Intersection of CurvesBaruch Zukerman and Ron Wein  
This package provides three free functions implemented
based on the sweepline paradigm: given a collection of input curves,
compute all intersection points, compute the set of subcurves that are
pairwise interiordisjoint induced by them, and check whether there
is at least one pair of curves among them that intersect in their
interior.

Introduced in: Cgal 2.4 Depends on: 2D Arrangements License: QPL Citation Entry User Manual Reference Manual 

2D Snap RoundingEli Packer  
Snap Rounding is a well known method for converting
arbitraryprecision arrangements of segments into a fixedprecision
representation. In the study of robust geometric computing, it can be
classified as a finite precision approximation technique. Iterated
Snap Rounding is a modification of Snap Rounding in which each vertex
is at least halfthewidthofapixel away from any nonincident
edge. This package supports both methods.

Introduced in: Cgal 3.1 Depends on: Arrangements License: QPL Citation Entry Demo: 2D Snap Rounding User Manual Reference Manual 

2D EnvelopesRon Wein  
This package consits of functions that computes the lower (or upper)
envelope of a set of arbitrary curves in 2D. The output is
represented as an envelope diagram, namely a subdivision of the
xaxis into intervals, such that the identity of the curves that
induce the envelope on each interval is unique.

Introduced in: Cgal 3.3 Depends on: 2D Arrangements License: QPL Citation Entry User Manual Reference Manual 

3D EnvelopesMichal Meyerovitch, Ron Wein and Baruch Zukerman  
This package consits of functions that compute the lower (or upper)
envelope of a set of arbitrary surfaces in 3D. The output is
represented as an 2D envelope diagram, namely a planar subdivision
such that the identity of the surfaces that induce the envelope over
each diagram cell is unique.

Introduced in: Cgal 3.3 Depends on: 2D Arrangements License: QPL Citation Entry Demo: 3D Envelopes User Manual Reference Manual 

 
2D TriangulationMariette Yvinec  
This package allows to build and handle
various triangulations for point sets two dimensions.
Any CGAL triangulation covers the convex hull of its
vertices. Triangulations are build incrementally
and can be modified by insertion or removal of vertices.
They offer point location facilities.
The package provides plain triangulation (whose faces depend on the insertion order of the vertices) and Delaunay triangulations. Regular triangulations are also provided for sets of weighted points. Delaunay and regular triangulations offer nearest neighbor queries and primitives to build the dual Voronoi and power diagrams. Finally, constrained and Delaunay constrained triangulations allows to force some constrained segments to appear as edges of the triangulation. Several versions of constrained and Delaunay constrained triangulations are provided: some of them handle intersections between input constraints segment while others do not.

Introduced in: Cgal 0.9 Depends on: 2D Triangulation Data Structure License: QPL Citation Entry Demo: Delaunay Triangulation Demo: Regular Triangulation Demo: Constrained Delaunay Triangulation User Manual Reference Manual 

2D Triangulation Data StructureSylvain Pion and Mariette Yvinec  
This package provides a data structure to store a twodimensional
triangulation that has the topology of a twodimensional sphere.
The package
acts as a container for the vertices and faces of the triangulation
and provides basic combinatorial operation on the triangulation.

Introduced in: Cgal 2.2 License: QPL Citation Entry User Manual Reference Manual 

3D TriangulationsSylvain Pion and Monique Teillaud  
This package allows to build and handle
triangulations for point sets in three dimensions.
Any Cgal triangulation covers the convex hull of its
vertices. Triangulations are build incrementally
and can be modified by insertion or removal of vertices.
They offer point location facilities.
The package provides plain triangulation (whose faces depends on the insertion order of the vertices) and Delaunay triangulations. Regular triangulations are also provided for sets of weighted points. Delaunay and regular triangulations offer nearest neighbor queries and primitives to build the dual Voronoi and power diagrams.

Introduced in: Cgal 2.1 License: QPL Citation Entry User Manual Reference Manual 

3D Triangulation Data StructureSylvain Pion and Monique Teillaud  
This package provides a data structure to store a threedimensional
triangulation that has the topology of a threedimensional sphere.
The package acts as a container for the vertices
and cells of the triangulation
and provides basic combinatorial operations on the triangulation.

Introduced in: Cgal 2.1 License: QPL Citation Entry User Manual Reference Manual 

3D Periodic TriangulationsManuel Caroli and Monique Teillaud  
This package allows to build and handle triangulations of point sets
in the three 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.

Introduced in: Cgal 3.5 Depends on: 3D Triangulation and 3D Triangulation Data Structure License: QPL Citation Entry Demo: Periodic Delaunay Triangulation User Manual Reference Manual 

2D Alpha ShapesTran Kai Frank Da  
This package offers a data structure encoding the whole family of alphacomplexes
related to a given 2D Delaunay or regular triangulation. In particular, the data structure
allows to retrieve the alphacomplex for any alpha value, the whole spectrum of critical
alpha values and a filtration on the triangulation faces (this filtration is based on the first
alpha value for which each face is included on the alphacomplex).

Introduced in: Cgal 2.1 Depends on: 2D Triangulation License: QPL Citation Entry Demo: 2D Alpha Shapes User Manual Reference Manual 

3D Alpha ShapesTran Kai Frank Da and Mariette Yvinec  
This package offers a data structure encoding the whole family of alphacomplexes
related to a given 3D Delaunay or regular triangulation. In particular, the data structure
allows to retrieve the alphacomplex for any alpha value, the whole spectrum of critical
alpha values and a filtration on the triangulation faces (this filtration is based on the first
alpha value for which each face is included on the alphacomplex).

Introduced in: Cgal 2.3 Depends on: 2D Triangulation License: QPL Citation Entry Demo: 3D Alpha Shapes User Manual Reference Manual 

 
2D Segment Delaunay GraphsMenelaos Karavelas  
An algorithm for computing the dual of a Voronoi diagram of a set
of segments under the Euclidean metric. It is a generalization of the
standard Voronoi diagram for points. The algorithms provided are
dynamic.

Introduced in: Cgal 3.1 Depends on: 2D Triangulation Data Structure License: QPL Citation Entry Demo: 2D Segment Voronoi Diagram User Manual Reference Manual 

2D Apollonius Graphs (Delaunay Graphs of Disks)Menelaos Karavelas and Mariette Yvinec  
Algorithms for computing the Apollonius
graph in two dimensions. The Apollonius graph is the dual of the
Apollonius diagram, also known as the additively weighted Voronoi
diagram. The latter can be thought of as the Voronoi diagram of a set
of disks under the Euclidean metric, and it is a generalization of the
standard Voronoi diagram for points. The algorithms provided are
dynamic.

Introduced in: Cgal 3.0 Depends on: 2D Triangulation Data Structure License: QPL Citation Entry Demo: 2D Apollonius Graph User Manual Reference Manual 

2D Voronoi Diagram AdaptorMenelaos Karavelas  
The 2D Voronoi diagram adaptor package provides an adaptor that adapts a
2dimensional 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.

Introduced in: Cgal 3.2 License: QPL Citation Entry User Manual Reference Manual 

 
2D Conforming Triangulations and MeshesLaurent Rineau  
This package implements a Delaunay refinement algorithm to construct
conforming triangulations and 2D meshes.
Conforming Delaunay triangulations are obtained from constrained Delaunay triangulations by refining constrained edges until they are Delaunay edges. Conforming Gabriel triangulations are obtained by further refining constrained edges until they become Gabriel edges. The package provides also a 2D mesh generator that refines triangles and constrained edges until user defined size and shape criteria on triangles are satisfied. The package can handle intersecting input constraints and set no restriction on the angle formed by two constraints sharing an endpoint.

Introduced in: Cgal 3.1 Depends on: 2D Delaunay Triangulation License: QPL Citation Entry Demo: 2D Mesh Generator User Manual Reference Manual 

3D Surface Mesh GenerationLaurent Rineau and Mariette Yvinec  
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 mesh generator 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 threedimensional image.

Introduced in: Cgal 3.2 License: QPL Citation Entry Demo: Surface Mesh Generator User Manual Reference Manual 

Surface Reconstruction from Point SetsPierre Alliez, Laurent Saboret, Gael Guennebaud  
This Cgal package implements a surface reconstruction method: Poisson Surface Reconstruction. It takes as input a set of points with oriented normals and computes an implicit function. The Cgal surface mesh generator can then be used to extract an isosurface from this function.

Introduced in: Cgal 3.5 Depends on: Taucs License: QPL Citation Entry Demo: Point Set Processing User Manual Reference Manual 

3D Skin Surface MeshingNico Kruithof  
This package allows to build a triangular mesh of a skin surface.
Skin surfaces are used for modeling large molecules in biological
computing. The surface is defined by a set of balls, representing
the atoms of the molecule, and a shrink factor that determines the
size of the smooth patches gluing the balls together.
The construction of a triangular mesh of a smooth skin surface is often necessary for further analysis and for fast visualization. This package provides functions to construct a triangular mesh approximating the skin surface from a set of balls and a shrink factor. It also contains code to subdivide the mesh efficiently.

Introduced in: Cgal 3.3 Depends on: 3D Triangulation and 3D Polyhedral Surface License: QPL Citation Entry User Manual Reference Manual 

3D Mesh GenerationLaurent Rineau, Stéphane Tayeb, Mariette Yvinec  
The generated meshes are 3 dimensional
isotropic simplicial meshes. The discretized region
may be a monodomain, i.e. a single connected component,
or a multidomain subdivided
into different subdomains.
The domain is input as an oracle able to answer
queries, of a few different types, on the domain.
In the current version,
the mesh generator is able to discretize
domains described
through implicit functions, 3D images or polyhedral boundaries.
The output is a 3D mesh of the domain volume
and conformal surface meshes for all the boundary and subdividing
surfaces.

Introduced in: Cgal 3.5 Depends on: 3D Triangulations, 2D Meshes, 3D Surface Mesh Generation License: QPL Citation Entry User Manual Reference Manual 

 
3D Surface Subdivision MethodsLeJeng Andy Shiue  
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 CatmullClark, Loop, DooSabin 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.

Introduced in: Cgal 3.2 License: LGPL Citation Entry Demo: Operations on Polyhedra User Manual Reference Manual 

Triangulated Surface Mesh SimplificationFernando Cacciola  
This package provides an algorithm to simplify a triangulated surface mesh
by edge collapsing. It is an implementation of the Turk/Lindstrom memoryless
mesh simplification algorithm.

Introduced in: Cgal 3.3 Depends on: Polyhedron License: QPL Citation Entry Demo: Operations on Polyhedra User Manual Reference Manual 

Planar Parameterization of Triangulated Surface MeshesLaurent Saboret, Pierre Alliez and Bruno Lévy  
Parameterizing a surface amounts to finding a onetoone 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 stateoftheart surface mesh parameterization methods,
such as least squares conformal maps, discrete conformal map, discrete
authalic parameterization, Floater mean value coordinates or Tutte
barycentric mapping.

Introduced in: Cgal 3.2 Depends on: Solvers as OpenNL or Taucs. License: QPL Citation Entry Demo: Operations on Polyhedra User Manual Reference Manual 

2D Placement of StreamlinesAbdelkrim Mebarki  
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 address different queries, and relies on choosing the
centers of the biggest empty circles to start the integration of the
streamlines.

Introduced in: Cgal 3.2 Depends on: 2D Delaunay triangulation License: QPL Citation Entry Demo: 2D Stream Lines User Manual Reference Manual 

Approximation of Ridges and Umbilics on Triangulated Surface MeshesMarc Pouget and Frédéric Cazals  
Global features related to curvature extrema encode
important informations used in segmentation, registration,
matching and surface analysis. Given pointwise estimations of
local differential quantities, this package allows the
approximation of differential features on a triangulated surface
mesh. Such curvature related features are curves: ridges or
crests, and points: umbilics.

Introduced in: Cgal 3.3 Depends on: Solvers as Lapack and Blas. License: QPL Citation Entry User Manual Reference Manual 

Estimation of Local Differential PropertiesMarc Pouget and Frédéric Cazals  
For a surface discretized as a point cloud or a mesh, it
is desirable to estimate pointwise differential quantities. More
precisely, first order properties correspond to the normal or the
tangent plane; second order properties provide the principal
curvatures and directions, third order properties provide the
directional derivatives of the principal curvatures along the
curvature lines, etc. This package allows the estimation of local
differential quantities of a surface from a point sample.

Introduced in: Cgal 3.3 Depends on: Solvers as Lapack and Blas. License: QPL Citation Entry Demo: Operations on Polyhedra User Manual Reference Manual 

Point Set ProcessingPierre Alliez, Laurent Saboret, Nader Salman  
This Cgal component implements methods to analyze and process unorganized point sets.
The input is an unorganized point set, possibly with normal attributes (unoriented or oriented).
The point set can be analyzed to measure its average spacing, and processed through functions devoted
to the simplification, outlier removal, smoothing, normal estimation and normal orientation.

Introduced in: Cgal 3.5 Depends on: Lapack License: QPL Citation Entry Demo: Point Set Processing User Manual Reference Manual 

 
2D Range and Neighbor SearchMatthias Bäsken  
This package supports circular, triangular, and isorectangular range search
queries as well as (k) nearest neighbor search queries on 2D point sets.
In contrast to the spatial searching package, this package uses a
Delaunay triangulation as underlying data structure.

Introduced in: Cgal 2.1 Depends on: 2D Delaunay triangulation License: QPL Citation Entry User Manual Reference Manual 

Interval Skip ListAndreas Fabri  
An interval skip list is a data structure for finding all
intervals that contain a point, and for stabbing queries, that is for
answering the question whether a given point is contained in an
interval or not. For a triangulated terrain, this allows to quickly
identify the triangles which intersect an iso line.

Introduced in: Cgal 3.0 License: QPL Citation Entry User Manual Reference Manual 

dD Spatial SearchingHans Tangelder and Andreas Fabri  
This package implements exact and approximate distance browsing by providing exact and approximate algorithms for range searching, knearest and kfurthest neighbor searching, as well as incremental nearest and incremental furthest neighbor searching, where the query items are points in dD Euclidean space.

Introduced in: Cgal 3.0 License: QPL Citation Entry Demo: 2D Spatial Searching User Manual Reference Manual 

dD Range and Segment TreesGabriele Neyer  
Range and segment trees allow to perform window queries on point
sets, and to enumerate all ranges enclosing a query point. The provided data structures
are static and they are optimized for fast queries.

Introduced in: Cgal 0.9 License: QPL Citation Entry User Manual Reference Manual 

Intersecting Sequences of dD Isooriented BoxesLutz Kettner, Andreas Meyer, and Afra Zomorodian  
An efficient algorithm for finding all intersecting pairs for large
numbers of isooriented boxes, in order to apply a user defined callback
on them. Typically these boxes will be bounding
boxes of more complicated geometries. The algorithm is useful for (self) intersection
tests of surfaces etc.

Introduced in: Cgal 3.1 License: QPL Citation Entry Demo: Operations on Polyhedra User Manual Reference Manual 

AABB TreePierre Alliez, Stéphane Tayeb, Camille Wormser  
The AABB (axisaligned bounding box) tree component offers a static data structure and algorithms to perform efficient intersection and distance queries on sets of finite 3D geometric objects.

Introduced in: Cgal 3.5 License: QPL Citation Entry Demo: AABB Tree User Manual Reference Manual 

Spatial SortingChristophe Delage  
This package provides functions
for sorting geometric objects in two and three dimensions, in order to improve
efficiency of incremental geometric algorithms.

Introduced in: Cgal 3.3 License: LGPL Citation Entry User Manual Reference Manual 

 
Bounding VolumesKaspar Fischer, Bernd Gärtner, Thomas Herrmann, Michael Hoffmann, and Sven Schönherr  
This package
provides algorithms for computing optimal bounding volumes of
point sets. In ddimensional space, the smallest enclosing sphere,
ellipsoid (approximate), and annulus can be computed. In
3dimensional space, the smallest enclosing strip is available as
well, and in 2dimensional space, there are algorithms for a number
of additional volumes (rectangles, parallelograms, k=2,3,4
axisaligned rectangles). The smallest enclosing
sphere algorithm can also be applied to a set of
ddimensional spheres.

Introduced in: Cgal 1.1 License: QPL Citation Entry Demo: Smallest Enclosing Circle Demo: Smallest Enclosing Ellipse Demo: Smallest Enclosing Quadrilateral Demo: 2D Rectangular pcenter User Manual Reference Manual 

Inscribed AreasMichael Hoffmann and Eli Packer  
This package provides algorithms for computing inscribed areas.
The algorithms for computing inscribed areas are: the largest inscribed
kgon (area or perimeter) of a convex point set and the largest inscribed
isorectangle.

Introduced in: Cgal 1.1 License: QPL Citation Entry Demo: 2D Inscribed kgon Demo: 2D Largest Empty Rectangle User Manual Reference Manual 

Optimal DistancesKaspar Fischer, Bernd Gärtner, Thomas Herrmann, Michael Hoffmann, and Sven Schönherr  
This package provides algorithms for computing the distance between the
convex hulls of two point sets in ddimensional space, without
explicitely constructing the convex hulls. It further provides
an algorithm to compute the width of a point set, and the furthest
point for each vertex of a convex polygon.

Introduced in: Cgal 1.1 License: QPL Citation Entry User Manual Reference Manual 

Principal Component AnalysisPierre Alliez, Sylvain Pion and Ankit Gupta  
This package provides functions to compute global information about the shape of a set of 2D or 3D objects. It provides the computation of axisaligned bounding boxes for point sets, and barycenters of weighted point sets. In addition, it provides computation of centroids (center of mass) and linear least squares fitting for point sets as well as for sets of other bounded objects. More specifically, it is possible to fit 2D lines to 2D segments, circles, disks, iso rectangles and triangles, as well as to fit 3D lines or 3D planes to 3D segments, triangles, iso cuboids, tetrahedra, spheres and balls. The common interface to these functions takes an iterator range of objects.

Introduced in: Cgal 3.2 License: QPL Citation Entry Demo: Operations on Polygons Demo: Operations on Polyhedra User Manual Reference Manual 

 
2D and Surface Function InterpolationJulia Flötotto  
This package implements different methods for scattered data
interpolation: Given measures of a function on a set of discrete data
points, the task is to interpolate this function on an arbitrary query
point. The package further offers functions for natural neighbor
interpolation.

Introduced in: Cgal 3.1 License: QPL Citation Entry User Manual Reference Manual 

 
Kinetic Data StructuresDaniel Russel  
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.

Introduced in: Cgal 3.2 Depends on: KDS Framework. Two dimensional visualization depends on Qt, three dimensional visualization depends on Coin. License: LGPL Citation Entry User Manual Reference Manual 

Kinetic FrameworkDaniel Russel  
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.

Introduced in: Cgal 3.2 Depends on: Two dimensional visualization depends on Qt, three dimensional visualization depends on Coin. License: LGPL Citation Entry User Manual Reference Manual 

 
STL Extensions for CGALMichael Hoffmann, Lutz Kettner, Sylvain Pion, and Ron Wein  
Cgal is designed in the spirit of the generic programming paradigm
to work together with the Standard Template Library (STL). This package provides
nongeometric STLlike algorithms and datastructures that are not provided in
the STL standard but in Cgal

Introduced in: Cgal 1.0 License: LGPL Citation Entry User Manual Reference Manual 

CGAL and the Boost Graph LibraryAndreas Fabri, Fernando Cacciola, and Ron Wein  
This package provides a framework for interfacing Cgal data structures with the algorithms of the BGL. It allows to run
graph algorithms directly on Cgal data structures which are
model of the BGL graph concepts, for example the shortest path
algorithm on a Delaunay triangulation in order to compute the Euclidean
minimum spanning tree.
Furthermore, it introduces a
new graph concept, the HalfedgeEdgeGraph. This concept describes
graphs which are embedded on surfaces.

Introduced in: Cgal 3.3 License: LGPL Citation Entry User Manual Reference Manual 

CGAL and Boost Property MapsAndreas Fabri and Laurent Saboret  
This package provides a framework for interfacing Cgal data structures with algorithms expecting Boost Property Maps.

Introduced in: Cgal 3.5 License: QPL Citation Entry User Manual Reference Manual 

Handles and CirculatorsOlivier Devillers, Lutz Kettner, Michael Seel, and Mariette Yvinec  
This package descibes handles and circulators. They are related to
iterators. Handles allow to dereference but neither to increment nor to decrement.
Circulators have no notion of pasttheend, and they are used in Cgal whenever
we have cyclic stuctures.

Introduced in: Cgal 1.0 License: LGPL Citation Entry User Manual Reference Manual 

Geometric Object GeneratorsSusan Hert, Michael Hoffmann, Lutz Kettner, and Sven Schönherr  
This package provides a variety of generators for geometric objects.
They are useful as synthetic test data sets, e.g. for testing
algorithms on degenerate object sets and for performance analysis.

Introduced in: Cgal 1.0 License: LGPL Citation Entry User Manual Reference Manual 

Profiling tools, Hash Map, Unionfind, ModifiersLutz Kettner, Sylvain Pion, and Michael Seel  
This package provides classes for profiling time and memory consumption,
a hash map, a union find data structure and a modifier.

Introduced in: Cgal 3.2 License: LGPL Citation Entry User Manual Reference Manual 

IO StreamsAndreas Fabri, GeertJan Giezeman, and Lutz Kettner  
All classes in the Cgal kernel provide input and output operators for
IO streams.
The basic task of such an operator is to produce a
representation of an object that can be written as a sequence of
characters on devices as a console, a file, or a pipe. In Cgal we distinguish between a raw ascii, a raw binary and a
pretty printing format.

Introduced in: Cgal 1.0 License: LGPL Citation Entry User Manual Reference Manual 

 
GeomviewAndreas Fabri and Sylvain Pion  
This package implements an interface to Geomview, an interactive 3D viewing program, originally developed at the Geometry Center in Minneapolis.

Introduced in: Cgal 2.0 License: LGPL Citation Entry User Manual Reference Manual 

CGAL and the Qt Graphics View FrameworkAndreas Fabri and Laurent Rineau  
This package provides classes for displaying Cgal objects
and data structures in the Qt 4 Graphics View Framework.

Introduced in: Cgal 3.4 Depends on: Qt 4 License: QPL Citation Entry User Manual Reference Manual 

CGAL IpeletsSébastien Loriot and Sylvain Pion  
This package provides
a generic framework to easily write ipelets (plugin's) using Cgal for the
the Ipe extensible drawing editor.

Introduced in: Cgal 3.5 License: LGPL Citation Entry User Manual Reference Manual 