d3-voronoi

Deprecation notice:Consider using the newerd3-delaunayinstead of d3-voronoi. Based onDelaunator,d3-delaunay is 5-10× faster than d3-voronoi to construct the Delaunay triangulation or the Voronoi diagram, is more robust numerically, has Canvas rendering built-in, allows traversal of the Delaunay graph, and a variety of other improvements.

---

This module implementsSteven J. Fortune’s algorithmfor computing theVoronoi diagramorDelaunay triangulationof a set of two-dimensional points. This implementation is largely based onwork by Raymond Hill.

Voronoi diagrams are not onlyvisuallyattractivebut practical tools for interaction, such as to increase the target area of points in a scatterplot. See“Strikeouts on the Rise”inThe New York Timesand thismulti-line chartfor examples; also see Tovi Grossman’s paper onbubble cursorsfor a related technique. Voronoi diagrams can also be used toautomate label positioning,and Delaunay meshes are useful in computing adjacency or grouping of visual elements.

Installing

If you use NPM,npm install d3-voronoi.Otherwise, download thelatest release.You can also load directly fromd3js.org,either as astandalone libraryor as part ofD3 4.0.AMD, CommonJS, and vanilla environments are supported. In vanilla, ad3global is exported:

<scriptsrc= "https://d3js.org/d3-voronoi.v1.min.js"></script>
<script>

varvoronoi=d3.voronoi();

</script>

Try d3-voronoi in your browser.

API Reference

#d3.voronoi()<>

Creates a new Voronoi layout with defaultx-andy-accessors and a nullextent.

#voronoi(data)<>

Computes theVoronoi diagramfor the specifieddatapoints.

#voronoi.x([x])<>

Ifxis specified, sets thex-coordinate accessor. Ifxis not specified, returns the currentx-coordinate accessor, which defaults to:

functionx(d){
returnd[0];
}

#voronoi.y([y])<>

Ifyis specified, sets they-coordinate accessor. Ifyis not specified, returns the currenty-coordinate accessor, which defaults to:

functiony(d){
returnd[1];
}

#voronoi.extent([extent])<>

Ifextentis specified, sets the clip extent of the Voronoi layout to the specified bounds and returns the layout. Theextentbounds are specified as an array [[x0,y0], [x1,y1]], wherex0is the left side of the extent,y0is the top,x1is the right andy1is the bottom. Ifextentis not specified, returns the current clip extent which defaults to null. A clip extent is required when usingvoronoi.polygons.

#voronoi.size([size])<>

An alias forvoronoi.extentwhere the minimumxandyof the extent are ⟨0,0⟩. Equivalent to:

voronoi.extent([[0,0],size]);

#voronoi.polygons(data)<>

Returns a sparse array of polygons, one for each unique input point in the specifieddatapoints, corresponding to the cells in the computed Voronoi diagram. Equivalent to:

voronoi(data).polygons();

Seediagram.polygonsfor more detail. Note: anextentis required.

#voronoi.triangles(data)<>

Returns the Delaunay triangulation of the specifieddataarray as an array of triangles. Each triangle is a three-element array of elements fromdata.Equivalent to:

voronoi(data).triangles();

Seediagram.trianglesfor more detail.

#voronoi.links(data)<>

Returns the Delaunay triangulation of the specifieddataarray as an array of links. Each link hassourceandtargetattributes referring to elements indata.Equivalent to:

voronoi(data).links();

Seediagram.linksfor more detail.

Voronoi Diagrams

#diagram<>

The computed Voronoi diagram returned byvoronoihas the following properties:

• edges- an array ofedges.
• cells- a sparse array ofcells,one for each unique input point.

For each set of coincident input points, one of the points is chosen arbitrarily and assigned the associated cell; the other coincident input points’ entries are missing from the returned sparse array.

#diagram.polygons()<>

Returns a sparse array of polygons clipped to theextent,one for each cell (each unique input point) in the diagram. Each polygon is represented as an array of points [x,y] wherexandyare the point coordinates, and adatafield that refers to the corresponding element indata.Polygons are open: they do not contain a closing point that duplicates the first point; a triangle, for example, is an array of three points. Polygons are also counterclockwise, assuming the origin ⟨0,0⟩ is in the top-left corner.

For each set of coincident input points, one of the points is chosen arbitrarily and assigned the associated polygon; the other coincident input points’ entries are missing from the returned sparse array.

#diagram.triangles()<>

Returns the Delaunay triangulation of the specifieddataarray as an array of triangles. Each triangle is a three-element array of elements fromdata.Since the triangulation is computed as the dual of the Voronoi diagram, and the Voronoi diagram is clipped by theextent,a subset of the Delaunay triangulation is returned.

#diagram.links()<>

Returns the Delaunay triangulation of the specifieddataarray as an array of links, one for each edge in the mesh. Each link has the following attributes:

• source- the source node, an element indata.
• target- the target node, an element indata.

Since the triangulation is computed as the dual of the Voronoi diagram, and the Voronoi diagram is clipped by theextent,a subset of the Delaunay links is returned.

#diagram.find(x,y[,radius])<>

Returns the nearest site to point [x,y]. Ifradiusis specified, only sites withinradiusdistance are considered.

See Philippe Rivière’sbl.ocks.org/1b7ddbcd71454d685d1259781968aefcfor an example.

#cell

Each cell in the diagram is an object with the following properties:

• site- thesiteof the cell’s associated input point.
• halfedges- an array of indexes intodiagram.edgesrepresenting the cell’s polygon.

#site

Each site in the diagram is an array [x,y] with two additional properties:

• index- the site’s index, corresponding to the associated input point.
• data- the input data corresponding to this site.

#edge

Each edge in the diagram is an array [[x0,y0], [x1,y1]] with two additional properties:

• left- thesiteon the left side of the edge.
• right- thesiteon the right side of the edge; null for a clipped border edge.