The area of computational geometry has been developed over the last twenty years as a discipline of theoretical computer science, which drew much of its motivation from geometric applications (computer graphics, robotics, VLSI design, CAD, GIS, scientific computing). It has extracted the essential basic geometric algorithmic problems and developed efficient solutions for them. It has to be admitted though that only a few of the results have made their way into the application areas.
The goal of the project is to make the most important of these solutions and methods available to users in industry and academia in the form of a C++ library: CGAL (Computational Geometry Algorithms Library).
The distinguishing features of CGAL are the careful and efficient treatment of robustness issues, the wide scope of the algorithms and data structures provided, and flexibility, extendibility, and ease of use. The goal is not to create a Geometric modeling system, CAD system, or Graphics library, but to provide easy access to useful geometric algorithms to speed up such systems and to make them robust.
ETH contributes primarily to the following parts of the project.
1. Implementation and research on basic geometric optimization problems (e.g. smallest enclosing ball or ellipsoid of a set of points, largest k-gon in a convex polygon, linear and quadratic programming).
2. Design and implementation of data structures for geometric queries as they are needed in geographic information systems.
3. Design and implementation from a software engineering point of view: increasing reusability and C++ standard compliance, porting to other platforms, installation and testing processes.
CGAL release 2.1 was available at
http://www.cgal.org starting January 2000.
There have been around 200 downloads per month, not counting ftp accesses.
