There are many areas of math and computer graphics where I have some surface-level familiarity, but have never personally dug deep. Every now and then something inspires me to do so. Voronoi recently came into my cross hairs, and I started looking into it.

I first encountered the classic Voronoi pattern in my early teens while tinkering with 3D graphics in Blender. Blender offered Voronoi as a procedural texture. I can't recall if I ever found a great use for it, but I experimented with the settings as the texture itself was fascinating to me. I had no idea how it was generated, and never really looked into it.

Recently, I was watching Matt Parker talk about the Scutoid and he showed an animation of how Voronoi cells are generated from a set of points. Essentially, given a set of 2D points, if you extend a circle outwards from each point until all the space is filled you end up with Voronoi cells around each point. I was thrilled seeing how such a simple technique was used to generate the pattern I've been vaguely familiar with for so many years.

This geometric intuition prompted me to experiment with generating a Voronoi pattern myself. I wanted to start simple, and so I used a brute force approach. There are absolutely better algorithms, such as Fortune's algorithm which works in O(n log n) time. For my experiment, I realized I could iterate through all pixels in the image to be generated, and compare the distance of each pixel to each Voronoi seed point. The closest point would determine which cell that pixel belonged to. By assigning random colors to each Voronoi seed point, and using the distance of each pixel from the target point to alter how bright the color appears, every cell is filled with a unique radial gradient. This algorithm's time complexity scales exponentially with the number of seed points used and the number of pixels, but it's incredibly simple and was a fun experiment. Check out the result below, and click to generate a new random pattern.

Other Demos

There is a cool interactive Voronoi generator that allows you to experiment with how points affect each other in real time.

It also occurred to me that Voronoi cells could be generated in 3D space. By generating a 3D point cloud, and using 3D distance calculations, the result would be a collection of 3D polyhedra with a distinct Voronoi form. I found an interactive demo that does just this. Pretty neat!