| ||
2D and 3D Linear KernelHervé Brönnimann, Andreas Fabri, Geert-Jan Giezeman, Susan Hert, Michael Hoffmann, Lutz Kettner, Sylvain Pion, and Stefan Schirra | ||
| This package contains kernels each containing objects of
constant size, such as point, vector, direction, line, ray, segment, circle
as well as predicates and constructions for these objects. The kernels
mainly differ in the way they handle robustness issues.
|
Introduced in: CGAL 0.9 License: LGPL BibTeX Key:cgal:bfghhkps-k23-06 User Manual Reference Manual |
|
dD KernelMichael Seel | ||
| The dD Kernel contains objects of constant size, such as point,
vector, direction, line, ray, segment, circle in d dimensional Euclidean space,
as well as predicates and constructions for these objects.
|
Introduced in: CGAL 1.1 License: LGPL User Manual Reference Manual |
|
2D Circular KernelSylvain Pion and Monique Teillaud | ||
|
This package is an extension of the linear CGAL Kernel. It offers
functionalities on circles, circular arcs and line segments in the
plane.
|
Introduced in: CGAL 3.2 License: QPL BibTeX Key:cgal:pt-cc2-06 User Manual Reference Manual |
|
| ||
2D Convex Hulls and Extreme PointsSusan Hert and Stefan Schirra | ||
| This package provides functions
for computing convex hulls in two dimensions as well as functions for
checking if sets of points are strongly convex are not. There are also
a number of functions described for computing particular extreme
points and subsequences of hull points, such as the lower and upper
hull of a set of points.
|
Introduced in: CGAL 1.0 License: QPL BibTeX Key:cgal:hs-chep2-06 User Manual Reference Manual |
|
3D Convex HullsSusan Hert and Stefan Schirra | ||
| This package provides functions
for computing convex hulls in three dimensions as well as functions
for checking if sets of points are strongly convex are not. One can
compute the convex hull of a set of points in three dimensions in one
of three ways: using a static algorithm, using an incremental
construction algorithm, or using a triangulation to get a fully
dynamic computation.
|
Introduced in: CGAL 1.1 Depends on: All algorithms produce as output a 3D Polyhedron. The dynamic algorithms depend on 3D Triangulations License: QPL BibTeX Key:cgal:hs-ch3-06 User Manual Reference Manual |
|
dD Convex Hulls and Delaunay TriangulationsSusan Hert and Michael Seel | ||
| This package provides functions
for computing convex hulls and Delaunay triagulations in -dimensional Euclidean space.
|
Introduced in: CGAL 2.3 License: LGPL BibTeX Key:cgal:hs-chdt3-06 User Manual Reference Manual |
|
| ||
2D PolygonGeert-Jan Giezeman and Wieger Wesselink | ||
|
This package provides a polygon class and operations on
sequences of points, like the simplicity test.
|
Introduced in: CGAL 0.9 License: LGPL BibTeX Key:cgal:gw-p2-06 User Manual Reference Manual |
|
2D Polygon PartitioningSusan Hert | ||
| This package provides functions
for partitioning polygons in monotone or convex polygons.
The algorithms can produce results with the minimal number of
polygons, as well as approximations which have no more than four
times the optimal number of convex pieces but they differ in
their runtime complexities.
|
Introduced in: CGAL 2.3 License: QPL BibTeX Key:cgal:h-pp2-06 User Manual Reference Manual |
|
3D Polyhedral SurfaceLutz Kettner | ||
| Polyhedral surfaces in three dimensions are composed of
vertices, edges, facets and an incidence relationship on them. The
organization beneath is a halfedge data structure, which restricts the
class of representable surfaces to orientable 2-manifolds - with and
without boundary. If the surface is closed we call it a polyhedron.
|
Introduced in: CGAL 1.0 Depends on: Halfedge Data Structure License: QPL BibTeX Key:cgal:k-ps-06 User Manual Reference Manual |
|
Halfedge Data StructuresLutz Kettner | ||
| A halfedge data structure is an edge-centered data structure
capable of maintaining incidence informations of vertices, edges and
faces, for example for planar maps, polyhedra, or other orientable,
two-dimensional surfaces embedded in arbitrary dimension. Each edge is
decomposed into two halfedges with opposite orientations. One incident
face and one incident vertex are stored in each halfedge. For each
face and each vertex, one incident halfedge is stored. Reduced
variants of the halfedge data structure can omit some of these
informations, for example the halfedge pointers in faces or the
storage of faces at all.
|
Introduced in: CGAL 1.0 License: LGPL BibTeX Key:cgal:k-hds-06 User Manual Reference Manual |
|
| ||
2D Regularized Boolean Set-OperationsEfi Fogel, Ron Wein, Baruch Zukerman, and Dan Halperin | ||
|
This package consists of the implementation of Boolean set-operations
on point sets bounded by weakly x-monotone curves in 2-dimensional
Euclidean space. In
particular, it contains the implementation of regularized Boolean
set-operations, intersection predicates, and point containment predicates.
|
Introduced in: CGAL 3.2 Depends on: 2D Arrangements License: QPL BibTeX Key:cgal:fwzh-rbso2-06 User Manual Reference Manual |
|
2D Boolean Operations on Nef PolygonsMichael Seel | ||
|
A Nef polygon is any set that can be obtained from a
finite set of open halfspaces by set complement and set intersection
operations. Due to the fact that all other binary set operations like
union, difference and symmetric difference can be reduced to
intersection and complement calculations, Nef polygons are also closed
under those operations. Apart from the set complement operation there
are more topological unary set operations that are closed in the
domain of Nef polygons interior, boundary, and closure.
|
Introduced in: CGAL 2.3 License: QPL BibTeX Key:cgal:s-bonp2-06 User Manual Reference Manual |
|
2D Boolean Operations on Nef Polygons Embedded on the SpherePeter Hachenberger, Lutz Kettner, and Michael Seel | ||
| This package offers the equivalent to 2D Nef Polygons in the plane.
Here halfplanes correspond to half spheres delimited by great circles.
|
Introduced in: CGAL 3.1 Depends on: 2D Nef Polygon BibTeX Key:cgal:s-bonpes2-06 User Manual Reference Manual |
|
3D Boolean Operations on Nef PolyhedraPeter Hachenberger, Lutz Kettner, and Michael Seel | ||
|
3D Nef polyhedra, are a
boundary representation for cell-complexes bounded by halfspaces that
supports Boolean operations and topological operations in full
generality including unbounded cells, mixed dimensional cells (e.g.,
isolated vertices and antennas). Nef polyhedra distinguish between
open and closed sets and can represent non-manifold geometry.
|
Introduced in: CGAL 3.1 Depends on: 2D Nef Polygons, Nef Polygons on the Sphere License: QPL BibTeX Key:cgal:s-bonp3-06 User Manual Reference Manual |
|
2D Straight Skeleton and Polygon OffsettingFernando Cacciola | ||
| This package implements an algorithm to construct a halfedge data
structure representing the straight skeleton in the interior of 2D
polygons with holes and an algorithm to construct inward offset
polygons at any offset distance given a straight skeleton.
|
Introduced in: CGAL 3.2 Depends on: Halfedge Data Structure License: QPL BibTeX Key:cgal:c-sspo2-06 User Manual Reference Manual |
|
| ||
2D ArrangementRon Wein, Efi Fogel, Baruch Zukerman, and Dan Halperin | ||
|
This package can be used to construct, maintain, alter, and display
arrangements in the plane. Once an arrangement is constructed, the
package can be used to obtain results of various queries on the
arrangement, such as point location. The package also includes generic
implementations of two algorithmic frameworks, that are, computing the
zone of an arrangement, and line-sweeping the plane, the arrangements
is embedded on. These frameworks are used in turn in the
implementations of other operations on arrangements. Computing the
overlay of two arrangements, for example, is based on the sweep-line
framework.
Arrangements and arrangement components can also be extended to store
additional data. An important extension stores the construction
history of the arrangement, such that it is possible to obtain the
originating curve of an arrangement subcurve.
|
Introduced in: CGAL 2.1 License: QPL BibTeX Key:cgal:wfzh-a2-06 User Manual Reference Manual |
|
2D Intersection of CurvesBaruch Zukerman and Ron Wein | ||
| This package provides three free functions implemented
based on the sweep-line paradigm: given a collection of input curves,
compute all intersection points, compute the set of subcurves that are
pairwise interior-disjoint induced by them, and check whether there
is at least one pair of curves among them that intersect in their
interior.
|
Introduced in: CGAL 2.4 Depends on: 2D Arrangements License: QPL BibTeX Key:cgal:wfz-ic2-06 User Manual Reference Manual |
|
2D Snap RoundingEli Packer | ||
|
Snap Rounding is a well known method for converting
arbitrary-precision arrangements of segments into a fixed-precision
representation. In the study of robust geometric computing, it can be
classified as a finite precision approximation technique. Iterated
Snap Rounding is a modification of Snap Rounding in which each vertex
is at least half-the-width-of-a-pixel away from any non-incident
edge. This package supports both methods.
|
Introduced in: CGAL 3.1 Depends on: Arrangements License: QPL BibTeX Key:cgal:p-sr2-06 User Manual Reference Manual |
|
| ||
2D TriangulationMariette Yvinec | ||
| This package allows to build and handle
various triangulations for point sets two dimensions.
Any CGAL triangulation covers the convex hull of its
vertices. Triangulations are build incrementally
and can be modified by insertion or removal of vertices.
They offer point location facilities.
The package provides plain triangulation (whose faces depend on the insertion order of the vertices) and Delaunay triangulations. Regular triangulations are also provided for sets of weighted points. Delaunay and regular triangulations offer nearest neighbor queries and primitives to build the dual Voronoi and power diagrams.
Finally, constrained and Delaunay contrained triangulations
allows to force some constrained segments to appear
as edges of the triangulation.
Several versions of constrained and Delaunay contrained triangulations
are provided: some of them handle intersections between input constraints
segment while others do not.
|
Introduced in: CGAL 0.9 Depends on: 2D Triangulation Data Structure License: QPL BibTeX Key:cgal:y-t2-06 User Manual Reference Manual |
|
2D Triangulation Data StructureSylvain Pion and Mariette Yvinec | ||
|
This package provides a data structure to store a two-dimensional
triangulation that has the topology of a two-dimensional sphere.
The package
acts as a container for the vertices and faces of the triangulation
and provides basic combinatorial operation on the triangulation.
|
Introduced in: CGAL 2.2 License: QPL BibTeX Key:cgal:py-tds2-06 User Manual Reference Manual |
|
3D TriangulationsSylvain Pion and Monique Teillaud | ||
|
This package allows to build and handle
triangulations for point sets in three dimensions.
Any CGAL triangulation covers the convex hull of its
vertices. Triangulations are build incrementally
and can be modified by insertion or removal of vertices.
They offer point location facilities.
The package provides plain triangulation (whose faces
depends on the insertion order of the vertices) and
Delaunay triangulations. Regular triangulations are
also provided for sets of weighted points.
Delaunay and regular
triangulations offer nearest neighbor queries
and primitives to build the dual Voronoi and power diagrams.
|
Introduced in: CGAL 2.1 License: QPL BibTeX Key:cgal:pt-t3-06 User Manual Reference Manual |
|
3D Triangulation Data StructureSylvain Pion and Monique Teillaud | ||
|
This package provides a data structure to store a three-dimensional
triangulation that has the topology of a three-dimensional sphere.
The package acts as a container for the vertices
and cells of the triangulation
and provides basic combinatorial operations on the triangulation.
|
Introduced in: CGAL 2.1 License: QPL BibTeX Key:cgal:pt-tds3-06 User Manual Reference Manual |
|
2D Alpha ShapesTran Kai Frank Da | ||
|
This package offers a data structure encoding the whole family of alpha-complexes
related to a given 2D Delaunay or regular triangulation. In particular, the data structure
allows to retrieve the alpha-complex for any alpha value, the whole spectrum of critical
alpha values and a filtration on the triangulation faces (this filtration is based on the first
alpha value for which each face is included on the alpha-complex).
|
Introduced in: CGAL 2.1 Depends on: 2D Triangulation License: QPL BibTeX Key:cgal:d-as2-06 User Manual Reference Manual |
|
3D Alpha ShapesTran Kai Frank Da and Mariette Yvinec | ||
| This package offers a data structure encoding the whole family of alpha-complexes
related to a given 3D Delaunay or regular triangulation. In particular, the data structure
allows to retrieve the alpha-complex for any alpha value, the whole spectrum of critical
alpha values and a filtration on the triangulation faces (this filtration is based on the first
alpha value for which each face is included on the alpha-complex).
|
Introduced in: CGAL 2.3 Depends on: 2D Triangulation License: QPL BibTeX Key:cgal:d-as3-06 User Manual Reference Manual |
|
| ||
2D Segment Delaunay GraphMenelaos Karavelas | ||
|
An algorithm for computing the dual of a Voronoi diagram of a set
of segments under the Euclidean metric. It is a generalization of the
standard Voronoi diagram for points. The algorithms provided are
dynamic.
|
Introduced in: CGAL 3.1 Depends on: 2D Triangulation Data Structure License: QPL BibTeX Key:cgal:k-sdg2-06 User Manual Reference Manual |
|
2D Apollonius Graphs (Delaunay Graphs of Disks)Menelaos Karavelas and Mariette Yvinec | ||
|
Algorithms for computing the Apollonius
graph in two dimensions. The Apollonius graph is the dual of the
Apollonius diagram, also known as the additively weighted Voronoi
diagram. The latter can be thought of as the Voronoi diagram of a set
of disks under the Euclidean metric, and it is a generalization of the
standard Voronoi diagram for points. The algorithms provided are
dynamic.
|
Introduced in: CGAL 3.0 Depends on: 2D Triangulation Data Structure License: QPL BibTeX Key:cgal:k-ag2-06 User Manual Reference Manual |
|
2D Voronoi Diagram AdaptorMenelaos Karavelas | ||
|
The 2D Voronoi diagram adaptor package provides an adaptor that adapts a
2-dimensional triangulated Delaunay graph to the corresponding a
Voronoi diagram, represented as a doubly connected edge list (DCEL)
data structure. The adaptor has the ability to automatically
eliminate, in a consistent manner, degenerate features of the Voronoi
diagram, that are artifacts of the requirement that Delaunay graphs
should be triangulated even in degenerate configurations. Depending on
the type of operations that the underlying Delaunay graph supports,
the adaptor allows for the incremental or dynamic construction of
Voronoi diagrams and can support point location queries.
|
Introduced in: CGAL 3.2 License: QPL BibTeX Key:cgal:k-vda2-06 User Manual Reference Manual |
|
| ||
2D Conforming Triangulations and MeshesLaurent Rineau | ||
|
This package implements a Delaunay refinement algorithm to construct
conforming triangulations and 2D meshes.
Conforming Delaunay triangulations are obtained from constrained Delaunay triangulations by refining constrained edges until they are Delaunay edges. Conforming Gabriel triangulations are obtained by further refining constrained edges until they become Gabriel edges.
The package provides also a 2D mesher that refines triangles
and constrained edges until user defined size and shape criteria on triangles
are satisfied.
The package can handle intersecting input constraints
and set no restriction on the angle formed
by two constraints sharing an endpoint.
|
Introduced in: CGAL 3.1 Depends on: 2D Delaunay Triangulation License: QPL User Manual Reference Manual |
|
3D Surface MesherLaurent Rineau and Mariette Yvinec | ||
|
This package provides functions to generate
surface meshes that interpolate
smooth surfaces. The meshing algorithm is based on Delaunay
refinement and provides some guarantees on the resulting mesh:
the user is able to control the size and shape of the mesh
elements and the accuracy of the surface approximation.
There is no restriction on the topology and number of components
of input surfaces. The surface mesher may also be used
for non smooth surfaces but without guarantee.
Currently, implementations
are provided for implicit surfaces described as the zero level set
of some function and surfaces described as a gray
level set in a three-dimensional image.
|
Introduced in: CGAL 3.2 License: QPL BibTeX Key:cgal:ry-sm2-06 User Manual Reference Manual |
|
3D Surface Subdivision MethodsLe-Jeng Andy Shiue | ||
|
Subdivision methods recursively refine a control mesh and generate
points approximating the limit surface. This package consists of four
popular subdivision methods and their refinement hosts. Supported
subdivision methods include Catmull-Clark, Loop, Doo-Sabin and sqrt(3)
subdivisions. Their respective refinement hosts are PQQ, PTQ, DQQ and sqrt(3) refinements. Variations of those methods
can be easily extended by substituting the geometry computation of the
refinement host.
|
Introduced in: CGAL 3.2 License: LGPL BibTeX Key:cgal:s-ssm2-06 User Manual Reference Manual |
|
Planar Parameterization of Triangulated Surface MeshesLaurent Saboret, Pierre Alliez and Bruno Lévy | ||
| Parameterizing a surface amounts to finding a one-to-one mapping from
a suitable domain to the surface. In this package, we focus on
triangulated surfaces that are homeomorphic to a disk and on piecewise
linear mappings into a planar domain. This package implements
some of the state-of-the-art surface mesh parameterization methods,
such as least squares conformal maps, discrete conformal map, discrete
authalic parameterization, Floater mean value coordinates or Tutte
barycentric mapping.
|
Introduced in: CGAL 3.2 Depends on: Solvers as OpenNL or Taucs. License: QPL BibTeX Key:cgal:sal-pptsm2-06 User Manual Reference Manual |
|
| ||
2D Search StructuresMatthias Bäsken | ||
|
This package supports circular, triangular, and isorectangular range search
queries as well as (k) nearest neighbor search queries on 2D point sets.
|
Introduced in: CGAL 2.1 Depends on: 2D Delaunay triangulation License: QPL BibTeX Key:cgal:b-ss2-06 User Manual Reference Manual |
|
Interval Skip ListAndreas Fabri | ||
| An interval skip list is a data strucure for finding all
intervals that contain a point, and for stabbing queries, that is for
answering the question whether a given point is contained in an
interval or not.
|
Introduced in: CGAL 3.0 License: QPL BibTeX Key:cgal:f-isl-06 User Manual Reference Manual |
|
dD Spatial SearchingHans Tangelder and Andreas Fabri | ||
|
This package implements exact and approximate distance browsing by
providing exact and approximate algorithms for range searching,
k-nearest and k-furthest neighbor searching, as well as incremental
nearest and incremental furthest neighbor searching, where the
query items are points in dD Euclidean space.
|
Introduced in: CGAL 3.0 License: QPL BibTeX Key:cgal:tf-ssd-06 User Manual Reference Manual |
|
dD Range and Segment TreesGabriele Neyer | ||
| Range and segment trees allow to perform window queries on point
sets, and to enumerate all ranges enclosing a query point. The provided data structures
are static and they are optimized for fast queries.
|
Introduced in: CGAL 0.9 License: QPL BibTeX Key:cgal:n-rstd-06 User Manual Reference Manual |
|
Intersecting Sequences of dD Iso-oriented BoxesLutz Kettner, Andreas Meyer, and Afra Zomorodian | ||
|
An efficient algorithm for finding all intersecting pairs for large
numbers of iso-oriented boxes, in order to apply a user defined callback
on them. Typically these boxes will be bounding
boxes of more complicated geometries. The algorithm is useful for (self-) intersection
tests of surfaces etc.
|
Introduced in: CGAL 3.1 License: QPL BibTeX Key:cgal:kmz-isiobd-06 User Manual Reference Manual |
|
| ||
Geometric OptimisationKaspar Fischer, Bernd Gärtner, Thomas Herrmann, Michael Hoffmann, Eli Packer, and Sven Schönherr | ||
|
This package provides algorithms for computing bounding volumes, inscribed areas and polytope distances.
The algorithms for bounding volumes for point sets in d-dimensional space are: the smallest enclosing sphere, annulus, ellipsoid, or strip. For 2-dimensional space, a number of additional volumes (rectangles, parallelograms, axis-aligned rectangles) are available. The smallest enclosing sphere algorithm can also be applied on a set of d-dimensional spheres. The algorithms for computing inscribed areas are: the largest inscribed k-gon (area or perimeter) of a convex point set and the largest inscribed rectangle. The polytope distance algorithm computes the distance between the convex hulls of two point sets in d-dimensional space, without explicitely constructing the convex hulls.
Finally this package offers a matrix search framework, which is
the underlying machinery of some of the algorithms of this package.
|
Introduced in: CGAL 1.1 License: QPL BibTeX Key:cgal:fghhps-go-06 User Manual Reference Manual |
|
Principal Component AnalysisPierre Alliez and Sylvain Pion | ||
|
This package provides functions to compute global informations on the
shape of a set of 2D or 3D objects such as points. It provides the
computation of axis-aligned bounding boxes, centroids of point sets,
barycenters of weighted point sets, as well as linear least squares
fitting for point sets in 2D, and point sets as well as triangle sets
in 3D.
|
Introduced in: CGAL 3.2 License: QPL BibTeX Key:cgal:ap-pcad-06 User Manual Reference Manual |
|
| ||
2D and Surface Function InterpolationJulia Flötotto | ||
|
This package implements different methods for scattered data
interpolation: Given measures of a function on a set of discrete data
points, the task is to interpolate this function on an arbitrary query
point. The package further offers functions for natural neighbor
interpolation.
|
Introduced in: CGAL 3.1 License: QPL BibTeX Key:cgal:f-i-06 User Manual Reference Manual |
|
2D Placement of StreamlinesAbdelkrim Mebarki | ||
|
Visualizing vector fields is important for many application domains. A
good way to do it is to generate streamlines that describe the flow
behaviour. This package implements the "Farthest Point Seeding"
algorithm for placing streamlines in 2D vector fields. It generates a
list of streamlines corresponding to an input flow using a specified
separating distance. The algorithm uses a Delaunay triangulation to
model objects and adress different queries, and relies on choosing the
centers of the biggest empty circles to start the integration of the
streamlines.
|
Introduced in: CGAL 3.2 Depends on: 2D Delaunay triangulation License: QPL BibTeX Key:cgal:m-ps-06 User Manual Reference Manual |
|
| ||
Kinetic Data StructuresDaniel Russel | ||
| Kinetic data structures allow combinatorial structures
to be maintained as the primitives move. The package provides
implementations of kinetic data structures for Delaunay triangulations
in two and three dimensions, sorting of points in one dimension and
regular triangulations in three dimensions. The package supports exact
or inexact operations on primitives which move along polynomial
trajectories.
|
Introduced in: CGAL 3.2 Depends on: KDS Framework. Two dimensional visualization depends on Qt, three dimensional visualization depends on Coin. License: LGPL User Manual Reference Manual |
|
Kinetic FrameworkDaniel Russel | ||
|
Kinetic data structures allow combinatorial geometric structures to be
maintained as the primitives move. The package provides a framework to
ease implementing and debugging kinetic data structures. The package
supports exact or inexact operations on primitives which move along
polynomial trajectories.
|
Introduced in: CGAL 3.2 Depends on: Two dimensional visualization depends on Qt, three dimensional visualization depends on Coin. User Manual Reference Manual |
|