| |||
Introduction |
|||
CGAL Editorial Board |
|||
This chapter explains how the manual is organized, presents a ``Hello World'' program, and gives recommendations for further readings. | |||
Preliminaries |
|||
CGAL Editorial Board |
|||
This chapter lists the licenses under which the Cgal datastructures and algorithms are distributed, how to control inlining, thread safety, code deprecation, checking of pre- and postconditions, and how to alter the failure behavior. | |||
Installation |
|||
Joachim Reichel and Fernando Cacciola |
Introduced in: Cgal 3.6
BibTeX: [cgal:cr-i-12] Demo: dlls used by all demos User Manual Reference Manual |
||
This chapter describes how to install Cgal, and lists the third party libraries
on which Cgal depends, or for which Cgal provides interfaces.
If you want to download and run any of the precompiled demos, here you can find the dlls that are shared by all of them. |
|||
| |||
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). | |||
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. | |||
Modular Arithmetic |
|||
Michael Hemmer |
|||
This package provides arithmetic over finite fields. The provided tools are in particular useful for filters based on modular arithmetic and algorithms based on Chinese remainder. | |||
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. | |||
Algebraic Kernel |
|||
Eric Berberich, Michael Hemmer, Michael Kerber, Sylvain Lazard, Luis Peñaranda, and Monique Teillaud |
Introduced in: Cgal 3.6
Depends on: Some models depend on RS. License: LGPL BibTeX: [cgal:bht-ak-12] User Manual Reference Manual |
||
Real solving of polynomials is a fundamental problem with a wide application range. This package is targeted to provide black-box implementations of state-of-the-art 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. | |||
| |||
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. | |||
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. |
|||
| |||
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. | |||
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. | |||
2D Circular Geometry Kernel |
|||
Pedro Machado Manhães de Castro, Sylvain Pion, and Monique Teillaud |
Introduced in: Cgal 3.2
License: GPL BibTeX: [cgal:cpt-cgk2-12] Demo: Arrangement of Circular Arcs User Manual Reference Manual |
||
This package is an extension of the linear Cgal kernel. It offers functionalities on circles, circular arcs and line segments in the plane. | |||
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. | |||
| |||
2D Convex Hulls and Extreme Points |
|||
Susan Hert and Stefan Schirra |
Introduced in: Cgal 1.0
License: GPL BibTeX: [cgal:hs-chep2-12] Demo: See Bounding Volumes User Manual Reference Manual |
||
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. | |||
3D Convex Hulls |
|||
Susan Hert and Stefan Schirra |
Introduced in: Cgal 1.1
Depends on: All algorithms produce as output a 3D Polyhedron. The dynamic algorithms depend on 3D Triangulations License: GPL BibTeX: [cgal:hs-ch3-12] Demo: See Polyhedral Surface User Manual Reference Manual |
||
This package provides functions for computing convex hulls in three dimensions as well as functions for checking if sets of points are strongly convex or not. One can compute the convex hull of a set of points in three dimensions in one of three ways: using a static algorithm, using an incremental construction algorithm, or using a triangulation to get a fully dynamic computation. | |||
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. | |||
| |||
2D Polygon |
|||
Geert-Jan Giezeman and Wieger Wesselink |
Introduced in: Cgal 0.9
License: LGPL BibTeX: [cgal:gw-p2-12] Demo: Operations on Polygons User Manual Reference Manual |
||
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. |
|||
2D Regularized Boolean Set-Operations |
|||
Efi Fogel, Ophir Setter, Ron Wein, Guy Zucker, Baruch Zukerman, and Dan Halperin |
Introduced in: Cgal 3.2
Depends on: 2D Arrangements License: GPL BibTeX: [cgal:fwzh-rbso2-12] Demo: Boolean operations User Manual Reference Manual |
||
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. | |||
2D Boolean Operations on Nef Polygons |
|||
Michael Seel |
Introduced in: Cgal 2.3
License: GPL BibTeX: [cgal:s-bonp2-12] Demo: 2D Nef Polygons User Manual Reference Manual |
||
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. | |||
2D Boolean Operations on Nef Polygons Embedded on the Sphere |
|||
Peter Hachenberger, Lutz Kettner, and Michael Seel |
Introduced in: Cgal 3.1
Depends on: 2D Nef Polygon License: GPL BibTeX: [cgal:hk-bonpes2-12] User Manual Reference Manual |
||
This package offers the equivalent to 2D Nef Polygons in the plane. Here halfplanes correspond to half spheres delimited by great circles. | |||
2D Polygon Partitioning |
|||
Susan Hert |
Introduced in: Cgal 2.3
License: GPL BibTeX: [cgal:h-pp2-12] Demo: 2D Polygon Partition Demo: Operations on Polygons User Manual Reference Manual |
||
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. | |||
2D Straight Skeleton and Polygon Offsetting |
|||
Fernando Cacciola |
Introduced in: Cgal 3.2
Depends on: Halfedge Data Structure License: GPL BibTeX: [cgal:c-sspo2-12] Demo: 2D Straight Skeleton Demo: Operations on Polygons User Manual Reference Manual |
||
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. | |||
2D Minkowski Sums |
|||
Ron Wein |
Introduced in: Cgal 3.3
Depends on: 2D Arrangements License: GPL BibTeX: [cgal:w-rms2-12] User Manual Reference Manual |
||
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. | |||
| |||
3D Polyhedral Surface |
|||
Lutz Kettner |
Introduced in: Cgal 1.0
Depends on: Halfedge Data Structure License: GPL BibTeX: [cgal:k-ps-12] Demo: Operations on Polyhedra User Manual Reference Manual |
||
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. | |||
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. | |||
Combinatorial Maps |
|||
Guillaume Damiand |
|||
This package
implements Combinatorial Maps in d-dimension. A combinatorial
map is a data structure allowing 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 an halfedge data structure. The package provides basic creations, modification operations, and several iterators allowing to run through some specific part of the object. |
|||
Linear Cell Complex |
|||
Guillaume Damiand |
Introduced in: Cgal 4.0
Depends on: Combinatorial Maps License: LGPL BibTeX: [cgal:d-lcc-12] Demo: 3D Linear Cell Complex User Manual Reference Manual |
||
This package implements linear cell complexes, objects
in d-dimension with linear geometry. The combinatorial part
of objects is described by a combinatorial map, representing all
the cells of the object plus the incidence and adjacency relations
between cells. Geometry is added to combinatorial maps 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. |
|||
3D Boolean Operations on Nef Polyhedra |
|||
Peter Hachenberger, Lutz Kettner, and Michael Seel |
Introduced in: Cgal 3.1
Depends on: 2D Nef Polygons, Nef Polygons on the Sphere License: GPL BibTeX: [cgal:hk-bonp3-12] Demo: Operations on Polyhedra User Manual Reference Manual |
||
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. | |||
Convex Decomposition of Polyhedra |
|||
Peter Hachenberger |
Introduced in: Cgal 3.5
Depends on: 2D Nef Polygons, Nef Polygons on the Sphere 3D Nef Polyhedra, License: GPL BibTeX: [cgal:h-emspe-12] Demo: Operations on Polyhedra User Manual Reference Manual |
||
This packages provides a function for decomposing a bounded polyhedron into convex sub-polyhedra. The decomposition yields O(r^{2}) convex pieces, where r is the number of edges, whose adjacent facets form an angle of more than 180 degrees with respect to the polyhedron's interior. This bound is worst-case optimal. | |||
3D Minkowski Sum of Polyhedra |
|||
Peter Hachenberger |
Introduced in: Cgal 3.5
Depends on: 2D Nef Polygons, Nef Polygons on the Sphere 3D Nef Polyhedra, Convex Decomposition of Polyhedra License: GPL BibTeX: [cgal:h-msp3-12] Demo: Operations on Polyhedra User Manual Reference Manual |
||
This package provides a function, which computes the Minkowski sum of two point sets in ℝ^{3}. These point sets may consist of isolated vertices, isolated edges, surfaces with convex facets without holes, and open and closed solids. Thus, it is possible to compute the configuration space of translational robots (even in tight passage scenarios) as well as several graphics operations, like for instance the glide operation, which computes the point set swept by a polyhedron that moves along a polygonal line. | |||
| |||
2D Arrangement |
|||
Ron Wein, Efi Fogel, Baruch Zukerman, Dan Halperin, Eric Berberich, and Oren Zalzman |
|||
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. |
|||
2D Intersection of Curves |
|||
Baruch Zukerman and Ron Wein |
Introduced in: Cgal 2.4
Depends on: 2D Arrangements License: GPL BibTeX: [cgal:wfz-ic2-12] User Manual Reference Manual |
||
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. | |||
2D Snap Rounding |
|||
Eli Packer |
Introduced in: Cgal 3.1
Depends on: Arrangements License: GPL BibTeX: [cgal:p-sr2-12] Demo: 2D Snap Rounding User Manual Reference Manual |
||
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. | |||
2D Envelopes |
|||
Ron Wein |
Introduced in: Cgal 3.3
Depends on: 2D Arrangements License: GPL BibTeX: [cgal:w-e2-12] User Manual Reference Manual |
||
This package consits of functions that computes the lower (or upper) envelope of a set of arbitrary curves in 2D. The output is represented as an envelope diagram, namely a subdivision of the x-axis into intervals, such that the identity of the curves that induce the envelope on each interval is unique. | |||
3D Envelopes |
|||
Dan Halperin, Michal Meyerovitch, Ron Wein and Baruch Zukerman |
Introduced in: Cgal 3.3
Depends on: 2D Arrangements License: GPL BibTeX: [cgal:mwz-e3-12] Demo: 3D Envelopes Demo: L1 Voronoi Diagram User Manual Reference Manual |
||
This package consits of functions that compute the lower (or upper) envelope of a set of arbitrary surfaces in 3D. The output is represented as an 2D envelope diagram, namely a planar subdivision such that the identity of the surfaces that induce the envelope over each diagram cell is unique. | |||
| |||
2D Triangulation |
|||
Mariette Yvinec |
Introduced in: Cgal 0.9
Depends on: 2D Triangulation Data Structure License: GPL BibTeX: [cgal:y-t2-12] Demo: Delaunay Triangulation Demo: Regular Triangulation Demo: Constrained Delaunay Triangulation User Manual Reference Manual |
||
This package allows to build and handle
various triangulations for point sets two dimensions.
Any Cgal triangulation covers the convex hull of its
vertices. Triangulations are build incrementally
and can be modified by insertion or removal of vertices.
They offer point location facilities.
The package provides plain triangulation (whose faces depend on the insertion order of the vertices) and Delaunay triangulations. Regular triangulations are also provided for sets of weighted points. Delaunay and regular triangulations offer nearest neighbor queries and primitives to build the dual Voronoi and power diagrams. Finally, constrained and Delaunay constrained triangulations allows to force some constrained segments to appear as edges of the triangulation. Several versions of constrained and Delaunay constrained triangulations are provided: some of them handle intersections between input constraints segment while others do not. |
|||
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. | |||
3D Triangulations |
|||
Sylvain Pion and Monique Teillaud |
Introduced in: Cgal 2.1
License: GPL BibTeX: [cgal:pt-t3-12] Demo: 3D Triangulation User Manual Reference Manual |
||
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. |
|||
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. | |||
3D Periodic Triangulations |
|||
Manuel Caroli and Monique Teillaud |
Introduced in: Cgal 3.5
Depends on: 3D Triangulation and 3D Triangulation Data Structure License: GPL BibTeX: [cgal:ct-pt3-12] Demo: Periodic Delaunay Triangulation User Manual Reference Manual |
||
This package allows to build and handle triangulations of point sets
in the three dimensional flat torus. Triangulations are built
incrementally and can be modified by insertion or removal of
vertices. They offer point location facilities.
The package provides Delaunay triangulations and offers nearest neighbor queries and primitives to build the dual Voronoi diagrams. |
|||
2D Alpha Shapes |
|||
Tran Kai Frank Da |
Introduced in: Cgal 2.1
Depends on: 2D Triangulation License: GPL BibTeX: [cgal:d-as2-12] Demo: 2D Alpha Shapes User Manual Reference Manual |
||
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). | |||
3D Alpha Shapes |
|||
Tran Kai Frank Da, Sébastien Loriot, and Mariette Yvinec |
Introduced in: Cgal 2.3
Depends on: 2D Triangulation License: GPL BibTeX: [cgal:dy-as3-12] Demo: 3D Alpha Shapes User Manual Reference Manual |
||
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). | |||
| |||
2D Segment Delaunay Graphs |
|||
Menelaos Karavelas |
Introduced in: Cgal 3.1
Depends on: 2D Triangulation Data Structure License: GPL BibTeX: [cgal:k-sdg2-12] Demo: 2D Segment Voronoi Diagram User Manual Reference Manual |
||
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. | |||
2D Apollonius Graphs (Delaunay Graphs of Disks) |
|||
Menelaos Karavelas and Mariette Yvinec |
Introduced in: Cgal 3.0
Depends on: 2D Triangulation Data Structure License: GPL BibTeX: [cgal:ky-ag2-12] Demo: 2D Apollonius Graph User Manual Reference Manual |
||
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. | |||
2D Voronoi Diagram Adaptor |
|||
Menelaos Karavelas |
Introduced in: Cgal 3.2
License: GPL BibTeX: [cgal:k-vda2-12] Demo: 2D Point Voronoi Diagram Demo: 2D Disk Voronoi Diagram Demo: 2D Segment Voronoi Diagram User Manual Reference Manual |
||
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. | |||
| |||
2D Conforming Triangulations and Meshes |
|||
Laurent Rineau |
Introduced in: Cgal 3.1
Depends on: 2D Delaunay Triangulation License: GPL BibTeX: [cgal:r-ctm2-12] Demo: 2D Mesh Generator User Manual Reference Manual |
||
This package implements a Delaunay refinement algorithm to construct
conforming triangulations and 2D meshes.
Conforming Delaunay triangulations are obtained from constrained Delaunay triangulations by refining constrained edges until they are Delaunay edges. Conforming Gabriel triangulations are obtained by further refining constrained edges until they become Gabriel edges. The package provides also a 2D mesh generator that refines triangles and constrained edges until user defined size and shape criteria on triangles are satisfied. The package can handle intersecting input constraints and set no restriction on the angle formed by two constraints sharing an endpoint. |
|||
3D Surface Mesh Generation |
|||
Laurent Rineau and Mariette Yvinec |
Introduced in: Cgal 3.2
License: GPL BibTeX: [cgal:ry-smg-12] Demo: Surface Mesh Generator User Manual Reference Manual |
||
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. |
|||
Surface Reconstruction from Point Sets |
|||
Pierre Alliez, Laurent Saboret, Gael Guennebaud |
Introduced in: Cgal 3.5
Depends on: Eigen License: GPL BibTeX: [cgal:asg-srps-12] Demo: Surface Reconstruction User Manual Reference Manual |
||
This Cgal package implements a surface reconstruction method: Poisson Surface Reconstruction. It takes as input a set of points with oriented normals and computes an implicit function. The Cgal surface mesh generator can then be used to extract an iso-surface from this function. | |||
3D Skin Surface Meshing |
|||
Nico Kruithof |
Introduced in: Cgal 3.3
Depends on: 3D Triangulation and 3D Polyhedral Surface License: GPL BibTeX: [cgal:k-ssm3-12] User Manual Reference Manual |
||
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. |
|||
3D Mesh Generation |
|||
Pierre Alliez, Laurent Rineau, Stéphane Tayeb, Jane Tournois, Mariette Yvinec |
Introduced in: Cgal 3.5
Depends on: 3D Triangulations, 2D Meshes, 3D Surface Mesh Generation License: GPL BibTeX: [cgal:rty-m3-12] Demo: 3D Mesh Generation User Manual Reference Manual |
||
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. | |||
| |||
3D Surface Subdivision Methods |
|||
Le-Jeng Andy Shiue |
Introduced in: Cgal 3.2
License: LGPL BibTeX: [cgal:s-ssm2-12] Demo: Operations on Polyhedra User Manual Reference Manual |
||
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. | |||
Triangulated Surface Mesh Simplification |
|||
Fernando Cacciola |
Introduced in: Cgal 3.3
Depends on: Polyhedron License: GPL BibTeX: [cgal:c-tsms-12] Demo: Operations on Polyhedra User Manual Reference Manual |
||
This package provides an algorithm to simplify a triangulated surface mesh by edge collapsing. It is an implementation of the Turk/Lindstrom memoryless mesh simplification algorithm. | |||
Planar Parameterization of Triangulated Surface Meshes |
|||
Laurent Saboret, Pierre Alliez and Bruno Lévy |
Introduced in: Cgal 3.2
Depends on: Solvers from Eigen. License: GPL BibTeX: [cgal:sal-pptsm2-12] Demo: Operations on Polyhedra User Manual Reference Manual |
||
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. | |||
2D Placement of Streamlines |
|||
Abdelkrim Mebarki |
Introduced in: Cgal 3.2
Depends on: 2D Delaunay triangulation License: GPL BibTeX: [cgal:m-ps-12] Demo: 2D Stream Lines User Manual Reference Manual |
||
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. | |||
Approximation of Ridges and Umbilics on Triangulated Surface Meshes |
|||
Marc Pouget and Frédéric Cazals |
Introduced in: Cgal 3.3
Depends on: Solvers from Eigen License: GPL BibTeX: [cgal:cp-arutsm-12] User Manual Reference Manual |
||
Global features related to curvature extrema encode important informations used in segmentation, registration, matching and surface analysis. Given pointwise estimations of local differential quantities, this package allows the approximation of differential features on a triangulated surface mesh. Such curvature related features are curves: ridges or crests, and points: umbilics. | |||
Estimation of Local Differential Properties of Point-Sampled Surfaces |
|||
Marc Pouget and Frédéric Cazals |
Introduced in: Cgal 3.3
Depends on: Solvers from Eigen License: GPL BibTeX: [cgal:pc-eldp-12] User Manual Reference Manual |
||
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. | |||
Point Set Processing |
|||
Pierre Alliez, Laurent Saboret, Nader Salman |
Introduced in: Cgal 3.5
Depends on: Solvers from Eigen License: GPL BibTeX: [cgal:ass-psp-12] Demo: Surface Reconstruction User Manual Reference Manual |
||
This Cgal component implements methods to analyze and process unorganized point sets. The input is an unorganized point set, possibly with normal attributes (unoriented or oriented). The point set can be analyzed to measure its average spacing, and processed through functions devoted to the simplification, outlier removal, smoothing, normal estimation and normal orientation. | |||
| |||
2D Range and Neighbor Search |
|||
Matthias Bäsken |
Introduced in: Cgal 2.1
Depends on: 2D Delaunay triangulation License: GPL BibTeX: [cgal:b-ss2-12] User Manual Reference Manual |
||
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. | |||
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. | |||
dD Spatial Searching |
|||
Hans Tangelder and Andreas Fabri |
Introduced in: Cgal 3.0
License: GPL BibTeX: [cgal:tf-ssd-12] Demo: 2D Spatial Searching User Manual Reference Manual |
||
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. | |||
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. | |||
Intersecting Sequences of dD Iso-oriented Boxes |
|||
Lutz Kettner, Andreas Meyer, and Afra Zomorodian |
Introduced in: Cgal 3.1
License: GPL BibTeX: [cgal:kmz-isiobd-12] Demo: Operations on Polyhedra User Manual Reference Manual |
||
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. | |||
3D Fast Intersection and Distance Computation (AABB Tree) |
|||
Pierre Alliez, Stéphane Tayeb, Camille Wormser |
Introduced in: Cgal 3.5
License: GPL BibTeX: [cgal:atw-aabb-12] Demo: AABB Tree User Manual Reference Manual |
||
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 3D geometric objects. | |||
Spatial Sorting |
|||
Christophe Delage and Olivier Devillers |
|||
This package provides functions for sorting geometric objects in two, three and higher dimensions, in order to improve efficiency of incremental geometric algorithms. | |||
| |||
Bounding Volumes |
|||
Kaspar Fischer, Bernd Gärtner, Thomas Herrmann, Michael Hoffmann, and Sven Schönherr |
Introduced in: Cgal 1.1
License: GPL BibTeX: [cgal:fghhs-bv-12] Demo: 2D Bounding Volumes User Manual Reference Manual |
||
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. | |||
Inscribed Areas |
|||
Michael Hoffmann and Eli Packer |
Introduced in: Cgal 1.1
License: GPL BibTeX: [cgal:hp-ia-12] Demo: 2D Inscribed k-gon as part of Polygon demo Demo: 2D Largest Empty Rectangle User Manual Reference Manual |
||
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. | |||
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 explicitely constructing the convex hulls. It further provides an algorithm to compute the width of a point set, and the furthest point for each vertex of a convex polygon. | |||
Principal Component Analysis |
|||
Pierre Alliez, Sylvain Pion and Ankit Gupta |
Introduced in: Cgal 3.2
License: GPL BibTeX: [cgal:ap-pcad-12] Demo: Principal Component Analysis Demo: Operations on Polygons Demo: Operations on Polyhedra User Manual Reference Manual |
||
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. | |||
| |||
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. | |||
| |||
Kinetic Data Structures |
|||
Daniel Russel |
Introduced in: Cgal 3.2
Depends on: KDS Framework. Two dimensional visualization depends on Qt, three dimensional visualization depends on Coin3D. License: LGPL BibTeX: [cgal:r-kds-12] User Manual Reference Manual |
||
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. | |||
Kinetic Framework |
|||
Daniel Russel |
Introduced in: Cgal 3.2
Depends on: Two dimensional visualization depends on Qt, three dimensional visualization depends on Coin3D. License: LGPL BibTeX: [cgal:r-kdsf-12] User Manual Reference Manual |
||
Kinetic data structures allow combinatorial geometric structures to be maintained as the primitives move. The package provides a framework to ease implementing and debugging kinetic data structures. The package supports exact or inexact operations on primitives which move along polynomial trajectories. | |||
| |||
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 provided in the STL standard but in Cgal | |||
CGAL and the Boost Graph Library |
|||
Andreas Fabri, Fernando Cacciola, and Ron Wein |
|||
This package provides a framework for interfacing Cgal data structures with the algorithms of the BGL. It allows to run graph algorithms directly on Cgal data structures which are model of the BGL graph concepts, for example the shortest path algorithm on a Delaunay triangulation in order to compute the Euclidean minimum spanning tree. Furthermore, it introduces a new graph concept, the HalfedgeEdgeGraph. This concept describes graphs which are embedded on surfaces. | |||
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. | |||
Handles and Circulators |
|||
Olivier Devillers, Lutz Kettner, Sylvain Pion, Michael Seel, and Mariette Yvinec |
|||
This package descibes handles and circulators. They are related to iterators. Handles allow to dereference but neither to increment nor to decrement. Circulators have no notion of past-the-end, and they are used in Cgal whenever we have cyclic stuctures. | |||
Geometric Object Generators |
|||
Olivier Devillers, Susan Hert, Michael Hoffmann, Lutz Kettner, and Sven Schönherr |
Introduced in: Cgal 1.0
License: LGPL BibTeX: [cgal:dhhk-gog-12] Demo: Generators User Manual Reference Manual |
||
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. | |||
Profiling tools, Hash Map, Union-find, Modifiers |
|||
Lutz Kettner, Sylvain Pion, and Michael Seel |
|||
This package provides classes for profiling time and memory consumption, a hash map, a union find data structure and a modifier. | |||
IO Streams |
|||
Andreas Fabri, Geert-Jan Giezeman, and Lutz Kettner |
|||
All classes in the Cgal kernel provide input and output operators for IO streams. The basic task of such an operator is to produce a representation of an object that can be written as a sequence of characters on devices as a console, a file, or a pipe. In Cgal we distinguish between a raw ascii, a raw binary and a pretty printing format. | |||
| |||
Geomview |
|||
Andreas Fabri and Sylvain Pion |
|||
This package implements an interface to Geomview, an interactive 3D viewing program, originally developed at the Geometry Center in Minneapolis. |
|||
CGAL and the Qt Graphics View Framework |
|||
Andreas Fabri and Laurent Rineau |
Introduced in: Cgal 3.4
Depends on: Qt 4 License: GPL BibTeX: [cgal:fr-cqgvf-12] User Manual Reference Manual |
||
This package provides classes for displaying Cgal objects and data structures in the Qt 4 Graphics View Framework. | |||
CGAL Ipelets |
|||
Sébastien Loriot and Sylvain Pion |
|||
This package provides a generic framework to easily write ipelets (plug-in's) using Cgal for the the Ipe extensible drawing editor. |