Hello World

Author

CGAL Editorial Board

The goal of this chapter is to get a first idea of the look and feel of a program that uses CGAL.

We will take a closer look at four CGAL example programs, all of them computing the 2D convex hull of a set of points. You will find the same ideas in other CGAL packages.

Points in a Built-in Array

In the first example we have as input 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 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.

Points in a Vector

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

File 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.

Points in Streams

The next 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 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.

About Traits Classes

If you look at the manual page of the function convex_hull_2() and the other 2D convex hull algorithms, you see that they come in two versions. In the examples we have seen so far the function that takes two iterators for the sequnce of input points and an output iterator for writing the result to. The second version has an additional template parameter Traits, and an additional parameter of this type.

What are the geometric primitives a typical convex hull algorithm uses? Of course, this depends on the algorithm, so let us consider what is probably the simplest efficient algorithm, the so-called "Graham/Andrew Scan". This algorithm first sorts the points from left to right, and then builds the convex hull incrementally by adding one point after another from the sorted list. To do this, it must at least know about some point type, it should have some idea how to sort those points, and it must be able to evaluate the orientation of a triple of points.

And that is where the template parameter Traits comes in. For ch_graham_andrew() it must provide the following nested types:

• Traits::Point_2
• Traits::Less_xy_2
• Traits::Left_turn_2
• Traits::Equal_2

As you can guess, Left_turn_2 is responsible for the orientation test, while Less_xy_2 does the sorting. The requirements these types have to satisfy are documented in full with the concept ConvexHullTraits_2.

The types are regrouped for a simple reason. The alternative would have been a rather lengthy function template, and an even longer function call.

template <class InputIterator, class OutputIterator, class Point_2, class Less_xy_2, class Lef_turn_2, class Equal_2>
OutputIterator
ch_graham_andrew( InputIterator  first,
                  InputIterator  beyond,
                  OutputIterator result);

There are two obvious questions: What can be used as argument for this template parameter? And why do we have template parameters at all?

Any CGAL Kernel provides what is required by ConvexHullTraits_2.

As for the second question, think about an application where we want to compute the convex hull of 3D points projected into the yz plane. Using the class Projection_traits_yz_3 this is a small modification of the previous example.

File Convex_hull_2/convex_hull_yz.cpp

#include <iostream>
#include <iterator>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Projection_traits_yz_3.h>
#include <CGAL/convex_hull_2.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K3;
typedef CGAL::Projection_traits_yz_3<K3> 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, K() );
  return 0;
}

Another example would be about a user defined point type, or a point type coming from a third party library other than CGAL. Put the point type together with the required predicates for this point type in the scope of a class, and you can run convex_hull_2() with these points.

Finally, let us explain why a traits object that is passed to the convex hull function? It would allow to use a more general projection traits object to store state, for example if the projection plane was given by a direction, which is hardwired in the class Projection_traits_yz_3.

Further Reading

We also recommend the standard text books "The C++ Standard Library, A Tutorial and Reference" by Nicolai M. Josuttis from Addison-Wesley, or "Generic Programming and the STL" by Matthew H. Austern 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/.