Delaunay Triangulation

Another fascinating branch of computational geometry that is applied within spatial analysis is Delaunay triangulation. On the face of it, it appears that all you do is create a triangular mesh between all seeds (points). However, it is not quite that simple. Firstly, the total mesh must form a convex polygon, as shown by the yellow area. The three points that make up vertices of a triangle, when circumscribed by a circle, must not contain any other seeds (points) within that circle. The diagram below also demonstrates the relationship to the resultant Voronoi diagram shown in lighter weight lines. There’s also an excellent interactive explanation at the Cartography Playground.

Example of the construction of Delaunay triangulation

Possibly the most evident use of Delaunay triangulation is in the application of Triangulated Irregular Networks (TIN) meshes for 3D terrains in GIS, but also used more widely in other forms of 3D modelling and game development. It’s a form also commonly used in photogrammetry when building models from point clouds.

Image of abstract form made up of TIN mesh

Developing parallel but coexistent worlds (terrains) modelled with photogrammetric tecnhniques.

This process also seems to lend itself to a great deal of artistic expression. There are numerous tools available for turning any image in to one made up of Delaunay triangles.

Photograph converted to Delaunay triangles

Triangulated mesh generated online by Triangulator, an online Delaunay triangulation image generator by Javier Bórquez.

Photograph converted to Delaunay triangles

Illustration for by Puckey Studio using their own developed tool for triangulated image extraction. They are developing their own app which should also allow point editing. One to watch.

The bottom line is I’m fascinated by tools that generate mathematical abstractions of reality; a simplification and generalisation process that has parallels to cartographic practice, and in form. Perhaps that is what appeals?