![](\"https://raw.githubusercontent.com/d3/d3-delaunay/master/img/voronator.jpg\")
\n\n
Georgy “The Voronator” Voronoy\n\nThis is a fast library for computing the [Voronoi diagram](https://en.wikipedia.org/wiki/Voronoi_diagram) of a set of two-dimensional points. It is based on [Delaunator](https://github.com/mapbox/delaunator), a fast library for computing the [Delaunay triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation) using [sweep algorithms](https://github.com/mapbox/delaunator/blob/master/README.md#papers). The Voronoi diagram is constructed by connecting the circumcenters of adjacent triangles in the Delaunay triangulation.\n\nFor an interactive explanation of how this library works, see [The Delaunay’s Dual](https://observablehq.com/@mbostock/the-delaunays-dual).\n\n## Installing\n\nIf you use npm, `npm install d3-delaunay`. You can also download the [latest release on GitHub](https://github.com/d3/d3-delaunay/releases/latest). For vanilla HTML in modern browsers, import d3-delaunay from Skypack:\n\n```html\n\n```\n\nFor legacy environments, you can load d3-delaunay’s UMD bundle from an npm-based CDN such as jsDelivr; a `d3` global is exported:\n\n```html\n\n\n```\n\n\n## API Reference\n\n### Delaunay\n\n# new Delaunay(points) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js \"Source\")\n\nReturns the Delaunay triangulation for the given flat array [*x0*, *y0*, *x1*, *y1*, …] of *points*.\n\n```js\nconst delaunay = new Delaunay(Float64Array.of(0, 0, 0, 1, 1, 0, 1, 1));\n```\n\n# Delaunay.from(points[, fx[, fy[, that]]]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js \"Source\")\n\nReturns the Delaunay triangulation for the given array or iterable of *points*. If *fx* and *fy* are not specified, then *points* is assumed to be an array of two-element arrays of numbers: [[*x0*, *y0*], [*x1*, *y1*], …]. Otherwise, *fx* and *fy* are functions that are invoked for each element in the *points* array in order, and must return the respective *x*- and *y*-coordinate for each point. If *that* is specified, the functions *fx* and *fy* are invoked with *that* as *this*. (See [Array.from](https://developer.mozilla.org/docs/Web/JavaScript/Reference/Global_Objects/Array/from) for reference.)\n\n```js\nconst delaunay = Delaunay.from([[0, 0], [0, 1], [1, 0], [1, 1]]);\n```\n\n# delaunay.points\n\nThe coordinates of the points as an array [*x0*, *y0*, *x1*, *y1*, …]. Typically, this is a Float64Array, however you can use any array-like type in the [constructor](#new_Delaunay).\n\n# delaunay.halfedges\n\nThe halfedge indexes as an Int32Array [*j0*, *j1*, …]. For each index 0 ≤ *i* < *halfedges*.length, there is a halfedge from triangle vertex *j* = *halfedges*[*i*] to triangle vertex *i*. Equivalently, this means that triangle ⌊*i* / 3⌋ is adjacent to triangle ⌊*j* / 3⌋. If *j* is negative, then triangle ⌊*i* / 3⌋ is an exterior triangle on the [convex hull](#delaunay_hull). For example, to render the internal edges of the Delaunay triangulation:\n\n```js\nconst {points, halfedges, triangles} = delaunay;\nfor (let i = 0, n = halfedges.length; i < n; ++i) {\n const j = halfedges[i];\n if (j < i) continue;\n const ti = triangles[i];\n const tj = triangles[j];\n context.moveTo(points[ti * 2], points[ti * 2 + 1]);\n context.lineTo(points[tj * 2], points[tj * 2 + 1]);\n}\n```\n\nSee also [*delaunay*.render](#delaunay_render).\n\n# delaunay.hull\n\nAn Int32Array of point indexes that form the convex hull in counterclockwise order. If the points are collinear, returns them ordered.\n\nSee also [*delaunay*.renderHull](#delaunay_renderHull).\n\n# delaunay.triangles\n\nThe triangle vertex indexes as an Uint32Array [*i0*, *j0*, *k0*, *i1*, *j1*, *k1*, …]. Each contiguous triplet of indexes *i*, *j*, *k* forms a counterclockwise triangle. The coordinates of the triangle’s points can be found by going through [*delaunay*.points](#delaunay_points). For example, to render triangle *i*:\n\n```js\nconst {points, triangles} = delaunay;\nconst t0 = triangles[i * 3 + 0];\nconst t1 = triangles[i * 3 + 1];\nconst t2 = triangles[i * 3 + 2];\ncontext.moveTo(points[t0 * 2], points[t0 * 2 + 1]);\ncontext.lineTo(points[t1 * 2], points[t1 * 2 + 1]);\ncontext.lineTo(points[t2 * 2], points[t2 * 2 + 1]);\ncontext.closePath();\n```\n\nSee also [*delaunay*.renderTriangle](#delaunay_renderTriangle).\n\n# delaunay.inedges\n\nThe incoming halfedge indexes as a Int32Array [*e0*, *e1*, *e2*, …]. For each point *i*, *inedges*[*i*] is the halfedge index *e* of an incoming halfedge. For coincident points, the halfedge index is -1; for points on the convex hull, the incoming halfedge is on the convex hull; for other points, the choice of incoming halfedge is arbitrary. The *inedges* table can be used to traverse the Delaunay triangulation; see also [*delaunay*.neighbors](#delaunay_neighbors).\n\n# delaunay.find(x, y[, i]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js \"Source\")\n\nReturns the index of the input point that is closest to the specified point ⟨*x*, *y*⟩. The search is started at the specified point *i*. If *i* is not specified, it defaults to zero.\n\n# delaunay.neighbors(i) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js \"Source\")\n\nReturns an iterable over the indexes of the neighboring points to the specified point *i*. The iterable is empty if *i* is a coincident point.\n\n# delaunay.render([context]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js \"Source\")\n\n![\"delaunay.render\"](\"https://raw.githubusercontent.com/d3/d3-delaunay/master/img/delaunay-mesh.png\")
\n\nRenders the edges of the Delaunay triangulation to the specified *context*. The specified *context* must implement the *context*.moveTo and *context*.lineTo methods from the [CanvasPathMethods API](https://www.w3.org/TR/2dcontext/#canvaspathmethods). If a *context* is not specified, an SVG path string is returned instead.\n\n# delaunay.renderHull([context]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js \"Source\")\n\n![\"delaunay.renderHull\"](\"https://raw.githubusercontent.com/d3/d3-delaunay/master/img/delaunay-hull.png\")
\n\nRenders the convex hull of the Delaunay triangulation to the specified *context*. The specified *context* must implement the *context*.moveTo and *context*.lineTo methods from the [CanvasPathMethods API](https://www.w3.org/TR/2dcontext/#canvaspathmethods). If a *context* is not specified, an SVG path string is returned instead.\n\n# delaunay.renderTriangle(i[, context]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js \"Source\")\n\n![\"delaunay.renderTriangle\"](\"https://raw.githubusercontent.com/d3/d3-delaunay/master/img/delaunay-triangle.png\")
\n\nRenders triangle *i* of the Delaunay triangulation to the specified *context*. The specified *context* must implement the *context*.moveTo, *context*.lineTo and *context*.closePath methods from the [CanvasPathMethods API](https://www.w3.org/TR/2dcontext/#canvaspathmethods). If a *context* is not specified, an SVG path string is returned instead.\n\n# delaunay.renderPoints(\\[context\\]\\[, radius\\]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js \"Source\")\n\nRenders the input points of the Delaunay triangulation to the specified *context* as circles with the specified *radius*. If *radius* is not specified, it defaults to 2. The specified *context* must implement the *context*.moveTo and *context*.arc methods from the [CanvasPathMethods API](https://www.w3.org/TR/2dcontext/#canvaspathmethods). If a *context* is not specified, an SVG path string is returned instead.\n\n# delaunay.hullPolygon() [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js \"Source\")\n\nReturns the closed polygon [[*x0*, *y0*], [*x1*, *y1*], …, [*x0*, *y0*]] representing the convex hull.\n\n# delaunay.trianglePolygons() [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js \"Source\")\n\nReturns an iterable over the [polygons for each triangle](#delaunay_trianglePolygon), in order.\n\n# delaunay.trianglePolygon(i) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js \"Source\")\n\nReturns the closed polygon [[*x0*, *y0*], [*x1*, *y1*], [*x2*, *y2*], [*x0*, *y0*]] representing the triangle *i*.\n\n# delaunay.update() [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js \"Source\")\n\nUpdates the triangulation after the points have been modified in-place.\n\n# delaunay.voronoi([bounds]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js \"Source\")\n\nReturns the [Voronoi diagram](#voronoi) for the associated [points](#delaunay_points). When rendering, the diagram will be clipped to the specified *bounds* = [*xmin*, *ymin*, *xmax*, *ymax*]. If *bounds* is not specified, it defaults to [0, 0, 960, 500]. See [To Infinity and Back Again](https://observablehq.com/@mbostock/to-infinity-and-back-again) for an interactive explanation of Voronoi cell clipping.\n\nThe Voronoi diagram is returned even in degenerate cases where no triangulation exists — namely 0, 1 or 2 points, and collinear points.\n\n### Voronoi\n\n# voronoi.delaunay\n\nThe Voronoi diagram’s associated [Delaunay triangulation](#delaunay).\n\n# voronoi.circumcenters\n\nThe [circumcenters](http://mathworld.wolfram.com/Circumcenter.html) 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.\n\n# voronoi.vectors\n\nA 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.\n\n# voronoi.xmin
\n# voronoi.ymin
\n# voronoi.xmax
\n# voronoi.ymax
\n\nThe bounds of the viewport [*xmin*, *ymin*, *xmax*, *ymax*] for rendering the Voronoi diagram. These values only affect the rendering methods ([*voronoi*.render](#voronoi_render), [*voronoi*.renderBounds](#voronoi_renderBounds), [*cell*.render](#cell_render)).\n\n# voronoi.contains(i, x, y) [<>](https://github.com/d3/d3-delaunay/blob/master/src/cell.js \"Source\")\n\nReturns true if the cell with the specified index *i* contains the specified point ⟨*x*, *y*⟩. (This method is not affected by the associated Voronoi diagram’s viewport [bounds](#voronoi_xmin).)\n\n# voronoi.neighbors(i) [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js \"Source\")\n\nReturns 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.\n\n# voronoi.render([context]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js \"Source\")\n\n![\"voronoi.render\"](\"https://raw.githubusercontent.com/d3/d3-delaunay/master/img/voronoi-mesh.png\")
\n\nRenders 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](https://www.w3.org/TR/2dcontext/#canvaspathmethods). If a *context* is not specified, an SVG path string is returned instead.\n\n# voronoi.renderBounds([context]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js \"Source\")\n\n![\"voronoi.renderBounds\"](\"https://raw.githubusercontent.com/d3/d3-delaunay/master/img/voronoi-bounds.png\")
\n\nRenders the viewport extent to the specified *context*. The specified *context* must implement the *context*.rect method from the [CanvasPathMethods API](https://www.w3.org/TR/2dcontext/#canvaspathmethods). 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.\n\n# voronoi.renderCell(i[, context]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js \"Source\")\n\n![\"cell.render\"](\"https://raw.githubusercontent.com/d3/d3-delaunay/master/img/spectral.png\")
\n\nRenders 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](https://www.w3.org/TR/2dcontext/#canvaspathmethods). If a *context* is not specified, an SVG path string is returned instead.\n\n# voronoi.cellPolygons() [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js \"Source\")\n\nReturns an iterable over the non-empty [polygons for each cell](#voronoi_cellPolygon), with the cell index as property.\n\n# voronoi.cellPolygon(i) [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js \"Source\")\n\nReturns the convex, closed polygon [[*x0*, *y0*], [*x1*, *y1*], …, [*x0*, *y0*]] representing the cell for the specified point *i*.\n\n# voronoi.update() [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js \"Source\")\n\nUpdates the Voronoi diagram and underlying triangulation after the points have been modified in-place — useful for Lloyd’s relaxation.\n","_attachments":{},"homepage":"https://github.com/d3/d3-delaunay","bugs":{"url":"https://github.com/d3/d3-delaunay/issues"},"license":"ISC"}