Generating plane tilings with diagrams

I’ve finally set up a diagrams-contrib package to serve as a home for user contributions to the diagrams project—generation of specialized diagrams, fun or instructive examples, half-baked ideas, stuff which is not sufficiently polished or general to go in the diagrams-lib package but is nonetheless worth sharing.

As the first “contribution” I put some code I wrote for fun that generates tilings of the Euclidean plane by regular polygons.

So how does it work? I’m sure there are more clever ways if you understand the mathematics better; but essentially it does a depth-first search along the edge graph, stopping when it reaches some user-defined limit, and drawing polygons and edges along the way. This sounds quite simple on the face of it; but there are two nontrivial problems to be worked out:

1. How can we tell whether we’ve visited a given vertex before?
2. How do we represent a tiling in a way that lets us easily traverse its edge graph?

The first question is really a question of representation: how do we represent vertices in such a way that we can decide their equality? Representing them with a pair of floating point coordinates does not work: taking two different paths to a vertex will surely result in slightly different coordinates due to floating point error. Another idea is to represent vertices by the path taken to reach them, but now we have to deal with the thorny problem of deciding when two paths are equivalent.

But it turns out we can do something a bit more clever. The only regular polygons that can appear in plane tilings are triangles, squares, hexagons, octagons, and dodecagons. If you remember your high school trigonometry, these all have “special” angles whose sines and cosines can be represented exactly using square roots. It suffices to work in \(\mathbb{Q}[\sqrt{2}, \sqrt{3}]\), that is, the ring of rational numbers adjoined with \(\sqrt{2}\) and \(\sqrt{3}\). Put simply, we use quadruples of rational numbers \((a,b,c,d)\) which represent the real number \(a + b\sqrt{2} + c\sqrt{3} + d\sqrt{6}\). Now we can represent vertices exactly, so remembering which we’ve already visited is easy.

The other question is how to represent tilings. I chose to use this “zipper-like” representation:

data Tiling = Tiling [TilingPoly] (Int -> Tiling)

Intuitively, a Tiling tells us what polygons surround the current vertex (ordered counterclockwise from the edge along which we entered the vertex), as well as what configurations we can reach by following edges out of the current vertex. Thanks to laziness and knot-tying, we can easily define infinite tilings, such as

t4 :: Tiling
t4 = Tiling (replicate 4 Square) (const t4)

This is a particularly simple example, but the principle is the same. You can look at the source for more complex examples.

Of course, this doesn’t really show off the capabilities of diagrams much (you can draw regular polygons with any old graphics library), but it sure was fun!