The state of d3 Voronoi (2017)

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:

Voronoi shader

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),
links = diagram.links(), // Delaunay graph
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).