Introduction

I've worked this project in between December 2017 and January 2018. I had known about (and was fascinated by!) Voronoi diagrams since I've come across them in the summer of 2016 (I think?). They looked cool and organic. But I never got any headway when I looked into the algorithms so I never looked much deeper into it.

Then, I was looking into Greg Egan's Zendegi and saw a comment by Craig Kaplan, on Islamic Star Patterns. This unveiled the huge amount of mathematical work done of Islamic Tilings and, in particular, I thought to apply Hankin's method to less regular tilings, like those generate by Voronoi diagrams! I had by this point taken more algorithmically heavy classes, so I was more comfortable with looking into Fortune's algorithm (which is very unique!) and things got going. Unfortunately, my idea didn't pan out at all,since the regularity of the tilings was more important than I expected.

I didn't want the whole thing to go to waste, so I decided to look into Wallpaper Groups instead and apply them to the voronoi tilings. I also discovered Craig Kaplan's paper with a similar idea.

How does it work?

Voronoi diagram

A voronoi tiling is a pretty elegant idea - you start with a set of generator-points, and the diagram divides the plane by the set of points that are closer to the generator than any one. It's a kind of nearest-neighbor, but the results are pretty cool!

To generate a symmetrical tiling, you just generate to use a symmetrical distribution of generator-points. To do this, enter wallpaper groups.

Wallpaper Groups

Wallpaper Groups are 17 different ways of transforming set of points symmetrically, in a way that extends infinitely in every direction. You typically start from a simple triangle and then copy it, rotate it, mirror it, and so on, throughout the plain. If you choose generator-point inside that triangle, you can then set them up symmetrically as well, and then apply the voronoi diagram.

In sum

• Choose the type of wallpaper symmetry you want;
• Generate a few points inside the triangle;
• Apply the wallpaper transformations;
• Apply a Voronoi algorithm to the resulting points.

Coloring

The easiest way to color a voronoi tiling is to assing a color to each of the points, and let the wallpaper groups take care of the rest. You can also change the color whenever you transform the triangle. This was harder to work with, but some of the examples could be pretty cool, as you can see below.

Conway et. al's book The Symmetry of Things has a pretty good treatment of frieze and wallpaper groups, and also color symmetry, but I confess I haven't look deeply into it at didn't implement it at the time. Instead, I contented myself with coloring the initial points (on the triangle) and let that be.

Related Work

First, there's Greg Egan, Craig Kaplan, and even Peter Cromwell (which I knew from his work on Celtic Knots!) on Islamic Star Patterns. The literature is much deeper on this point, and very interesting. Jay Bonner's book is probably the most comprehensive one on the subject, with a chapter by Kaplan on computer rendering (with variations on spherical and hyperbolical geometry). There are many different approaches to Islamic Star Patterns, from Hankin's method to tile substitution to recursion and aperiodicity (some of which may be spurious, but hey, still interesting to look into!).

Then, about the voronoi tilings, you can also see Kaplan's work, or Jos Leys' (who is better known for fractals).

Gallery

Software

You can download this one on my itch.io page. If you want to look into the code, feel free to ask.