An example algorithm : bi-dimensional Delaunay triangulation

Given a set of point, one wants to construct a partition of the space between these points (in other words, the space inside the convex hull) into triangles. Moreover, one whishes these triangles to be close to equilateral triangles as possible. One way to fulfill this last requirement is to make sure that the circle going through the three points of each triangle contains no other points from the input data.

The algorithm we study in this page works in the following way:

adds the points one by one
if the new point is outside the convex hulls of the previous points, add the corresponding triangles, and then check for each new triangle whether its circle contains the extra point of adjacent triangles. When this is the case, then flip the corresponding edge
if the new point falls inside an existing triangle, decompose this triangle into three new triangles, and then check for each new triangle with its circle contains the extra point of adjacent triangles. Again, when needed, flip the corresponding edge.

This algorithm depends on an auxillary algorithm, which tells how to find the triangle that contains a given point.

Implementations

I developed two small implementations, limited to a thousand elements (a thousand edges, a thousand points, a thousand triangles), with the ultimate aim to provide a formal verification of these implementations.

In the first implementation, I use a data-structure inspired from hypermaps. The basic objects are darts, which represent half edges. Each dart has a pointer to its other half edge and a pointer to its neighbor around a point. Combinations of the two pointers make it possible to compute triangles.
In the second implementation, I use a data-structure inspired from simplicial complexes. The basic objects are triangles, edges, or points. Each triangle has pointers to its edges, each edge has pointers to the points it connects and to the triangles it separates, points only have coordinates.