d3-geo-voronoi

d3-geo-voronoi

This module adapts d3-delaunay for spherical data. Given a set of objects in spherical coordinates, it computes their Delaunay triangulation and its dual, the Voronoi diagram.

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.

The module offers two APIs.

The GeoJSON API is the most convenient for drawing the results on a map. It follows as closely as possible the API of the d3-voronoi module. It is available with d3.geoVoronoi().

A lighter API is available with d3.geoDelaunay(). It offers the same contents, but with a different presentation, where every vertex, edge, polygon… is referenced by an id rather than by its coordinates. This allows a more compact representation in memory and eases topology computations.

Installing

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

API Reference

# d3.geoDelaunay([data]) · Source

Creates a new spherical Voronoi layout. data must be passed as an array of [lon, lat] coordinates.

• delaunay.find(x,y,node): pass a starting node (not a radius).

• delaunay.urquhart(distances): retrieve a vector of urquhart edges indices.

• delaunay.hull(): list of indices of points on the hull (empty if the points cover more than a hemisphere).

• delaunay.edges: list of edges as indices of points [from, to] (might change to a typed in the future)

• delaunay.triangles: list of edges as indices of points [a, b, c] (might change to a typed in the future)

• delaunay.centers: list of centers in spherical coordinates; the first t centers are the t triangles’s circumcenters. More centers might be listed in order to build the voronoi diagram for degenerate cases such as n=1,2,3 points.

• delaunay.neighbors, an array of neighbors indices for each vertex.

• delaunay.polygons, an array of centers for each vertex, order in a clockwise manner.

• delaunay.mesh, a list of all the edges of the voronoi polygons

# d3.geoContour() · Source

Using d3-tricontour, creates spherical contours for non-gridded data.

Documentation TBD.

# d3.geoVoronoi([data]) · Source, Examples

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.delaunay

The raw d3.geoDelaunay() object used to compute this diagram.

# 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]) · Source, Examples

Returns the Voronoi tessellation 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.cellMesh([data]) · Source

Returns the Voronoi tessellation as a GeoJSON mesh (MultiLineString).

# voronoi.triangles([data]) · Source, Examples

Returns the Voronoi tessellation 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.mesh([data]) · Source, Examples

Returns the Delaunay edges as a GeoJSON mesh (MultiLineString).

# voronoi.links([data]) · Source, Examples

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.

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

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 degrees.

# voronoi.hull(data) · Source, Examples

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();

Other tools & 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.

Geo_triangulate converts GeoJSON to triangles for 3d rendering.

Comparison with planar Voronoi Diagrams

• the Delaunay/Voronoi topology is quite different on the sphere and on the plane. This module deals with these differences by first projecting the points with a stereographic projection, then stitching the geometries that are near the singularity of the projection (the “infinite horizon” on the plane is one point on the sphere).

• 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 is built on d3-delaunay, which is also exposed as d3.geoDelaunay in this library. If you want to have the fastest results, you should try to use d3.geoDelaunay directly (see the examples).

• geoVoronoi and geoDelaunay offer methods to compute the spherical convex hull and the Urquhart graph of the data set. These can be achieved with the planar Voronoi (hull, Urquhart, but are not part of d3-voronoi or d3-delaunay.

Changes

• the module needs d3-delaunay and doesn't embed it.

<script src="https://unpkg.com/d3-delaunay@5"></script>
<script src="https://unpkg.com/d3-geo-voronoi@1"></script>

(To access the previous (slow) version, please use https://unpkg.com/d3-geo-voronoi@0.)