D3

Delaunay triangulations ​

The Delaunay triangulation is a triangular mesh formed from a set of points in x and y. No point is inside the circumcircle of any triangle, which is a nice geometric property for certain applications, and tends to avoid “sliver” triangles. The Delaunay triangulation is the dual of the Voronoi diagram.

new Delaunay(points) ​

Source · Returns the Delaunay triangulation for the given flat array [x0, y0, x1, y1, …] of points.

js
const delaunay = new d3.Delaunay(Float64Array.of(0, 0, 0, 1, 1, 0, 1, 1));

The given points may be any array-like type, but is typically a Float64Array.

delaunay.points ​

The coordinates of the points as an array [x0, y0, x1, y1, …].

delaunay.halfedges ​

The 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. For example, to render the internal edges of the Delaunay triangulation:

js
const {points, halfedges, triangles} = delaunay;
for (let i = 0, n = halfedges.length; i < n; ++i) {
  const j = halfedges[i];
  if (j < i) continue;
  const ti = triangles[i];
  const tj = triangles[j];
  context.moveTo(points[ti * 2], points[ti * 2 + 1]);
  context.lineTo(points[tj * 2], points[tj * 2 + 1]);
}

See also delaunay.render.

delaunay.hull ​

An Int32Array of point indexes that form the convex hull in counterclockwise order. If the points are collinear, returns them ordered.

See also delaunay.renderHull.

delaunay.triangles ​

The 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. For example, to render triangle i:

js
const {points, triangles} = delaunay;
const t0 = triangles[i * 3 + 0];
const t1 = triangles[i * 3 + 1];
const t2 = triangles[i * 3 + 2];
context.moveTo(points[t0 * 2], points[t0 * 2 + 1]);
context.lineTo(points[t1 * 2], points[t1 * 2 + 1]);
context.lineTo(points[t2 * 2], points[t2 * 2 + 1]);
context.closePath();

See also delaunay.renderTriangle.

delaunay.inedges ​

The 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.from(points, fx, fy, that) ​

TIP

Delaunay.from is typically slower than new Delaunay because it requires materializing a new flat array of xy coordinates.

Source · Returns 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], …].

js
const delaunay = d3.Delaunay.from([[0, 0], [0, 1], [1, 0], [1, 1]]);

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.

js
const delaunay = d3.Delaunay.from([{x: 0, y: 0}, {x: 0, y: 1}, {x: 1, y: 0}, {x: 1, y: 1}], (d) => d.x, (d) => d.y);

If that is specified, the functions fx and fy are invoked with that as this. (See Array.from for reference.)

delaunay.find(x, y, i) ​

js
delaunay.find(0, 0) // -1

Examples · Source · Returns 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.

delaunay.neighbors(i) ​

js
delaunay.neighbors(-1) // []

Source · Returns an iterable over the indexes of the neighboring points to the specified point i. The iterable is empty if i is a coincident point.

delaunay.render(context) ​

Source · Renders 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. If a context is not specified, an SVG path string is returned instead.

delaunay.renderHull(context) ​

Source · Renders 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. If a context is not specified, an SVG path string is returned instead.

delaunay.renderTriangle(i, context) ​

Source · Renders 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. If a context is not specified, an SVG path string is returned instead.

delaunay.renderPoints(context, radius) ​

Source · Renders 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. If a context is not specified, an SVG path string is returned instead.

delaunay.hullPolygon() ​

Source · Returns the closed polygon [[x0, y0], [x1, y1], …, [x0, y0]] representing the convex hull. See also delaunay.renderHull.

delaunay.trianglePolygons() ​

Source · Returns an iterable over the polygons for each triangle, in order. See also delaunay.renderTriangle.

delaunay.trianglePolygon(i) ​

Source · Returns the closed polygon [[x0, y0], [x1, y1], [x2, y2], [x0, y0]] representing the triangle i. See also delaunay.renderTriangle.

delaunay.update() ​

Source · Recomputes the triangulation after the points have been modified in-place.

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].

js
const delaunay = d3.Delaunay.from(points);
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.