CGAL is an acronym for the Computational Geometry Algorithms Library. It is at the same time the short name for the CGAL Open Source Project. The goal of the project is to provide easy access to efficient and reliable geometric algorithms to users in industry and academia.
For more information see the project members and the partners and funding sources pages.
See this page for information about the construction of the CGAL logo.
CGAL is pronounced like "seagull" in English, or "cigale" in French.
Yes. The CGAL distribution includes two directories containing example programs: <CGALROOT>/examples/ and <CGALROOT>/demo/. Here you find the source code and makefiles for these programs. The current CGAL manual provides a nice overview of packages from where you can also get the demo source code and Windows executables.
Yes. See the web page describing the CGAL mailing lists.
Please follow the bug reporting instructions.
All released files as well as manuals are available in the release section of the CGAL GitHub repository.
Please have a look at the Installation Guide.
Please have a look at the Installation Guide.
Packages for Debian unstable (sid) are available from the official Debian repository. Debian stable (bullseye) and Debian testing (bookworm) might not contain the latest version of CGAL. In that case, add
deb http://debian.cgal.org bullseye main deb-src http://debian.cgal.org bullseye mainor
deb http://debian.cgal.org bookworm main deb-src http://debian.cgal.org bookworm mainto /etc/apt/sources.list (note that you only need the pair of lines corresponding to the release you are using) and make sure that the package apt-transport-https is installed. The packages are called libcgal-dev, libcgal-qt5-dev, libcgal-demo and libcgal-ipelets. Packages for older CGAL versions are available at http://debian.cgal.org/archive or from the official Debian archive.
The Ubuntu repository also contains packages for CGAL, but not always for the latest version. The Debian packages might work on Ubuntu as well.
Install the CGAL packages (see the preceding entry). Unpack the examples and demos in some directory, e.g., $HOME/cgal.
$ mkdir $HOME/cgal $ cd $HOME/cgal $ tar xzf /usr/share/doc/libcgal-demo/examples.tar.gz $ tar xzf /usr/share/doc/libcgal-demo/demo.tar.gz
Configure and build the desired examples or demos, e.g., the demos of Triangulation_2.
$ cd demo/Triangulation_2 $ cmake . $ make
Then run the demos.
$ ./Constrained_delaunay_triangulation_2 & $ ./Delaunay_triangulation_2 & $ ./Regular_triangulation_2 &
See also /usr/share/doc/libcgal-dev/README.Debian for more information.
No, it is not and there is no hope that you can make the necessary fixes yourself to get it running with this compiler. The issue lies in the fact that VC6 did not support the template mechanism well enough. The solution is to either use an old version of CGAL or to upgrade to newer versions of the Microsoft compiler.
All the demos use Qt5. The 2D demos are based on the GraphicsView framework, the 3D demos on the libQGLViewer.
The default compiler on Mac OS X is g++ 4.0 (at least on Tiger and Leopard). It has some bugs that are unfortunately encountered by some programs using CGAL when optimizing. We recommend that you use a more recent version of g++, such as g++ 4.2, which you can get by upgrading to the latest XCode, or using Fink. You can then select it by passing the following flags to CMake : -DCMAKE_CXX_COMPILER=/usr/bin/g++-4.2 -DCMAKE_C_COMPILER=/usr/bin/gcc-4.2
CGAL is heavily using C++ templates, and this has an impact on compilation speed. Here are some hints that can help speed up compilation of programs using CGAL:
-g
if you can.
Indeed, generating debug information can be very costly for
template instantiations, both in terms of running time and
memory usage by the compiler tool chain.
-O2
when
you do not need them, such as in the early steps of the development cycle of
your programs.
There is no universal answer to this question (which is why there are different kernels in the first place). The subsection Choosing a Kernel of section Kernel Representations in the manual provides some guidance.
There is no universal answer to this question either (which is why our kernels are templates). The answer depends, among other things, on how important robustness is in comparison to speed, whether your program involves the construction of new objects or simply predicate evaluation and comparisons, and on the size of the input numbers. The section Choosing a kernel in the kernel manual should provide some guidance.
Geometric predicates are used to test properties of geometric objects and return, for example, a boolean value (true or false). An example of predicate would be testing whether a point lies inside a sphere is a predicate as is testing whether three points form a left turn, right turn or are collinear. A geometric construction creates a new geometric object, such as the line through two different points or the center of a circle defined by a certain set of points.
Constructions are problematic with respect to robustness since the
constructed object has to be stored in a particular representation.
If this representation does not capture the object's properties
sufficiently, due, for example, to limited precision roundoffs, the
correctness of subsequent computations with this object cannot be
guaranteed. However, providing exact constructions is currently
less efficient, which is basically the reason why the kernel
CGAL::Exact_predicates_inexact_constructions_kernel exists;
double is used as the representation
type in this case.
While it may well be a bug in CGAL, with such number types you are more likely to suffer from a problem with robustness. In particular, using the kernel CGAL::Cartesian with number types double or float is likely to give you wrong results.
The problem is that double and float are inexact number types, and as such they cannot guarantee exact results in all cases. Worse than this, small roundoff errors can have large consequences, up to the point where an algorithm crashes. Algorithms in geometric computing are particularly sensitive in this respect.
This was the bad news. The good news is that CGAL provides an easy way for programmers to get around the limitations of inexact number types like double and float, through its templated kernels. See also our page on The Exact Computation Paradigm.
A solution that always works (although it might slow down the algorithm considerably) is to use an exact multi-precision number type such as CGAL::Quotient<CGAL::MP_Float> or CGAL::Gmpq, instead of double or float.
If your program does not involve the construction of new objects from the input data (such as the intersection of two objects, or the center of a sphere defined by the input objects), the CGAL::Exact_predicates_inexact_constructions_kernel kernel provides a nice and fast way to use exact predicates together with an inexact number type such as double for constructions.
When your program uses constructions of new objects, you can still
speed things up by using the number type
CGAL::Lazy_exact_nt
on top of an exact number type.
Good references that discuss the robustness problem in geometric computing are:
Our kernel concept is representation-independent.
There is no assumption on how a Point_3, for example, is represented. In
particular, it need not be represented by Cartesian coordinates. Thus
writing code that relies on being able to change these coordinates may
lead to inefficient code. Our basic library algorithms are designed
around the predicates that operate on the geometric objects and do not
require this mutability.
Non-modifiability also makes the underlying handle-rep scheme used (by
default) to allocate, copy, etc., CGAL objects somewhat easier.
We recognize, however, that users may want this flexibility and thus
are working on providing mutable kernel objects.
The only way to do this currently is to construct a new point and assign
it to the old one : use p = Point_2(p.x(), p.y()+1);
as if you would like to do p.y() += 1;
.
All number types used by CGAL provide a conversion function called
CGAL::to_double. For example: double x = CGAL::to_double(p.x());
.
This is an internal exception, which is caught by CGAL code. Users are not supposed to be concerned by this, it is correct behaviour, except that it sometimes shows up, for example when debugging. It is safe to ignore these exceptions. See here for more information on how to disable the warning.
There are two means provided in CGAL for performing boolean operations on polygons in the plane. One is provided via the class template Nef_polyhedron_2. The other is provided via the Boolean Set-Operations package. There are demo programs illustrating boolean operations using both of these. The manual pages provide more information regarding, for example, additional functionality available with these class templates. See also the section on this page related to planar maps and boolean operations.
For this, one should use one of the constrained triangulation classes: Constrained_triangulation_2, Constrained_Delaunay_triangulation_2 or Constrained_triangulation_plus_2. The edges of the polygon should be input as constraints to the triangulation. The constructed triangulation will be a triangulation of the whole convex hull, but including as edges the edges of the polygon which are marked as constrained edges. From there it is easy to output the faces inside (resp. outside) the polygon or to mark these faces as such. See ($CGALROOT)/demo/Triangulation_2/constrained.cpp for an example.
The outer CCB of a face of an arrangement is NOT necessarily a simple polygon. Consider the case where there are "inner antennas"; imagine a face represented by a simple polygon and a vertex v on the outer CCB of the face. Now connect a component that starts and ends at v and lies in the interior of the face (one edge incident at v suffices).
Mind that if you are using an inexact number type you might get a non-simple polygon even if the outer CCB represents one due to numerical errors.
The package Regularized Boolean Set-Operation 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.
Ordinary Boolean set-operations that operate on (linear) polygons, which distinguish between the interior and the boundary of a polygon, are supported by the Planar Nef Polyhedra package.
For intersections of the interiors of polygons also refer to the polygon intersection demo program, which is also available in the demo directory of the CGAL distribution.
Before the specific tips, we remind you that compiling
programs with debug flags disabled and with optimization flags
enabled significantly reduces the running time.
insert()
is more efficient (in running time) and less demanding (in
traits-class functionality) than passing general curves.
Arr_non_caching_segment_traits_2
rather then the default one
(Arr_segment_traits_2
).
If the segments may intersect each other, the default
traits class
Arr_segment_traits_2
can be safely used with the somehow limited number type
Quotient<MP_float>.
On rare occasions the traits class
Arr_non_caching_segment_traits_2
exhibits slightly better performance than the default one
(Arr_segment_traits_2
)
even when the segments intersect each other, due to the
small overhead of the latter (optimized) traits class.
(For example, when the the so called LEDA
rational kernel is used).
insert_in_face_interior()
,
insert_from_left_vertex()
,
insert_from_right_vertex()
, and
insert_at_vertices()
can be used according to the available information. These
functions hardly involve any geometric operations, if at
all. They accept topologically related parameters, and use
them to operate directly on the DCEL records,
thus saving algebraic operations, which are especially
expensive when high-degree curves are involved.
A polygon, represented by a list of segments along its
boundary, can be inserted into an empty arrangement as
follows. First, one segment is inserted using
insert_in_face_interior()
into the unbounded face. Then, a segment with a common end
point is inserted using either
insert_from_left_vertex()
or
insert_from_right_vertex()
,
and so on with the rest of the segments except for the last,
which is inserted using
insert_at_vertices()
,
as both endpoints of which are the mapping of known
vertices.
You need to change the DCEL, so that its vertex, halfedge, and/or face types will contain the information you want. The package facilitates the coding necessary to achieve this task. Refer to Section Extending the DCEL for further details.
You have to supply your model of the concept
ArrangementDcel, which represents the extended
DCEL, and instantiate
CGAL::Arrangement_on_surface_2<Traits,Dcel>
properly.
If Face is the only feature type you need to extend, refer to the example at <CGALROOT>/examples/Arrangement_on_surface_2/face_extension.cpp. The example <CGALROOT>/examples/Arrangement_on_surface_2/ex_dcel_extension.cpp demonstrates how to extend all the feature types simultaneously.
The polyhedral surface (and other data structures in the Basic Library) can have added geometric attributes by the user that would make a generally working transform function for affine transformations difficult to provide in the class, and on the other hand it is easy for a user to apply standard generic algorithms for that purpose, for example, to transform the points stored in a polyhedral surface P with a CGAL affine transformation given in A (which is a proper STL functor) one can write:
std::transform( P.points_begin(), P.points_end(), P.points_begin(), A);
The plane() member function in facets does not compute the plane equation, it is only the access to function to the variable stored in facets.
The plane equations must be computed separately by the user. There is currently no general method available in CGAL that computes the plane equations, since the requirements could vary considerably with the number type chosen or the possible knowledge of the facet types (convex, triangles, ...). Assuming strictly convex facets and exact arithmetic (or the willingness to live with rounding errors), the example <CGALROOT>/examples/Polyhedron/polyhedron_prog_normals.cpp computes these plane equations, see also the User Manual for polyhedral surfaces.
For inexact double arithmetic and/or non-convex facets one might consider the method of Newell which computes the least-square-fit normal of the plane equation, see for example Filippo Tampieri: Newell's Method for Computing the Plane Equation of a Polygon. Graphics Gems III, David Kirk (Ed.), AP Professional, 1992.