CGAL图形编程库

Cgal编程函数库，方便图形学编程，能够为您提供方便的程序调用Contents1 Introduction1. I Primary design goals1. 2 The overall design2 Coding Conventions2.1 Naming scheme2.2 Programming conventions2. 3 Code format558992. 4 File header3 Geometry Kernels3. 1 Cartesian and homogeneous representation3.2 Cartesian versus homogeneous computation123.3 Available kernels133. 4 Kernel design and conventions3.5 Number-type based predicates143.6 Missing functionality144 Traits classes154.1 What are traits classes in cgal?154.2 Why are traits classes in CGAL?154.3 An example-planar convex hulls164.4 Alphabetical List of Reference Pages164.5 Kernel as traits185 Checks: Pre- and Postconditions, Assertions, and Warnings195.1 Categories of checks195.2 USing checks5.3 Controlling checks at a finer granularity205.4 Exception handling216 Reference Counting and Handle Types236.1 Reference counting236.2 Handle rep236.3 USing handle re256.4 Templated handles256.5 USing templated handles266.6 Allocation7 Memory Management297. 1 The C++ standard allocator interface7. 2 The allocator macro7. 3 Using the allocator.318 Namespaces338.1 What are namespaces338.2 Namespace std..338.3 Namespace CGAL348.4 Name lookup348.5 Namespace CGaL: NTS369 Polymorphic Return Types10 Iterators and Circulators(and Handles)4110.1 Iterator and circulator traits..4110.2 Input and output iterators4210.3 Writing code with and for iterators, circulators, and handles11 Robustness issues11. 1 The role of predicates and constructions12 Portability Issues12. 1 Checking for LEDA or GMP support12. 2 Using Boost5012.3 USing the version-number and configuration macros and flags12. 4 Identifying compilers and architectures5112.5 Known problems and workarounds5113 Debugging Tips5713.1 Graphical debugging5713.2 Cross-checkers13.3 Examining the values of variables5814 Editorial Committee6115 Recommended readingIndex66Chapter 1IntroductionSusan Hert(hert@mpi-sb. mpg. de)Stefan Schirra(stschirrampi-sb mpc ce)COMPUTATIONAL GEOMETRY ALGORITHMS LIBRARYThe goal of cgal is to make available to users in industry and academia the most importantefficient solutions to basic geometric problems developed in the area of computational geometry ina Ctt software library.Work on CGal has been supported by ESPRit IV projects 21957(CGAL) and 28 155 (GALIA).1.1 Primary design goalsThe primary design goals of CGAL are [FGKt00CorrectnessA library component is correct if it behaves according to its specification. Basically, correctness is therefore amatter of verification that documentation and implementation coincide. In a modularized program the correct-ness of a module is determined by its own correctness and the correctness of all the modules it depends onClearly, in order to get correct results, correct algorithms and data structures must be usedExactness should not be confused with correctness in the sense of reliability. There is nothing wrong withalgorithms 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 correctwith respect to its specification, al though in CGAL. we would like to provide algorithms handling degeneraciesRorobustnessa design goal particularly relevant for the implementation of geometric algorithms is robustness. Many im-plementations of geometric algorithms lack robustness because of precision problems; see Chapter 11 for adiscussion of robustness issues within cgadFlexibilitThe different needs of the potential application areas demand fexibility in the library. Four sub-issues of flexi-bility can be identifiedModularity. a clear structuring of CGal into modules with as few dependencies as possible helps a user inlearning and using CGAL, since the overall structure can be grasped more easily and the focus can be narrowedto those modules that are actually of interestAdaptability CGal might be used in an already established environment with geometric classes and algorithmsin which case the modules will most probably need adaptation before they can be usedExtensibility. Not all wishes can be fulfilled with CGAL. Users may want to extend the library. It should bepossible 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 librariesand programs. The C++ Standard [C++98] defines with the C++ Standard Library a common foundation forall C++ platforms. So it is easy and natural to gain openness by following this standard. There are importantlibraries outside the standard, and cgal should be easily adaptable to them as wellEfusMany different qualities can contribute to the ease of use of a library. Which qualities are most important differsaccording to the experience of the user. The above-mentioned correctness and robustness issues are among thesequalities. Of general importance is the length of time required before the library becomes useful. Another issueis the number of new concepts and exceptions to general rules that must be learned and rememberedEase of use tends to conflict with fexibility, but in many situations a solution can be found. The flexibility ofCGAL Should not distract a novice who takes the first steps with CGaLUniformity. A uniform look and feel of the design in CGaL will help in learning and memorizing. A conceptonce learned should be applicable in all places where one would wish to apply it. a function name once learnedfor a specific class should not be named differently for another classCGAL is based in many places on concepts borrowed from StL (Standard Template Library)or the other partsof the Ctt Standard Library. An example is the use of streams and stream operators in CGAL. Another exampleis the use of container classes and algorithms from the stl. so these concepts should be used uniformlComplete and Minimal Interfaces. A goal with similar implications as uniformity is a design with completeand minimal interfaces, see for example Item 18 in Ref [Mey97]. An object or module should be complete in itsfunctionality, but should not provide additional decorating functionality. Even if a certain function night looklike it contributes to the ease of use for a certain class, in a more global picture it might hinder the understandingof similarities and differences among classes, and make it harder to learn and memorizeRich and complete functionality. We aim for a useful and rich collection of geometric classes, data structuresand algorithms. CGAL is supposed to be a foundation for algorithmic research in computational geometry andFigure 1.1: The generic design of cgaltherefore needs a certain breadth and depth. The standard techniques in the field are supposed to appear inCGALCompleteness is also related to robustness. We aim for general-purpose solutions that are, for example, notrestricted by assumptions on general positions. Algorithms in CGal should be able to handle special cases anddegeneracies. In those cases where handling of degeneracies turns out to be inefficient, special variants that aremore efficient but less general should be provided in the library in addition to the general algorithms handlinall degeneracies. Of course, it needs to be clearly documented which degeneracies are handled and which arenotEfficiencyFor most geometric algorithms theoretical results for the time and space complexity are known. Also, thetheoretic interest in efficiency for realistic inputs, as opposed to worst-case situations, is growing [Vle97]. Forpractical purposes, insight into the constant factors hidden in the O-notation is necessary, especially if there areseveral competing algorithms. Therefore, different implementations should be supplied if there is not one bestsolution, as, for example, when there is a tradeoff between time and space or a more efficient implementationwhen there are no or few degeneracies1. 2 The overall designThe design goals, especially flexibility and efficient robust computation, have led us to opt for the genericprogramming paradigm using templates in C++. In the overall design of CGaL two major layers can beidentified, the layer of algorithms and data structures and the kernel layer(Figure 1. 1)Algorithms and data structures in CGAL are parameterized by the types of objects and operations they use. Theywork with any concrete template arguments that fulfill certain syntactical as well as semantic requirements. InIn appropriate places, however, CGAL does and should make use of object-oriented solutions and design patterns, as well.order to avoid long parameter lists, the parameter types are collected into a single class, called the traits classin CGAL(Chapter 4.) A concept is an abstraction of a type defined by a set of requirements. Any concretetype is called a model for a concept if it fulfills the set of requirements corresponding to the concept. Using thisterminology, we can say a Cgal algorithm or data structure comes with a traits concept and can be used withany concrete traits model for this concept Further contributions to Cgal should continue the current high levelgeCGal defines the concept of a geometry kernel. Ideally, any model for this concept can be used with any CGalalgorithm This holds, of course only if the requirements of an algorithm or data structure on its traits class aresubsumed by the kernel concepts, i.e., if an algorithm or data structure has no special requirements not coveredin the definition of the kernel conceptCGAL currently provides four models for the CGAL 2D and 3D kernel concept. Those are again parameterizedand differ in their representation of the geometric objects and the exchangeability of the types involved. In allcases the kernels are parameterized by a number type, which is used to store coordinates and which determinesthe basic arithmetic of the kernel primitives. See Chapter 3 for more detailsThere are further complementary layers in CGAL. The most basic layer is the configuration layer. This layertakes care of setting configuration flags according to the outcome of tests run during installation. The supportlibrary layer is documented in the Support Library Reference Manual and contains packages that deal withthings such as visualization, number types, streams, and stl extensions in CGAL