Voronoi Diagrams

Back in Creating Gradients Programmatically in Python I presented some code for writing out PNGs according to some rgb-function of x and y.

The relevant write_png(filename, width, height, rgb_func) is here:

http://jtauber.com/2008/11/png.py

This enables one to quickly generate PNGs based on all sorts of functions of position.

For example, here's a Voronoi diagram:

Take any metric space and pick a discrete number of points in that space we'll designate "control points" (the black dots in the above example). Now colour each other point in the space based on which control point is closest. In other words, two points are the same colour if and only if they have the same "closest control point".

Here's how to generate such a diagram using write_png...

First of all, here's a function that given an (x, y) coordinate and a list of control points, returns a pair of:

• which control point is the closest to (x, y)
• what the distance was

def closest(x, y, control_points):
    closest = None
    distance = None
    for i, pt in enumerate(control_points):
        px, py = pt
        d = ((px - x) ** 2 + (py - y) ** 2)
        if d == 0:
            return i, 0
        if d < distance or not distance:
            closest = i
            distance = d
    return closest, distance

Now we can use this and write_png to generate a PNG Voronoi diagram for a given set of control points:

def voronoi(filename, size, control_points):
    def f(x, y):
        c, d = closest(x, y, control_points)
        # draw points in black
        if d < 5:
            return 0, 0, 0
        px, py = control_points[c]
        # just one way to generate a colour
        m = px * 255 / size
        n = py * 255 / size
        return m, 255 - ((m + n) / 2), n
    write_png(filename, size, size, f)

Of course, this is just a brute-force way of establishing the Voronoi diagram, but for just generating examples a few hundred points by a few hundred points, it's Good Enough.

Note the choice of colouring, based on the coordinates of the control point is just one of many possibilities. You could also just colour based on control_point number (i.e. c) The current approach has one disadvantage that two control points very close to one another can be given almost indistinguishable colours.

The example diagram was just randomly generated with the following code:

import random
from voronoi import voronoi
space_size = 200
num_control = 8
control_points = []
for i in range(num_control):
    x = random.randrange(space_size)
    y = random.randrange(space_size)
    control_points.append((x, y))
voronoi("voronoi.png", space_size, control_points)

You can read more about Voronoi diagrams on Wikipedia.