Voronoi Whirls

Towards the end of previous posts on Sliders and Bézier Curve Animations, we could draw Polygon Whirls for any regular or irregular convex polygon using a recursive method.  I wanted to see if I could tile many convex polygons with whirls to fill an area.

Here is what I had in mind (all other convex polygons filled with whirls as well):

Expected Polygon Whirls Tiling

Basic Voronoi

While searching how to fill a space with convex polygons, I came across and learnt about Voronoi Diagrams.  If we get the individual Voronoi convex polygons, we can then draw the whirls within them as we did in previous posts.

The first piece of code I saw to do this in Python was this.  This code colors each pixel by computing the distance to all the seeds and figuring out the closest seed.  This didn't give me the polygons I need and to do that, I have to figure out the edges, vertices etc from the pixel colors.

After more searches, I came across these two Python implementations here and here.  Both of them needed some changes for them to work in Trinket (because Trinket does not have support for all libraries).  There were also bugs in both of them (incorrect edges at times in the former, division by zero errors in the later, etc).  I picked the former, which mentioned it is an implementation of Fortune's Algorithm.  I didn't quite understand the full Algorithm yet, but wanted to use the code to see if it helps.  Given Trinket doesn't support all libraries (like heapq for example), I had to create a separate file with just the needed functions (see min_heapq.py in the code below).

This code gave me a set of edges as the output as shown below: (the black dots are the random seeds, the inner rectangle is the bounding box and the red lines are the edges returned with the red dots being the vertices of the edges)

Voronoi Basic Edges

What I want is separate polygons corresponding to each seed.  My next step was to clip the edges so that they do not cross the bounding box.  One way to do that is to calculate the intersection of each edge with the four sides of the bounding box.  I first did that and then to keep it simple, I learnt about line clipping and used the code from here, which was better. (see line_clip.py in code below)

With this, I could get clipped edges as shown below (in blue):

Voronoi Clipped Edges

My next step was to connect the vertices on the border of the bounding box.  To do that, I sorted the vertices by x or y (depending on which side of the bounding box) and created edges between them in sequence. (see 'get_voronoi_polygons' function in voronoi_helpers.py in the code below)

This is what I had after this step:

Voronoi Filled Edges

At this point, I still had only the edges and no polygons.  To create polygons corresponding to each seed, I did the following:

• Calculated the distance from the mid point of each edge to each of the seeds
• For each edge, the closest two seeds are the cells that this edge belongs to
• For the edges on the border, there is only one cell

Next, to get the order of vertices in the polygon, I did the following:

• Calculated the approximate center (average of x and y of all vertices)
• Calculated the angle to the center from each of the vertex and sorted them
• Picked the vertices from the lowest to the highest angle to form the closed polygon

(see 'get_voronoi_polygons' function in voronoi_helpers.py in the code below)

With this, I could get polygons (set of vertices) for each of the seeds as drawn below:

Voronoi Polygons

As you can see from the previous image, there are more than two vertices (blue dots) on some edges because of how the Voronoi algorithm calculated the edges.  This will be a problem when we try to draw whirls, so I wanted to remove these unnecessary vertices in between.

To do this, I used the method described here to determine if a point is between two points.

(see 'get_voronoi_polygons' function in voronoi_helpers.py in the code below)

Finally, I now have simplified polygons corresponding to each seed as shown below:

Voronoi Simplified Polygons

Once we have clean polygons, we can do all kinds of stuff with them.

Here is an example of a basic colored Voronoi Diagram:

Voronoi Diagram

Here is all the code for generating basic Voronoi polygons:

Note: You can run, edit and make your own changes to all the code samples in this post and try them out (thanks to trinket).

  

Whirls

Now that we have basic Voronoi polygons, we can now draw whirls that we set out to do.  I used the same recursive method from previous posts to draw these whirls.

Here is an example of one such whirl with lines:

Voronoi Whirls with lines

Here are a couple of other examples with different line spacing between them:

Voronoi Whirls with lines other examples

We can also draw polygons inside themselves in a concentric way.  To do that I needed to know the center (or centroid) of each polygon and I found out how to do that here.  (Note that all our polygons are Convex in a Voronoi diagram)   There are also multiple ways to draw concentric polygons depending on the spacing between them.

Here are some examples of concentric polygons:

Voronoi concentric lines examples

We can also draw these lines closer to each other with gradient colors.

Here are some examples that show gradients for both concentric and whirls:

Voronoi gradients examples

We can also use different gradients for each of the polygons to make them even more colorful.

Here is an example for concentric polygons:

Voronoi random gradients concentric

Here is an example for polygon whirls:

Voronoi random gradients whirls

Here is the code for all the outputs shown above:

Note: You can run, edit and make your own changes to all the code samples in this post and try them out (thanks to trinket).  You can tweak the variables below to generate all the variations shown above.

 

Summary

Tiling polygon whirls turned out to be more involved than what I anticipated in the beginning. There are a lot of details I learnt during this process of making this work in Trinket along with some new geometric algorithms.

In the process, I also learnt about Voronoi diagrams and found them to be very interesting and beautiful. There are many other interesting variations / ideas using Voronoi that I would like to explore in the future.

All the code in this post is available on GitHub.

- Pardhav Maradani