Voronoi diagrams

Given a set of points, the Voronoi diagram partitions the plane into cells representing the region of the plane that is closest to the corresponding point. The Voronoi diagram is the dual of the Delaunay triangulation.

delaunay.voronoi(bounds)

Source · Returns the Voronoi diagram for the given Delaunay triangulation. When rendering, the diagram will be clipped to the specified bounds = [xmin, ymin, xmax, ymax].

const delaunay = d3.Delaunay.from([[0, 0], [0, 100], [100, 0], [100, 100]]);
const voronoi = delaunay.voronoi([0, 0, 640, 480]);

If bounds is not specified, it defaults to [0, 0, 960, 500]. The Voronoi diagram is returned even in degenerate cases where no triangulation exists — namely 0, 1 or 2 points, and collinear points.

voronoi.delaunay

The Voronoi diagram’s associated Delaunay triangulation.

voronoi.circumcenters

The circumcenters of the Delaunay triangles as a Float64Array [cx0, cy0, cx1, cy1, …]. Each contiguous pair of coordinates cx, cy is the circumcenter for the corresponding triangle. These circumcenters form the coordinates of the Voronoi cell polygons.

voronoi.vectors

A Float64Array [vx0, vy0, wx0, wy0, …] where each non-zero quadruple describes an open (infinite) cell on the outer hull, giving the directions of two open half-lines.

voronoi.xmin
voronoi.ymin
voronoi.xmax
voronoi.ymax

The bounds of the viewport [xmin, ymin, xmax, ymax] for rendering the Voronoi diagram. These values only affect the rendering methods (voronoi.render, voronoi.renderBounds, voronoi.renderCell).

voronoi.contains(i, x, y)

Source · Returns true if the cell with the specified index i contains the specified point ⟨x, y⟩; i.e., whether the point i is the closest point in the diagram to the specified point. (This method is not affected by the associated Voronoi diagram’s viewport bounds.)

voronoi.neighbors(i)

voronoi.neighbors(-1) // []

Source · Returns an iterable over the indexes of the cells that share a common edge with the specified cell i. Voronoi neighbors are always neighbors on the Delaunay graph, but the converse is false when the common edge has been clipped out by the Voronoi diagram’s viewport.

voronoi.render(context)

Source · Renders the mesh of Voronoi cells to the specified context. The specified context must implement the context.moveTo and context.lineTo methods from the CanvasPathMethods API. If a context is not specified, an SVG path string is returned instead.

voronoi.renderBounds(context)

Source · Renders the viewport extent to the specified context. The specified context must implement the context.rect method from the CanvasPathMethods API. Equivalent to context.rect(voronoi.xmin, voronoi.ymin, voronoi.xmax - voronoi.xmin, voronoi.ymax - voronoi.ymin). If a context is not specified, an SVG path string is returned instead.

voronoi.renderCell(i, context)

Source · Renders the cell with the specified index i to the specified context. The specified context must implement the context.moveTo , context.lineTo and context.closePath methods from the CanvasPathMethods API. If a context is not specified, an SVG path string is returned instead.

voronoi.cellPolygons()

Source · Returns an iterable over the non-empty polygons for each cell, with the cell index as property. See also voronoi.renderCell.

voronoi.cellPolygon(i)

Source · Returns the convex, closed polygon [[x0, y0], [x1, y1], …, [x0, y0]] representing the cell for the specified point i. See also voronoi.renderCell.

voronoi.update()

Source · Updates the Voronoi diagram and underlying triangulation after the points have been modified in-place — useful for Lloyd’s relaxation. Calls delaunay.update on the underlying Delaunay triangulation.