The Algorithm Design Manual Second Edition

19.1.2

CGAL

The Computational Geometry Algorithms Library or CGAL provides efficient and

reliable geometric algorithms in C++. It is extremely comprehensive, offering a rich

variety of triangulations, Voronoi diagrams, operations on polygons and polyhedra,

line/curve arrangements, alpha-shapes, convex-hull algorithms, geometric search

structures, and more. Many work in three dimensions and some beyond.

CGAL (www.cgal.org) should be the first place to go for serious geometric com-

puting, although you should expect to spend some start-up time getting oriented

to the CGAL way of thinking. CGAL is distributed under a dual-license scheme.

It can be used together with open source software free of charge but using CGAL

in other contexts requires obtaining a commercial license.

---

1 9 . 1

S O F T W A R E S Y S T E M S