SOFTWARE—PRACTICE AND EXPERIENCESoftw. Pract. Exper., 29(00), 1–38 (1999) Prepared using speauth.cls [Version: 1999/06/11 v1.1a]On the design of CGAL,a computational geometry algorithms libraryAndreas Fabri1, Geert-Jan Giezeman2, Lutz Kettner3, Stefan Schirra4∗, and Sven Sch¨onherr51ABB Baden, Switzerland (email: [email protected])2Utrecht University, The Netherlands (email: [email protected])3ETH Z¨urich, Switzerland (email: [email protected])4Max-Planck-Institut f¨ur Informatik, Saarbr¨ucken, Germany (email: [email protected])5Freie Universit¨at Berlin, Germany (email: [email protected])SUMMARYCGAL is a Computational Geometry Algorithms Library written inC++, which is beingdeveloped by researchgroups in Europe and Israel. The goal is to make the large body of geometric algorithms developedin the field of computational geometry available for industrial application. We discuss the major designgoals for CGAL, which are correctness, flexibility, ease-of-use, efficiency, and robustness, and present ourapproach to reach these goals. Generic programming using templates in C++plays a central role in thearchitecture of CGAL. We give a short introduction to generic programming in C++, compare it to theobject-oriented programming paradigm, and present examples where both paradigms are used effectivelyin CGAL. Moreover, we give an overview of the current structure of the CGAL-library and consider softwareengineering aspects in the CGAL-project. Copyrightc 1999 John Wiley & Sons, Ltd.KEY WORDS: computational geometry; software library; C++; generic programming;INTRODUCTIONGeometric algorithms arise in various areas of computer science. Computer graphicsand virtual reality, computer aided design and manufacturing, solid modeling, robotics,geographical information systems, computer vision, shape reconstruction, molecularmodeling, and circuit design are well-known examples. Research on specific geometricproblems in these areas led to the more general study of geometric algorithms in the fieldof Computational Geometry. A lot of efficient geometric methods and data structures havebeen developed in this subfield of algorithm design over the past two decades. But many ofthese techniques have not found their way into practice yet. An important cause for this is∗Correspondence to: Stefan Schirra, Max-Planck-Institut f¨ur Informatik, Im Stadtwald, 66123 Saarbr¨ucken, GermanyCCC 0038–0644/99/0000001–38$17.50 Received 21 August 1998Copyrightc 1999 John Wiley & Sons, Ltd. Revised July 28, 1999Accepted 14 May 19992 A. FABRI, G.-J. GIEZEMAN, L. KETTNER, S. SCHIRRA, S. SCH¨ONHERRthe fact that the correct implementation of even the simplest of these algorithms can be anotoriously difficult task [1].There are two particular aspects that need to be dealt with to close the gap between thetheoretical results of computational geometry and practical implementations [2]. First, thereis the precision problem. Theoretical papers assume exact arithmetic with real numbers. Thecorrectness proof of the algorithms relies on the exact computations, thus replacing exactarithmetic by imprecise built-in floating-point arithmetic does not work in general.Second, there is the degeneracy problem. Often, theoretical papers exclude degenerateconfigurations for the input to the algorithms they describe. Typically, these degeneracies areproblem specific and would involve the treatment of special cases in the algorithm. Simpleexamples of configurations considered as degenerate are duplicate points in a point set orthree lines intersecting in one point. For some problems, it is not difficult to handle thedegeneracies, but for other problems the special case treatment distracts from the solutionof the general problem and it can amount to a considerable fraction of the coding effort,especially if handling of degeneraciesis treated as an afterthought [3]. In theory, this approachof excluding degeneracies from consideration is justified by the argument that degeneratecases are very rare in the set of all possible inputs over the real numbers, i.e. they are veryunlikely if the input set is randomly chosen over the real numbers. Another argument is thatit is first of all important to understand the general case before treating special cases. Inpractice, however, degenerate inputs do occur frequently. For instance, the coordinates of thegeometric objects may not be randomly chosen over the real numbers, but lie on a grid, forexample they may be created by clicking in a window in a graphical user interface. In someapplications, what are called degeneracies are even high-valued design criterias, for examplein architecture, where features of buildings do align on purpose. As a consequence, a librarymust address the handling of degeneracies.Besides the precision problem and the degeneracy problem, advanced algorithms bring aboutthe additional difficulty that they are frequently hard to understand and hard to code. Forthese reasons it is impractical for users to implement geometric algorithms from scratch.To remedy this situation a computational geometry library providing correct and efficientreusable implementations is needed. Such a library, called CGAL, Computational GeometryAlgorithms Library, is being developed in a common project of several universities andresearch institutes in Europe and Israel. In this paper we present and discuss the design ofthis C++software library.The sites contributing to CGAL are Utrecht University (The Netherlands), ETHZ¨urich (Switzerland), Freie Universit¨at Berlin (Germany), Martin-Luther Universit¨atHalle (Germany), INRIA Sophia-Antipolis (France), Max-Planck-Institut f¨ur Informatik,Saarbr¨ucken (Germany), RISC Linz (Austria), and Tel-Aviv University (Israel). Theparticipating sites are leading in the field of computational geometry in Europe and haveample experience with the implementation of geometric algorithms [4, 5, 6, 7, 8, 9]. Work onthe CGAL-library is the central task of two successive ESPRIT IV LTR projects with the namesCGAL and GALIA. It is the goal of these projects tomake the large body of geometric algorithms developed in the field ofcomputational geometry available for industrial application.Copyrightc 1999 John Wiley & Sons, Ltd. Softw. Pract. Exper., 29(00), 1–38 (1999)Prepared using speauth.clsON THE DESIGN OF CGAL 3The CGAL-library is our key tool in reaching this goal. It will be the basis for implementationsof geometric algorithms