# The state of d3 Voronoi (2017)

9 January 2017

A Voronoi diagram is a simple yet powerful concept; given a set of sites in a space, it partitions that space in cells — one cell for each site. Each cell contains all the points that are closer to that site than to any other. This is useful in many different areas, such as spatial/network analysis, pattern recognition, label placement on maps and graphics, generative games, generative art, UX improvements and all sorts of experiments. Here we explore what our favourite javascript library, d3.js, allows to do with this concept.

#### by Philippe Rivière

Note: this article was published in 2017 and a lot has happened since then in the land of D3 & Voronoi. See d3-delaunay for up-to-date examples.

— -

In 1854, in Soho (London), the physician John Snow did nearest-neighbour calculations to understand the causes of a cholera epidemy — and was able to link it to the water pump on Broad Street.

What’s important to understand is that the Voronoi diagram is not always meant to be drawn directly. It is a topological structure that can be used to compute networks, or to increase the user experience when interacting with graphics, as the following examples demonstrate.

the following variation by Frank Lebeau shows the underlying (hidden) cells, which can be computed with the d3-distanceLimitedVoronoi plugin:

This technique has been given an upgrade recently with the introduction of `voronoi.find()`, see this nice tutorial by Peter Beshai.

There are also lots of uses for maps, which is what drew me to it initially.

Scientists use Voronoi cells to simplify 3D structures of proteins, where it is crucial to know if there is a physical geometric complementarity between, for example, an antibody and an antigen. So you can have an idea that your candidate drug is going to fail before you try it in the test tube. For them, a Voronoi model is literally worth hundreds of thousands of dollars.

#### Let’s draw

A naïve algorithm would paint pixels with a different color for each site, like this:

However this is awfully slow, in `O(n*x*y)`. And the results are pixels, not an abstract layout, which means that they’re difficult to reuse for geometric calculations. What we want in most cases is not just to paint the cells, but an actionable topology, so that we can interact with the cells, compute their surfaces, know which cells are neighbors to which, etc.

So, exit painting, enter computational geometry.

(Georgy Voronoy, Boris Delaunay, Delaunay triangulation & Voronoi Diagram.)

At the d3 unconf in San Francisco, in October 2016, we showed how to draw Voronoi diagrams by hand. Here are nice results from participants:

Thankfully, d3 does this for us!

## d3-voronoi

`d3-voronoi` is the standard D3 module that helps draw Voronoi diagrams [1]. It offers methods to compute a 2D planar euclidean Voronoi, with optional rectangular clipping.

The D3 Voronoi layout — an object called `Diagram` — is computed with the constructive (and exact) algorithm published by Steven Fortune in “A sweepline algorithm for Voronoi diagrams” (1986), and implemented by Mike Bostock, largely based on work by Raymond Hill.

`d3-voronoi` allows an easy and fast computation of the Voronoi cells, as well as the (closely related) Delaunay triangulation of the sites, in the shape of links (which for some reason are exposed as directed source → target) or triangles.

The API can’t be more concise:

``````var voronoi = d3.voronoi();
var diagram = voronoi(sites),
triangles = diagram.triangles(), // Delaunay triangles
polygons = diagram.polygons(); // Voronoi cells``````

For our aesthetic pleasure as well as for some practical uses, `d3-voronoi` allows clipping the Voronoi cells to a (rectangular) bounding box.

``````var voronoi = d3.voronoi()
.extent([[-1, -1], [width + 1, height + 1]]);``````

(The way this extent affects the Delaunay links is, unfortunately, not as gracious. Rule of thumb: don’t use extents if you’re going to use the triangulation, use extents if you’re going to use the polygons.)

## Extensions

### Other geometries

Cylinder. Computing a Voronoi diagram on a cylindric space has probably not many applications, but it makes a gentle introduction to the next level. The recipe is almost straightforward, leveraging the planar algorithm on three copies of the dataset (one placed on the left, one at the center, one on the right), and extracting the polygons and links that belong to the center.

Torus. Computing things on a torus (where the top is stitched to the bottom, and left stitched to the right), is remarkably friendly: all polygons are finite, and all are treated in exactly the same way — our space is finite but is has no edges! This time, we need nine copies of the sites (three vertically, three horizontally). Still running in `O(n log(n))`!

But these were just an appetizer for the main course: the spherical (or geo-) Voronoi.

#### geo-Voronoi

As Jason Davies has magistrally demonstrated, the Voronoi layout can be a powerful and beautiful tool for the sphere. Earth — or any other spherical object, including VR photo scenes — can put such a diagram to use.

The geometry of the sphere (finite, geodesic distance, etc) makes striking graphics. Several algorithms have been proposed to compute the spherical Voronoi diagram. I managed to build a wrapper around Loren Petrich’s Delaunay Triangulation library to create `d3-geo-voronoi`. It is not perfect, but it has the merit of being available now and shared as a free/libre library.

The API for `d3-geo-voronoi` is based on geojson: it will return the cells as `FeatureCollections` of Polygons (including the `{Sphere}` if you pass it only one site).

Simple examples from https://github.com/Fil/d3-geo-voronoi :

#### Nearest-neighbour, aka Voronoi.find()

This extension to `d3-voronoi` is a very simple but very fast nearest-neighbor algorithm. It builds upon the pre-computed Voronoi layout to answer the following question: my mouse is at (x,y), which is the closest site?

This function’s API is similar to `simulation.find()`. Its raw speed — in `O(sqrt(n))` once the Voronoi Diagram has been computed — makes it cheap to use it a lot, for example to do Voronoi binning, or graph analysis.

This function has been integrated recently into `d3-voronoi`. It is also available with `d3-geo-voronoi`.

With `Voronoi.find()`, we can trim down Nadieh Bremer’s UX example, remove the hidden SVG layer and directly compute the site that is closest to the mouse.

Same with the multi-line Voronoi example:

#### Urquhart graph, alpha shapes, convex hull…

The Delaunay graph almost begs to be processed for network analysis.

Alpha shapes are obtained if you remove all Delaunay links that are longer than a certain threshold α, then merge the surviving triangles. They can be used to construct shapes from sets of points.

(initial block by zpconn, merge function from Jason Davies)

Urquhart graph. The Urquhart graph is a subset of the Delaunay. It is obtained by removing the largest edge of each of the Delaunay triangles. Removing edge AC from the triangle ABC does not break the connectedness of A to C, which are still connected through the connection that exists from A to B, and from B to C. Hence the nice property: the Urquhart graph is fully connected, in other words it is a spanning graph. Also, it contains the minimal spanning tree.

`d3-geo-voronoi`’s links have an additional `urquhart` property, making it easy to visualize:

Convex hull.

### ✪ ✪ ✪

And now some considerations about future developments.

## More extensions are needed

#### Weighted Voronoi

Suppose you are working with sites of different importances. You will be tempted to ask for cells with a surface that reflects the relative importance of each site. The Voronoi diagram, and Fortune’s algorithm do not allow this. Of course we’re not totally blocked: we can have fun creating various experiments to sort-of give more importance to some sites (e.g. by giving them “more dots”, or using “Voronoi relaxation”).

Weighted Voronoi” allow a direct and exact computation, as Jason Davies has demonstrated. Weighted Voronoi diagrams come in several flavors: additively weighted, power diagrams, multiplicatively weighted.

Franck Lebeau has published a library to compute weighted Voronoi diagrams.

#### Non-euclidean distances

The Euclidean distance `sqrt(dx^2+dy^2)` (aka bird fly distance) doesn’t express the complexity of all real-world processes.

For example, take the Manhattan distance, where the time it takes to walk from one place to the other is computed in number of blocks that must be walked in the two dimensions (N-S / E-W), not in a diagonal line.

If you work on (say) accessibility, the distance is even more complex: it is in itself a routing cost computation where you will weigh the (bird fly) distance with the time it takes to go across that space. i.e. walking 1km across a swamp takes 2 hours, whereas running on a track takes 10 minutes.

#### Faster algorithms

Fortune’s algorithm in `O(n logn)` is very fast, but has to be computed wholesale from a given set of sites. It would be desirable to use an algorithm that allows for the addition/removal/update of sites without having to reboot the algorithm (issue #9).

The algorithm in `d3-geo-voronoi` is in `O(n^2)`, and although it works beautifully for hundreds of sites, it becomes painfully slow as the number of sites reaches 1000+, and impractical after 2000 sites (d3-geo-voronoi issue #1).

#### Approximated algorithms

With cylindrical and toric examples, we have seen that we could “wrap” the space before feeding it to our algorithms. But we can indeed transform it any way we want, compute the diagram, then send the results back to the initial space. This transformation could be called a projection, and the reverse operation the inverse projection (not necessarily a geo projection: the initial space is not always a sphere).

#### Shortest distance to complex objects

This is also very much needed in geography where the distance to the coastline determines which country owns the territory and exclusive rights in the seas and Oceans — from fishing rights to seabed and oil exploitation.

We should be able to approximate this by sampling points on the paths, and merging the resulting polygons. This will also necessitate arbitrary clipping.

#### Arbitrary clipping

Rectangular clipping is nice for demos and some applications but it’s a mathematical monstruosity. Circular clipping is also a thing, with a radius around each site. However, implementations that rely on the browser to do the clipping in screen space are not simple nor sustainable. Instead, use either `voronoi.find()` or the algorithm implemented in Franck Lebeau’s d3-distanceLimitedVoronoi plugin.

#### 3D

d3 is and intends to remain a 2-dimensional library, so higher dimensions are not part of the scope. However as a planar additive weighted Voronoi can be seen as a slice of a 3D non-weighted Voronoi, it might be useful to study the problem in a higher dimension.

#### Reliability

`d3-voronoi` can fail when sites are “almost collinear” or “almost coplanar”. This can be avoided in most cases by adding “some” random jitter — but then with random you can also get unlucky. Take home message: it most likely works, but sometimes it might fail (issue #12). Maybe a different algorithm would help (pull-request #13 by Adithya Abraham Philip).