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.
(sorry - unprojected)
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.
(a temperature isoline map generated in Flash from a field of only 50 or so weather stations of the form lat, lon, temp)
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.
- Full .zip with necessary classes and example .fla
- For browsing, the main Delaunay.as file
3 Comments
Triangulation is a fun algorithm to play with - well done for cracking it, and thanks for sharing the code.
I’m curious what the next steps are to go from a triangulation + heights to iso lines? I’ve tackled it before but I never managed to generate useful vectors, the best I got was a texture-map hack which was fast but inflexible:
http://www.tom-carden.co.uk/p5/contours_by_1D_texture/applet/
And then I got side-tracked by 3D, which never seems satisfying in the end:
http://www.tom-carden.co.uk/p5/gpx_contours/applet/
hi Tom, I just used the technique, remembered from a couple manual cartography exercises, of constructing a triangulated irregular network, interpolating along it its edges, stringing isolines between certain values, and smoothing them. My package was just released here. It’s certainly not the best method (better would be inverse-distance or kriging), and data often doesn’t come in this format (point data with attributes attached; for example, elevation data might come in as a white-to-black DEM).
ur api for contour is wonderful
and thanks a lot to u
i’d like to fill color between lines ,and want it bo be like
http://blog.spatialkey.com/images/sacbee1.png
how can i extend ur api?
can u give me some hint?
thanks a lot!
One Trackback
[...] week or so back I wrote about a package I ported/modified to create the Delaunay triangulation in Flash with a few AS3 classes. [...]