CGAL 6.2 - Manual

Loading...
Searching...
No Matches
Package Overview

# Arithmetic and Algebra

## Algebraic Foundations

Michael 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).
User Manual Reference Manual
Introduced in: CGAL 3.3
BibTeX: cgal:h-af-26a
License: LGPL

## Number Types

Michael 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.
User Manual Reference Manual
Introduced in: CGAL 1.0
BibTeX: cgal:hhkps-nt-26a
License: LGPL

## Modular Arithmetic

Michael Hemmer and Sylvain Pion
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.
User Manual Reference Manual
Introduced in: CGAL 3.4
BibTeX: cgal:h-ma-26a
License: LGPL

## Polynomial

Michael Hemmer
This package introduces a concept for univariate and 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 this concept.
User Manual Reference Manual
Introduced in: CGAL 3.3
BibTeX: cgal:h-p-26a
License: LGPL

## Algebraic Kernel

Eric Berberich, Michael Hemmer, Michael Kerber, 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 black-box implementation algorithms to determine, compare and approximate real roots of univariate polynomials and bivariate polynomial systems. Such a black-box 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.
User Manual Reference Manual
Introduced in: CGAL 3.6
BibTeX: cgal:bht-ak-26a
License: LGPL

# Combinatorial Algorithms

## Monotone and Sorted Matrix Search

Michael 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 k-gons inscribed into a planar point set, and computing rectangular p-centers.
User Manual Reference Manual
Introduced in: CGAL 1.1
BibTeX: cgal:h-msms-26a
License: GPL

## Linear and Quadratic Programming Solver

Kaspar 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.
User Manual Reference Manual
Introduced in: CGAL 3.3
BibTeX: cgal:fgsw-lqps-26a
License: GPL

# Geometry Kernels

## 2D and 3D Linear Geometry 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.
User Manual Reference Manual
Introduced in: CGAL 0.9
BibTeX: cgal:bfghhkps-lgk23-26a
License: LGPL

## dD Geometry 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.
User Manual Reference Manual
Introduced in: CGAL 1.1
BibTeX: cgal:s-gkd-26a
License: LGPL

## 2D Circular Geometry Kernel

Pedro 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.
User Manual Reference Manual
Introduced in: CGAL 3.2
BibTeX: cgal:cpt-cgk2-26a
License: GPL
Windows Demo: Arrangement of Circular Arcs

## 3D Spherical Geometry Kernel

Pedro 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.
User Manual Reference Manual
Introduced in: CGAL 3.4
BibTeX: cgal:cclt-sgk3-26a
License: GPL

# 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.
User Manual Reference Manual
Introduced in: CGAL 1.0
BibTeX: cgal:hs-chep2-26a
License: GPL
Windows Demo: See Bounding Volumes

## 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 or not, and checking if two convex hulls intersect or not. One can compute the convex hull of a set of points in three dimensions in three ways: using a static algorithm, using a triangulation to get a fully dynamic computation, or using the specific data structure `Convex_hull_hierarchy_3` for optimal intersection testing.
User Manual Reference Manual
Introduced in: CGAL 1.1
Depends on: The dynamic algorithms depend on 3D Triangulations.
BibTeX: cgal:hs-ch3-26a
License: GPL
Windows Demo: CGAL Lab

## dD Convex Hulls and Delaunay Triangulations

Susan Hert and Michael Seel
This package provides functions for computing convex hulls and Delaunay triangulations in \( d\)-dimensional Euclidean space.
User Manual Reference Manual
Introduced in: CGAL 2.3
BibTeX: cgal:hs-chdt3-26a
License: GPL

# Polygons

## 2D Polygons

Geert-Jan 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.
User Manual Reference Manual
Introduced in: CGAL 0.9
BibTeX: cgal:gw-p2-26a
License: LGPL
Windows Demo: Operations on Polygons

## 2D Polygon Repair

Ken Arroyo Ohori
This package provides algorithms to repair 2D polygons, polygons with holes, and multipolygons with holes, by selecting faces of the arrangement of the input based on a selection rule. The even-odd rule and the non-zero rule are provided for dealing with self intersections. The union and the intersection rule enable to combine similar polygons.
User Manual Reference Manual
Introduced in: CGAL 6.0
Depends on: 2D Polygons, 2D Triangulations
BibTeX: cgal:a-pr-26a
License: GPL

## 2D Regularized Boolean Set-Operations

Efi Fogel, Ophir Setter, Ron Wein, Guy Zucker, 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.
User Manual Reference Manual
Introduced in: CGAL 3.2
Depends on: 2D Arrangements
BibTeX: cgal:fwzh-rbso2-26a
License: GPL

## 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.
User Manual Reference Manual
Introduced in: CGAL 2.3
BibTeX: cgal:s-bonp2-26a
License: GPL

## 2D Boolean Operations on Nef Polygons Embedded on the Sphere

Peter Hachenberger and Lutz Kettner
This package offers the equivalent to 2D Nef Polygons in the plane. Here halfplanes correspond to half spheres delimited by great circles.
User Manual Reference Manual
Introduced in: CGAL 3.1
Depends on: 2D Boolean Operations on Nef Polygons
BibTeX: cgal:hk-bonpes2-26a
License: GPL

## 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.
User Manual Reference Manual
Introduced in: CGAL 2.3
BibTeX: cgal:h-pp2-26a
License: GPL

## 2D Straight Skeleton and Polygon Offsetting

Fernando Cacciola, Sébastien Loriot, and Mael Rouxel-Labbé
This package implements an algorithm to construct a halfedge data structure representing the weighted 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.
User Manual Reference Manual
Introduced in: CGAL 3.2
Depends on: Halfedge Data Structures
BibTeX: cgal:c-sspo2-26a
License: GPL

## 2D Minkowski Sums

Ron Wein, Alon Baram, Eyal Flato, Efi Fogel, Michael Hemmer, and Sebastian Morr
This package consists of functions that compute the Minkowski sum of two simple straight-edge 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.
User Manual Reference Manual
Introduced in: CGAL 3.3
Depends on: 2D Arrangements, 2D and 3D Fast Intersection and Distance Computation, 2D Triangulations
BibTeX: cgal:w-rms2-26a
License: GPL

## 2D Polyline Simplification

Andreas Fabri
This package enables to simplify polylines with the guarantee that the topology of the polylines does not change. This can be done for a single polyline as well as for a set of polyline constraints in a constrained triangulation. The simplification can be controlled with cost and stop functions.
User Manual Reference Manual
Introduced in: CGAL 4.6
Depends on: 2D Triangulations
BibTeX: cgal:f-ps2-26a
License: GPL
Windows Demo: Polyline Simplification

## dD Fréchet Distance

André Nusser, Marvin Künnemann, and Karl Bringmann
This package provides functions for computing an approximation of the Fréchet distance of two polylines in any dimension under the Euclidean metric.
User Manual Reference Manual
Introduced in: CGAL 6.1
BibTeX: cgal:nkb-fd-26a
License: GPL

## 2D Visibility Computation

Michael Hemmer, Kan Huang, Francisc Bungiu, and Ning Xu
This package provides several variants to compute the visibility area of a point within polygonal regions in two dimensions.
User Manual Reference Manual
Introduced in: CGAL 4.7
Depends on: 2D Arrangements
Depends on: 2D Triangulations
BibTeX: hhb-visibility-2-26a
License: GPL

## 2D Movable Separability of Sets

Shahar Shamai and Efi Fogel
Movable Separability of Sets [13] is a class of problems that deal with moving sets of objects, such as polygons in the plane; the challenge is to avoid collisions between the objects while considering different kinds of motions and various definitions of separation.
User Manual Reference Manual
Introduced in: CGAL 4.12
Depends on: 2D Polygons
BibTeX: cgal:sf-sms2-26a
License: GPL

# Cell Complexes and Polyhedra

## 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.
User Manual Reference Manual
Introduced in: CGAL 1.0
Depends on: Halfedge Data Structures
BibTeX: cgal:k-ps-26a
License: GPL
Windows Demo: CGAL Lab

## Halfedge Data Structures

Lutz Kettner
A halfedge data structure is an edge-centered data structure capable of maintaining incidence information 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 information, for example the halfedge pointers in faces or the storage of faces at all.
User Manual Reference Manual
Introduced in: CGAL 1.0
BibTeX: cgal:k-hds-26a
License: LGPL

## Surface Mesh

Mario Botsch, Daniel Sieger, Philipp Moeller, and Andreas Fabri
The surface mesh class provided by this package is an implementation of the halfedge data structure allowing to represent polyhedral surfaces. It is an alternative to the packages Halfedge Data Structures and 3D Polyhedral Surface. The main differences are that it is indexed based and not pointer based, and that the mechanism for adding information to vertices, halfedges, edges, and faces is much simpler and can be used at runtime and not at compile time.
User Manual Reference Manual
Introduced in: CGAL 4.6
BibTeX: cgal:bsmf-sm-26a
License: GPL

## Combinatorial Maps

Guillaume Damiand
This package implements Combinatorial Maps in d dimensions. A combinatorial map is a data structure enabling to represent an orientable subdivided object by describing all the cells of the subdivision (for example in 3D vertices, edges, faces, volumes) and all the incidence and adjacency relationships between these cells. Information can be associated to cells thanks to attributes. In 2D, a combinatorial map is equivalent to a halfedge data structure. The package provides basic creation, modification operations, and several iterators enabling to run through some specific part of the object.
User Manual Reference Manual
Introduced in: CGAL 3.9
BibTeX: cgal:d-cm-26a
License: LGPL

## Generalized Maps

Guillaume Damiand
This package implements Generalized Maps in d dimensions. A generalized map is a data structure enabling to represent an orientable or non orientable subdivided object by describing all the cells of the subdivision (for example in 3D vertices, edges, faces, volumes) and all the incidence and adjacency relationships between these cells. Information can be associated to cells thanks to attributes. The package provides basic creation, modification operations, and several iterators enabling to run through some specific part of the object.
User Manual Reference Manual
Introduced in: CGAL 4.9
BibTeX: cgal:d-gm-26a
License: LGPL

## Linear Cell Complex

Guillaume Damiand
This package implements linear cell complexes, objects in d-dimension with linear geometry. The combinatorial part of objects is described either by a combinatorial or a generalized map, representing all the cells of the object plus the incidence and adjacency relations between cells. Geometry is added to the combinatorial data-structure simply by associating a point to each vertex of the map. Taking a 2D combinatorial map, and using 3D points, gives a linear cell complex equivalent to a Polyhedron_3.
User Manual Reference Manual
Introduced in: CGAL 4.0
Depends on: Combinatorial Maps
Depends on: Generalized Maps
BibTeX: cgal:d-lcc-12-26a
License: LGPL
Windows Demo: 3D Linear Cell Complex

## 3D Boolean Operations on Nef Polyhedra

Peter Hachenberger and Lutz Kettner
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.
User Manual Reference Manual
Introduced in: CGAL 3.1
Depends on: 2D Boolean Operations on Nef Polygons, 2D Boolean Operations on Nef Polygons Embedded on the Sphere
BibTeX: cgal:hk-bonp3-26a
License: GPL
Windows Demo: CGAL Lab

## Convex Decomposition of Polyhedra

Peter Hachenberger, Sven Oesau
This packages provides two functions for computing a set of convex volumes that cover a bounded polyhedron. A convex decomposition of Nef Polyhedra into \(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 worst-case optimal. A second method approximates the input mesh with convex volumes. While these convex volumes cover additional space outside of the polyhedron, the computation is fast for any chosen number of convex volumes.
User Manual Reference Manual
Introduced in: CGAL 3.5
BibTeX: cgal:h-emspe-26a
License: GPL
Windows Demo: CGAL Lab

## 3D Minkowski Sum of Polyhedra

Peter Hachenberger
This package provides a function, which computes the Minkowski sum of two point sets in \( \mathbb{R}^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.
User Manual Reference Manual
Introduced in: CGAL 3.5
Depends on: 3D Boolean Operations on Nef Polyhedra, Convex Decomposition of Polyhedra
BibTeX: cgal:h-msp3-26a
License: GPL
Windows Demo: CGAL Lab

# Arrangements

## 2D Arrangements

Ron Wein, Eric Berberich, Efi Fogel, Dan Halperin, Michael Hemmer, Oren Salzman, and Baruch Zukerman
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.
User Manual Reference Manual
Introduced in: CGAL 2.1
BibTeX: cgal:wfzh-a2-26a
License: GPL
Windows Demo: 2D Arrangements

## 2D Intersection of Curves

Baruch Zukerman, Ron Wein, and Efi Fogel
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.
User Manual Reference Manual
Introduced in: CGAL 2.4
Depends on: 2D Arrangements
BibTeX: cgal:wfz-ic2-26a
License: GPL

## 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.
User Manual Reference Manual
Introduced in: CGAL 3.1
Depends on: 2D Arrangements
BibTeX: cgal:p-sr2-26a
License: GPL
Windows Demo: 2D Snap Rounding

## 2D Envelopes

Ron Wein
This package consists 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 \( x\)-axis into intervals, such that the identity of the curves that induce the envelope on each interval is unique.
User Manual Reference Manual
Introduced in: CGAL 3.3
Depends on: 2D Arrangements
BibTeX: cgal:w-e2-26a
License: GPL

## 3D Envelopes

Dan Halperin, Michal Meyerovitch, Ron Wein, and Baruch Zukerman
This package consists 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.
User Manual Reference Manual
Introduced in: CGAL 3.3
Depends on: 2D Arrangements
BibTeX: cgal:mwz-e3-26a
License: GPL

# Triangulations and Delaunay Triangulations

## 2D Triangulations

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 built 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.
User Manual Reference Manual
Introduced in: CGAL 0.9
Depends on: 2D Triangulation Data Structure
BibTeX: cgal:y-t2-26a
License: GPL
Windows Demos: Delaunay Triangulation, Regular Triangulation, Constrained Delaunay Triangulation

## 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.
User Manual Reference Manual
Introduced in: CGAL 2.2
BibTeX: cgal:py-tds2-26a
License: GPL

## 2D Triangulations on the Sphere

Mael Rouxel-Labbé, Monique Teillaud, and Claudia Werner
This package enables the construction and manipulation of Delaunay triangulations on the 2-sphere. Triangulations are built incrementally and can be modified by insertion or removal of vertices. Point location querying and primitives to build the dual Voronoi diagram are provided.
User Manual Reference Manual
Introduced in: CGAL 5.3
Depends on: 2D Triangulation Data Structure
BibTeX: cgal:rtw-tos2-26a
License: GPL
Windows Demo: 2D Triangulations on the sphere

## 2D Periodic Triangulations

Nico Kruithof
This package allows to build and handle triangulations of point sets in the two 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.
User Manual Reference Manual
Introduced in: CGAL 4.3
Depends on: 2D Triangulations
BibTeX: cgal:k-pt2-13-26a
License: GPL
Windows Demo: Periodic Delaunay Triangulation

## 2D Hyperbolic Delaunay Triangulations

Mikhail Bogdanov, Iordan Iordanov, and Monique Teillaud
This package enables building and handling Delaunay triangulations of point sets in the Poincaré disk model of the hyperbolic plane. Triangulations are built incrementally and can be modified by insertion and removal of vertices; point location facilities are also offered, as well as primitives to build the dual Voronoi diagrams.
User Manual Reference Manual
Introduced in: CGAL 4.14
Depends on: 2D Triangulations
BibTeX: cgal:bt-ht2-17-26a
License: GPL
Windows Demo: Hyperbolic Delaunay Triangulation

## 2D Triangulations on Hyperbolic Surfaces

Vincent Despré, Loïc Dubois, Marc Pouget and Monique Teillaud
This package enables building and handling triangulations of closed orientable hyperbolic surfaces. It offers functions for the generation of the triangulation from a convex fundamental domain, the Delaunay flip algorithm and the construction of a portion of the lift of the triangulation in the Poincaré disk. A method is offered that generates such domains in genus two.
User Manual Reference Manual
Introduced in: CGAL 6.1
Depends on: Combinatorial Maps
BibTeX: cgal:ddpt-thss-26a
License: GPL
Windows Demo: 2D Triangulations on Hyperbolic Surfaces

## 2D Periodic Hyperbolic Triangulations

Iordan Iordanov and Monique Teillaud
This package enables building and handling triangulations of point sets on the two dimensional hyperbolic Bolza surface. Triangulations are built incrementally and can be modified by insertion or removal of vertices. Point location facilities are also offered. The package provides Delaunay triangulations and offers primitives to build the dual Voronoi diagrams.
User Manual Reference Manual
Introduced in: CGAL 4.14
Depends on: 2D Hyperbolic Delaunay Triangulations
BibTeX: cgal:i-p4ht2-17-26a
License: GPL
Windows Demo: Periodic Hyperbolic Delaunay Triangulation

## 3D Triangulations

Clément Jamin, 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, displacements 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. Optionally, the main Delaunay and regular triangulation algorithms (insert, remove) support multi-core shared-memory architectures to take advantage of available parallelism.
User Manual Reference Manual
Introduced in: CGAL 2.1
Depends on: 3D Triangulation Data Structure
BibTeX: cgal:pt-t3-26a
License: GPL
Windows Demo: 3D Triangulations

## 3D Triangulation Data Structure

Clément Jamin, 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.
User Manual Reference Manual
Introduced in: CGAL 2.1
BibTeX: cgal:pt-tds3-26a
License: GPL

## 3D Constrained Triangulations

Laurent Rineau and Jane Tournois
This package implements the construction of a 3D Constrained Delaunay triangulation. This triangulation is a generalization of a 3D Delaunay Triangulation which conforms to the set of faces of a 3D piecewise linear complex (PLC), ensuring that these faces are part of the triangulation. As not all PLCs are tetrahedralizable, the algorithm may insert Steiner points to construct the constrained triangulation.
User Manual Reference Manual
Introduced in: CGAL 6.1
Depends on: 3D Triangulations
BibTeX: cgal:rt-cdt3-26a
License: GPL
Windows Demo: CGAL Lab

## 3D Periodic Triangulations

Manuel Caroli, Aymeric Pellé, Mael Rouxel-Labbé, 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 and regular triangulations and offers nearest neighbor queries and primitives to build the dual Voronoi diagrams.
User Manual Reference Manual
Introduced in: CGAL 3.5
Depends on: 3D Triangulation Data Structure
BibTeX: cgal:ct-pt3-26a
License: GPL
Windows Demos: 3D Periodic Delaunay Triangulation, 3D Periodic Lloyd

## dD Triangulations

Olivier Devillers, Samuel Hornus, and Clément Jamin
This package provides classes for manipulating triangulations (pure simplicial complexes) in Euclidean spaces whose dimension can be specified at compile-time or at run-time. Specifically, it provides a data structure to store the triangulations, and two classes to handle triangulations and Delaunay triangulations of point sets. Point location and point insertion are supported. The Delaunay triangulation also supports point removal.
User Manual Reference Manual
Introduced in: CGAL 4.6
BibTeX: cgal:hdj-t-26a
License: GPL

## 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).
User Manual Reference Manual
Introduced in: CGAL 2.1
Depends on: 2D Triangulations
BibTeX: cgal:d-as2-26a
License: GPL
Windows Demo: 2D Alpha Shapes

## 3D Alpha Shapes

Tran Kai Frank Da, Sébastien Loriot, and Mariette Yvinec
This package offers a data structure encoding either one alpha-complex or the whole family of alpha-complexes related to a given 3D Delaunay or regular triangulation. In the latter case, 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).
User Manual Reference Manual
Introduced in: CGAL 2.3
Depends on: 3D Triangulations
BibTeX: cgal:dy-as3-26a
License: GPL
Windows Demo: 3D Alpha Shapes

# Voronoi Diagrams

## 2D Segment Delaunay Graphs

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.
User Manual Reference Manual
Introduced in: CGAL 3.1
Depends on: 2D Triangulation Data Structure
BibTeX: cgal:k-sdg2-26a
License: GNU GPL
Windows Demo: 2D Segment Voronoi Diagram

## L Infinity Segment Delaunay Graphs

Panagiotis Cheilaris, Sandeep Kumar Dey, and Evanthia Papadopoulou
Algorithms and geometric traits for computing the dual of the Voronoi diagram of a set of points and segments under the \(L_{\infty}\) metric.
User Manual Reference Manual
Introduced in: CGAL 4.7
Depends on: 2D Segment Delaunay Graphs
BibTeX: cgal:cdp-sdglinf2-26a
License: GPL

## 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.
User Manual Reference Manual
Introduced in: CGAL 3.0
Depends on: 2D Triangulation Data Structure
BibTeX: cgal:ky-ag2-26a
License: GPL
Windows Demo: 2D Apollonius Graph

## 2D Voronoi Diagram Adaptor

Menelaos Karavelas
The 2D Voronoi diagram adaptor 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.
User Manual Reference Manual
Introduced in: CGAL 3.2
BibTeX: cgal:k-vda2-26a
License: GPL
Windows Demos: 2D Point Voronoi Diagram , 2D Disk Voronoi Diagram, 2D Segment Voronoi Diagram

# Mesh Generation

## 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 mesh generator that refines triangles and constrained edges until user defined size and shape criteria on triangles are satisfied. The generated meshes can be optimized using the Lloyd algorithm, also provided in this package. The package can handle intersecting input constraints and set no restriction on the angle formed by two constraints sharing an endpoint.
User Manual Reference Manual
Introduced in: CGAL 3.1
Depends on: 2D Triangulations
BibTeX: cgal:r-ctm2-26a
License: GPL
Windows Demo: 2D Mesh Generator

## 2D Alpha Wrapping

Pierre Alliez, David Cohen-Steiner, Michael Hemmer, Cédric Portaneri, and Mael Rouxel-Labbé
This component takes a polygon soup, a 2D segment soup, and/or a 2D point set as input, and generates a valid (watertight, intersection-free and 1-manifold) multi-polygon that strictly encloses the input. The algorithm proceeds by shrink-wrapping and refining a 2D Delaunay triangulation starting from a loose bounding box of the input. Two user-defined parameters, alpha and offset, offer control over the maximum size of cavities where the shrink-wrapping process can enter, and the tightness of the final polygon(s) to the input, respectively. Once combined, these parameters provide a means to trade fidelity to the input for complexity of the output.
User Manual Reference Manual
Introduced in: CGAL 6.2
Depends on: 2D Triangulations and 2D Polygon Repair
BibTeX: cgal:achpr-aw2-26a
License: GPL

## 3D Surface Mesh Generation

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 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 three-dimensional image.
User Manual Reference Manual
Introduced in: CGAL 3.2
Depends on: 3D Triangulations
BibTeX: cgal:ry-smg-26a
License: GNU GPL

## 3D Skin Surface Meshing

Nico 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.
User Manual Reference Manual
Introduced in: CGAL 3.3
Depends on: 3D Triangulations and 3D Polyhedral Surface
BibTeX: cgal:k-ssm3-26a
License: GPL

## 3D Simplicial Mesh Data Structure

Pierre Alliez, Clément Jamin, Laurent Rineau, Stéphane Tayeb, Jane Tournois, and Mariette Yvinec
This package provides a data structure to store three-dimensional simplicial meshes and their subcomplexes. It provides an API for tetrahedral meshes generated with CGAL or not, to be processed with CGAL 3D mesh generation and remeshing algorithms, along with iterators, IO functions, and additional helper functions.
User Manual Reference Manual
Introduced in: CGAL 5.6
Depends on: 3D Triangulations
BibTeX: cgal:ajrtty-mds3-26a
License: GPL
Windows Demo: CGAL Lab

## 3D Mesh Generation

Pierre Alliez, Clément Jamin, Laurent Rineau, Stéphane Tayeb, Jane Tournois, and Mariette Yvinec
This package is devoted to the generation of isotropic simplicial meshes discretizing 3D domains. The domain to be meshed is a region of 3D space that has to be bounded. The region may be connected or composed of multiple components and/or subdivided in several subdomains. The domain is input as an oracle able to answer queries, of a few different types, on the domain. Boundary and subdivision surfaces are either smooth or piecewise smooth surfaces, formed with planar or curved surface patches. Surfaces may exhibit 1-dimensional features (e.g., crease edges) and 0-dimensional features (e.g., singular points as corners tips, cusps or darts), that have to be fairly approximated in the mesh. Optionally, the algorithms support multi-core shared-memory architectures to take advantage of available parallelism.
User Manual Reference Manual
Introduced in: CGAL 3.5
Depends on: 3D Triangulations and Eigen
BibTeX: cgal:rty-m3-26a
License: GPL
Windows Demo: CGAL Lab

## 3D Isosurfacing

Mael Rouxel-Labbé, Julian Stahl, Daniel Zint, and Pierre Alliez
This package implements several grid-based isosurfacing algorithms (Marching Cubes, its topologically correct variant, and Dual Contouring) that enable generating surface meshes from 3D value and gradient fields. The methods are generic with respect to the definition of the grid and the fields, and all methods offer parallel implementations. The output is a polygon soup (i.e., a container of 3D point coordinates and indexed faces).
User Manual Reference Manual
Introduced in: CGAL 6.1
BibTeX: cgal:sz-mc-26a
License: GPL
Windows Demo: Polyhedron demo

## Tetrahedral Remeshing

Jane Tournois, Noura Faraj, Jean-Marc Thiery, and Tamy Boubekeur
The package provides a function for remeshing tetrahedral meshes, targeting high quality meshes with respect to dihedral angles. This practical iterative remeshing algorithm is designed to remesh multi-material tetrahedral meshes, by iteratively performing a sequence of elementary operations such as edge splits, edge collapses, edge flips, and vertex relocations following a Laplacian smoothing. The algorithm results in high-quality uniform isotropic meshes, with the desired mesh density, while preserving the input geometric curve and surface features.
User Manual Reference Manual
Introduced in: CGAL 5.1
Depends on: 3D Triangulations
BibTeX: cgal:tftb-tr-26a
License: GPL
Windows Demo: CGAL Lab

## 3D Periodic Mesh Generation

Mikhail Bogdanov, Aymeric Pellé, Mael Rouxel-Labbé, and Monique Teillaud
This package is devoted to the generation of isotropic simplicial meshes discretizing periodic 3D domains. The domain to be meshed is a region of the three-dimensional flat torus. The periodic mesh generator provides users with the same flexibility that is offered in the 3D Mesh Generation package.
User Manual Reference Manual
Introduced in: CGAL 4.13
Depends on: 3D Periodic Triangulations, 3D Mesh Generation, and Eigen
BibTeX: cgal:btprl-p3m3-26a
License: GPL

## 3D Alpha Wrapping

Pierre Alliez, David Cohen-Steiner, Michael Hemmer, Cédric Portaneri, and Mael Rouxel-Labbé
This component takes a 3D triangle mesh, a triangle soup, or a point set as input, and generates a valid triangulated surface mesh that strictly contains the input (watertight, intersection-free and 2-manifold). The algorithm proceeds by shrink-wrapping and refining a 3D Delaunay triangulation starting from a loose bounding box of the input. Two user-defined parameters, alpha and offset, offer control over the maximum size of cavities where the shrink-wrapping process can enter, and the tightness of the final surface mesh to the input, respectively. Once combined, these parameters provide a means to trade fidelity to the input for complexity of the output.
User Manual Reference Manual
Introduced in: CGAL 5.5
Depends on: 3D Triangulations and Polygon Mesh Processing
BibTeX: cgal:achpr-aw3-26a
License: GPL

# Shape Reconstruction

## Poisson Surface Reconstruction

Pierre Alliez, Laurent Saboret, and Gaël Guennebaud
This 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 iso-surface from this function.
User Manual Reference Manual
Introduced in: CGAL 3.5
Depends on: CGAL and Solvers
BibTeX: cgal:asg-srps-26a
License: GPL
Windows Demo: CGAL Lab

## Scale-Space Surface Reconstruction

Thijs van Lankveld
This method allows to reconstruct a surface that interpolates a set of 3D points using either an alpha shape or the advancing front surface reconstruction method. The output interpolates the point set (as opposed to approximating the point set). How the surface connects the points depends on a scale variable, which can be estimated semi-automatically.
User Manual Reference Manual
Introduced in: CGAL 4.6
BibTeX: cgal:ssr3-26a
License: GPL
Depends on: 3D Alpha Shapes, dD Spatial Searching, CGAL and Solvers

## Advancing Front Surface Reconstruction

Tran Kai Frank Da and David Cohen-Steiner
This package provides a greedy algorithm for surface reconstruction from an unorganized point set. Starting from a seed facet, a piecewise linear surface is grown by adding Delaunay triangles one by one. The most plausible triangles are added first, in a way that avoids the appearance of topological singularities.
User Manual Reference Manual
Introduced in: CGAL 4.7
Depends on: 3D Triangulations
BibTeX: cgal:dc-afsr-26a
License: GPL

## Polygonal Surface Reconstruction

Liangliang Nan
This package provides a method for piecewise planar object reconstruction from point clouds. The method takes as input an unordered point set (and optionally planar segments) of a piecewise planar object and outputs a lightweight and watertight surface mesh interpolating the input point set. The method can handle arbitrary piecewise planar objects and is capable of recovering sharp features and is robust to noise and outliers.
User Manual Reference Manual
Introduced in: CGAL 4.14
Depends on: 2D Alpha Shapes and CGAL and Solvers
BibTeX: cgal:x-x-26a
License: GPL

## Kinetic Space Partition

Sven Oesau and Florent Lafarge
This package implements kinetic space partition. Based on a set of planar input shapes the bounding box of the input data is split into convex volumes. The complexity of the partition can be adjusted with a single parameter.
User Manual Reference Manual
Introduced in: CGAL 6.0
Depends on: Surface Mesh, Linear Cell Complex
BibTeX: cgal:ol-kinetic-partition-26a
License: GPL

## Kinetic Surface Reconstruction

Sven Oesau and Florent Lafarge
The package implements a piece-wise planar surface reconstruction pipeline from point clouds combining methods from the Shape Detection, Shape Regularization and Kinetic Shape Partition packages and graph-cut.
User Manual Reference Manual
Introduced in: CGAL 6.0
Depends on: Kinetic Space Partition, Surface Mesh, Linear Cell Complex, Shape Detection
BibTeX: cgal:ol-kinetic-reconstruction-26a
License: GPL

## Optimal Transportation Curve Reconstruction

Pierre Alliez, David Cohen-Steiner, Fernando de Goes, Clément Jamin, and Ivo Vigan
This package provides an algorithm to reconstruct and simplify a shape from a point set in the plane, possibly hampered with noise and outliers. It generates as output a set of line segments and isolated points, which approximate the input point set.
User Manual Reference Manual
Introduced in: CGAL 4.8
Depends on: 2D Triangulations
BibTeX: cgal:gavj-rs-26a
License: GPL
Windows Demo: 2D Optimal Transportation Curve Reconstruction

# Polygon Mesh Processing

David Coeurjolly, Jacques-Olivier Lachaud, Konstantinos Katrioplas, Sébastien Loriot, Ivan Pađen, Mael Rouxel-Labbé, Hossam Saeed, Jane Tournois, Sébastien Valette, and Ilker O. Yaz
This package provides a collection of methods and classes for polygon mesh processing, ranging from basic operations on simplices such as the computation of an edge length, to complex geometry processing algorithms such as collision and intersection detection, computation of distances between meshes, and more.
User Manual Reference Manual
Introduced in: CGAL 4.7
Depends on: documented for each function
BibTeX: cgal:lty-pmp-26a
License: GPL
Windows Demo: CGAL Lab

## Boolean Operations on Meshes

Sébastien Loriot, Léo Valque, and Ilker O. Yaz
This package provides a collection of methods and classes to compute Boolean operations on meshes (union, intersection, and difference), clipping and splitting of meshes using planes, boxes, or other meshes, and slicing of triangulated surfaces.
User Manual Reference Manual
Introduced in: CGAL 4.7
Depends on: documented for each function
BibTeX: cgal:pmp-boolop-26a
License: GPL
Windows Demo: CGAL Lab

## Meshing and Remeshing of Polygon Meshes

Sébastien Loriot, Jane Tournois, Mael Rouxel-Labbé, Konstantinos Katrioplas, Ivan Pađen, Hossam Saeed, Ilker O. Yaz, and Sébastien Valette
This package provides a collection of methods and classes to perform meshing and remeshing of polygonal meshes, including triangulation of non-triangulated meshes, refinement and simplification, as well as optimization and smoothing algorithms.
User Manual Reference Manual
Introduced in: CGAL 4.7
Depends on: documented for each function
BibTeX: cgal:pmp-remesh-26a
License: GPL
Windows Demo: CGAL Lab

## Polygon Mesh Repair

Sébastien Loriot, Mael Rouxel-Labbé, and Ilker O. Yaz
This CGAL package provides methods that enable treating both combinatorial and geometrical defects in polygon meshes and polygon soups: orientation, hole filling, degeneracies removal, boundary stitching, and more.
User Manual Reference Manual
Introduced in: CGAL 4.7
Depends on: documented for each function
BibTeX: cgal:pmp-repair-26a
License: GPL
Windows Demo: CGAL Lab

## 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.
User Manual Reference Manual
Introduced in: CGAL 4.11
BibTeX: cgal:s-ssm2-26a
License: LGPL
Windows Demo: CGAL Lab

## Triangulated Surface Mesh Segmentation

Ilker O. Yaz and Sébastien Loriot
This package provides a method to generate a segmentation of a triangulated surface mesh. The algorithm first computes the Shape Diameter Function (SDF) for all facets and applies a graph-cut based algorithm over these values. Low level functions are provided to replace any intermediate step by a custom one.
User Manual Reference Manual
Introduced in: CGAL 4.4
Depends on: 2D and 3D Fast Intersection and Distance Computation
BibTeX: cgal:y-smsimpl-26a
License: GPL
Windows Demo: CGAL Lab

## Triangulated Surface Mesh Simplification

Fernando Cacciola, Mael Rouxel-Labbé, Baskın Şenbaşlar, and Julian Komaromy
This package provides an algorithm to simplify a triangulated surface mesh by edge collapsing. Users can define cost, constraints, and placement strategies to decide when and how should edges be collapsed. A few strategies are offered by default, such as the Turk/Lindstrom and Garland-Heckbert memoryless approaches.
User Manual Reference Manual
Introduced in: CGAL 3.3
BibTeX: cgal:c-tsms-12-26a
License: GPL
Windows Demo: CGAL Lab

## Triangulated Surface Mesh Deformation

Sébastien Loriot, Olga Sorkine-Hornung, Yin Xu, and Ilker O. Yaz
This package offers surface mesh deformation algorithms which provide new positions to the vertices of a surface mesh under positional constraints of some of its vertices, without requiring any additional structure other than the surface mesh itself.
User Manual Reference Manual
Introduced in: CGAL 4.5
Depends on: CGAL and Solvers and Eigen
BibTeX: cgal:lsxy-tsmd-26a
License: GPL
Windows Demo: CGAL Lab

## Triangulated Surface Mesh Parameterization

Laurent Saboret, Pierre Alliez, Bruno Lévy, Mael Rouxel-Labbé, Andreas Fabri, and Hardik Jain
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 several surface mesh parameterization methods, such as As Rigid As Possible Parameterization, Discrete Authalic Parameterization, Discrete Conformal Map, Floater Mean Value Coordinates, Least Squares Conformal Maps, Orbifold Tutte Embedding, or Tutte Barycentric Mapping. The code is generic and works with any model of the `FaceGraph` concept.
User Manual Reference Manual
Introduced in: CGAL 3.2
Depends on: CGAL and Solvers
BibTeX: cgal:salf-pptsm2-26a
License: GPL
Windows Demo: CGAL Lab

## Triangulated Surface Mesh Shortest Paths

Stephen Kiazyk, Sébastien Loriot, and Éric Colin de Verdière
The package provides methods for computing geodesic shortest path on triangulated surface meshes. The algorithm used is based on a paper by Xin and Wang [15] . The input of this package can be any model of the `FaceListGraph` concept.
User Manual Reference Manual
Introduced in: CGAL 4.7
BibTeX: cgal:klcdv-tsmsp-26a
License: GPL
Windows Demo: CGAL Lab

## Triangulated Surface Mesh Skeletonization

Xiang Gao, Sébastien Loriot, and Andrea Tagliasacchi
This package provides a (1D) curve skeleton extraction algorithm for a triangulated polygonal mesh without borders based on the mean curvature flow. The particularity of this skeleton is that it captures the topology of the input. For each skeleton vertex one can obtain its location and its corresponding vertices from the input mesh. The code is generic and works with any model of the `FaceListGraph` concept.
User Manual Reference Manual
Introduced in: CGAL 4.7
Depends on: CGAL and Solvers
BibTeX: cgal:glt-tsms-26a
License: GPL
Windows Demo: CGAL Lab

## Triangulated Surface Mesh Approximation

Pierre Alliez, David Cohen-Steiner, and Lingjie Zhu
This package implements the Variational Shape Approximation method to approximate an input surface triangle mesh by a simpler surface triangle mesh. The algorithm proceeds by iterative clustering of triangles, the clustering process being seeded randomly, incrementally or hierarchically. While the default function runs an automated version of the algorithm, interactive control is possible via a class interface. The API is flexible and can be extended to user-defined proxies and error metrics.
User Manual Reference Manual
Introduced in: CGAL 4.14
BibTeX: cgal:az-tsma-26a
Depends on: Eigen
License: GPL
Windows Demo: CGAL Lab

## The Heat Method

Keenan Crane, Christina Vaz, and Andreas Fabri
The package provides an algorithm that solves the single- or multiple-source shortest path problem by returning an approximation of the geodesic distance for all vertices of a triangle mesh to the closest vertex in a given set of source vertices.
User Manual Reference Manual
Introduced in: CGAL 4.14
Depends on: CGAL and Solvers
BibTeX: cgal:cvf-hm3-26a
License: GPL
Windows Demo: CGAL Lab

## Surface Mesh Topology

Guillaume Damiand and Francis Lazarus
This package provides a toolbox for manipulating curves on a combinatorial surface from the topological point of view. Two main functionalities are proposed. One is the computation of shortest curves that cannot be continuously deformed to a point. This includes the computation of the so-called edge width and face width of the vertex-edge graph of a combinatorial surface. The other functionality is the homotopy test for deciding if two given curves on a combinatorial surface can be continuously deformed one into the other.
User Manual Reference Manual
Introduced in: CGAL 5.1
BibTeX: cgal:dl-smtopology-26a
License: GPL

# Point Set Processing

## Approximation of Ridges and Umbilics on Triangulated Surface Meshes

Marc Pouget and Frédéric Cazals
Global features related to curvature extrema encode important information 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.
User Manual Reference Manual
Introduced in: CGAL 3.3
Depends on: CGAL and Solvers
BibTeX: cgal:cp-arutsm-26a
License: GPL

## Estimation of Local Differential Properties of Point-Sampled Surfaces

Marc 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.
User Manual Reference Manual
Introduced in: CGAL 3.3
Depends on: CGAL and Solvers and Eigen
BibTeX: cgal:pc-eldp-26a
License: GPL
Windows Demo: CGAL Lab

## 3D Point Set

Simon Giraudot
This component provides the user with a flexible 3D point set data structure. The user can define any additional property needed such as normal vectors, colors or labels. CGAL algorithms can be easily applied to this data structure.
User Manual Reference Manual
Introduced in: CGAL 4.10
BibTeX: cgal:g-ps-26a
License: GPL
Windows Demo: CGAL Lab

## Point Set Processing

Pierre Alliez, Simon Giraudot, Clément Jamin, Florent Lafarge, Quentin Mérigot, Jocelyn Meyron, Sven Oesau, Laurent Saboret, Nader Salman, Shihao Wu, and Necip Fazil Yildiran
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, normal orientation, feature edges estimation and registration.
User Manual Reference Manual
Introduced in: CGAL 3.5
Depends on: CGAL and Solvers
BibTeX: cgal:ass-psp-26a
License: GPL
Windows Demo: CGAL Lab

## Shape Detection

Sven Oesau, Yannick Verdie, Clément Jamin, Pierre Alliez, Florent Lafarge, Simon Giraudot, Thien Hoang, and Dmitry Anisimov
This package implements the Efficient RANSAC (RANdom SAmple Consensus) approach for detecting arbitrary shapes in an unorganized point set with unoriented normals and the Region Growing approach for detecting shapes in a set of arbitrary items.
User Manual Reference Manual
Introduced in: CGAL 4.7
Depends on: Eigen
BibTeX: cgal:ovja-pssd-26a
License: GPL
Windows Demo: CGAL Lab

## Shape Regularization

Dmitry Anisimov, Gennadii Sytov, Simon Giraudot, Jean-Philippe Bauchet, and Florent Lafarge
Regularization of a set of segments and open or closed contours in 2D and a set of planes in 3D such that all input objects are rotated and aligned with respect to the user-specified conditions.
User Manual Reference Manual
Introduced in: CGAL 5.4
Depends on: CGAL and Solvers
BibTeX: cgal:asgbl-sr-26a
License: GPL
Windows Demo: CGAL Lab

## 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 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.
User Manual Reference Manual
Introduced in: CGAL 3.2
Depends on: 2D Triangulations
BibTeX: cgal:m-ps-26a
License: GPL
Windows Demo: 2D Stream Lines

## Classification

Simon Giraudot and Florent Lafarge
This component implements an algorithm that classifies a data set into a user-defined set of labels (such as ground, vegetation, buildings, etc.). A flexible API is provided so that users can classify any type of data, compute their own local features on the input data set, and define their own labels.
User Manual Reference Manual
Introduced in: CGAL 4.12
Depends on: CGAL and Solvers, dD Spatial Searching
BibTeX: cgal:lm-clscm-12-26a
License: GPL
Windows Demo: CGAL Lab

# Spatial Searching and Sorting

## 2D Range and Neighbor Search

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. In contrast to the spatial searching package, this package uses a Delaunay triangulation as underlying data structure.
User Manual Reference Manual
Introduced in: CGAL 2.1
Depends on: 2D Triangulations
BibTeX: cgal:b-ss2-26a
License: GPL

## Interval Skip List

Andreas 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.
User Manual Reference Manual
Introduced in: CGAL 3.0
BibTeX: cgal:f-isl-26a
License: GPL

## 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.
User Manual Reference Manual
Introduced in: CGAL 3.0
BibTeX: cgal:tf-ssd-26a
License: GPL
Windows Demo: 2D Spatial Searching

## 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.
User Manual Reference Manual
Introduced in: CGAL 0.9
BibTeX: cgal:n-rstd-26a
License: GPL

## 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.
User Manual Reference Manual
Introduced in: CGAL 3.1
BibTeX: cgal:kmz-isiobd-26a
License: GPL
Windows Demo: CGAL Lab

## 2D and 3D Fast Intersection and Distance Computation

Pierre Alliez, Stéphane Tayeb, and Camille Wormser
The AABB (axis-aligned bounding box) tree component offers a static data structure and algorithms to perform efficient intersection and distance queries on sets of finite 2D and 3D geometric objects.
User Manual Reference Manual
Introduced in: CGAL 3.5
BibTeX: cgal:atw-aabb-26a
License: GPL
Windows Demo: AABB Tree

## Quadtrees, Octrees, and Orthtrees

Jackson Campolattaro, Simon Giraudot, Cédric Portaneri, Tong Zhao, and Pierre Alliez
The Orthtree package provides a data structure that subdivides space, with specializations for 2D (Quadtree) and 3D (Octree), along with a collection of algorithms for operating on these structures.
User Manual Reference Manual
Introduced in: CGAL 5.3
BibTeX: cgal:cpz-o-26a
License: GPL

## Spatial Sorting

Christophe Delage and Olivier Devillers
This package provides functions for sorting geometric objects in two, three and higher dimensions, including on a sphere, in order to improve efficiency of incremental geometric algorithms.
User Manual Reference Manual
Introduced in: CGAL 3.3
BibTeX: cgal:dd-ss-26a
License: LGPL

# Geometric Optimization

## Bounding Volumes

Kaspar 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 d-dimensional space, the smallest enclosing sphere, ellipsoid (approximate), and annulus can be computed. In 3-dimensional space, the smallest enclosing strip is available as well, and in 2-dimensional space, there are algorithms for a number of additional volumes (rectangles, parallelograms, \( k=2,3,4\) axis-aligned rectangles). The smallest enclosing sphere algorithm can also be applied to a set of d-dimensional spheres.
User Manual Reference Manual
Introduced in: CGAL 1.1
Depends on: Eigen
BibTeX: cgal:fghhs-bv-26a
License: GPL
Windows Demo: 2D Bounding Volumes

## Inscribed Areas

Michael Hoffmann and Eli Packer
This package provides algorithms for computing inscribed areas. The algorithms for computing inscribed areas are: the largest inscribed k-gon (area or perimeter) of a convex point set and the largest inscribed iso-rectangle.
User Manual Reference Manual
Introduced in: CGAL 1.1
BibTeX: cgal:hp-ia-26a
License: GPL
Windows Demos: 2D Inscribed k-gon as part of Polygon demo, 2D Largest Empty Rectangle

## Optimal Distances

Kaspar 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 d-dimensional space, without explicitly 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.
User Manual Reference Manual
Introduced in: CGAL 1.1
BibTeX: cgal:fghhs-od-26a
License: GPL

## Principal Component Analysis

Pierre 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 axis-aligned 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.
User Manual Reference Manual
Introduced in: CGAL 3.2
Depends on: CGAL and Solvers
BibTeX: cgal:ap-pcad-26a
License: GPL
Windows Demos: Principal Component Analysis, Operations on Polygons, CGAL Lab

## Optimal Bounding Box

Konstantinos Katrioplas and Mael Rouxel-Labbé
This package provides functions to compute tight oriented bounding boxes around a point set or a polygon mesh.
User Manual Reference Manual
Introduced in: CGAL 5.1
Depends on: 3D Convex Hulls
BibTeX: cgal:obb-26a
License: GPL
Windows Demo: CGAL Lab

# 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.
User Manual Reference Manual
Introduced in: CGAL 3.1
BibTeX: cgal:f-i-26a
License: GPL

## 2D Generalized Barycentric Coordinates

Dmitry Anisimov, David Bommes, Kai Hormann, and Pierre Alliez
This package offers an efficient and robust implementation of 2D generalized barycentric coordinates defined for simple polygons in the plane. If coordinates with respect to multivariate scattered points instead of a polygon are required, please refer to natural neighbor coordinates from the Package 2D and Surface Function Interpolation.
User Manual Reference Manual
Introduced in: CGAL 4.6
BibTeX: cgal:abha-gbc-26a
License: GPL

## 3D Generalized Barycentric Coordinates

Antonio Gomes, Dmitry Anisimov
The package 3D Generalized Barycentric Coordinates offers an efficient and robust implementation of three-dimensional closed-form generalized barycentric coordinates defined for convex simplicial polytopes.
User Manual Reference Manual
Introduced in: CGAL 6.2
BibTeX: abha-gbc-26a
License: GPL

# Support Library

## STL Extensions for CGAL

Michael 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 non-geometric STL-like algorithms and datastructures that are not in the STL standard, as well as functions to change the failure behavior of assertions.
User Manual Reference Manual
Introduced in: CGAL 1.0
BibTeX: cgal:hkpw-se-26a
License: LGPL

## CGAL and the Boost Graph Library

Andreas Fabri, Fernando Cacciola, Philipp Moeller, and Ron Wein
This package provides a framework for interfacing CGAL data structures with the algorithms of the Boost Graph Library, or BGL for short. 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 several new graph concepts describing halfedge data structures.
User Manual Reference Manual
Introduced in: CGAL 3.3
BibTeX: cgal:cfw-cbgl-26a
License: LGPL

## CGAL and Solvers

Simon Giraudot, Pierre Alliez, Frédéric Cazals, Gaël Guennebaud, Bruno Lévy, Marc Pouget, Laurent Saboret, and Liangliang Nan
This package provides concepts and models for solving linear systems with dense or sparse matrices, mixed integer programming problems with or without constraints, and nonlinear programming problems with or without constraints.
User Manual Reference Manual
Introduced in: CGAL 4.8
BibTeX: cgal:eb-solver-26a
License: LGPL

## CGAL and Boost Property Maps

Andreas Fabri and Laurent Saboret
This package provides a framework for interfacing CGAL data structures with algorithms expecting Boost Property Maps.
User Manual Reference Manual
Introduced in: CGAL 3.5
BibTeX: cgal:fs-cbpm-26a
License: LGPL

## Weight Interface

Dmitry Anisimov
Many geometric algorithms rely on weighted constructions. This package provides a simple and unified interface to different types of weights. In particular, it includes numerous weights with a simple analytic expression, generalized barycentric weights, and weighting regions. All weights are available both in 2D and 3D.
User Manual Reference Manual
Introduced in: CGAL 5.4
BibTeX: cgal:a-wi-26a
License: LGPL
Windows Demo: CGAL Lab

## Cone-Based Spanners

Weisheng Si, Quincy Tse, and Frédérik Paradis
This package provides functors for constructing two kinds of cone-based spanners: Yao graph and Theta graph, given a set of vertices on the plane and the directions of cone boundaries. Both exact and inexact constructions are supported. In exact construction, the cone boundaries are calculated using the roots of polynomials, thus avoiding the use of \( \pi \), which cannot be represented exactly. In inexact construction, the cone boundaries are calculated using the approximate \( \pi \) value defined in CGAL, which is still accurate enough for most applications. Moreover, for visualization purpose, this package provides a global function to generate the data and script files used by Gnuplot to plot the constructed graphs. This package also provides options for the Half Yao graph and the Half Theta graph.
User Manual Reference Manual
Introduced in: CGAL 4.9
BibTeX: cgal:st-cbs-26a
License: GPL

## Handles and Circulators

Olivier Devillers, Lutz Kettner, Sylvain Pion, Michael Seel, and Mariette Yvinec
This package describes handles and circulators. They are related to iterators. Handles allow to dereference but neither to increment nor to decrement. Circulators have no notion of past-the-end, and they are used in CGAL whenever we have cyclic structures.
User Manual Reference Manual
Introduced in: CGAL 1.0
BibTeX: cgal:dksy-hc-26a
License: LGPL

## Geometric Object Generators

Pedro M. M. de Castro, Olivier Devillers, Susan Hert, Michael Hoffmann, Lutz Kettner, Sven Schönherr, Alexandru Tifrea, and Maxime Gimeno
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.
User Manual Reference Manual
Introduced in: CGAL 1.0
BibTeX: cgal:dhhk-gog-26a
License: LGPL
Windows Demo: Generators

## Profiling tools, Hash Map, Union-find, Modifiers

Lutz Kettner, Sylvain Pion, and Michael Seel
This package provides classes for profiling time and memory consumption, profiling macros, a hash map, a union find data structure and a modifier.
User Manual Reference Manual
Introduced in: CGAL 3.2
BibTeX: cgal:kps-pthum-26a
License: LGPL

## I/O Streams

Andreas Fabri, Geert-Jan Giezeman, and Lutz Kettner
All classes in the CGAL kernel provide input and output operators for I/O 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.
User Manual Reference Manual
Introduced in: CGAL 1.0
BibTeX: cgal:fgk-ios-12-26a
License: LGPL

# Visualization

## CGAL and the Qt Graphics View Framework

Andreas Fabri and Laurent Rineau
This package provides classes for displaying CGAL objects and data structures in the Qt 6 Graphics View Framework.
User Manual Reference Manual
Introduced in: CGAL 3.4
Depends on: Qt 6
BibTeX: cgal:fr-cqgvf-26a
License: GPL

## CGAL Ipelets

Olivier Devillers, Sébastien Loriot, and Sylvain Pion
This package provides a generic framework to easily write ipelets (plug-in's) using CGAL for the Ipe extensible drawing editor.
User Manual Reference Manual
Introduced in: CGAL 3.5
BibTeX: cgal:lp-gi-26a
License: LGPL

## Basic Viewer

Guillaume Damiand and Mostafa Ashraf
This package provides interactive visualization for most CGAL packages. First, the function `draw()` is provided for each data structure. Several data structures can be added to a same graphics scene and visualized simultaneously. Rendering can be controlled (color, point size, etc.). Finally a Qt widget is provided that can be integrated in the GUI of a user application.
User Manual Reference Manual
Introduced in: CGAL 6.0
BibTeX: cgal:d-bv-26a
License: LGPL