Frequently Asked Questions

• What is CGAL?
• Who is involved in CGAL?
• How did you make the CGAL logo?
• How do you pronounce CGAL?
• Are there example/demo programs somewhere?
• Is there a mailing list for users?
• I think I have encountered a bug in CGAL. What should I do?
• Where do I find old releases of CGAL?

• How do I install CGAL?
• How do I compile a program using CGAL?
• Are there packages for Debian / Ubuntu available?
• How do I compile and execute the demos and examples on Debian / Ubuntu?
• Is VC++ 6 supported?
• Which versions of Qt are supported?
• Why do I get errors when using compiler optimization on Mac OS X?
• How to reduce compilation time of programs using CGAL ?

• CGAL offers many different kernels templates. Which is the right one for my program?
• What is the right number type for my program?
• What is the difference between a predicate and a construction and why does this make a difference for the robustness of my program?
• I am using double (or float or ...) as my number type and get assertion failures or incorrect output. Is this a bug in CGAL?
• 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?
• I want to convert a number type, e.g. FT to double. How do I do that?
• My program reports "Microsoft C++ exception: CGAL::Uncertain_conversion_exception at memory location ...". Why?

• How can I do boolean operations on polygons?
• How do I compute the triangulation of the interior of a polygon?

• Is the outer CCB (counterclockwise boundary) of a face of an arrangement a SIMPLE polygon?
• Boolean set operations: How can I compute them?
• How can I accelerate the work with arrangements?
• How can I attach information to a vertex, a halfedge, or a face?

• Why is there no transform function for Polyhedron_3?
• Where can I find examples of polyhedral surfaces?
• How can I compute the plane equation (normal) for a facet in a polyhedral surface?

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 (bookworm) and Debian testing (trixie) might not contain the latest version of CGAL. In that case, add

   deb http://debian.cgal.org bookworm main
   deb-src http://debian.cgal.org bookworm main

   deb http://debian.cgal.org trixie main
   deb-src http://debian.cgal.org trixie main

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:

• 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 in the early steps of the development cycle of your programs.
• Regroup translation units : if your program is composed of many small translation units to be compiled and linked, try to reduce their numbers by merging them. This traditional style for C programs is actually 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. This 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 feature.

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:

• S. Schirra. Robustness and precision issues in geometric computation. Research Report MPI-I-98-004, Max Planck Institute for Computer Science, 1998. [ps-file] 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, 40(1):61-78, 2008. [html]

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.

1. Passing x-monotone curves that are pairwise disjoint in their interior to the overloaded insertion-function insert() is more efficient (in running time) and less demanding (in traits-class functionality) than passing general curves.
2. 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).

3. Prior knowledge of the combinatorial structure of the arrangement can be used to accelerate operations that insert x-monotone 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 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.

4. The main trade-off among point-location 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.
5. If point-location queries are not performed frequently, but other modifying functions, such as removing, splitting, or merging edges are, then using a point-location strategy that does not require the maintenance of auxiliary structures, such as the the naive or walk strategies, is preferable.
6. There is a trade-off 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.
7. 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.
8. Maintaining short bit-lengths 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.
9. 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 combinatorial-function calls or increased space consumption. For example, repetition of geometric-function calls could be avoided by storing the results obtained by the first call, and reusing them when needed.

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.