I’ve been writing a lot of code for my next video in Code, Sound & Surround. One small part of that has turned out to be interesting enough to show off on its own. I built some tools for plotting and animating Voronoi diagrams in Ruby, and now I’ve published them on GitHub.

Update: I’ve also made a YouTube video showing these geometric algorithms.

A Voronoi diagram (Voronoi rhymes with “enjoy”) or Voronoi partition shows which areas are closest to a set of starting points. Choose one or more points on a 2D plane (you can also do 3D or higher, but I haven’t done that). Draw a convex polygon around each point, showing the area that is closest to that point. That’s a Voronoi diagram.

Each edge of a polygon should be half-way between two points, and each corner of a polygon is equally distant to three or more points. Every polygon has one point inside it, and every point has one polygon around it, with no overlap. Give each surrounding polygon its own color, and you get something like this:

Skip ahead to the applications section to see how to make your own animations with my code, or keep reading to learn more about the math and geometry behind them.

Triangles and circles

The Voronoi diagram is related to another concept, called a Delaunay triangulation. My code uses Delaunay triangulation to build its Voronoi diagrams. Delaunay triangulation is a way to connect a bunch of points together into triangles, such that no point is inside a triangle, and no point is inside of a triangle’s circumcircle (a circle drawn through all three corners of a triangle). This reduces the chances of there being really thin and long triangles.

The center of each triangle’s circumcircle corresponds to a corner/vertex of a Voronoi polygon – a point equidistant to three or more points. Each edge of a Voronoi polygon is a perpendicular bisector (a segment rotated 90 degrees at the edge’s midpoint) of an edge of a Delaunay triangle. You can see this below, where I’ve overlaid a Voronoi diagram with a Delaunay triangulation.

Challenges and edge cases

Unlike the Voronoi diagram, a Delaunay triangulation is not always unique for a given set of points, and a Delaunay triangulation only exists if there are three or more points not on the same line. If four or more nearby points are all on the same circle, with no points inside the circle, then the triangulation is not unique. Note that the corners of a square, or any other regular polygon, all lie on a circle, so this happens fairly often! Both of the images below are valid Delaunay triangulations of a perfect square:

On top of the ambiguity of collinear and co-circular points, another difficulty arises if two or more points get very close together. When points are very close together, or very nearly (but not quite) on the same line, floating point rounding error can lead to bugs or crashes in implementations of Delaunay triangulation. This is either because the circumcircle radius becomes extremely large, or because the distances and angles between points become extremely small.

Often, animating a bunch of points can just happen to make two or more points land in the same place, so a robust implementation of Delaunay triangulation and Voronoi partitioning needs to take rounding error into account. Otherwise you can get some surprisingly incorrect results, such as this single frame from an animation where several points end up in the same place:

Applications

So that’s a bit of the geometry underlying Voronoi diagrams. What are they used for? Voronoi diagrams and Delaunay triangulations find application in computer graphics, geospatial information systems, art, and more. Delaunay triangulations help generate good polygon meshes for randomly sampled height maps. Voronoi partitions help locate the nearest point of interest on a map. And by carefully choosing where we place our input points, and by animating those points, we can create some really striking images and videos with a sort of stained glass look.

How it works

I’ll go into more detail about how the algorithms work and how the code is structured either in my next video or in a future blog post. For now, you can explore the mb-geometry Ruby source code, and use the command-line tools I’ve provided to make your own animations.

The command-line tools I’ve released use a simple JSON or YML file to describe where points should be, and a few command line options (or a bit of Ruby code) to animate them. The source code of my voronoi_transitions.rb script shows how this works, and I’ve placed some examples below.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# square.yml
bounding_box:
  - -1
  - -1
  - 1
  - 1
points:
  - :x: -0.75
    :y: -0.75
  - :x: -0.75
    :y: 0.75
  - :x: 0.75
    :y: 0.75
  - :x: 0.75
    :y: -0.75

1
2
3
4

XRES=640 YRES=640 \
bin/voronoi_to_svg.rb \
  test_data/square.yml \
  /tmp/square.svg

1
2
3
4

# 3gon_polygen.yml
generator: :polygon
sides: 3
radius: 2

1
2
3
4
5
6
7

XRES=640 YRES=640 \
DELAUNAY=1 \
CIRCUMCIRCLES=1 \
bin/voronoi_transitions.rb \
  /tmp/3g.mp4 \
  test_data/3gon_polygen.yml 1 30 \
  __cycle 60 30

Thanks for reading, and be sure to check out the mb-geometry source code on GitHub! And if you view the HTML source of this post, you’ll see I documented how I made some of these images in the HTML comments. Cheers!