|
CGAL 4.14 - Manual
|
|
CGAL 4.14 - Manual
|
The goal of the CGAL Open Source Project is to provide easy access to efficient and reliable geometric algorithms in the form of a C++ library. CGAL is used in various areas needing geometric computation, such as: computer graphics, scientific visualization, computer aided design and modeling, geographic information systems, molecular biology, medical imaging, robotics and motion planning, mesh generation, numerical methods...
Work on CGAL has been supported in the past by esprit iv projects 21957 (CGAL) and 28155 (GALIA).
The primary design goals of CGAL are described in [4]
A library component is correct if it behaves according to its specification. Basically, correctness is therefore a matter of verification that documentation and implementation coincide. In a modularized program the correctness of a module is determined by its own correctness and the correctness of all the modules it depends on. Clearly, in order to get correct results, correct algorithms and data structures must be used.
Exactness should not be confused with correctness in the sense of reliability. There is nothing wrong with algorithms computing approximate solutions instead of exact solutions, as long as their behavior is clearly documented and they do behave as specified. Also, an algorithm handling only non-degenerate cases can be correct with respect to its specification, although in CGAL we would like to provide algorithms handling degeneracies.
A design goal particularly relevant for the implementation of geometric algorithms is robustness. Many implementations of geometric algorithms lack robustness because of precision problems; see Chapter Robustness Issues for a discussion of robustness issues within CGAL.
The different needs of the potential application areas demand flexibility in the library. Four sub-issues of flexibility can be identified.
Modularity.
A clear structuring of CGAL into modules with as few dependencies as possible helps a user in learning and using CGAL, since the overall structure can be grasped more easily and the focus can be narrowed to those modules that are actually of interest.
Adaptability.
CGAL might be used in an already established environment with geometric classes and algorithms in which case the modules will most probably need adaptation before they can be used.
Extensibility.
Not all wishes can be fulfilled with CGAL. Users may want to extend the library. It should be possible, and in fact desirable, to integrate new classes and algorithms into CGAL.
Openness.
CGAL should be open to coexist with other libraries, or better, to work together with other libraries and programs. The C++ Standard [3]
defines with the C++ Standard Library a common foundation for all C++ platforms. So it is easy and natural to gain openness by following this standard. There are important libraries outside the standard, and CGAL should be easily adaptable to them as well.
Many different qualities can contribute to the ease of use of a library. Which qualities are most important differs according to the experience of the user. The above-mentioned correctness and robustness issues are among these qualities. Of general importance is the length of time required before the library becomes useful. Another issue is the number of new concepts and exceptions to general rules that must be learned and remembered.
Ease of use tends to conflict with flexibility, but in many situations a solution can be found. The flexibility of CGAL should not distract a novice who takes the first steps with CGAL.
Uniformity.
A uniform look and feel of the design in CGAL will help in learning and memorizing. A concept once learned should be applicable in all places where one would wish to apply it. A function name once learned for a specific class should not be named differently for another class.
CGAL is based in many places on concepts borrowed from STL (Standard Template Library) or the other parts of the C++ Standard Library. An example is the use of streams and stream operators in CGAL. Another example is the use of container classes and algorithms from the STL. So these concepts should be used uniformly.
During the past few years, CGAL has moved towards using on concepts and ideas from the boost libraries, as well as providing interfaces towards boost libraries. These include the boost graph library and the boost property maps library.
Complete and Minimal Interfaces.
A goal with similar implications as uniformity is a design with complete and minimal interfaces, see for example Item 18 in Ref. [7]. An object or module should be complete in its functionality, but should not provide additional decorating functionality. Even if a certain function might look like it contributes to the ease of use for a certain class, in a more global picture it might hinder the understanding of similarities and differences among classes, and make it harder to learn and memorize.
Rich and Complete Functionality.
We aim for a useful and rich collection of geometric classes, data structures and algorithms. CGAL is supposed to be a foundation for algorithmic research in computational geometry and therefore needs a certain breadth and depth. The standard techniques in the field are supposed to appear in CGAL.
Completeness is also related to robustness.
We aim for general-purpose solutions that are, for example, not restricted by assumptions on general positions. Algorithms in CGAL should be able to handle special cases and degeneracies.
In those cases where handling of degeneracies turns out to be inefficient, special variants that are more efficient but less general should be provided in the library in addition to the general algorithms handling all degeneracies. Of course, it needs to be clearly documented which degeneracies are handled and which are not.
For most geometric algorithms theoretical results for the time and space complexity are known. Also, the theoretic interest in efficiency for realistic inputs, as opposed to worst-case situations, is growing [11]. For practical purposes, insight into the constant factors hidden in the \( O\)-notation is necessary, especially if there are several competing algorithms.
Therefore, different implementations should be supplied if there is not one best solution, as, for example, when there is a tradeoff between time and space or a more efficient implementation when there are no or few degeneracies.
The design goals, especially flexibility and efficient robust computation, have led us to opt for the generic programming paradigm using templates in C++.In appropriate places, however, CGAL does and should make use of object-oriented solutions and design patterns, as well. In the overall design of CGAL three major layers can be identified, the layer of algorithms and data structures, the kernel layer and the arithmetic and algebra layer. (Figure 0.1 ).
Algorithms and data structures in CGAL are parameterized by the types of objects and operations they use. They work with any concrete template arguments that fulfill certain syntactical as well as semantic requirements. In order to avoid long parameter lists, the parameter types are collected into a single class, called the traits class in CGAL (Chapter Traits Classes ). A concept is an abstraction of a type defined by a set of requirements. Any concrete type is called a model for a concept if it fulfills the set of requirements corresponding to the concept. Using this terminology, we can say a CGAL algorithm or data structure comes with a traits concept and can be used with any concrete traits model for this concept. Further contributions to CGAL should continue the current high level of genericity.
CGAL defines the concept of a geometry kernel. Ideally, any model for this concept can be used with any CGAL algorithm. This holds, of course, only if the requirements of an algorithm or data structure on its traits class are subsumed by the kernel concepts, i.e., if an algorithm or data structure has no special requirements not covered in the definition of the kernel concept. Currently, CGAL offers a concept for a fundamental geometry kernel, that defines various geometric objects such as points, line segments, lines, circles, and operations on them, as well as two additional concepts, the circular and the spherical kernel. The goal of the last two kernels is to specify a large set of functionalities on circles and circular arcs on the plane (circular kernel), and analogous functionalities for circles, circular arcs living on a 3D sphere (spherical kernel).
CGAL currently provides several models for the CGAL 2D and 3D kernel concept, and one model for the 2D circular and the 3D spherical kernel concepts.. Those are again parameterized and differ in their representation of the geometric objects and the exchangeability of the types involved. In the first four cases the kernels are parameterized by a number type, which is used to store coordinates and which determines the basic arithmetic of the kernel primitives.
In the last two cases, the circular and spherical kernel are also parametrized by Algebraic Kernels, which, along with Algebraic Foundations, is the third distinct high level of genericity in CGAL. The algebraic foundations in CGAL is a collection of concepts representing algebraic structures, and are motivated by well-known counterparts in traditional algebra. The algebraic foundations determine the operations per algebraic structure, their properties (e.g., whether they are supposed to be exact or approximate), as well as interoperability between them. An algebraic kernel is responsible for providing an abstraction for the algebraic operations required by either geometry kernels or traits classes used in CGAL algorithms. The goal is to be able to construct, compare and perform operations on real roots of polynomial equations. There are different concepts depending on the number of variables of the polynomials used to determine the roots (currently there are concepts for univariate and bivariate algebraic kernel), as well as specialized concepts targeted towards specific geometric higher level layers of the library (such as the circular and spherical kernels). These concepts are accompanied by at least one model per concept.
There are further complementary layers in CGAL. The most basic layer is the configuration layer. This layer takes care of setting configuration flags according to the outcome of tests run during installation. The support library layer is documented in the Support Library Manual and contains packages that deal with things such as visualization, number types, streams, and STL extensions in CGAL.
1.8.13