D3 · all subjects

d3-delaunay

36 notes, read out of this brain and free to use. Each one was extracted from a source and is re-checked against its exam.

d3-delaunay module overview

d3-delaunay computes Delaunay triangulation and Voronoi diagrams for two-dimensional points. It provides Delaunay class with methods for finding closest points, computing neighbors, and rendering, plus Voronoi diagram access with containment testing and cell polygon generation.

d3-delaunay computes Voronoi diagrams and Delaunay triangulations

d3-delaunay is a fast library for computing the Voronoi diagram of a set of two-dimensional points. It is based on Delaunator, which computes the Delaunay triangulation using sweep algorithms. The Voronoi diagram is constructed by connecting the circumcenters of adjacent triangles in the Delaunay triangulation.

voronoi.renderBounds method signature and behavior

The voronoi.renderBounds(context) method renders the viewport extent to the specified context. The context must implement the context.rect method from the CanvasPathMethods API. It is 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 method signature and behavior

The voronoi.renderCell(i, context) method renders the cell with the specified index i to the specified context. The 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 method signature and behavior

The voronoi.cellPolygons() method returns an iterable over the non-empty polygons for each cell, with the cell index as property.

voronoi.cellPolygon method signature and format

The voronoi.cellPolygon(i) method returns the convex, closed polygon [[x0, y0], [x1, y1], …, [x0, y0]] representing the cell for the specified point i.

voronoi.contains method signature and behavior

The voronoi.contains(i, x, y) method returns true if the cell with the specified index i contains the specified point ⟨x, y⟩, meaning 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.delaunay property

The voronoi.delaunay property returns the Voronoi diagram's associated Delaunay triangulation.

voronoi.circumcenters property

The voronoi.circumcenters property returns 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 property

The voronoi.vectors property returns 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 bounds properties: xmin, ymin, xmax, ymax

The voronoi.xmin, voronoi.ymin, voronoi.xmax, and voronoi.ymax properties specify 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(), and voronoi.renderCell().

voronoi.update method signature and behavior

The voronoi.update() method updates the Voronoi diagram and underlying triangulation after the points have been modified in-place, useful for Lloyd's relaxation. It calls delaunay.update() on the underlying Delaunay triangulation.

voronoi.neighbors method signature and behavior

The voronoi.neighbors(i) method 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.

delaunay.hullPolygon method signature

delaunay.hullPolygon() returns the closed polygon [[x0, y0], [x1, y1], …, [x0, y0]] representing the convex hull.

delaunay.trianglePolygons method signature

delaunay.trianglePolygons() returns an iterable over the polygons for each triangle, in order.

delaunay.trianglePolygon method signature

delaunay.trianglePolygon(i) returns the closed polygon [[x0, y0], [x1, y1], [x2, y2], [x0, y0]] representing triangle i.

delaunay.update method signature

delaunay.update() recomputes the triangulation after the points have been modified in-place.

delaunay.voronoi method signature

delaunay.voronoi(bounds) returns the Voronoi diagram for the given Delaunay triangulation. 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]. The Voronoi diagram is returned even in degenerate cases with 0, 1, 2 points, or collinear points.

Delaunay triangulation definition

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

Delaunay.from example with array of arrays

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

Delaunay.from example with accessor functions

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);

Rendering internal edges of Delaunay triangulation example

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]); } This example shows how to render the internal edges using halfedges and triangles properties.

Rendering a triangle example

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(); This example shows how to render triangle i to a canvas context.

Creating Voronoi diagram from Delaunay example

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

Delaunay constructor signature

new Delaunay(points) returns the Delaunay triangulation for a flat array [x0, y0, x1, y1, …] of points. The points parameter may be any array-like type but is typically a Float64Array. Example: new d3.Delaunay(Float64Array.of(0, 0, 0, 1, 1, 0, 1, 1))

Delaunay.from static method signature

Delaunay.from(points, fx, fy, that) returns the Delaunay triangulation for an array or iterable of points. If fx and fy are not specified, points is assumed to be an array of two-element arrays [[x0, y0], [x1, y1], …]. Otherwise, fx and fy are functions invoked for each element that return the x and y coordinate respectively. If that is specified, fx and fy are invoked with that as this. This method is typically slower than new Delaunay because it requires materializing a new flat array of xy coordinates.

delaunay.points property

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

delaunay.halfedges property

An Int32Array [j0, j1, …] of halfedge indexes. For each index 0 ≤ i < halfedges.length, there is a halfedge from triangle vertex j = halfedges[i] to triangle vertex i. Triangle ⌊i / 3⌋ is adjacent to triangle ⌊j / 3⌋. If j is negative, triangle ⌊i / 3⌋ is an exterior triangle on the convex hull.

delaunay.hull property

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

delaunay.triangles property

A Uint32Array [i0, j0, k0, i1, j1, k1, …] of triangle vertex indexes. Each contiguous triplet of indexes i, j, k forms a counterclockwise triangle. Triangle coordinates are found through delaunay.points.

delaunay.inedges property

An Int32Array [e0, e1, e2, …] of incoming halfedge indexes. For each point i, inedges[i] is the halfedge index e of an incoming halfedge. For coincident points the index is -1; for points on the convex hull the incoming halfedge is on the convex hull; for other points the choice is arbitrary. The inedges table can traverse the Delaunay triangulation.

delaunay.find method signature

delaunay.find(x, y, i) returns the index of the input point 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 method signature

delaunay.neighbors(i) 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.renderHull method signature

delaunay.renderHull(context) renders the convex hull of the Delaunay triangulation to the specified context. The context must implement moveTo and lineTo methods from the CanvasPathMethods API. If context is not specified, returns an SVG path string instead.

delaunay.renderTriangle method signature

delaunay.renderTriangle(i, context) renders triangle i of the Delaunay triangulation to the specified context. The context must implement moveTo, lineTo, and closePath methods from the CanvasPathMethods API. If context is not specified, returns an SVG path string instead.

delaunay.renderPoints method signature

delaunay.renderPoints(context, radius) renders the input points of the Delaunay triangulation to the specified context as circles. If radius is not specified, it defaults to 2. The context must implement moveTo and arc methods from the CanvasPathMethods API. If context is not specified, returns an SVG path string instead.

Give your agent this brain