d3.geo.voronoi

[mbostock]

This would probably make a good plugin rather than for core, since I don’t know how frequently it would be used, but @jasondavies and I discussed this in the past so I wanted to write it down somewhere.

Lots of people take the 2D Voronoi algorithm and apply it to projected coordinates, but this is misleading (probably especially in Mercator with Alaska) because of the distortion of the projection, and because the topology of a plane is different from a sphere.

Edit: what I thought was an example of this bad practice was actually done correctly using a spherical Voronoi diagram generator. Here’s what it made:

However, you can see some artifacts resulting from the Petrich’s generator sampling the great arc edges as polygons. D3 could do a better job here using adaptive resampling, with the edges between polygons being great arcs rather than pre-sampled.

An algorithm for computing Voronoi Diagrams on the Sphere doesn’t look too complicated — you transform the points and then compute a planar Voronoi, and then some additional magic I don’t yet understand. It’d be nice if we could release an easy-to-use d3.geo.voronoi that did the right thing, returning GeoJSON Polygons for cells in spherical coordinates.

[jasondavies]

I wasn’t sure how the two planar diagrams should be reconnected, so I took an alternative approach: the 3D convex hull of the spherical points is equivalent to the spherical Delaunay triangulation of those points. The spherical Voronoi diagram is the dual. My convex hull algorithm is a simple incremental O(n^2) approach but I think it can be optimised to O(n log n).

[jasondavies]

I fixed an orientation bug with voronoi centres. There is still an issue with Delaunay links that are longer than 180°. Here’s a stress test demonstrating the need for optimisations…

[mbostock]

Maybe slow, but still amazing. :)

[jasondavies]

I’ve figured out the issue with Delaunay. If the set of points is within one hemisphere, then the Delaunay triangulation has a boundary edge. Otherwise, the union of triangles covers the whole sphere. I’ve filtered the offending triangles out in the example but ideally this would be done automatically (I need to keep the triangles at the moment to compute the Voronoi diagram).

[mbostock]

I would love to have this as a D3 plugin (say, geo/voronoi in d3/d3-plugins). I think it probably makes more sense to start there than in core, and plus that means we don’t have to worry as much about the initial API. Though I think returning a non-quantized TopoJSON topology as in d3.geom.voronoi topology would be an ideal starting point. Related #1819.

[ianschillebeeckx]

I'm in a Computational Geometry class and for a final project I plan to implement a O(nlogn) incremental algorithm to compute the voronoi directly. It was going to be a webapp, so i figured I would try to contribute to d3. How can I best incorporate into the existing geo.voronoi library and what should i stay away from?

As a side note: I'm not familiar with d3 but why is geo.voronoi separated from geom.voronoi?

[mbostock]

d3.geo.voronoi is for spherical Voronoi diagrams (and spherical Delaunay triangulations).

d3.geom.voronoi is for planar Voronoi diagrams (and planar Delaunay triangulations).

In general, d3.geo is for spherical geometry (geography), and d3.geom is for 2D planar geometry.

[jrus]

@jasondavies is there a freely-ish licensed version of your geo-voronoi code? The one on your website seems to only be available as minified javascript with no explicit mention of licensing or copyright.

If that code is not freely licensed, should someone be reimplementing it separately? @ianschillebeeckx did you have any luck with implementing a faster spherical voronoi ever?

[Fil]

I have implemented geoVoronoi as a d3 wrapper around Loren Petrich's library (linked in @mbostock's initial comment). It seems to work quite well. I'm still building the examples and documentation, and welcome comments, insults, pull-requests etc.
https://github.com/Fil/d3-geo-voronoi