The GeometryFactory and CGAL -
The Computational Geometry Algorithm Library

by Andreas Fabri

The mission of the GeometryFactory is to make the large body of geometric computing accessible to industrial developers in the form of easy to integrate C++ software components. The GeometryFactory is a start-up of the of the academic CGAL project (www.cgal.org) which was founded by seven European research groups in 1996, and which develops CGAL, the Computational Geometry Algorithm Library.

An Ubiquituous Need for Geometric Computing
The CGAL users are in domains as different as computer aided design (ECL), structural geology (Midland Valley, Agip, IFP), geographical information systems (Leica Geosystems, BAeSystems), finite elements for weather forcast (WeatherNews), antenna placement (France Telecom, British Telecom), location based services (TruePosition), VLSI (Toshiba) biochemistry (see figure), etc. The above mentioned companies switched from pure inhouse software development, based on scientific publications and on non supported freely accessible prototypes, to 'commercial off the shelf software', which allows them to focus on the application layer where their core competence is.

Technology
The library contains data structures and algorithms like Delaunay triangulations in 2D, 3D and dD, Voronoi diagrams for points, segments, and circles, Boolean operations on 2D polygons and 3D polyhedra, arrangements of segments and circular arcs, nearest neighbor search, convex hull, and much more.
The geometric software components of CGAL are a unique combination of extreme reliability, speed, ease of integration, interoperability, and in many cases unique functionality. The value for the users are a reduction of the risk of delays, a reduction of development costs, and of time to market.

The CGAL library represents cutting-edge technology. This holds for the geometric algorithms, which are directly transfered from academia, as well as for the software design, where we did not reinvent the wheel, but follow best practice.

Modeling protein-protein interfaces using the Voronoi diagram of balls (that is the weighted alpha shape of CGAL). The yellow/green/red facets model interactions between the two (red and blue) proteins, and the interface of the complex consists of the collection of such facets. The interface is discontinued due to crystallographic water molecules trapped between the proteins. (Courtesy of Frederic Cazals, INRIA).

Exact Computation Paradigm
Correct geometric algorithms need reliable numerical computations as foundation. We follow the exact computation paradigm that is well established in the computational geometry research community. It requires the exact evaluation of geometric predicates, ie, decisions derived from geometric computations have to be correct. Results obtained by researchers of the CGAL project make that this exact evaluation of predicates can be done efficiently. In a nutshell, this is achieved by combining interval arithmetic on floating point numbers with arbitrary precision numbers as they are provided by the GMP (GNU Multiple Precision) arithmetic library, http://www.swox.com/gmp) or the CORE library (http://www.cs. nyu.edu/exact/core/).
Our approach is in contrast to current industry practice that uses a small value below which two numbers are considered equal. Such an approach leads to unreliable solutions that are hard to debug and almost impossible to prove to be correct.

Generic Programming Paradigm
Generic programming gives a tremendous flexibility at development time, and efficient code at run time of a program. Its power became apparent with the STL, the Standard Template Library, which is shipped with every C++ compiler.

As the 'std::set' containers of the STL is parameterised with the type of the objects it contains, and an order predicate for comparing the elements in the set, CGAL data structures are parameterised by, for example, the point type and orientation predicates on this point type.

Back in 1995 we took the risk to adopt the generic programming paradigm for the design of CGAL. It was a risk, because neither the compilers nor the potential customers were mature. Now, in 2004, all C++ compilers comply with the C++ ISO standard. Furthermore, today most C++ developers are familiar with generic programming. We are hence beyond the phase where only early adopters of technology use CGAL.

License Issues
CGAL is available under the {\sc Qpl} Open Source license which does not allow commercial usage. For the latter users need a commercial license from the GeometryFactory. The Industry Research License gives access to all CGAL components for a low annual rental fee. The Industial Development License for individual software components allows integration in commercial products.

Links:
http://www.cgal.org
http://www.geometryfactory.com

Please contact:
Andreas Fabri, Geometryfactory, France
E-mail: Andreas.Fabrigeometryfactory.com