d3-geo-voronoi
Spherical Voronoi Diagram and Delaunay Triangulation
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.
If you use npm, npm install d3-geo-voronoi. You can also download the latest release on GitHub. For vanilla HTML in modern browsers, import d3-geo-voronoi from Skypack:
<script type="module">
import {geoDelaunay} from "https://cdn.skypack.dev/d3-geo-voronoi@2";
</script>For legacy environments, you can load d3-geo-voronoi’s UMD bundle from an npm-based CDN such as jsDelivr; a d3 global is exported:
<script src="https://cdn.jsdelivr.net/npm/d3-geo-voronoi@2"></script>
<script>
d3.geoContour();
</script>This API is a similar to d3-delaunay’s API. It provides information on the Delaunay triangulation (edges, triangles, neighbors, Voronoi cells, etc) as indices in two arrays — the array of points, and the array of circumcenters. It facilitates topological computations. To draw the actual triangles, Voronoi cells etc, the Voronoi API described in the next section will often be easier to use.
# d3.geoDelaunay([data]) · Source
Creates a new spherical Delaunay layout. data must be passed as an array of [lon, lat] coordinates.
# delaunay.find(lon, lat[, node])
Returns the closest point to [lon, lat]; optionally starting the search at node to boost the performance.
# delaunay.urquhart([distances])
Given a vector of distances (in the same order as the edges list), returns a vector of boolean values: true if the edge belongs to the Urquhart graph, false otherwise.
# delaunay.hull()
Returns an array of indices of points on the hull. The array is empty if the points cover more than a hemisphere.
# delaunay.edges
An array of edges as indices of points [from, to].
# delaunay.triangles
An array of the triangles, as indices of points [a, b, c]. The triangles are orientated in a clockwise manner, triangles that span more than the hemisphere are removed.
# delaunay.centers
The array 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 smaller number of points (n≤3).
# delaunay.neighbors
The array of neighbors indices for each vertex.
# delaunay.polygons
Array of Voronoi cells for each vertex. Each cell is an array of centers ordered in a clockwise manner.
# delaunay.mesh
An array containing all the edges of the Voronoi polygons.
This API is a wrapper around the Delaunay API, with inputs and outputs in GeoJSON, ready to draw on a map.
# 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 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();
Create spherical contours for non-gridded data.
The API of geoContour is similar to that of d3-contour and d3-tricontour:
# d3.geoContour() · Source, Examples
Constructs a new geocontour generator with the default settings.
Returns an array of contours, one for each threshold. The contours are MultiPolygons in GeoJSON format, that contain all the points with a value larger than the threshold. The value is indicated as geometry.value.
The data is passed as an array of points, by default with the format [lon, lat, value].
# geocontour.contour(data[, threshold])
Returns a contour, as a MultiPolygon in GeoJSON format, containing all points with a value larger or equal to threshold. The threshold is indicated as geometry.value
# geocontour.contours(data)
Returns an iterable over the contours.
# geocontour.isobands(data)
Returns an iterable over the isobands: contours between pairs of consecutive threshold values v0 (inclusive) and v1 (exclusive). geometry.value is equal to v0, geometry.valueMax to v1.
# geocontour.x([x])
Sets the x (longitude) accessor. Defaults to `d => d[0]`. If x is not given, returns the current x accessor.
# geocontour.y([y])
Sets the y (latitude) accessor. Defaults to `d => d[1]`. If y is not given, returns the current y accessor.
# geocontour.value([value])
Sets the value accessor. Defaults to `d => d[2]`. Values must be defined and finite. If value is not given, returns the current value accessor.
# geocontour.thresholds([thresholds])
Sets the thresholds, either explicitly as an array of values, or as a count that will be passed to d3.ticks. If empty, returns the current thresholds.
Note: d3.geoContour uses the experimental API of d3-tricontour: triangulate, pointInterpolate and ringsort.
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.
-
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.