Frequently Asked Questions

• General Information
  • 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?
• Installation and Compilation
  • 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?
  • Is Qt3/Qt4 supported?
  • Why do I get errors when using compiler optimization on Mac OS X?
  • How to reduce compilation time of programs using CGAL ?
• Kernels and Number Types
  • 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?
• Polygons
  • How can I do boolean operations on polygons?
  • How do I compute the triangulation of the interior of a polygon?
• Planar Maps and Arrangements
  • 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?
• Polyhedral Surfaces
  • 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?

• 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 CGAL-3.4, all released files as well as manuals are on the INRIA Gforge.

  This page shows the releases of CGAL before CGAL-3.4.

• 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.mpi-sb.mpg.de/pub/outgoing/CGAL/debian wheezy main contrib non-free
  deb-src ftp://ftp.mpi-sb.mpg.de/pub/outgoing/CGAL/debian wheezy main contrib non-free
  

  to /etc/apt/sources.list (for jessie simply replace "wheezy" by "jessie"). The packages are called libcgal10, libcgal-dev, libcgal-qt4-10, libcgal-qt4-dev, libcgal-demo and libcgal-ipelets. Packages for older CGAL versions are available at ftp://ftp.mpi-sb.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/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/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/gcc-4.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.

• 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 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]

• 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 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;.

• 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.

• 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 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.

• 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.

• 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 non-simple polygon even if the outer CCB represents one due to numerical errors.

• Boolean set operations: How can I compute them?

  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.

• 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.
  
  

  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. When the curves to be inserted into an arrangement are available in advance (as opposed to supplied on-line), it is advised to use the more efficient aggregate (sweep-based) insertion over the incremental insertion; e.g., insert_curves().
  8. 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.
  9. 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.
  10. 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.
• 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.

• 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 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.