Monday, April 23, 2012

Explicit Delaunay triangulation

Hello guys. In this post I'm not going to discuss in details the Delaunay triangulation, but I want to give a hint about implementing Delaunay method explicitly.

As we know, for a set of points triangulated using Delaunay triangulation, each triangle has no points inside the circumscribed circle of it. So, I tried to implement this principle explicitly by the following method.

For each combination of 3 points compute the circumcenter and radius of the circumcircle and check distances between this circumcenter and all points. If the minimum distance of those distances is larger than the radius, then no points exist inside the circumscribed circle and this triangulation is valid.

Actually, this method is quite stupid, but why? The problem in this method is degeneracies. We have two cases of degeneracies:
1. Three points are on the same line. So, using direct geometry concepts or substitution in equations that compute the coordinates of the circumcenter will return no circumcenter or circumcircle.
2. Certain number of points forms a cyclic polygon. In this case, when checking for 3 points of them we will find other points on the circumcircle and so we have to make a decision (see figure below)
a. First decision: assume points on the circumcenter are inside the circumcenter. As a result, no triangulation will be created.
b. Second decision: assume points on the circumcenter are outside the circumcenter. The result is overlapping triangles. 

So, we should look for another method to compute the Delaunay triangulation like the randomized incremental method introduced by Boywer-Watson, randomized incremental method introduced by Lawson, Voronoi-Delaunay duality, projection method, or edge flipping (optimization).

When you implement any method for triangulation, just check if it's going to work with the degeneracies or not.