The CGAL project

CGAL logo

I have been following and using this project for some years now, on and off. In my opinion, a very remarkable cooperative effort of several research centers, coordinated at INRIA Sophia Antipolis. They provide very robust implementations of algorithms on computational geometry: Delaunay triangulations, Voronoi diagrams ski sums, meshes, alpha shapes, convex hulls, all that. Warning: very abstract C++ is needed (I actually learned C++ because of these libraries).

These libraries make extensive use of templates. This is a concept from generic programming: you don’t write code for this, or that, but for a generic use. It’s simpler for functions:

template <class myType>
myType GetMax (myType a, myType b) {
return (a>b?a:b);

Now, you may call it thus:

int i=1; int j=k;

int k=GetMax(i,j);

The compiler will know that “myType” has to be “int” in this case, and will compile the suitable (“instantiated”) GetMax function.

But that’s just the tip of the iceberg. CGAL strongly uses the manners of the STL, the Standard Template Library. As its name suggests, this is a library that introduces templates for a number of data structures (“containers”) and algorithms. Most interesting, for scientific computing, are the vector and list structures, and the algorithms that join them, sort them, find things in them, etc.

So, this is how CGAL would build Delaunay triangulation. First, you define your choices (don’t get scared yet):

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_3.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Delaunay_triangulation_3                     Delaunay;

typedef Delaunay::Point   Point;

Then, you build the triangulation up:

Delaunay T;

while () {
// Get some x,y,z values somehow

When you are done, you may perform queries on it:

 Delaunay::Finite_vertices_iterator vit;
 for (vit = T.finite_vertices_begin(); vit != T.finite_vertices_end(); ++vit)
      std::cout << "X coordinate: " << vit->point()[0];

OK, you may panic now. But believe, you get to learn this strange language, and it’s much, much better than trying to build you own algorithms (that is, if you are just trying to apply them, as is my case.)

Some links:


One thought on “The CGAL project

  1. Pingback: The alpha shapes « Daniel Duque Campayo

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s