d3-geo-voronoi

d3-geo-voronoi

This module wraps d3 around Loren Petrich's Spherical Delaunay triangulation library, following as closely as possible the API of the d3-voronoi module.

Given a set of objects in spherical coordinates, it computes their Delaunay triangulation and its dual, the Voronoi diagram (d3 issue #1820).

In addition, it offers convenience methods to extract the convex hull, the Urquhart graph, the circumcenters of the Delaunay triangles, and to find the cell that contains any given point on the sphere.

Installing

If you use NPM, npm install d3-geo-voronoi. Otherwise, download the latest release.

API Reference

# d3.geoVoronoi([data]) <>

Creates a new spherical Voronoi layout. data can be passed as an array of [lon, lat] coordinates, an array of GeoJSON features, or a GeoJSON FeatureCollection.

The following methods are similar to d3-voronoi's methods:

# voronoi.x([x])

Sets or returns the x accessor. The default x and y accessors are smart enough to recognize GeoJSON objects and return the geoCentroid of each feature.

# voronoi.y([y])

Sets or returns the y accessor.

# voronoi.polygons([data])

Returns the Voronoi tesselation of the data as a GeoJSON collection of polygons. (If there is only one data point, returns the Sphere). Each polygon exposes its datum in its properties.

# voronoi.triangles([data])

Returns the spherical Delaunay triangulation of the data as a GeoJSON collection of polygons. Each triangle exposes in its properties the three sites, its spherical area (in steradians), and its circumcenter.

# voronoi.links([data])

Returns the Delaunay links of the data as a GeoJSON collection of lines. Each line exposes its source and target in its properties, but also its length (in radians), and a boolean flag for links that belong to the Urquhart graph.

voronoi.extent([extent]) and voronoi.size([size]) are not implemented.

Indeed, defining the “paper extent” of the geoVoronoi polygons can be quite tricky, as this block demonstrates.

The following new methods are introduced:

# voronoi.find(x,y,[angle])

Finds the closest site to point x,y, i.e. the Voronoi polygon that contains it. Optionally, return null if the distance between the point and the site is larger than angle radians.

# voronoi.hull(data)

Returns the spherical convex hull of the data array, as a GeoJSON polygon. Returns null if the dataset spans more than a hemisphere. Equivalent to:

voronoi(data).hull();

Note: there might be a better way to compute the geoHull, and this should probably be part of d3-geo. This method is experimental and may be removed from the API.

Other projections

There is no reason to limit the display of Voronoi cells to the orthographic projection. The example below displays the Urquhart graph of top container ports on a Winkel tripel map.

Comparison with planar Voronoi Diagrams

• geoVoronoi is for points on the sphere, d3-voronoi is for points on a plane (or possibly a torus or a cylinder).

• geoVoronoi uses a different algorithm (in O(n^2), which is much slower as the number of sites grows past 1000) -- and its internal data structure is different.

• geoVoronoi returns GeoJSON objects, which are often FeatureCollections. By consequence, you will have to change .data(voronoi.polygons()) to .data(geovoronoi.polygons().features), and so on.

• geoVoronoi offers methods to compute the convex hull, the Urquhart graph. These can be achieved with the planar Voronoi (hull, Urquhart, but are not part of d3-voronoi.