Package Overview

Kernels

2D and 3D Linear Kernel

Hervé Brönnimann, Andreas Fabri, Geert-Jan 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
BibTeX Key:cgal:bfghhkps-k23-06
User Manual   Reference Manual

dD Kernel

Michael 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
User Manual   Reference Manual

2D Circular Kernel

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
BibTeX Key:cgal:pt-cc2-06
User Manual   Reference Manual

Convex Hull Algorithms

2D Convex Hulls and Extreme Points

Susan 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
BibTeX Key:cgal:hs-chep2-06
User Manual   Reference Manual

3D Convex Hulls

Susan 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 are 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
BibTeX Key:cgal:hs-ch3-06
User Manual   Reference Manual

dD Convex Hulls and Delaunay Triangulations

Susan Hert and Michael Seel

This package provides functions for computing convex hulls and Delaunay triagulations in d-dimensional Euclidean space.

Introduced in: CGAL 2.3
BibTeX Key:cgal:hs-chdt3-06
User Manual   Reference Manual

Polygons and Polyhedra

2D Polygon

This package provides a polygon class and operations on sequences of points, like the simplicity test.

Introduced in: CGAL 0.9
BibTeX Key:cgal:gw-p2-06
User Manual   Reference Manual

2D Polygon Partitioning

Susan 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
BibTeX Key:cgal:h-pp2-06
User Manual   Reference Manual

3D Polyhedral Surface

Lutz 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 2-manifolds - with and without boundary. If the surface is closed we call it a polyhedron.

Introduced in: CGAL 1.0
Depends on: Halfedge Data Structure
BibTeX Key:cgal:k-ps-06
User Manual   Reference Manual

Halfedge Data Structures

Lutz Kettner

A halfedge data structure is an edge-centered data structure capable of maintaining incidence informations of vertices, edges and faces, for example for planar maps, polyhedra, or other orientable, two-dimensional 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 informations, for example the halfedge pointers in faces or the storage of faces at all.

Introduced in: CGAL 1.0
BibTeX Key:cgal:k-hds-06
User Manual   Reference Manual

Polygon and Polyhedron Operations

2D Regularized Boolean Set-Operations

Efi Fogel, Ron Wein, Baruch Zukerman, and Dan Halperin

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.

Introduced in: CGAL 3.2
Depends on: 2D Arrangements
BibTeX Key:cgal:fwzh-rbso2-06
User Manual   Reference Manual

2D Boolean Operations on Nef Polygons

Michael 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
BibTeX Key:cgal:s-bonp2-06
User Manual   Reference Manual

2D Boolean Operations on Nef Polygons Embedded on the Sphere

Peter 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
BibTeX Key:cgal:s-bonpes2-06
User Manual   Reference Manual

3D Boolean Operations on Nef Polyhedra

Peter Hachenberger, Lutz Kettner, and Michael Seel

3D Nef polyhedra, are a boundary representation for cell-complexes 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 non-manifold geometry.

Introduced in: CGAL 3.1
Depends on: 2D Nef Polygons, Nef Polygons on the Sphere
BibTeX Key:cgal:s-bonp3-06
User Manual   Reference Manual

2D Straight Skeleton and Polygon Offsetting

Fernando 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
BibTeX Key:cgal:c-sspo2-06
User Manual   Reference Manual

Arrangements

2D Arrangement

Ron 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 line-sweeping 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 sweep-line 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
BibTeX Key:cgal:wfzh-a2-06
User Manual   Reference Manual

2D Intersection of Curves

Baruch Zukerman and Ron Wein

This package provides three free functions implemented based on the sweep-line paradigm: given a collection of input curves, compute all intersection points, compute the set of subcurves that are pairwise interior-disjoint 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
BibTeX Key:cgal:wfz-ic2-06
User Manual   Reference Manual

2D Snap Rounding

Eli Packer

Snap Rounding is a well known method for converting arbitrary-precision arrangements of segments into a fixed-precision 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 half-the-width-of-a-pixel away from any non-incident edge. This package supports both methods.

Introduced in: CGAL 3.1
Depends on: Arrangements
BibTeX Key:cgal:p-sr2-06
User Manual   Reference Manual

Triangulations and Delaunay Triangulations

2D Triangulation

Mariette 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 contrained triangulations allows to force some constrained segments to appear as edges of the triangulation. Several versions of constrained and Delaunay contrained 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
BibTeX Key:cgal:y-t2-06
User Manual   Reference Manual

2D Triangulation Data Structure

Sylvain Pion and Mariette Yvinec

This package provides a data structure to store a two-dimensional triangulation that has the topology of a two-dimensional 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
BibTeX Key:cgal:py-tds2-06
User Manual   Reference Manual

3D Triangulations

Sylvain 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
BibTeX Key:cgal:pt-t3-06
User Manual   Reference Manual

3D Triangulation Data Structure

Sylvain Pion and Monique Teillaud

This package provides a data structure to store a three-dimensional triangulation that has the topology of a three-dimensional 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
BibTeX Key:cgal:pt-tds3-06
User Manual   Reference Manual

2D Alpha Shapes

Tran Kai Frank Da

This package offers a data structure encoding the whole family of alpha-complexes related to a given 2D Delaunay or regular triangulation. In particular, the data structure allows to retrieve the alpha-complex 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 alpha-complex).

Introduced in: CGAL 2.1
Depends on: 2D Triangulation
BibTeX Key:cgal:d-as2-06
User Manual   Reference Manual

3D Alpha Shapes

Tran Kai Frank Da and Mariette Yvinec

This package offers a data structure encoding the whole family of alpha-complexes related to a given 3D Delaunay or regular triangulation. In particular, the data structure allows to retrieve the alpha-complex 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 alpha-complex).

Introduced in: CGAL 2.3
Depends on: 2D Triangulation
BibTeX Key:cgal:d-as3-06
User Manual   Reference Manual

Voronoi Diagrams

2D Segment Delaunay Graph

Menelaos 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
BibTeX Key:cgal:k-sdg2-06
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
BibTeX Key:cgal:k-ag2-06
User Manual   Reference Manual

Menelaos Karavelas

The 2D Voronoi diagram adaptor package provides an adaptor that adapts a 2-dimensional triangulated Delaunay graph to the corresponding a 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
BibTeX Key:cgal:k-vda2-06
User Manual   Reference Manual

Meshing

2D Conforming Triangulations and Meshes

Laurent 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 mesher 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
User Manual   Reference Manual

3D Surface Mesher

Laurent 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 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.

Introduced in: CGAL 3.2
BibTeX Key:cgal:ry-sm2-06
User Manual   Reference Manual

3D Surface Subdivision Methods

Le-Jeng 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 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.

Introduced in: CGAL 3.2
BibTeX Key:cgal:s-ssm2-06
User Manual   Reference Manual

Planar Parameterization of Triangulated Surface Meshes

Laurent Saboret, Pierre Alliez and Bruno Lévy

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.

Introduced in: CGAL 3.2
Depends on: Solvers as OpenNL or Taucs.
BibTeX Key:cgal:sal-pptsm2-06
User Manual   Reference Manual

Search Structures

2D Search Structures

Matthias Bäsken

This package supports circular, triangular, and isorectangular range search queries as well as (k) nearest neighbor search queries on 2D point sets.

Introduced in: CGAL 2.1
Depends on: 2D Delaunay triangulation
BibTeX Key:cgal:b-ss2-06
User Manual   Reference Manual

Interval Skip List

Andreas Fabri

An interval skip list is a data strucure 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.

Introduced in: CGAL 3.0
BibTeX Key:cgal:f-isl-06
User Manual   Reference Manual

dD Spatial Searching

Hans Tangelder and Andreas Fabri

This package implements exact and approximate distance browsing by providing exact and approximate algorithms for range searching, k-nearest and k-furthest 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
BibTeX Key:cgal:tf-ssd-06
User Manual   Reference Manual

dD Range and Segment Trees

Gabriele 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
BibTeX Key:cgal:n-rstd-06
User Manual   Reference Manual

Intersecting Sequences of dD Iso-oriented Boxes

Lutz Kettner, Andreas Meyer, and Afra Zomorodian

An efficient algorithm for finding all intersecting pairs for large numbers of iso-oriented 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
BibTeX Key:cgal:kmz-isiobd-06
User Manual   Reference Manual

Geometric Optimization

Geometric Optimisation

Kaspar Fischer, Bernd Gärtner, Thomas Herrmann, Michael Hoffmann, Eli Packer, and Sven Schönherr

This package provides algorithms for computing bounding volumes, inscribed areas and polytope distances.

The algorithms for bounding volumes for point sets in d-dimensional space are: the smallest enclosing sphere, annulus, ellipsoid, or strip. For 2-dimensional space, a number of additional volumes (rectangles, parallelograms, k=2,3,4 axis-aligned rectangles) are available. The smallest enclosing sphere algorithm can also be applied on a set of d-dimensional spheres.

The algorithms for computing inscribed areas are: the largest inscribed k-gon (area or perimeter) of a convex point set and the largest inscribed rectangle.

The polytope distance algorithm computes the distance between the convex hulls of two point sets in d-dimensional space, without explicitely constructing the convex hulls.

Finally this package offers a matrix search framework, which is the underlying machinery of some of the algorithms of this package.

Introduced in: CGAL 1.1
BibTeX Key:cgal:fghhps-go-06
User Manual   Reference Manual

Principal Component Analysis

Pierre Alliez and Sylvain Pion

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.

Introduced in: CGAL 3.2
User Manual   Reference Manual

Interpolation

2D and Surface Function Interpolation

Julia 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
BibTeX Key:cgal:f-i-06
User Manual   Reference Manual

2D Placement of Streamlines

Abdelkrim Mebarki

Visualizing vector fields is important for many application domains. A good way to do it is to generate streamlines that describe the flow behaviour. 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.

Introduced in: CGAL 3.2
Depends on: 2D Delaunay triangulation
BibTeX Key:cgal:m-ps-06
User Manual   Reference Manual

Kinetic Data Structures

Kinetic Data Structures

Daniel 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.