![](\"https://raw.githubusercontent.com/d3/d3-delaunay/master/img/voronator.jpg\")
\n\n
Georgy “The Voronator” Voronoy\n\nThis is a fast, no-dependency 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://beta.observablehq.com/@mbostock/the-delaunays-dual).\n\n## Installing\n\nTo install, `npm install d3-delaunay` or `yarn add d3-delaunay`. You can also download the [latest release](https://github.com/d3/d3-delaunay/releases/latest) or load directly from [unpkg](https://unpkg.com/d3-delaunay/). AMD, CommonJS, ES5 and ES6+ environments are supported. In vanilla, a `d3` global is exported.\n\n```js\nimport {Delaunay} from \"d3-delaunay\";\n\nconst points = [[0, 0], [0, 1], [1, 0], [1, 1]];\nconst delaunay = Delaunay.from(points);\nconst voronoi = delaunay.voronoi([0, 0, 960, 500]);\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 half-edge indexes as an Int32Array [*j0*, *j1*, …]. For each index 0 ≤ *i* < *halfedges*.length, there is a half-edge 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] * 2;\n const tj = triangles[j] * 2;\n context.moveTo(points[ti], points[ti + 1]);\n context.lineTo(points[tj], points[tj + 1]);\n}\n```\n\nSee also [*delaunay*.render](#delaunay_render).\n\n# delaunay.hull\n\nThe convex hull as an a Uint32Array [*i0*, *i1*, …] of triangle vertex indexes. For example, to render the exterior edges of the Delaunay triangulation:\n\n```js\nconst {hull, triangles} = delaunay;\nconst n = hull.length;\nlet i0, i1 = triangles[hull[n - 1]] * 2;\nfor (let i = 0; i < n; ++i) {\n i0 = i1, i1 = triangles[hull[i]] * 2;\n context.moveTo(points[i0], points[i0 + 1]);\n context.lineTo(points[i1], points[i1 + 1]);\n}\n```\n\nSee also [*delaunay*.renderHull](#delaunay_renderHull).\n\n# delaunay.triangles\n\nThe triangle vertex indexes as an Int32Array [*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] * 2;\nconst t1 = triangles[i * 3 + 1] * 2;\nconst t2 = triangles[i * 3 + 2] * 2;\ncontext.moveTo(points[t0], points[t0 + 1]);\ncontext.lineTo(points[t1], points[t1 + 1]);\ncontext.lineTo(points[t2], points[t2 + 1]);\ncontext.closePath();\n```\n\nSee also [*delaunay*.renderTriangle](#delaunay_renderTriangle).\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).\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).\n\n# delaunay.renderTriangle(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).\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://beta.observablehq.com/@mbostock/to-infinity-and-back-again) for an interactive explanation of Voronoi cell clipping.\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.edges\n\n… TODO The triangle indexes [*i0*, *i1*, …] in counterclockwise order. Together with the start and end vectors [*cell*.v0](#cell_v0) and [*cell*.vn](#cell_vn) if any, the [circumcenters](#voronoi_circumcenters) of these triangles form the exterior polygon of the cell. For coincident points, only the cell associated with the first input point is non-null.\n\n# voronoi.index\n\n… TODO The triangle indexes [*i0*, *i1*, …] in counterclockwise order. Together with the start and end vectors [*cell*.v0](#cell_v0) and [*cell*.vn](#cell_vn) if any, the [circumcenters](#voronoi_circumcenters) of these triangles form the exterior polygon of the cell. For coincident points, only the cell associated with the first input point is non-null.\n\n# voronoi.vectors\n\n… TODO The start vector [*vx0*, *vy0*], if the cell’s associated point is on the [convex hull](#delaunay_hull) of the Delaunay triangulation. Together with the cell’s [triangle circumcenters](#cell_triangles) and end vector [*cell*.vn](#cell_vn) if any, the start vector forms the exterior polygon of the cell. The end vector [*vxn*, *vyn*], if the cell’s associated point is on the [convex hull](#delaunay_hull) of the Delaunay triangulation. Together with the cell’s [triangle circumcenters](#cell_triangles) and start vector [*cell*.v0](#cell_v0) if any, the end vector forms the exterior polygon of the cell.\n\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.find(x, y[, i]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js \"Source\")\n\nReturns the index of the cell that contains the specified point ⟨*x*, *y*⟩. The search is started at the specified point *i*. If *i* is not specified, it defaults to zero. (This method is not affected by the associated Voronoi diagram’s viewport [bounds](#voronoi_xmin).)\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.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).\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).\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).\n","gitHead":"bcdfe5546a8696ce3f457d2ac62bf6c178781397","license":"ISC","scripts":{"test":"tape -r esm 'test/**/*-test.js'","build":"rm -rf dist && mkdir dist && rollup -c","postpublish":"git push && git push --tags && zip -j dist/d3-delaunay.zip -- LICENSE README.md dist/d3-delaunay.js dist/d3-delaunay.min.js","prepublishOnly":"yarn build && yarn test"},"_npmUser":{"name":"mbostock","email":"mike@ocks.org"},"homepage":"https://github.com/d3/d3-delaunay","keywords":["voronoi","delaunay","geometry"],"repository":{"url":"git+https://github.com/d3/d3-delaunay.git","type":"git"},"_npmVersion":"5.6.0","description":"Compute the Voronoi diagram of a set of two-dimensional points.","directories":{},"maintainers":[{"name":"mbostock","email":"mike@ocks.org"}],"_nodeVersion":"8.9.4","contributors":[{"url":"http://agafonkin.com/en/","name":"Vladimir Agafonkin"}],"dependencies":{"delaunator":"^2.0.0"},"publishConfig":{"tag":"next"},"_hasShrinkwrap":false,"readmeFilename":"README.md","devDependencies":{"esm":"^3.0.7","tape":"4","rollup":"^0.57.1","@observablehq/tape":"~0.0.1","rollup-plugin-uglify":"^3.0.0","rollup-plugin-node-resolve":"^3.3.0"},"_npmOperationalInternal":{"tmp":"tmp/d3-delaunay_3.0.0-alpha.1_1523392739151_0.8423757779081258","host":"s3://npm-registry-packages"},"_id":"d3-delaunay@3.0.0-alpha.1","version":"3.0.0-alpha.1"}