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 T.insert(Point(x,y,z)); }

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:

- The CGAL homepage. Great manual, also for general computational geometry.
- C++ and Object Oriented Numeric Computing for Scientists and Engineers, by Daoqi Yang. A must-have, in my opinion.
- cplusplus.com, general reference on C++.
- cppreference, another good reference. This one is a wiki.
- Visual C++ Developer Center. OK, so it’s microsoft. But they have some good things, like this reference manual. And some others, like their technical support.

Pingback: The alpha shapes « Daniel Duque Campayo