I have to confess... I've been a little obsessed with triangular shapes.

This obsession actually goes back a couple of months ago, when I worked on a little sketch where I tried to pack as many triangles as possible, as closely as possible, somehow coming up with a peculiar triangle packing algorithm. While this take on triangle packing was super fun to make and nets you visually interesting results, an alternative method to split a plane into triangles would be the construction of a Delaunay Triangulation. I attached some of the artworks I've made with Delaunay triangulations to this post, as well as the sketch where this entire triangle thing started:

Consider this post an initiation into Delaunay triangulations and related concepts like Voronoi tessellations, as well as the many methods with which they can be achieved. So much interesting art has come from these two techniques, so much so that I believe the topic requires a little attention from everyone who wants to seriously get into creative coding. In terms of different things you can do with these techniques, we've got quite some ground to cover.

Delaunay triangulations were coined after Boris Delaunay for his research on this topic in 1934, and we'll talk a little bit more about him in one of the following sections, as well as Georgy Voronoy, both of which actually knew each other.

For now, you just need to know that for our purposes a triangulation simply means the subdivision and/or partitioning of a geometric shape into smaller triangles. Delaunay triangulations additionally  also have many geometric properties that are useful for a plethora of applications across various fields, and can in many ways be used to derive a dual Voronoi diagram, and vice versa!  Let's first have a look at some creative things that have been created with these two space partioning algorithms.

Creative coding with Delaunay Triangulations

One artwork that really stands out, and that probably serves as a good starting point would be Ignazio Lucenti's amazing Delaunified portraits:

I find these to be incredibly visually appealing, almost like the faces are woven out of thin threads. This is done by first sampling some points on top of the portrait, where the points are more frequent over the coloured regions of the image and then connecting them with a Delaunay triangulation.

As mentioned earlier, delaunay Triangulations always bring with them a dual Voronoi Tesselation, and we'll talk more about the technical aspects of this later, but for now it's interesting to have a look at some more pieces of art that also make use of Voronoi diagrams. The most mind-blowing piece I've seen using Voronoi tessellations is Raven Kwok's generative music video for the track Skylines by Karma Fields, which is just really brilliant on so many levels:

Another artist who's really harnessed Voronoi Tesselations as an expressive medium is Michael Kennan. I remember first coming across his work on the generative subreddit, where he posted a piece titled 'Im Sturz durch Raum und Zeit':

This must have been one of the earliest sketches that I've come across on the subreddit, and left me utterly clueless as to how something like that would be possible. At this point I believe that it makes use of Lloyd's algorithm with which you can turn a Voronoi diagram into a centroidal Voronoi diagram. More on that in a future post though.

With a few modifications Voronoi diagrams also allow for interesting stippling and pointillist effects and artworks, which is a huge topic in of itself:

Stippling is the creation of a pattern simulating varying degrees of solidity or shading by using small dots. And it turns out that Voronoi diagrams can be used to achieve this effect, turning a given source image into one that is made out of many dots. I think that at this point it's clear, that spending some time with Delaunay triangulations and all the related topics is a worthwhile endeavour for creating interesting artworks.

Besides being aesthetically pleasing, Delaunay triangulations are also really useful for a lot of practical applications, for example terrain generation, or creating minimum spanning trees that connect rooms in a procedurally generated dungeon:

One last thing worth mentioning here is that Delaunay triangulations are probably also great tools for creating low-poly graphics and aesthetics, as an ode to an aesthetic from an era long past where game devs had to make do with limited computational resources. Nowadays low-poly games don't always entirely use triangular shapes, here's a really cool post by Martyna Stachowiak from Displate on this aesthetic in any case.

Origins

Delaunay Triangulations and Voronoi Diagrams are not only mathematically closely related but also historically. The most comprehensive resource on this relationship is Liebling's and Pournin's paper titled 'Voronoi Diagrams and Delaunay Triangulations: Ubiquitous Siamese Twins'. The very first paragraph reads beautifully:

Concealing their rich structure behind apparent simplicity, Voronoi diagrams and their dual Siamese twins, the Delaunay triangulations constitute remarkably powerful and ubiquitous concepts well beyond the realm of mathematics. This may be why they have been discovered and rediscovered time and again. They were already present in fields as diverse as astronomy and crystallography centuries before the birth of the two Russian mathematicians whose names they carry. In more recent times, they have become cornerstones of modern disciplines such as discrete and computational geometry, algorithm design, scientific computing, and optimization.

I really recommend reading at the least the first two sections of the paper as it draws a beautiful picture of how both Delaunay triangulations and Voronoi diagrams were discovered and re-discovered over the years, in addition to some interesting anecdotes and stories around the people that explored this field of mathematics. Unsurprisingly Voronoi was actually a friend of Delone's (Boris Delaunay) father, which had a big influence on his later work and can be inferred from the title of his 1934 paper 'Sur la sphere vide. A la memoire de Georges Voronoi.' (French for: On the empty Sphere. In memory of Georges Voronoi.)

At this point in time it is hard to say exactly what kind of relationship Voronoi and Delone had, and it seems like Voronoi was not actually Delone's supervisor (based on the paper I just mentioned). I genuinely couldn't find out more about it however. An additional fun fact here is that Georgy Voronoy was a student of Andrey Markov, who worked on the concept that is better known today as Markov Chains.

The very first instance of Voronoi diagrams dates back much further than Voronoi's times, all the way back to the Renaissance where Renes Descartes created the first Voronoi Diagram on record. Image from the same paper:

Another historical record of Voronoi diagrams is the figure to the right by John Snow (not the guy from Game of Thrones), where he was able to pinpoint a  defective water pump with a Voronoi diagram. That defective pump was at the root of a cholera outbreak in Victorian England. Actually a very interesting story, you can read more about it here and here. I'm not exactly sure of the timeline here, but Dirichlet was working with Voronoi diagrams around the same time, which is why Voronoi diagrams are also sometimes known as Dirichlet Tesselations. Voronoi then later extended Dirichlets ideas to higher dimensions.

https://mathshistory.st-andrews.ac.uk/Biographies/Voronoy/

So what's a Delaunay Triangulation?

A Delaunay triangulation for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P).

Wikipedia sums up Delaunay triangulations succinctly. A valid Delaunay triangulation hence needs to satisfy the condition that none of it's vertices are inside the circumcircle of any of the triangles that make up this triangulation.

In other words, given a set of points, we need to draw edges between these points in such a manner that a triangular mesh emerges. None of the initial points are allowed to be contained within the diameter of any circumcircle of the triangles that make up this mesh. Ultimately, all points should lie on these circumcircles, where the circumcircle is the circle centered at the circumcenter of a triangle, which is a point that is equidistant from all three vertices of the triangle.

There's a number of procedures for constructing such a triangulation, one of them being the Bowyer-Watson algorithm, which I'll cover in the next post. Furthermore, as mentioned a couple of times already, we can derive the dual Voronoi diagram from this Delaunay triangulation, simply by connecting the circumcenters of adjacent triangles:

Voronoi Diagrams

A Voronoi diagram can also be constructed without the delaunay triangulation. Given a set of points, we want to partition and assign a portion of the plane to each one of those points, in such a manner that each position in a given region is closer to that point than any other:

And again there's a number of algorithms to achieve Voronoi diagrams, I haven't decided yet on which one to cover, but a popular sweep line algorithm is fortune's algorithm (obviously in addition to the Bowyer-Watson algorithm as an indirect approach).

And that's all I've got for you this time around. Keep your eyes peeled though there's gonna be a bunch of new posts very soon on Delaunay triangulations and Voronoi Diagrams, as well as Lloyd's relaxation and weighted Voronoi stippling! Thank you for reading, and if you've enjoyed reading, consider supporting by sharing this post or following me on my social media accounts, cheers!