CGAL Interview Questions & Answers

5 avg. rating (100% score) - 1 votes

CGAL Interview Questions

    1. Question 1. What Is Cgal?

      Answer :

      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.

    2. Question 2. How Do You Pronounce Cgal?

      Answer :

      CGAL is pronounced like "seagull" in English, or "cigale" in French.

    3. Question 3. Are There Example/demo Programs Somewhere?

      Answer :

      Yes. The CGAL distribution includes two directories containing example programs: <CGALROOT>/examples/ and <CGALROOT>/demo/. Here you find the source code and make files 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.

    4. Question 4. Where Do I Find Old Releases Of Cgal?

      Answer :

      All released files as well as manuals are available in the release section of the CGAL GitHub repository.

    5. Question 5. Is Visual C++ 6 Supported?

      Answer :

      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.

    6. Question 6. Which Versions Of Qt Are Supported?

      Answer :

      All the demos use Qt5. The 2D demos are based on the Graphics View framework, the 3D demos on the libQGLViewer.

    7. Question 7. Why Do I Get Errors When Using Compiler Optimization On Mac Os X?

      Answer :

      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

    8. Question 8. How To Reduce Compilation Time Of Programs Using Cgal?

      Answer :

      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.

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

    9. Question 9. What Is The Difference Between A Predicate And A Construction And Why Does This Make A Difference For The Robustness Of My Program?

      Answer :

      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 round offs, 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.

    10. Question 10. 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?

      Answer :

      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.

    11. Question 11. I Want To Convert A Number Type, E.g. Ft To Double. How Do I Do That?

      Answer :

      All number types used by CGAL provide a conversion function called CGAL::to double. 

      For example: double x = CGAL::to double (p.x ()).

    12. Question 12. My Program Reports Microsoft C++ Exception: Cgal::uncertain_conversion_exception At Memory Location ... Why?

      Answer :

      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.

    13. Question 13. How Can I Do Boolean Operations On Polygons?

      Answer :

      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.

    14. Question 14. How Do I Compute The Triangulation Of The Interior Of A Polygon?

      Answer :

      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.

    15. Question 15. Is The Outer Ccb (counterclockwise Boundary) Of A Face Of An Arrangement A Simple Polygon?

      Answer :

      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.

    16. Question 16. Boolean Set Operations: How Can I Compute Them?

      Answer :

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

    17. Question 17. How Can I Attach Information To A Vertex, A Half Edge, Or A Face?

      Answer :

      You need to change the DCEL, so that its vertex, half edge, 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 Arrangement Dcel, which represents the extended DCEL and instantiate CGAL::Arrangement On Surface 2 <Traits, Dcel> properly.

    18. Question 18. Why Is There No Transform Function For Polyhedron_3?

      Answer :

      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);

Popular Interview Questions

All Interview Questions

All Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Tutorial