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.

Note to myself – Image Magick commands that you will use

Dear future me, here are some ImageMagick commands that you will end up using over an over again and have to look up repeatedly (unless I write them down now, in which case you will surely remember all of them):

  • Convert from from one image format to another (PNG in this case):  mogrify -format png <files>
  • Resize pictures:  convert <input> -resize 25% <output>
  • Add label to the bottom right:  composite label:<text> -gravity southeast <input> <output>
  • Add a white border to the image:  convert -bordercolor White -border 10x10 <input> <output> 
  • Arrange images horizontally such that the spacing between images is just as large as the frame of the whole batch (20px, in this case):  cmd /c "montage preview-1.png preview-2.png preview-3.png -geometry 500X500+10+0 -tile x1 - | convert - -bordercolor White -border 10x20 preview.png" — note the use of CMD here, since Windows PowerShell screws up piping of binary data (“Hey, it’s a string, let’s make it Unicode!”)
  • Cut out the center in a square format:  convert <input> -set option:distort:viewport "%[fx: w>h ? h : w]x%[fx: w>h ? h : w]+%[fx: w>h ? (w - h)/2 : 0]+%[fx: w>h ? 0 : (h - w)/2]" -filter point -distort SRT 0 +repage <output>
  • Cut out the center in a 2/3 format:  convert <input> -set option:distort:viewport "%[fx: w>(3/2*h) ? 3/2*h : w]x%[fx: w>(3/2*h) ? h : 2/3*w]+%[fx: w>(3/2*h) ? (w - 3/2*h)/2 : 0]+%[fx: w>(3/2*h) ? 0 : (h - 2/3*w)/2]" -filter point -distort SRT 0 +repage <output>