In April 2019 I didn’t know about a term generative art. I wanted to use Math and programming skills implement something visually pleasing. Metaballs seemed a good idea to start with. I collected some information and stumbled upon nice article of Jamie Wong “Metaballs and Marching Squares”. He mentioned “Voronoish” style example. I recalled Voronoi diagrams and… here we are.

I don’t know if it’s a good idea to implement classic algorithms from scratch. I enjoy it as it is a good chance to become better developer. Also don’t be mistaken that implementing FortunesAlgorithm is just a matter of typing what’s said in the book. Believe me, platform restrictions and cruel edge cases wont let you relax.

## The goal

To understand this article you should be familiar with Euclid geometry. Computer Science background and some proficiency in Swift language are also required.

## Definition

Voronoi diagram is a diagram that assigns a set of predefined points in a plane into an equal number of cells, such that each point ${p}$ is inside a cell consisting of all regions closer to ${p}$ than to any other point.

## Intuition

Assume You own N data transmitters. Each of your customers can connect to one and only one transmitter (the closest one). Knowing geographic coordinates of each transmitter, how to count approximate number of customers?

Let’s rephrase it a bit.

Suppose we have some magnets and metal balls placed on the table. Each magnet has the same attraction force. Magnet attracts a metal ball closest to it. Or ball will be assigned to the nearest magnet. As it illustrated on fig 1, magnet A will attract all the metal balls placed in the cell colored blue, B - red and so on.

In computational geometry magnets are called Sites. Geometric interpretation of the model where point is assigned to the nearest site is called Voronoi assignment model. If we contour the regions of attraction for each magnet, we will receive planar subdivision called Voronoi diagram of the set of sites.

Voronoi diagrams are fundamental data structures that have been extensively studied in Computational Geometry. Range of Voronoi diagrams is very wide. They are used in physics, astronomy, robotics, spatial analysis, social geography, computer graphics and many more. There are many of Voronoi diagrams1.

## Fortunes algorithm

Fortune’s algorithm is a sweep line algorithm for generating a Voronoi diagram from a set of points in a plane using O(n log n) time and O(n) space. It was originally published by Steven Fortune in 1986 in his paper “A sweepline algorithm for Voronoi diagrams.”

## Home work

Here is a list of definitions required to understand the implementation:

• Input
• Site

Processing - Circle event - Site event - Sweep line - Beach line

• Output
• DCEL
• Cell
• Half-edge
• Vertex
• Site

The list is based on understanding of the following Geometry and Computer Science concepts:

Geometry:

Computer Science:

If you are not familiar with some of them - don’t worry. You will be provided with brief explanation and resources for further reading. Also you can always come back to this list at any time and refresh your memories.

Hope you will be interested in Part 2 Where reader will be provided with an easy to grasp explanation of DCEL data structure.

Sincerely yours, @fewlinesofcode!

## Sources

1. Camille Wormser. Generalized Voronoi Diagrams and Applications. Computer Science [cs]. Université Nice Sophia Antipolis, 2008. English. tel-00410850

2. Fortune, S. A sweepline algorithm for Voronoi diagrams. Algorithmica 2, 153 (1987). https://doi.org/10.1007/BF01840357