Introduction

CGAL Editorial Board

The goal of the Cgal Open Source Project is to provide
*easy access to efficient and reliable geometric algorithms*
in the form of a C`++` library.

The Computational Geometry Algorithms Library offers data structures and algorithms like triangulations, Voronoi diagrams, Boolean operations on polygons and on polyhedra, arrangements of curves, mesh generation, geometry processing, convex hull algorithms, to name just a few.

All these data structures and algorithms operate on geometric objects
like points and segments, and perform geometric tests on them.
These objects and predicates are regrouped in Cgal *Kernels*.

Finally, the Cgal *Support Library*
offers geometric object generators and spatial sorting functions,
as well as a matrix search framework and a solver for linear and quadratic programs.
It further offers interfaces to third party software such as the Gui libraries Qt,
Geomview, and the Boost Graph Library.

This manual is organized in several parts covering the many domains
of computational geometry. Each part consists of several chapters,
and each chapter is split into a *user manual* and a *reference
manual*. The user manual gives the general idea and comes with examples.
The reference manual presents the Api of the various classes
and functions.

The manual has a table of contents, and an index, as well as a package overview, which gives a short paragraph what the package is about, what license it has, and on which other packages it depends. It further provides links to precompiled demo programs for the Windows platform.

In the distribution of the library you find the two directories *demo*
and *examples*. They contain subdirectories for the Cgal packages.
The demos use third party libraries for the graphical user interface. The
examples don't have this dependency and most examples are refered to in the
user manual.

In this section we will take a closer look at three Cgal example programs, all of them computing the 2D convex hull of a set of points.

In the first example we have an array of five points. As the convex hull of these points is a subset of the input it is safe to provide an array for storing the result which has the same size.

File:examples/Convex_hull_2/array_convex_hull_2.cpp

#include <iostream> #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/convex_hull_2.h> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef K::Point_2 Point_2; int main() { Point_2 points[5] = { Point_2(0,0), Point_2(10,0), Point_2(10,10), Point_2(6,5), Point_2(4,1) }; Point_2 result[5]; Point_2 *ptr = CGAL::convex_hull_2( points, points+5, result ); std::cout << ptr - result << " points on the convex hull" << std::endl; return 0; }

All Cgal header files are in the subdirectory ``include/CGAL''. All Cgal classes and functions are in the namespace ``CGAL''. The geometric primitives, like the point type, are defined in a kernel. Cgal comes with several kernels, and as the convex hull algorithm only makes comparisons of coordinates and orientation tests of input points, we can choose a kernel that provides exact predicates, but no exact geometric construction.

The convex hull function takes three arguments, the start and past-the-end pointer for the input, and the start pointer of the array for the result. The function returns the pointer into the result array just behind the last convex hull point written, so the pointer difference tells us how many points are on the convex hull.

In the second example we replace the built-in array
by a *std::vector* of the Standard Template Library.

File:examples/Convex_hull_2/vector_convex_hull_2.cpp

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/convex_hull_2.h> #include <vector> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef K::Point_2 Point_2; typedef std::vector<Point_2> Points; int main() { Points points, result; points.push_back(Point_2(0,0)); points.push_back(Point_2(10,0)); points.push_back(Point_2(10,10)); points.push_back(Point_2(6,5)); points.push_back(Point_2(4,1)); CGAL::convex_hull_2( points.begin(), points.end(), std::back_inserter(result) ); std::cout << result.size() << " points on the convex hull" << std::endl; return 0; }

We put some points in the vector calling the *push_back()*
method of the *std::vector* class.

We then call the convex hull function. The first two arguments,
*points.begin()* and *points.end()* are *iterators*,
which are a generalization of pointers:
they can be dereferenced and incremented. The convex hull
function is *generic* in the sense that it takes as
input whatever can be dereferenced and incremented.

The third argument is where the result gets written to.
In the previous example we provided a pointer to allocated memory.
The generalization of such a pointer is the *output iterator*,
which allows to increment and assign a value to the dereferenced iterator.
In this example we start with an empty vector which grows as needed.
Therefore, we cannot simply pass it *result.begin()*, but
an output iterator generated by the helper function *std::back_inserter(result)*.
This output iterator does nothing when incremented,
and calls *result.push_back(..)* on the assignment.

The last example program reads a sequence of points from standard
input *std::cin* and writes the points on the convex hull to
standard output *std::cout*.

Instead of storing the points in a container such as an
*std::vector*, and passing the begin/end iterator of the vector to
the convex hull function, we use helper classes that turn file
pointers into iterators.

File:examples/Convex_hull_2/iostream_convex_hull_2.cpp

#include <iostream> #include <iterator> #include <CGAL/Exact_predicates_inexact_constructions_kernel.h> #include <CGAL/convex_hull_2.h> typedef CGAL::Exact_predicates_inexact_constructions_kernel K; typedef K::Point_2 Point_2; int main() { std::istream_iterator< Point_2 > input_begin( std::cin ); std::istream_iterator< Point_2 > input_end; std::ostream_iterator< Point_2 > output( std::cout, "\n" ); CGAL::convex_hull_2( input_begin, input_end, output ); return 0; }

In the example code you see input and output stream iterators
templated with the point type. A *std::istream_iterator<Point_2>*
hence allows to traverse a sequence of objects of type *Point_2*, which
come from standard input as we pass *std::cin* to the
constructor of the iterator. The variable *input_end* denotes
end-of-file.

A *std::ostream_iterator<Point_2>* is an output iterator,
that is an iterator to which, when dereferenced, we can assign a value.
When such an assignment to the output iterator
happens somewhere inside the convex hull function, the iterator
just writes the assigned point to standard output, because the iterator
was constructed with *std::cout*.

The call to the convex hull function takes three arguments, the input iterator range, and the output iterator to which the result gets written.

If you know the STL, the Standard Template Library, the above makes perfect sense, as this is the way the STL decouples algorithms from containers. If you don't know the STL, you maybe better first familiarize yourself with its basic ideas.

We also recommend the standard text books by
Josuttis [Jos99], or Austern [Aus98] for the
STL and its notion of *concepts* and *models*.

Other resources for Cgal are the tutorials at
`http://www.cgal.org/Tutorials/` and the user support page at
`http://www.cgal.org/`.

Next: Reference Manual

CGAL Open Source Project.
Release 3.9.
26 September 2011.