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
10 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!
17fqimyjpbvyyx8h
a wonderful flash program and an absolute great blog!! I am enjoying your works. thanks.
Do I not allow more than one points having the same coordination or too close?
I try this algorithm on some random data set which containing some points having the same x,y. And the result is weired and wrong.
var vertics:Array = new Array();
vertics.push(new Vertex(635.05, 172.8));
vertics.push(new Vertex(671.9, 146.3));
vertics.push(new Vertex(672.45, 114.15));
vertics.push(new Vertex(684.9, 129.5));
vertics.push(new Vertex(843.3, 513.6));
vertics.push(new Vertex(843.3, 513.6));
vertics.push(new Vertex(843.3, 513.6));
vertics.push(new Vertex(843.3, 513.6));
vertics.push(new Vertex(871.95, 73.5));
Hi, Why does drawDelaunay function uses negative Y values to draw points and lines? I took me some time to figure out why I had noting showing up at the screen. I use Flex Builder so usually point (0,0) is where it’s supposed to be i.e. top left corner
Hey bros,
Am testing out our code. On the whole is pretty elegant and well done. Kudos~! I love it and thanks for taking the effort to write it.
There are some bugs that I have encountered in the code and I hope this comment would help others:
1) all the y coordinates are inverted while cause them to be drawn out of bounce
2) the endfill() methods is not called while drawing the points.
Cheers
Greetings from Loss angeles! I’m bored to death at work
so I decided to browse your blog on my iphone during lunch break.
I enjoy the information you provide here and can’t wait
to take a look when I get home. I’m amazed at how quick your blog loaded on my phone ..
I’m not even using WIFI, just 3G .. Anyways, superb blog!
@zach’ry:Hello,have you finished doing “hypsometric tinting”?
6 Trackbacks
[...] week or so back I wrote about a package I ported/modified to create the Delaunay triangulation in Flash with a few AS3 classes. [...]
[...] some talented developers have already explained and implemented it in AS 3.0. You can find one here from Zachary Forest Johnson or here from [...]
[...] hope that someone had already created the algorithm in AS3 that I could use. I found this post on indiemaps.com. It’s a lovely post if you want to understand what the Delaunay Triangulation is or what it [...]
[...] siguiente ejemplo está creado a partir de las clases de Zachary Forest Johnson. Basicamente utilizo su mismo código, con alguna modificación de mi [...]
[...] a Delaunay triangulation applet that he made and read some background about this Delaunay idea here. To see how Zach uses these triangulations in his map-making, you’ve gotta check out the [...]
[...] week or so back I wrote about a package I ported/modified to create the Delaunay triangulation in Flash with a few AS3 classes. [...]