delaunay triangulation in ActionScript 3

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.

10 Comments

  1. 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/

    Tom Carden
    Posted June 8, 2008 at 8:18 pm | Permalink
  2. 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).

    Posted June 9, 2008 at 1:28 am | Permalink
  3. 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!

    aiya
    Posted September 2, 2008 at 1:20 am | Permalink
  4. 17fqimyjpbvyyx8h

    Devon Klein
    Posted November 12, 2008 at 4:33 pm | Permalink
  5. a wonderful flash program and an absolute great blog!! I am enjoying your works. thanks.

    easy
    Posted April 22, 2009 at 2:10 am | Permalink
  6. 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));

    easy
    Posted June 11, 2009 at 7:01 pm | Permalink
  7. 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 :)

    Marcin
    Posted June 29, 2010 at 7:01 am | Permalink
  8. 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

    Toms
    Posted August 7, 2010 at 9:45 am | Permalink
  9. 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!

    Posted October 19, 2013 at 7:18 am | Permalink
  10. @zach’ry:Hello,have you finished doing “hypsometric tinting”?

    monica
    Posted May 5, 2014 at 3:13 am | Permalink

6 Trackbacks

  1. [...] week or so back I wrote about a package I ported/modified to create the Delaunay triangulation in Flash with a few AS3 classes. [...]

  2. By Muki Muki - Benjamin Jung's Flash Blog » Morphing on May 10, 2009 at 1:29 pm

    [...] 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  [...]

  3. By “Clean Code” in AS3 at AlecMcE.com on August 25, 2009 at 6:14 pm

    [...] 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 [...]

  4. By Triangulación de Delaunay y deformaciones « The So3 blog on January 28, 2010 at 6:04 am

    [...] 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 [...]

  5. By Circling, Squaring, and Triangulating | Math Munch on May 8, 2013 at 8:12 am

    [...] 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 [...]

  6. By [置顶] 温度场有限差分(有限容积)程序入门之六:后处理.isoline的绘制.基于Flash.Display.Graphics绘图API - iew3c on May 11, 2013 at 12:45 am

    [...] week or so back I wrote about a package I ported/modified to create the Delaunay triangulation in Flash with a few AS3 classes. [...]

Post a Comment

Your email is never published nor shared. Required fields are marked *