packages/charts/src/utils/d3-delaunay/index.ts

/** * @notice * This product includes code that is adapted d3-delaunay@5.2.1, * which is available under a "ISC" license. * * Copyright 2018 Observable, Inc. * * Permission to use, copy, modify, and/or distribute this software for any purpose * with or without fee is hereby granted, provided that the above copyright notice * and this permission notice appear in all copies. * * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH * REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND * FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS * OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF * THIS SOFTWARE. */ // @ts-nocheck /** * Delaunay triangulation */ interface DelaunayI { /** * The 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. */ points: ArrayLike<number>; /** * The halfedge indices 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. */ halfedges: Int32Array; /** * An arbitrary node on the convex hull. * The convex hull is represented as a circular doubly-linked list of nodes. */ hull: Node; /** * The triangle vertex indices as an Uint32Array [i0, j0, k0, i1, j1, k1, ...]. * Each contiguous triplet of indices i, j, k forms a counterclockwise triangle. * The coordinates of the triangle's points can be found by going through 'points'. */ triangles: Uint32Array; /** * 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. */ inedges: Int32Array; /** * The outgoing halfedge indexes as a Int32Array [e0, e1, e2, ...]. * For each point i on the convex hull, outedges[i] is the halfedge index e of the corresponding outgoing halfedge; for other points, the halfedge index is -1. */ outedges: Int32Array; /** * 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. */ find(x: number, y: number, i?: number): number; /** * 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. */ neighbors(i: number): IterableIterator<number>; /** * Returns the closed polygon [[x0, y0], [x1, y1], ..., [x0, y0]] representing the convex hull. */ hullPolygon(): Polygon; /** * Returns the closed polygon [[x0, y0], [x1, y1], [x2, y2], [x0, y0]] representing the triangle i. */ trianglePolygon(i: number): Triangle; /** * Returns an iterable over the polygons for each triangle, in order. */ trianglePolygons(): IterableIterator<Triangle>; /** * Returns the Voronoi diagram for the associated 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 for an interactive explanation of Voronoi cell clipping. */ voronoi(bounds?: Bounds): Voronoi; } /** * A point represented as an array tuple [x, y]. */ type Point = number[]; /** * A closed polygon [[x0, y0], [x1, y1], [x2, y2], [x0, y0]] representing a triangle. */ type Triangle = Point[]; /** * A closed polygon [[x0, y0], [x1, y1], ..., [x0, y0]]. */ type PolygonI = Point[]; /** * A rectangular area [x, y, width, height]. */ export type Bounds = number[]; /** * A function to extract a x- or y-coordinate from the specified point. */ type GetCoordinate<P, PS> = (point: P, i: number, points: PS) => number; /** * A point node on a convex hull (represented as a circular linked list). */ interface Node { /** * The index of the associated point. */ i: number; /** * The x-coordinate of the associated point. */ x: number; /** * The y-coordinate of the associated point. */ y: number; /** * The index of the (incoming or outgoing?) associated halfedge. */ t: number; /** * The previous node on the hull. */ prev: Node; /** * The next node on the hull. */ next: Node; /** * Whether the node has been removed from the linked list. */ removed: boolean; } /** * An interface for the rect() method of the CanvasPathMethods API. */ interface RectContext { /** * rect() method of the CanvasPathMethods API. */ rect(x: number, y: number, width: number, height: number): void; } /** * An interface for the moveTo() method of the CanvasPathMethods API. */ interface MoveContext { /** * moveTo() method of the CanvasPathMethods API. */ moveTo(x: number, y: number): void; } /** * An interface for the lineTo() method of the CanvasPathMethods API. */ interface LineContext { /** * lineTo() method of the CanvasPathMethods API. */ lineTo(x: number, y: number): void; } /** * An interface for the arc() method of the CanvasPathMethods API. */ interface ArcContext { /** * arc() method of the CanvasPathMethods API. */ arc(x: number, y: number, radius: number, startAngle: number, endAngle: number, counterclockwise?: boolean): void; } /** * An interface for the closePath() method of the CanvasPathMethods API. */ interface ClosableContext { /** * closePath() method of the CanvasPathMethods API. */ closePath(): void; } /** * Voronoi regions */ interface VoronoiI { /** * The Voronoi diagram’s associated Delaunay triangulation. */ delaunay: DelaunayI; /** * The circumcenters of the Delaunay triangles [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. */ circumcenters: Float64Array; /** * An array [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. */ vectors: Float64Array; /** * 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, cell.render). */ xmin: number; ymin: number; xmax: number; ymax: number; /** * Returns 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.) */ contains(i: number, x: number, y: number): boolean; /** * Returns the convex, closed polygon [[x0, y0], [x1, y1], ..., [x0, y0]] representing the cell for the specified point i. */ cellPolygon(i: number): PolygonI; /** * Returns an iterable over the polygons for each cell, in order. */ cellPolygons(): IterableIterator<PolygonI>; } // https://github.com/d3/d3-delaunay v5.2.1 Copyright 2020 Mike Bostock // https://github.com/mapbox/delaunator v4.0.1. Copyright 2019 Mapbox, Inc. // Type definitions for d3-delaunay 4.1 // Project: https://github.com/d3/d3-delaunay // Definitions by: Bradley Odell <https://github.com/BTOdell> // Definitions: https://github.com/DefinitelyTyped/DefinitelyTyped const EPSILON = Math.pow(2, -52); const EDGE_STACK = new Uint32Array(512); class Delaunator { static from(points, getX = defaultGetX, getY = defaultGetY) { const n = points.length; const coords = new Float64Array(n * 2); for (let i = 0; i < n; i++) { const p = points[i]; coords[2 * i] = getX(p); coords[2 * i + 1] = getY(p); } return new Delaunator(coords); } constructor(coords) { const n = coords.length >> 1; if (n > 0 && typeof coords[0] !== 'number') throw new Error('Expected coords to contain numbers.'); this.coords = coords; // arrays that will store the triangulation graph const maxTriangles = Math.max(2 * n - 5, 0); this._triangles = new Uint32Array(maxTriangles * 3); this._halfedges = new Int32Array(maxTriangles * 3); // temporary arrays for tracking the edges of the advancing convex hull this._hashSize = Math.ceil(Math.sqrt(n)); this._hullPrev = new Uint32Array(n); // edge to prev edge this._hullNext = new Uint32Array(n); // edge to next edge this._hullTri = new Uint32Array(n); // edge to adjacent triangle this._hullHash = new Int32Array(this._hashSize).fill(-1); // angular edge hash // temporary arrays for sorting points this._ids = new Uint32Array(n); this._dists = new Float64Array(n); this.update(); } update() { const { coords, _hullPrev: hullPrev, _hullNext: hullNext, _hullTri: hullTri, _hullHash: hullHash } = this; const n = coords.length >> 1; // populate an array of point indices; calculate input data bbox let minX = Infinity; let minY = Infinity; let maxX = -Infinity; let maxY = -Infinity; for (let i = 0; i < n; i++) { const x = coords[2 * i]; const y = coords[2 * i + 1]; if (x < minX) minX = x; if (y < minY) minY = y; if (x > maxX) maxX = x; if (y > maxY) maxY = y; this._ids[i] = i; } const cx = (minX + maxX) / 2; const cy = (minY + maxY) / 2; let minDist = Infinity; let i0, i1, i2; // pick a seed point close to the center for (let i = 0; i < n; i++) { const d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]); if (d < minDist) { i0 = i; minDist = d; } } const i0x = coords[2 * i0]; const i0y = coords[2 * i0 + 1]; minDist = Infinity; // find the point closest to the seed for (let i = 0; i < n; i++) { if (i === i0) continue; const d = dist(i0x, i0y, coords[2 * i], coords[2 * i + 1]); if (d < minDist && d > 0) { i1 = i; minDist = d; } } let i1x = coords[2 * i1]; let i1y = coords[2 * i1 + 1]; let minRadius = Infinity; // find the third point which forms the smallest circumcircle with the first two for (let i = 0; i < n; i++) { if (i === i0 || i === i1) continue; const r = circumradius(i0x, i0y, i1x, i1y, coords[2 * i], coords[2 * i + 1]); if (r < minRadius) { i2 = i; minRadius = r; } } let i2x = coords[2 * i2]; let i2y = coords[2 * i2 + 1]; if (minRadius === Infinity) { // order collinear points by dx (or dy if all x are identical) // and return the list as a hull for (let i = 0; i < n; i++) { this._dists[i] = coords[2 * i] - coords[0] || coords[2 * i + 1] - coords[1]; } quicksort(this._ids, this._dists, 0, n - 1); const hull = new Uint32Array(n); let j = 0; for (let i = 0, d0 = -Infinity; i < n; i++) { const id = this._ids[i]; if (this._dists[id] > d0) { hull[j++] = id; d0 = this._dists[id]; } } this.hull = hull.subarray(0, j); this.triangles = new Uint32Array(0); this.halfedges = new Uint32Array(0); return; } // swap the order of the seed points for counter-clockwise orientation if (orient(i0x, i0y, i1x, i1y, i2x, i2y)) { const i = i1; const x = i1x; const y = i1y; i1 = i2; i1x = i2x; i1y = i2y; i2 = i; i2x = x; i2y = y; } const center = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y); this._cx = center.x; this._cy = center.y; for (let i = 0; i < n; i++) { this._dists[i] = dist(coords[2 * i], coords[2 * i + 1], center.x, center.y); } // sort the points by distance from the seed triangle circumcenter quicksort(this._ids, this._dists, 0, n - 1); // set up the seed triangle as the starting hull this._hullStart = i0; let hullSize = 3; hullNext[i0] = hullPrev[i2] = i1; hullNext[i1] = hullPrev[i0] = i2; hullNext[i2] = hullPrev[i1] = i0; hullTri[i0] = 0; hullTri[i1] = 1; hullTri[i2] = 2; hullHash.fill(-1); hullHash[this._hashKey(i0x, i0y)] = i0; hullHash[this._hashKey(i1x, i1y)] = i1; hullHash[this._hashKey(i2x, i2y)] = i2; this.trianglesLen = 0; this._addTriangle(i0, i1, i2, -1, -1, -1); for (let k = 0, xp, yp; k < this._ids.length; k++) { const i = this._ids[k]; const x = coords[2 * i]; const y = coords[2 * i + 1]; // skip near-duplicate points if (k > 0 && Math.abs(x - xp) <= EPSILON && Math.abs(y - yp) <= EPSILON) continue; xp = x; yp = y; // skip seed triangle points if (i === i0 || i === i1 || i === i2) continue; // find a visible edge on the convex hull using edge hash let start = 0; for (let j = 0, key = this._hashKey(x, y); j < this._hashSize; j++) { start = hullHash[(key + j) % this._hashSize]; if (start !== -1 && start !== hullNext[start]) break; } start = hullPrev[start]; let e = start, q; while (((q = hullNext[e]), !orient(x, y, coords[2 * e], coords[2 * e + 1], coords[2 * q], coords[2 * q + 1]))) { e = q; if (e === start) { e = -1; break; } } if (e === -1) continue; // likely a near-duplicate point; skip it // add the first triangle from the point let t = this._addTriangle(e, i, hullNext[e], -1, -1, hullTri[e]); // recursively flip triangles from the point until they satisfy the Delaunay condition hullTri[i] = this._legalize(t + 2); hullTri[e] = t; // keep track of boundary triangles on the hull hullSize++; // walk forward through the hull, adding more triangles and flipping recursively let n = hullNext[e]; while (((q = hullNext[n]), orient(x, y, coords[2 * n], coords[2 * n + 1], coords[2 * q], coords[2 * q + 1]))) { t = this._addTriangle(n, i, q, hullTri[i], -1, hullTri[n]); hullTri[i] = this._legalize(t + 2); hullNext[n] = n; // mark as removed hullSize--; n = q; } // walk backward from the other side, adding more triangles and flipping if (e === start) { while (((q = hullPrev[e]), orient(x, y, coords[2 * q], coords[2 * q + 1], coords[2 * e], coords[2 * e + 1]))) { t = this._addTriangle(q, i, e, -1, hullTri[e], hullTri[q]); this._legalize(t + 2); hullTri[q] = t; hullNext[e] = e; // mark as removed hullSize--; e = q; } } // update the hull indices this._hullStart = hullPrev[i] = e; hullNext[e] = hullPrev[n] = i; hullNext[i] = n; // save the two new edges in the hash table hullHash[this._hashKey(x, y)] = i; hullHash[this._hashKey(coords[2 * e], coords[2 * e + 1])] = e; } this.hull = new Uint32Array(hullSize); for (let i = 0, e = this._hullStart; i < hullSize; i++) { this.hull[i] = e; e = hullNext[e]; } // trim typed triangle mesh arrays this.triangles = this._triangles.subarray(0, this.trianglesLen); this.halfedges = this._halfedges.subarray(0, this.trianglesLen); } _hashKey(x, y) { return Math.floor(pseudoAngle(x - this._cx, y - this._cy) * this._hashSize) % this._hashSize; } _legalize(a) { const { _triangles: triangles, _halfedges: halfedges, coords } = this; let i = 0; let ar = 0; // recursion eliminated with a fixed-size stack while (true) { const b = halfedges[a]; /* if the pair of triangles doesn't satisfy the Delaunay condition * (p1 is inside the circumcircle of [p0, pl, pr]), flip them, * then do the same check/flip recursively for the new pair of triangles * * pl pl * /||\ / \ * al/ || \bl al/ \a * / || \ / \ * / a||b \ flip /___ar___\ * p0\ || /p1 => p0\---bl---/p1 * \ || / \ / * ar\ || /br b\ /br * \||/ \ / * pr pr */ const a0 = a - (a % 3); ar = a0 + ((a + 2) % 3); if (b === -1) { // convex hull edge if (i === 0) break; a = EDGE_STACK[--i]; continue; } const b0 = b - (b % 3); const al = a0 + ((a + 1) % 3); const bl = b0 + ((b + 2) % 3); const p0 = triangles[ar]; const pr = triangles[a]; const pl = triangles[al]; const p1 = triangles[bl]; const illegal = inCircle( coords[2 * p0], coords[2 * p0 + 1], coords[2 * pr], coords[2 * pr + 1], coords[2 * pl], coords[2 * pl + 1], coords[2 * p1], coords[2 * p1 + 1], ); if (illegal) { triangles[a] = p1; triangles[b] = p0; const hbl = halfedges[bl]; // edge swapped on the other side of the hull (rare); fix the halfedge reference if (hbl === -1) { let e = this._hullStart; do { if (this._hullTri[e] === bl) { this._hullTri[e] = a; break; } e = this._hullPrev[e]; } while (e !== this._hullStart); } this._link(a, hbl); this._link(b, halfedges[ar]); this._link(ar, bl); const br = b0 + ((b + 1) % 3); // don't worry about hitting the cap: it can only happen on extremely degenerate input if (i < EDGE_STACK.length) { EDGE_STACK[i++] = br; } } else { if (i === 0) break; a = EDGE_STACK[--i]; } } return ar; } _link(a, b) { this._halfedges[a] = b; if (b !== -1) this._halfedges[b] = a; } // add a new triangle given vertex indices and adjacent half-edge ids _addTriangle(i0, i1, i2, a, b, c) { const t = this.trianglesLen; this._triangles[t] = i0; this._triangles[t + 1] = i1; this._triangles[t + 2] = i2; this._link(t, a); this._link(t + 1, b); this._link(t + 2, c); this.trianglesLen += 3; return t; } } // monotonically increases with real angle, but doesn't need expensive trigonometry function pseudoAngle(dx, dy) { const p = dx / (Math.abs(dx) + Math.abs(dy)); return (dy > 0 ? 3 - p : 1 + p) / 4; // [0..1] } function dist(ax, ay, bx, by) { const dx = ax - bx; const dy = ay - by; return dx * dx + dy * dy; } // return 2d orientation sign if we're confident in it through J. Shewchuk's error bound check function orientIfSure(px, py, rx, ry, qx, qy) { const l = (ry - py) * (qx - px); const r = (rx - px) * (qy - py); return Math.abs(l - r) >= 3.3306690738754716e-16 * Math.abs(l + r) ? l - r : 0; } // a more robust orientation test that's stable in a given triangle (to fix robustness issues) function orient(rx, ry, qx, qy, px, py) { const sign = orientIfSure(px, py, rx, ry, qx, qy) || orientIfSure(rx, ry, qx, qy, px, py) || orientIfSure(qx, qy, px, py, rx, ry); return sign < 0; } function inCircle(ax, ay, bx, by, cx, cy, px, py) { const dx = ax - px; const dy = ay - py; const ex = bx - px; const ey = by - py; const fx = cx - px; const fy = cy - py; const ap = dx * dx + dy * dy; const bp = ex * ex + ey * ey; const cp = fx * fx + fy * fy; return dx * (ey * cp - bp * fy) - dy * (ex * cp - bp * fx) + ap * (ex * fy - ey * fx) < 0; } function circumradius(ax, ay, bx, by, cx, cy) { const dx = bx - ax; const dy = by - ay; const ex = cx - ax; const ey = cy - ay; const bl = dx * dx + dy * dy; const cl = ex * ex + ey * ey; const d = 0.5 / (dx * ey - dy * ex); const x = (ey * bl - dy * cl) * d; const y = (dx * cl - ex * bl) * d; return x * x + y * y; } function circumcenter(ax, ay, bx, by, cx, cy) { const dx = bx - ax; const dy = by - ay; const ex = cx - ax; const ey = cy - ay; const bl = dx * dx + dy * dy; const cl = ex * ex + ey * ey; const d = 0.5 / (dx * ey - dy * ex); const x = ax + (ey * bl - dy * cl) * d; const y = ay + (dx * cl - ex * bl) * d; return { x, y }; } function quicksort(ids, dists, left, right) { if (right - left <= 20) { for (let i = left + 1; i <= right; i++) { const temp = ids[i]; const tempDist = dists[temp]; let j = i - 1; while (j >= left && dists[ids[j]] > tempDist) ids[j + 1] = ids[j--]; ids[j + 1] = temp; } } else { const median = (left + right) >> 1; let i = left + 1; let j = right; swap(ids, median, i); if (dists[ids[left]] > dists[ids[right]]) swap(ids, left, right); if (dists[ids[i]] > dists[ids[right]]) swap(ids, i, right); if (dists[ids[left]] > dists[ids[i]]) swap(ids, left, i); const temp = ids[i]; const tempDist = dists[temp]; while (true) { do i++; while (dists[ids[i]] < tempDist); do j--; while (dists[ids[j]] > tempDist); if (j < i) break; swap(ids, i, j); } ids[left + 1] = ids[j]; ids[j] = temp; if (right - i + 1 >= j - left) { quicksort(ids, dists, i, right); quicksort(ids, dists, left, j - 1); } else { quicksort(ids, dists, left, j - 1); quicksort(ids, dists, i, right); } } } function swap(arr, i, j) { const tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } function defaultGetX(p) { return p[0]; } function defaultGetY(p) { return p[1]; } const epsilon = 1e-6; class Path { constructor() { this._x0 = this._y0 = this._x1 = this._y1 = null; // start of current subpath // end of current subpath this._ = ''; } moveTo(x, y) { this._ += `M${(this._x0 = this._x1 = +x)},${(this._y0 = this._y1 = +y)}`; } closePath() { if (this._x1 !== null) { (this._x1 = this._x0), (this._y1 = this._y0); this._ += 'Z'; } } lineTo(x, y) { this._ += `L${(this._x1 = +x)},${(this._y1 = +y)}`; } arc(x, y, r) { (x = +x), (y = +y), (r = +r); const x0 = x + r; const y0 = y; if (r < 0) throw new Error('negative radius'); if (this._x1 === null) this._ += `M${x0},${y0}`; else if (Math.abs(this._x1 - x0) > epsilon || Math.abs(this._y1 - y0) > epsilon) this._ += 'L' + x0 + ',' + y0; if (!r) return; this._ += `A${r},${r},0,1,1,${x - r},${y}A${r},${r},0,1,1,${(this._x1 = x0)},${(this._y1 = y0)}`; } rect(x, y, w, h) { this._ += `M${(this._x0 = this._x1 = +x)},${(this._y0 = this._y1 = +y)}h${+w}v${+h}h${-w}Z`; } value() { return this._ || null; } } class Polygon { constructor() { this._ = []; } moveTo(x, y) { this._.push([x, y]); } closePath() { this._.push(this._[0].slice()); } lineTo(x, y) { this._.push([x, y]); } value() { return this._.length ? this._ : null; } } export class Voronoi implements VoronoiI { xmin: number; ymin: number; xmax: number; ymax: number; /** * The Voronoi diagram’s associated Delaunay triangulation. */ delaunay: DelaunayI; /** * The circumcenters of the Delaunay triangles [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. */ circumcenters: Float64Array; /** * An array [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. */ vectors: Float64Array; constructor(delaunay: DelaunayI, [xmin, ymin, xmax, ymax]: Bounds = [0, 0, 960, 500]) { if (!((xmax = +xmax) >= (xmin = +xmin)) || !((ymax = +ymax) >= (ymin = +ymin))) throw new Error('invalid bounds'); this.delaunay = delaunay; this._circumcenters = new Float64Array(delaunay.points.length * 2); this.vectors = new Float64Array(delaunay.points.length * 2); (this.xmax = xmax), (this.xmin = xmin); (this.ymax = ymax), (this.ymin = ymin); this._init(); } update() { this.delaunay.update(); this._init(); return this; } _init() { const { delaunay: { points, hull, triangles }, vectors, } = this; // Compute circumcenters. const circumcenters = (this.circumcenters = this._circumcenters.subarray(0, (triangles.length / 3) * 2)); for (let i = 0, j = 0, n = triangles.length, x, y; i < n; i += 3, j += 2) { const t1 = triangles[i] * 2; const t2 = triangles[i + 1] * 2; const t3 = triangles[i + 2] * 2; const x1 = points[t1]; const y1 = points[t1 + 1]; const x2 = points[t2]; const y2 = points[t2 + 1]; const x3 = points[t3]; const y3 = points[t3 + 1]; const dx = x2 - x1; const dy = y2 - y1; const ex = x3 - x1; const ey = y3 - y1; const bl = dx * dx + dy * dy; const cl = ex * ex + ey * ey; const ab = (dx * ey - dy * ex) * 2; if (!ab) { // degenerate case (collinear diagram) x = (x1 + x3) / 2 - 1e8 * ey; y = (y1 + y3) / 2 + 1e8 * ex; } else if (Math.abs(ab) < 1e-8) { // almost equal points (degenerate triangle) x = (x1 + x3) / 2; y = (y1 + y3) / 2; } else { const d = 1 / ab; x = x1 + (ey * bl - dy * cl) * d; y = y1 + (dx * cl - ex * bl) * d; } circumcenters[j] = x; circumcenters[j + 1] = y; } // Compute exterior cell rays. let h = hull[hull.length - 1]; let p0, p1 = h * 4; let x0, x1 = points[2 * h]; let y0, y1 = points[2 * h + 1]; vectors.fill(0); for (let i = 0; i < hull.length; ++i) { h = hull[i]; (p0 = p1), (x0 = x1), (y0 = y1); (p1 = h * 4), (x1 = points[2 * h]), (y1 = points[2 * h + 1]); vectors[p0 + 2] = vectors[p1] = y0 - y1; vectors[p0 + 3] = vectors[p1 + 1] = x1 - x0; } } /** * 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. */ render(context: MoveContext & LineContext): void { const buffer = context === null ? (context = new Path()) : undefined; const { delaunay: { halfedges, inedges, hull }, circumcenters, vectors, } = this; if (hull.length <= 1) return null; for (let i = 0, n = halfedges.length; i < n; ++i) { const j = halfedges[i]; if (j < i) continue; const ti = Math.floor(i / 3) * 2; const tj = Math.floor(j / 3) * 2; const xi = circumcenters[ti]; const yi = circumcenters[ti + 1]; const xj = circumcenters[tj]; const yj = circumcenters[tj + 1]; this._renderSegment(xi, yi, xj, yj, context); } let h0, h1 = hull[hull.length - 1]; for (let i = 0; i < hull.length; ++i) { (h0 = h1), (h1 = hull[i]); const t = Math.floor(inedges[h1] / 3) * 2; const x = circumcenters[t]; const y = circumcenters[t + 1]; const v = h0 * 4; const p = this._project(x, y, vectors[v + 2], vectors[v + 3]); if (p) this._renderSegment(x, y, p[0], p[1], context); } return buffer && buffer.value(); } /** * 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). */ renderBounds(context: RectContext): void { const buffer = context === null ? (context = new Path()) : undefined; context.rect(this.xmin, this.ymin, this.xmax - this.xmin, this.ymax - this.ymin); return buffer && buffer.value(); } /** * 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. */ renderCell(i: number, context: MoveContext & LineContext & ClosableContext): void { const buffer = context == null ? (context = new Path()) : undefined; const points = this._clip(i); if (points === null) return; context.moveTo(points[0], points[1]); let n = points.length; while (points[0] === points[n - 2] && points[1] === points[n - 1] && n > 1) n -= 2; for (let i = 2; i < n; i += 2) { if (points[i] !== points[i - 2] || points[i + 1] !== points[i - 1]) context.lineTo(points[i], points[i + 1]); } context.closePath(); return buffer && buffer.value(); } *cellPolygons() { const { delaunay: { points }, } = this; for (let i = 0, n = points.length / 2; i < n; ++i) { const cell = this.cellPolygon(i); if (cell) yield cell; } } cellPolygon(i) { const polygon = new Polygon(); this.renderCell(i, polygon); return polygon.value(); } _renderSegment(x0, y0, x1, y1, context) { let S; const c0 = this._regioncode(x0, y0); const c1 = this._regioncode(x1, y1); if (c0 === 0 && c1 === 0) { context.moveTo(x0, y0); context.lineTo(x1, y1); } else if ((S = this._clipSegment(x0, y0, x1, y1, c0, c1))) { context.moveTo(S[0], S[1]); context.lineTo(S[2], S[3]); } } contains(i, x, y) { if (((x = +x), x !== x) || ((y = +y), y !== y)) return false; return this.delaunay._step(i, x, y) === i; } *neighbors(i) { const ci = this._clip(i); if (ci) for (const j of this.delaunay.neighbors(i)) { const cj = this._clip(j); // find the common edge if (cj) loop: for (let ai = 0, li = ci.length; ai < li; ai += 2) { for (let aj = 0, lj = cj.length; aj < lj; aj += 2) { if ( ci[ai] == cj[aj] && ci[ai + 1] == cj[aj + 1] && ci[(ai + 2) % li] == cj[(aj + lj - 2) % lj] && ci[(ai + 3) % li] == cj[(aj + lj - 1) % lj] ) { yield j; break loop; } } } } } _cell(i) { const { circumcenters, delaunay: { inedges, halfedges, triangles }, } = this; const e0 = inedges[i]; if (e0 === -1) return null; // coincident point const points = []; let e = e0; do { const t = Math.floor(e / 3); points.push(circumcenters[t * 2], circumcenters[t * 2 + 1]); e = e % 3 === 2 ? e - 2 : e + 1; if (triangles[e] !== i) break; // bad triangulation e = halfedges[e]; } while (e !== e0 && e !== -1); return points; } _clip(i) { // degenerate case (1 valid point: return the box) if (i === 0 && this.delaunay.hull.length === 1) { return [this.xmax, this.ymin, this.xmax, this.ymax, this.xmin, this.ymax, this.xmin, this.ymin]; } const points = this._cell(i); if (points === null) return null; const { vectors: V } = this; const v = i * 4; return V[v] || V[v + 1] ? this._clipInfinite(i, points, V[v], V[v + 1], V[v + 2], V[v + 3]) : this._clipFinite(i, points); } _clipFinite(i, points) { const n = points.length; let P = null; let x0, y0, x1 = points[n - 2], y1 = points[n - 1]; let c0, c1 = this._regioncode(x1, y1); let e0, e1; for (let j = 0; j < n; j += 2) { (x0 = x1), (y0 = y1), (x1 = points[j]), (y1 = points[j + 1]); (c0 = c1), (c1 = this._regioncode(x1, y1)); if (c0 === 0 && c1 === 0) { (e0 = e1), (e1 = 0); if (P) P.push(x1, y1); else P = [x1, y1]; } else { let S, sx0, sy0, sx1, sy1; if (c0 === 0) { if ((S = this._clipSegment(x0, y0, x1, y1, c0, c1)) === null) continue; [sx0, sy0, sx1, sy1] = S; } else { if ((S = this._clipSegment(x1, y1, x0, y0, c1, c0)) === null) continue; [sx1, sy1, sx0, sy0] = S; (e0 = e1), (e1 = this._edgecode(sx0, sy0)); if (e0 && e1) this._edge(i, e0, e1, P, P.length); if (P) P.push(sx0, sy0); else P = [sx0, sy0]; } (e0 = e1), (e1 = this._edgecode(sx1, sy1)); if (e0 && e1) this._edge(i, e0, e1, P, P.length); if (P) P.push(sx1, sy1); else P = [sx1, sy1]; } } if (P) { (e0 = e1), (e1 = this._edgecode(P[0], P[1])); if (e0 && e1) this._edge(i, e0, e1, P, P.length); } else if (this.contains(i, (this.xmin + this.xmax) / 2, (this.ymin + this.ymax) / 2)) { return [this.xmax, this.ymin, this.xmax, this.ymax, this.xmin, this.ymax, this.xmin, this.ymin]; } return P; } _clipSegment(x0, y0, x1, y1, c0, c1) { while (true) { if (c0 === 0 && c1 === 0) return [x0, y0, x1, y1]; if (c0 & c1) return null; let x, y, c = c0 || c1; if (c & 0b1000) (x = x0 + ((x1 - x0) * (this.ymax - y0)) / (y1 - y0)), (y = this.ymax); else if (c & 0b0100) (x = x0 + ((x1 - x0) * (this.ymin - y0)) / (y1 - y0)), (y = this.ymin); else if (c & 0b0010) (y = y0 + ((y1 - y0) * (this.xmax - x0)) / (x1 - x0)), (x = this.xmax); else (y = y0 + ((y1 - y0) * (this.xmin - x0)) / (x1 - x0)), (x = this.xmin); if (c0) (x0 = x), (y0 = y), (c0 = this._regioncode(x0, y0)); else (x1 = x), (y1 = y), (c1 = this._regioncode(x1, y1)); } } _clipInfinite(i, points, vx0, vy0, vxn, vyn) { let P = Array.from(points), p; if ((p = this._project(P[0], P[1], vx0, vy0))) P.unshift(p[0], p[1]); if ((p = this._project(P[P.length - 2], P[P.length - 1], vxn, vyn))) P.push(p[0], p[1]); if ((P = this._clipFinite(i, P))) { for (let j = 0, n = P.length, c0, c1 = this._edgecode(P[n - 2], P[n - 1]); j < n; j += 2) { (c0 = c1), (c1 = this._edgecode(P[j], P[j + 1])); if (c0 && c1) (j = this._edge(i, c0, c1, P, j)), (n = P.length); } } else if (this.contains(i, (this.xmin + this.xmax) / 2, (this.ymin + this.ymax) / 2)) { P = [this.xmin, this.ymin, this.xmax, this.ymin, this.xmax, this.ymax, this.xmin, this.ymax]; } return P; } _edge(i, e0, e1, P, j) { while (e0 !== e1) { let x, y; switch (e0) { case 0b0101: e0 = 0b0100; continue; // top-left case 0b0100: (e0 = 0b0110), (x = this.xmax), (y = this.ymin); break; // top case 0b0110: e0 = 0b0010; continue; // top-right case 0b0010: (e0 = 0b1010), (x = this.xmax), (y = this.ymax); break; // right case 0b1010: e0 = 0b1000; continue; // bottom-right case 0b1000: (e0 = 0b1001), (x = this.xmin), (y = this.ymax); break; // bottom case 0b1001: e0 = 0b0001; continue; // bottom-left case 0b0001: (e0 = 0b0101), (x = this.xmin), (y = this.ymin); break; // left } if ((P[j] !== x || P[j + 1] !== y) && this.contains(i, x, y)) { P.splice(j, 0, x, y), (j += 2); } } if (P.length > 4) { for (let i = 0; i < P.length; i += 2) { const j = (i + 2) % P.length, k = (i + 4) % P.length; if ((P[i] === P[j] && P[j] === P[k]) || (P[i + 1] === P[j + 1] && P[j + 1] === P[k + 1])) P.splice(j, 2), (i -= 2); } } return j; } _project(x0, y0, vx, vy) { let t = Infinity, c, x, y; if (vy < 0) { // top if (y0 <= this.ymin) return null; if ((c = (this.ymin - y0) / vy) < t) (y = this.ymin), (x = x0 + (t = c) * vx); } else if (vy > 0) { // bottom if (y0 >= this.ymax) return null; if ((c = (this.ymax - y0) / vy) < t) (y = this.ymax), (x = x0 + (t = c) * vx); } if (vx > 0) { // right if (x0 >= this.xmax) return null; if ((c = (this.xmax - x0) / vx) < t) (x = this.xmax), (y = y0 + (t = c) * vy); } else if (vx < 0) { // left if (x0 <= this.xmin) return null; if ((c = (this.xmin - x0) / vx) < t) (x = this.xmin), (y = y0 + (t = c) * vy); } return [x, y]; } _edgecode(x, y) { return ( (x === this.xmin ? 0b0001 : x === this.xmax ? 0b0010 : 0b0000) | (y === this.ymin ? 0b0100 : y === this.ymax ? 0b1000 : 0b0000) ); } _regioncode(x, y) { return ( (x < this.xmin ? 0b0001 : x > this.xmax ? 0b0010 : 0b0000) | (y < this.ymin ? 0b0100 : y > this.ymax ? 0b1000 : 0b0000) ); } } const tau = 2 * Math.PI; function pointX(p) { return p[0]; } function pointY(p) { return p[1]; } // A triangulation is collinear if all its triangles have a non-null area function collinear(d) { const { triangles, coords } = d; for (let i = 0; i < triangles.length; i += 3) { const a = 2 * triangles[i], b = 2 * triangles[i + 1], c = 2 * triangles[i + 2], cross = (coords[c] - coords[a]) * (coords[b + 1] - coords[a + 1]) - (coords[b] - coords[a]) * (coords[c + 1] - coords[a + 1]); if (cross > 1e-10) return false; } return true; } function jitter(x, y, r) { return [x + Math.sin(x + y) * r, y + Math.cos(x - y) * r]; } export class Delaunay implements DelaunayI { /** * The 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. */ points: ArrayLike<number>; /** * The halfedge indices 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. */ halfedges: Int32Array; /** * An arbitrary node on the convex hull. * The convex hull is represented as a circular doubly-linked list of nodes. */ hull: Node; /** * The triangle vertex indices as an Uint32Array [i0, j0, k0, i1, j1, k1, ...]. * Each contiguous triplet of indices i, j, k forms a counterclockwise triangle. * The coordinates of the triangle's points can be found by going through 'points'. */ triangles: Uint32Array; /** * 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. */ inedges: Int32Array; /** * The outgoing halfedge indexes as a Int32Array [e0, e1, e2, ...]. * For each point i on the convex hull, outedges[i] is the halfedge index e of the corresponding outgoing halfedge; for other points, the halfedge index is -1. */ outedges: Int32Array; /** * Returns the Delaunay triangulation for the given array or iterable of points. * Otherwise, the getX and getY functions are invoked for each point in order, and must return the respective x- and y-coordinate for each point. * If that is specified, the functions getX and getY are invoked with that as this. * (See Array.from for reference.) */ static from( points: ArrayLike | Iterable, fx: GetCoordinate<P, ArrayLike | Iterable> = pointX, fy: GetCoordinate<P, ArrayLike | Iterable> = pointY, that?: any, ): Delaunay { return new Delaunay( 'length' in points ? flatArray(points, fx, fy, that) : Float64Array.from(flatIterable(points, fx, fy, that)), ); } /** * Returns the Delaunay triangulation for the given flat array [x0, y0, x1, y1, …] of points. */ constructor(points: ArrayLike<number>) { this._delaunator = new Delaunator(points); this.inedges = new Int32Array(points.length / 2); this._hullIndex = new Int32Array(points.length / 2); this.points = this._delaunator.coords; this._init(); } update() { this._delaunator.update(); this._init(); return this; } _init() { const d = this._delaunator, points = this.points; // check for collinear if (d.hull && d.hull.length > 2 && collinear(d)) { this.collinear = Int32Array.from({ length: points.length / 2 }, (_, i) => i).sort( (i, j) => points[2 * i] - points[2 * j] || points[2 * i + 1] - points[2 * j + 1], ); // for exact neighbors const e = this.collinear[0], f = this.collinear[this.collinear.length - 1], bounds = [points[2 * e], points[2 * e + 1], points[2 * f], points[2 * f + 1]], r = 1e-8 * Math.sqrt((bounds[3] - bounds[1]) ** 2 + (bounds[2] - bounds[0]) ** 2); for (let i = 0, n = points.length / 2; i < n; ++i) { const p = jitter(points[2 * i], points[2 * i + 1], r); points[2 * i] = p[0]; points[2 * i + 1] = p[1]; } this._delaunator = new Delaunator(points); } else { delete this.collinear; } const halfedges = (this.halfedges = this._delaunator.halfedges); const hull = (this.hull = this._delaunator.hull); const triangles = (this.triangles = this._delaunator.triangles); const inedges = this.inedges.fill(-1); const hullIndex = this._hullIndex.fill(-1); // Compute an index from each point to an (arbitrary) incoming halfedge // Used to give the first neighbor of each point; for this reason, // on the hull we give priority to exterior halfedges for (let e = 0, n = halfedges.length; e < n; ++e) { const p = triangles[e % 3 === 2 ? e - 2 : e + 1]; if (halfedges[e] === -1 || inedges[p] === -1) inedges[p] = e; } for (let i = 0, n = hull.length; i < n; ++i) { hullIndex[hull[i]] = i; } // degenerate case: 1 or 2 (distinct) points if (hull.length <= 2 && hull.length > 0) { this.triangles = new Int32Array(3).fill(-1); this.halfedges = new Int32Array(3).fill(-1); this.triangles[0] = hull[0]; this.triangles[1] = hull[1]; this.triangles[2] = hull[1]; inedges[hull[0]] = 1; if (hull.length === 2) inedges[hull[1]] = 0; } } voronoi(bounds) { return new Voronoi(this, bounds); } *neighbors(i) { const { inedges, hull, _hullIndex, halfedges, triangles, collinear } = this; // degenerate case with several collinear points if (collinear) { const l = collinear.indexOf(i); if (l > 0) yield collinear[l - 1]; if (l < collinear.length - 1) yield collinear[l + 1]; return; } const e0 = inedges[i]; if (e0 === -1) return; // coincident point let e = e0, p0 = -1; do { yield (p0 = triangles[e]); e = e % 3 === 2 ? e - 2 : e + 1; if (triangles[e] !== i) return; // bad triangulation e = halfedges[e]; if (e === -1) { const p = hull[(_hullIndex[i] + 1) % hull.length]; if (p !== p0) yield p; return; } } while (e !== e0); } find(x, y, i = 0) { if (((x = +x), x !== x) || ((y = +y), y !== y)) return -1; const i0 = i; let c; while ((c = this._step(i, x, y)) >= 0 && c !== i && c !== i0) i = c; return c; } _step(i, x, y) { const { inedges, hull, _hullIndex, halfedges, triangles, points } = this; if (inedges[i] === -1 || !points.length) return (i + 1) % (points.length >> 1); let c = i; let dc = (x - points[i * 2]) ** 2 + (y - points[i * 2 + 1]) ** 2; const e0 = inedges[i]; let e = e0; do { let t = triangles[e]; const dt = (x - points[t * 2]) ** 2 + (y - points[t * 2 + 1]) ** 2; if (dt < dc) (dc = dt), (c = t); e = e % 3 === 2 ? e - 2 : e + 1; if (triangles[e] !== i) break; // bad triangulation e = halfedges[e]; if (e === -1) { e = hull[(_hullIndex[i] + 1) % hull.length]; if (e !== t) { if ((x - points[e * 2]) ** 2 + (y - points[e * 2 + 1]) ** 2 < dc) return e; } break; } } while (e !== e0); return c; } /** * 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. */ render(context: MoveContext & LineContext): void { const buffer = context == null ? (context = new Path()) : undefined; const { points, halfedges, triangles } = this; for (let i = 0, n = halfedges.length; i < n; ++i) { const j = halfedges[i]; if (j < i) continue; const ti = triangles[i] * 2; const tj = triangles[j] * 2; context.moveTo(points[ti], points[ti + 1]); context.lineTo(points[tj], points[tj + 1]); } this.renderHull(context); return buffer && buffer.value(); } /** * 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. */ renderPoints(context: MoveContext & ArcContext, r?: number): void { const buffer = context == null ? (context = new Path()) : undefined; const { points } = this; for (let i = 0, n = points.length; i < n; i += 2) { const x = points[i], y = points[i + 1]; context.moveTo(x + r, y); context.arc(x, y, r, 0, tau); } return buffer && buffer.value(); } /** * 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. */ renderHull(context: MoveContext & LineContext): void { const buffer = context == null ? (context = new Path()) : undefined; const { hull, points } = this; const h = hull[0] * 2, n = hull.length; context.moveTo(points[h], points[h + 1]); for (let i = 1; i < n; ++i) { const h = 2 * hull[i]; context.lineTo(points[h], points[h + 1]); } context.closePath(); return buffer && buffer.value(); } hullPolygon() { const polygon = new Polygon(); this.renderHull(polygon); return polygon.value(); } /** * 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. */ renderTriangle(i: number, context: MoveContext & LineContext & ClosableContext): void { const buffer = context == null ? (context = new Path()) : undefined; const { points, triangles } = this; const t0 = triangles[(i *= 3)] * 2; const t1 = triangles[i + 1] * 2; const t2 = triangles[i + 2] * 2; context.moveTo(points[t0], points[t0 + 1]); context.lineTo(points[t1], points[t1 + 1]); context.lineTo(points[t2], points[t2 + 1]); context.closePath(); return buffer && buffer.value(); } *trianglePolygons() { const { triangles } = this; for (let i = 0, n = triangles.length / 3; i < n; ++i) { yield this.trianglePolygon(i); } } trianglePolygon(i) { const polygon = new Polygon(); this.renderTriangle(i, polygon); return polygon.value(); } } function flatArray(points, fx, fy, that) { const n = points.length; const array = new Float64Array(n * 2); for (let i = 0; i < n; ++i) { const p = points[i]; array[i * 2] = fx.call(that, p, i, points); array[i * 2 + 1] = fy.call(that, p, i, points); } return array; } function* flatIterable(points, fx, fy, that) { let i = 0; for (const p of points) { yield fx.call(that, p, i, points); yield fy.call(that, p, i, points); ++i; } }

packages/charts/src/utils/d3-delaunay/index.ts (923 lines of code) (raw):