The Delauney Triangulation

The Delauney Triangulation is the dual to the Voronoi Diagram, and may be defined as follows.

Let P be a set of points in the plane, and let C be the Convex Hull of the points. Then, draw straight lines (not crossing each other) from points on the interior to points on the boundary of the convex hull (or to each other), until the whole convex hull is divided into a set of polygons, with all vertices being elements of P. Then, if any of the polygons are not triangles, divide them into triangles by drawing more lines between vertices of the polygons. This will give a triangulation of the set of points.

There are many ways to draw a triangulation, since there are many different ways to choose the lines we draw in the above procedure. Amongst all the different triangulations, there will be one which has the smallest possible total edge length. This one is the Delauney Triangulation.

The DotPlacer Applet (on this site) allows you to place a set of points on the screen, and have it draw the delauney triangulation for you. You can even move the points around, and watch the figure change. Try it!

I used the following algorithm to draw the delauney triangulation. Most of the calculations are the same as used to draw the voronoi diagram. First of all, for each set of three points, I calculate the orthocentre of the three points. That is, I calculate the point which is equidistant from all three points. Then, for each orthocentre x, I check all the points in P, to make sure that the three points used to find x are the three closest points of P to x. If they are not, I reject x from consideration. It is not needed to draw the voronoi diagram. Then, for each orthocentre x not rejected, I draw lines between the points that were used to find this orthocentre. Roughly speaking, that's it.

The algorithm used is certainly not the most efficient one available for constructing the delauney triangulation, but it works. Furthermore, the cost is almost zero if the applet is drawing the voronoi diagram also.

For more information on the delauney triangulation, see this World of Mathematics article. Or perhaps you'd like a solid text on the subject? Clicking the book on the left will allow you to get one that covers the Delauney Triangulation, and other topcis, in depth. The book on the right, with code samples and good explanations, is regarded by many as one of the best books around for applying java (and smalltalk) to numerical methods.