Frequently Asked Questions
General Information

What is CGAL?
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.

Who is involved in CGAL?
For more information see the project members and the
partners and funding sources pages.

How did you make the CGAL logo?
See here for information about the CGAL logo construction.

How do you pronounce CGAL?
CGAL is pronounced like "seagull" in English, or "cigale" in French.

Are there example/demo programs somewhere?
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.

Is there a mailing list for users?
Yes. See the web page describing the CGAL mailing lists.

I think I have encountered a bug in CGAL. What should I do?
Please follow the bug reporting instructions.

Where do I find old releases of CGAL?
Since CGAL3.4, all released files as well as manuals are on
the INRIA
Gforge.
This page shows the
releases of CGAL before CGAL3.4.
Installation and Compilation

How do I install CGAL?
Please have a look at the Installation Guide.

How do I compile a program using CGAL?
Please have a look at the Installation Guide.

Are there packages for Debian / Ubuntu available?
Packages for Debian unstable (sid) are available from the official
Debian repository. Debian testing (jessie) and Debian stable (wheezy)
might not contain the latest version of CGAL. In that case, add
deb ftp://ftp.mpisb.mpg.de/pub/outgoing/CGAL/debian wheezy main contrib nonfree
debsrc ftp://ftp.mpisb.mpg.de/pub/outgoing/CGAL/debian wheezy main contrib nonfree
to /etc/apt/sources.list (for jessie simply replace
"wheezy" by "jessie"). The packages are called libcgal10,
libcgaldev, libcgalqt410, libcgalqt4dev,
libcgaldemo and libcgalipelets.
Packages for older CGAL versions are available at
ftp://ftp.mpisb.mpg.de/pub/outgoing/CGAL/debian/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.

How do I compile and execute the demos and examples on Debian / Ubuntu?
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/libcgaldemo/examples.tar.gz
$ tar xzf /usr/share/doc/libcgaldemo/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/libcgal10/README.Debian for more information.

Is Visual C++ 6 supported?
No it isn't and there is no hope that you can make the necessary
fixes yourself to get it running with this compiler.
The fact is that VC6 didn't support the template mechanism good
enough. The solution is to either use an old version of CGAL,
or to upgrade to newer versions of the Microsoft compiler.

Is Qt3/Qt4 supported?
Some CGAL demos use Qt3 together with a widget class developed by the CGAL project.
We discourage to use it, and already removed it from the documentation.
More recent demos use Qt4, the 2D demos are based on the
GraphicsView framework,
the 3D demos on the libQGLViewer.

Why do I get errors when using compiler optimization on Mac OS X?
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/gcc4.2

How to reduce compilation time of programs using CGAL ?
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.
 Remove compiler debugging options like
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.
 Remove compiler optimization options like
O2 , when
you do not need them, such as early in the development cycle of
your programs.
 Regroup translation units : if your program is composed of
lots of small translation units to be compiled and linked, try to
reduce their numbers by merging them. This traditional style
for C programs is very slow for programs heavily using C++ templates.
Regrouping them reduces the time spent by the compiler to parse
the header files, and avoids redundant template instantiations.
 Precompile header files : some compilers, such as GCC, provide
a feature named
precompiled headers. It can be mostly useful if you can regroup in a
single header file most of the header files that you use, together with
most template instantiations. Refer to your compiler documentation to use this.
Kernels and Number Types

CGAL offers many different kernel templates. Which is the right
one for my program?
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.

What is the right number type for my program?
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, the size of the input numbers. The
section on
choosing a kernel in the kernel manual should provide some guidance.

What is the difference between a predicate and a construction and
why does this make a difference for the robustness of my program?
Geometric predicates are used to test properties of geometric objects
and return, for example, a boolean value (true or false). For
example, 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 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.

I am using double (or float or ...) as my number
type
and get assertion failures or incorrect output. Is this a bug in CGAL?
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 CGAL Philosophy.
A solution that always works (although it might slow down the algorithm
considerably) is to use an exact multiprecision 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
 S. Schirra. Robustness and precision issues in geometric
computation. Research Report MPII98004, Max Planck
Institute for Computer Science, 1998.
[psfile]
Revised version of: Robustness and precision issues in
geometric computations. Ch 9, in M. van Kreveld et al.
(eds.), Algorithmic Foundations of Geographic Information
Systems, LNCS 1340, Springer, 1997.
 S. Schirra. Robustness and precision issues in geometric
computation. in J.R. Sack and J. Urrutia (eds.),
Handbook of Computational Geometry Chapter 14,
Elsevier Science, 1999
 Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra, and
Chee Yap. Classroom Examples of Robustness Problems in
Geometric Computations, Computational Geometry: Theory and
Algorithms, to appear. [html]

I want to modify the coordinates of a point, or the endpoints of a
segment, but the CGAL kernel does not seem to support that. Why?
Our kernel concept is representationindependent.
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.
Nonmodifiability also makes the underlying handlerep 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; .

I want to convert a number type, e.g. FT to double.
How do I do that?
All number types used by CGAL provide a conversion function called
CGAL::to_double. For example: double x = CGAL::to_double(p.x());.

My program reports "Microsoft C++ exception: CGAL::Uncertain_conversion_exception at memory location ...". Why?
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.
Polygons

How can I do boolean operations on polygons?
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 SetOperations 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.

How do I compute the triangulation of the interior of a polygon?
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.
Planar Maps and Arrangements

Is the outer CCB (counterclockwise boundary) of a face of an
arrangement a SIMPLE polygon?
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 nonsimple polygon even if the outer CCB represents one
due to numerical errors.

Boolean set operations: How can I compute them?
The package
Regularized Boolean SetOperation
consists of the implementation of Boolean setoperations on
point sets bounded by weakly xmonotone curves in
2dimensional Euclidean space. In particular, it contains the
implementation of regularized Boolean setoperations,
intersection predicates, and point containment predicates.
Ordinary Boolean setoperations 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.

How can I accelerate the work with arrangements?
Before the specific tips, we remind you that compiling
programs with debug flags disabled and with optimization flags
enabled significantly reduces the running time.
 Passing xmonotone curves that are pairwise
disjoint in their interior to the overloaded insertionfunction
insert()
is more efficient (in running time) and less demanding (in
traitsclass functionality) than passing general curves.
 When the curves to be inserted into an arrangement are
segments that are pairwise disjoint in their interior, it
is more efficient to use the traits class
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).
 Prior knowledge of the combinatorial structure of the
arrangement can be used to accelerate operations that insert
xmonotone curves, whose interior is disjoint
from existing edges and vertices of the arrangement. The
specialized insertion functions, i.e.,
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 highdegree 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.
 The main tradeoff among pointlocation strategies, is
between time and storage. Using the
naive
or
walk
strategies, for example, takes more query time but does not
require preprocessing or maintenance of auxiliary structures
and saves storage space.
 If pointlocation queries are not performed frequently,
but other modifying functions, such as removing, splitting,
or merging edges are, then using a pointlocation strategy
that does not require the maintenance of auxiliary
structures, such as the
the
naive
or
walk
strategies, is preferable.
 There is a tradeoff between two modes of the
RIC
strategy that enables the user to choose whether
preprocessing should be performed or not. If preprocessing
is not used, the creation of the structure is
faster. However, for some input sequences the structure
might be unbalanced and therefore queries and updates might
take longer, especially, if many removal and split
operations are performed.
 When the curves to be inserted into an arrangement are
available in advance (as opposed to supplied online), it is
advised to use the more efficient aggregate (sweepbased)
insertion over the incremental insertion; e.g.,
insert_curves() .
 The various traits classes should be instantiated with
an exact number type to ensure robustness, when the input of
the operations to be carried out might be degenerate,
although inexact number types could be used at the user's
own risk.
 Maintaining short bitlengths of coordinate
representations may drastically decrease the time
consumption of arithmetic operations on the coordinates.
This can be achieved by caching certain information or
normalization (of rational numbers). However, both solutions
should be used cautiously, as the former may lead to an
undue space consumption, and indiscriminate normalization
may considerably slow down the overall process.
 Geometric functions (e.g., traits methods) dominate the
time consumption of most operations. Thus, calls to such
function should be avoided or at least their number should
be decreased, perhaps at the expense of increased
combinatorialfunction calls or increased space
consumption. For example, repetition of geometricfunction
calls could be avoided by storing the results obtained by
the first call, and reusing them when needed.

How can I attach information to a vertex, a halfedge, or a face?
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.
Polyhedral Surfaces

Why is there no transform function for
Polyhedron_3?
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);

Where can I find examples of polyhedral surfaces?
We have support for the Object File Format (OFF) as used by
Geomview. The
Geomview distribution contains several example objects. The
CGAL distribution contains in examples/Polyhedron_IO/
a few example objects and example programs around the file IO
support for polyhedral surfaces. Among them is a file converter
iv2off.cpp reading Inventor or VRML 1.0 files
extracting IndexedFaceSet nodes (in a rather crude
fashion, but it may still be useful). Another converter is
located in demo/Polyhedron_IO/ reading geometry
files in Viewpoint Data Labs mesh format, see http://www.viewpoint.com/
for its description and for examples.
Another source for many objects in various formats
is the
3D Cafe. Although a bit outdated, another
source of references to geometric models and other test
data sets is the
CGAL Workpackage 4, Report 2, Fall 1997.
The easiest solution to read and write polyhedrons in OFF is
to include CGAL/IO/Polyhedron_iostream.h and use the
standard stream operators with a CGAL::Polyhedron_3.

How can I compute the plane equation (normal) for a facet
in a polyhedral surface?
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 nonconvex facets one
might consider the method of Newell which computes the
leastsquarefit 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.
