Voronoi Stained Glass Maker

Scatter some seeds on a table. Give every spot on the table to whichever seed is closest. That is the whole rule, and it cuts the table into tidy polygons with no gaps.

The result is called a Voronoi diagram, after Georgy Voronoi, who defined and studied the general case in any number of dimensions in 1908. He was not the first. Rene Descartes drew such regions as early as 1644, and Dirichlet used them in 1850, which is why the picture is also called a Dirichlet tessellation. Meteorologists call the cells Thiessen polygons, so the name depends on which field you learned them in.

One rule, many places

The idea keeps being found again because the rule is so natural. John Snow’s 1854 map of cholera deaths in London carries a line marking equal distance between the Broad Street pump and its neighbors, which is in effect the boundary of that pump’s cell. People walk to the nearest pump, so a map of nearness is also a map of who drank from which one.

Animals draw the diagram without a pencil. Male mouthbreeder fish dig breeding pits in sand by spitting sand outward toward their neighbors. When the fish are crowded, the spat sand piles up into ridges between pits, and photographs of a pool floor show polygonal territories that researchers found to be very closely matched by a Voronoi tessellation. Each ridge sits where two neighbors push equally hard.

The same picture serves people who design things. A stained glass window is a flat region divided into pieces, with a line of metal between every pair of neighbors. Divide the region by nearness to a set of points and you get pieces that are never dented inward, which matters a great deal when each one has to be cut from a brittle sheet.

Why the cells are always convex

Take two seeds. The points that are equally far from both form a straight line, the perpendicular bisector of the segment between them. Everything on one side is closer to the first seed. So “closer to me than to that one seed” is a half plane, and a seed’s cell is what is left after intersecting one half plane for every other seed.

An intersection of half planes cannot have a dent, so every cell is convex. Counting with Euler’s formula shows there is not much to store either: a diagram of n seeds has about 2n corners and about 3n edges. Each edge is shared by two cells, so a typical cell in a large diagram has an average of just under 6 sides.

There is a second structure hiding in the first. Join two seeds whenever their cells share an edge, and the result is the Delaunay triangulation. Two seeds are joined exactly when some circle passes through both and has no other seed inside. Either structure can be read off the other, so a program may build whichever is more convenient. The widely used SciPy routine, for example, hands the job to the Qhull library.

Computing it without being fooled by rounding

The obvious method is the definition: start with the whole frame and cut it with one bisector after another. Done naively, with every seed cutting against every other, that is slow for large sets, and cleverer methods exist, the best known being Steven Fortune’s sweep line, which runs in time proportional to n log n.

But the obvious method has a shortcut that makes it fast in practice. Suppose a cell has been cut a few times and its farthest corner is at distance R from its seed. A seed farther away than 2R has its bisector more than R away, so it cannot touch the cell. Visit neighbors nearest first, stop when the rest are beyond 2R, and most cells are finished after a dozen or two cuts. This is how the Voro++ library builds cells.

The real difficulty is not speed. It is arithmetic. Computers round, and geometric programs make yes or no decisions, such as which side of a line a point is on. The trouble is easy to state. When the true answer is near zero, rounding can give it the wrong sign, and the inconsistency can spread until a program crashes or produces output far from the correct one. Exact arithmetic would cure it but is slow. The usual remedy is a filter: compute quickly, keep a bound on the error, and repeat with more precision only when the bound cannot settle the sign. Jonathan Shewchuk published fast adaptive tests of this kind in 1997.

So a diagram that looks right is not yet a diagram that is right. The difference is too small to see and quite large enough to spoil a cut.

Awkward inputs are exactly the pretty ones. A square grid of seeds puts four cells at every corner. Seeds on a circle send all their bisectors through one center. The cell-cutting approach handles this with a small, stated tolerance: a corner within a hair of the cutting line is treated as lying on it, as Voro++ does, so four cells simply keep the same corner. Whatever method is used, the honest step is to check the output afterward. Are the pieces convex? Do they overlap? Do their areas add up to the frame? Is every shared edge equally far from its two seeds?

Evening out the cells

Random seeds give a ragged diagram, with slivers beside sprawling cells. Stuart Lloyd met the same problem in a different trade. In a Bell Laboratories note dated 1957, published only in 1982, he asked where to place a limited number of signal levels so that rounding a voltage to the nearest level loses the least. His answer was a loop: assign every value to its nearest level, move each level to the center of mass of what it was assigned, and repeat.

In two dimensions that loop is build the diagram, move each seed to the centroid of its cell, build again. Each pass lowers a single number, the total of squared distances from every point of the frame to its seed, and the cells drift toward even, rounded shapes. A diagram whose seeds already sit on their centroids is called a centroidal Voronoi tessellation, and it is the reason relaxed patterns look calm.

Add a weight and the same loop draws. Adrian Secord used the darkness of a photograph as a density, so that centroids are pulled toward dark areas and seeds crowd there, which turns a picture into stipple dots. For glass, the same trick gives small pieces where the picture is busy and large quiet pieces where it is not.

Good starting seeds help. Poisson disc sampling, often called blue noise, keeps every pair of seeds at least a distance r apart. Robert Bridson’s method grows the set outward from existing samples, allowing up to 30 tries around a sample (the paper’s typical setting) before retiring it, and takes time proportional to the number of seeds. A sunflower spiral is another start: seed number n goes at a radius proportional to the square root of n, turned by 137.508 degrees each time.

From diagram to glass

A real panel has thickness between its pieces. In leaded work the pieces sit in H-shaped strips of lead called cames, which are soldered to one another, and the panel is then sealed with putty. The National Park Service notes that came ranges from 1/8 to 1 1/2 in wide, and that its strength depends on the center web, the heart, and on the flanges that cover the glass edges.

That heart is why a cutting pattern cannot simply reuse the cell outlines. Each piece has to be smaller than its cell by half the gap on every side. For a convex polygon this inward offset is exact: move every edge line inward by the same distance and intersect. A piece that is too small simply vanishes, and it is better to learn that on screen than at the bench.

Here is a panel to reproduce. Choose a rectangle 300 by 225 mm, blue noise, 160 points, seed 7, and 4 relaxing steps. The method lands on 162 pieces. The lead line, every shared edge counted once plus the frame, comes to 6.91 m. With a 1.5 mm gap the glass itself covers 582 square centimeters of the panel’s 675, so about a seventh of the area is not glass at all. Relaxing lowered the energy by 9 percent. Printed at full size the pattern takes two A4 sheets, and the 100 mm ruler on each sheet should measure 100 mm before any glass is cut.

A diagram has limits as a design. Every edge is straight and every piece convex, so it cannot follow the curve of a face or the stem of a flower the way a hand-drawn cartoon does. Average colors flatten detail smaller than a cell. And a screen color is only a guide to a sheet of real glass, which changes with the light behind it.

Two cautions belong with any pattern meant for the bench. Medieval glaziers split glass with a heated iron point and chipped the pieces to shape with a hooked grozing iron, and diamond-tipped cutters, which spread between the 14th and 16th centuries, allowed more precise cuts, but a cut edge is sharp whatever makes it. Lead needs more respect still. It enters the body mainly by breathing and swallowing, often from contaminated hands, and New York’s health department lists stained glass among hobbies with a high risk of exposure. Wash your hands and face before eating, and keep food away from the work.