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.
File translated from TEX by TTH, version 2.25.