A few months ago I was playing around with Delaunay triangulations and realised today that I never wrote anything about it. Briefly, a Delaunay triangulation of a set of points is a way of drawing triangles connecting those points in order to maximize the minimum angle of all of the triangles. They often look something like this:

As you can see, the triangles are all pretty nicely-shaped with no long, skinny triangles or short, fat triangles to be found. Now, you've probably seen those desktop backgrounds with all the little colored triangles — that's what I wanted to create. It looks like Delaunay triangulation is the way everyone does it, so I wrote a little Python script to do the math for me.

The Algorithm

One of the more straightforward methods for finding a Delaunay triangulation is the Bowyer-Watson algorithm. This algorithm works by adding the points to the triangulation one at a time. It has basically 4 steps:

1. Add a point to the triangulation
2. Find all of the triangles whose circumcircles contain the new point (the "bad" triangles)
3. Remove the bad triangles from the triangulation, leaving a star-shaped hole
4. Re-triangulate the hole using the new point, i.e. connect each pair of hole vertices to the new point, making a new triangle

Simple enough, but how do we get the valid starting triangulation? Well, the easy way to do it is to start with a triangle that encloses all of the points we want to triangulate. There are a lot of algorithms out there for finding a bounding triangle for a set of points, but I don't really care whether or not my choice of triangle is optimal. I just started with a convex hull (which is easy to find) and then brute-forced a triangle using some of those edges. Some of the bounding triangles are pretty gnarly, but it works well enough for this purpose. Here's what that looks like with 20 random points:

That's probably not the smallest triangle that contains all of those points, but it doesn't really matter since it gets thrown out at the end anyway. Once it finds a bounding triangle, my algorithm scales it up a bit to make sure none of its vertices lie in the set of points to triangulate. So, starting with this bounding triangle, we add the points one at a time, using the Bowyer-Watson algorithm to update the triangulation. Here's what that looks like a step at a time using the same eight points from the beginning of this article:

Now that we can calculate a Delaunay triangulation of an arbitrary set of points, let's use it to make something nice to look at.

Pretty Pictures

Using Delaunay triangulations to generate interesting images is fairly simple. The first thing we do is generate some points to triangulate. I started with random points, but I wanted to generate right and equilateral triangles too. Fortunately it's easy to calculate points that will result in the kind of triangles I want. Once we've got the triangles, we need a method for coloring them. A popular one seems to be to use gradients, so that's what I started with. I tried a bunch of simple linear gradients and they all look pretty good. the color of each triangle is calculated based on the value of the gradient at its centroid with a random amount of darkening added to help each triangle stand out. Here are some samples of the output:

Neat. I thought it would be fun if I could triangulate images too, so I wrote some code that would take an image and use the pixels in the image instead of coloring the triangles using a gradient. Here's what that looks like:

The code is available on GitHub if you'd like to play with it. I've made some pretty neat desktops for myself with it, so hopefully somebody else will be able to enjoy it too.