update: for a cool usage of Delaunay triangulation, see my isolining package for ActionScript 3
The Delaunay triangulation was invented in 1934 by Boris Delaunay. According to Paul Bourke,
The Delaunay triangulation is closely related geometrically to the Direchlet tesselation also known as the Voronoi or Theissen tesselations. These tesselations split the plane into a number of polygonal regions called tiles. Each tile has one sample point in its interior called a generating point. All other points inside the polygonal tile are closer to the generating point than to any other. The Delauney triangulation is created by connecting all generating points which share a common tile edge. Thus formed, the triangle edges are perpendicular bisectors of the tile edges.
What all that means is that the resultant triangles will be as equilateral as possible. The triangular mesh has the advantage of minimizing the distance over which interpolations must take place.
Go ahead, try it out.
With the idea of creating client-side isolines and inspired in part by the spirit of Keith Peters’ ongoing MathWorld Problem of the Week, I set out to write an AS3 class to create the above triangulation. After an hour of hacking, I gave up, and decided to just port the algorithm from another language. I chose Florian Jenett’s Java version, itself a port of Paul Bourke’s original C. The port was easy, and makes it a cinch to create a triangulation of, say, selected weather stations in the U.S.
Of course, this triangulation isn’t really interesting in its own right, but rather for what it allows us to do, at run-time, with near real-time data, in Flash. On that, check this out.
I’ll release a full isolining package — complete with smoothing and hypsometric tinting — soon. For now, here’s the source code to the Delaunay triangulation in AS3.