Variations on Voronoi

Lately I have returned to the awesome Processing library, which provides a very simple infrastructure for creating interactive experiments that produce nice images. I have not been using it since version 2; the last time I was using it was in 2009, I think. It was mostly a need to do something different from my daily routine that made me return to Processing, since I have very fond memories of toying around with Processing. Working with Processing made my again painfully aware of the differences between Java and C#, but overall it was a pleasant experience leading to pictures like this here:

Definitely not a Voronoi diagram.
A picture that is definitely not a Voronoi diagram.

The program that I have been working on is inspired by Voronoi diagrams. Voronoi diagrams take as input a plane (say, the unit square) and a set of distinguished positions in that plane. For each point of the plane, the output at that point is the closest of the distinguished positions to that point. This information can then be used to color the plane, yielding a picture of colored cells, see Wikipedia. There are several ways to compute a Voronoi diagram, the one I decided to use probably does not count as a sensible method: Our plane is a picture (which means that it is subdivided into pixels) and we compute the diagram iteratively by repeatedly adding the pixels surrounding each distinguished point to its cell. Each pixel is given the color of its cell (the cell color has been predetermined in some way using the associated distinguished point) and after sufficiently many simulation steps, we get a finished diagram, like this one here:

Looks like a Voronoi diagram with a Manhattan metric.
Looks like a Voronoi diagram with a Manhattan metric.

One thing that might happen in this simulation is that a pixel is halfway between two distinguished points, in which case that pixel is added to whichever cell is simulated first in the update step of the simulation. Alternatively, we can simply note that pixel as conflicted and color it black. Note also that I never specified what exactly surrounding pixels means in this context: The most sensible notions that come to mind is that for any pixel, its neighbors are given by its left, right, top, and bottom neighbors. You could also add in the diagonals. Or do something entirely different, which will generate Voronoi-like-diagrams for different metrics (check for yourself whether a measure of distance given by such a neighborhood actually induces a metric). This generates pictures such as this one:

Voronoi-like diagram with a strange distance measure
Voronoi-like diagram with a strange distance measure, simulation is still running
Voronoi-like diagram with a strange distance measure
Voronoi-like diagram with a strange distance measure

Of course, there are several factors that can be changed to create interesting pictures:

  • the kind of neighborhood used to determine surrounding cells
  • the initial distribution of distinguished points
  • the initial colors of every cell
  • how we color pixels belonging to a cell (just the solid color? take the distance into account? do some crazy bit-arithmetic based on the current cell size?)
  • how we handle conflicts (always mark them as black borders? give the pixel to one of the conflict partners at random? etc.)

To explore the kinds of pictures that arise in this way, I wrote a program to specify these parameters and tweak them during the simulation, which leads to rather interesting pictures showing great diversity. Actually, I lied a bit: Before writing the program, I felt the need to write a simple custom GUI library for Processing, because it does not come with one and the ones I tried did some things that I didn’t like (this, of course, is not a good reason to write a GUI library – or any library at all, – but integrates neatly with the mindset of most programmers I know). Here are some of the pictures generated with the program, along with some detail-shots at the pixel-level (click the pictures to get a larger view). I am also currently experimenting with printing, you can buy prints here.