The goal of CGAL is to make available to users in industry and academia the most important efficient solutions to basic geometric problems developed in the area of computational geometry in a C++ software library.
Work on CGAL has been supported by ESPRIT IV projects 21957 (CGAL) and 28155 (GALIA).
This manual is meant to be a resource for developers who wish to contribute to the CGAL library either by designing new packages or maintaining or enhancing existing ones. The manual is organized roughly in the order in which a developer will need the information in order to produce a package for the library. We begin in this chapter with a description of the design goals of CGAL and the overall design, which should be kept in mind during all stages of development. The remaining chapters describe in more concrete terms the requirements and recommendations for documentation, code writing, and testing that are derived from these goals. We also describe a number of tools that have been created to help in the development process and give pointers to other sources of information.
A description of how the specification for a package should be documented is provided along with information about the tools available to help produce the documentation in Chapter 2. Chapter 3 discusses the SVN server on which all CGAL source code is kept. Chapter 4 describes the directory structure required for a package and Chapter 5 describes a set of tools that may be used to create or modify various files required within this directory structure. Chapters 6 through 15 discuss issues related to the writing of code that is in keeping with the goals of CGAL. Chapter 16 describes issues related to the configuration of CGAL and discusses portability issues for various platforms. Chapter 17 describes the requirements and behaviour of the test suite for a package and Chapter 18 consists of various hints for debugging. Guidelines for the development of example and demo programs are given in Chapter 19. Information about how to submit a package's specification to the editorial board for approval and the implementation (and documentation) for inclusion in internal releases is presented in Chapter 20. Chapter 21 gives information about the creation of the internal, public, and bug-fix releases. Chapter 22 provides information about the CGAL web site and what developers should do to assure that it is kept up to date. Chapters 23 and Chapter 24 provide information about mailing lists and other information resources developers might find useful.
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.
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 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 [C++98] 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.
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.
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. [Mey97]. 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.
The design goals, especially flexibility and efficient robust computation, have led us to opt for the generic programming paradigm using templates in C++.1 In the overall design of CGAL two major layers can be identified, the layer of algorithms and data structures and the kernel layer (Figure 1.3).
Figure: The generic design of CGAL.
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 8.) 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.
CGAL currently provides four models for the CGAL 2D and 3D kernel concept. Those are again parameterized and differ in their representation of the geometric objects and the exchangeability of the types involved. In all 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. See Chapter 7 for more details.
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 Reference Manual and contains packages that deal with things such as visualization, number types, streams, and STL extensions in CGAL.
| 1 | In appropriate places, however, CGAL does and should make use of object-oriented solutions and design patterns, as well. |