Tuesday, April 19, 2011

Delaunay Triangulations - Algorithms and APIs

The triangulation of a surface is a topological process. The concept of triangulation is well explained in Algebraic topology and followed up with enormous amount of research in Computational Geometry.

Delaunay Triangulation is a different ball game because in the process of triangulation, a certain rule has to be followed - Any point must not lie in the circumcircle formed by three other points. Put in pretty simple words, wow, what a rule! I will attempt to simplify the explanation of the process in the following paragraphs.

Let us suppose that we are given a set of N two dimensional points. For the sake of simplicity let us assume that these points are unique (no two points have the same coordinates). We take out three points from this set of N points, and then check whether these points are collinear or not. If they are, we will have to choose another subset of three points. So let us suppose that they are not collinear. Create a triangle with these three points. Take out another point from the main set.  Check if this point falls within the circumcircle of the earlier triangle. If yes, "cancel" the earlier triangle, and create triangles such that the given rule is followed. If no, create another triangle with the nearest edge. This process goes on and on until the entire list of points is exhausted.

We have to understand that this is a computationally intensive process. Now as a person, working with LiDAR data and interested in processing it to extract features like buildings, trees etc. you might not be really interested in designing and coding the algorithm for creating the Delaunay Triangulation of a given set of points. Surely there are people in the domain of computer science who have already done the hard work for coding these algorithms. Two of the most popular resources are QHULL and CGAL.

QHULL is a divide and conquer algorithm (Barber, C.B., Dobkin, D.P., and Huhdanpaa, H.T., "The Quickhull algorithm for convex hulls," ACM Trans. on Mathematical Software, 22(4):469-483, Dec 1996), and is available as an open source project on the Internet (http://www.qhull.org). The binaries are available too! One just needs to spawn the binary executable with the right options to generate the delaunay triangulation. Till very recently, MATLAB was using the QHULL library but has switched over to CGAL (for better or worse). Apart from usual computations of Delaunay Triangles, the QHULL code is able to compute the convex hulls and the voronoi diagrams. A comprehensive help is given on their website.

The Computational Geometry Algorithms Library (CGAL) is a large collection of algorithms in the field and a small section of this is also the computation of convex hulls, alpha shapes, and Delaunay Triangulations. (We can talk about alpha shapes later on.) CGAL has an API with C++ to enable programmers to write codes for computation of triangulations and delaunay triangulations. It is important to note that in the jargon of CGAL, "triangulation" and "delaunay triangulation" are two different processes.

As on April 20, 2011, I received a mail from the CGAL project people [subscribe to the cgal-announce newsletter] that they have released CGAL 3.8, with new features. It supports 3D mesh generation, 2D and 3D triangulations (faster and efficient algorithms), and better computations of 3D alpha shapes.