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.

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.

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.

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?