New Case Study:See how Anthropic automated 95% of dependency reviews with Socket.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

d3-delaunay

Package Overview
Dependencies
Maintainers
1
Versions
41
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

d3-delaunay - npm Package Compare versions

Comparing version 2.0.1 to 3.0.0-alpha.1

1432

dist/d3-delaunay.js

@@ -1,833 +0,871 @@

// https://github.com/d3/d3-delaunay Version 2.0.1. Copyright 2018 Observable, Inc.
// https://github.com/mapbox/delaunator Version 1.0.5. Copyright 2017, Mapbox, Inc.
// https://github.com/d3/d3-delaunay Version 3.0.0-alpha.1. Copyright 2018 Observable, Inc.
// https://github.com/mapbox/delaunator Version 2.0.0. Copyright 2017, Mapbox, Inc.
(function (global, factory) {
typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
typeof define === 'function' && define.amd ? define(['exports'], factory) :
(factory((global.d3 = global.d3 || {})));
typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
typeof define === 'function' && define.amd ? define(['exports'], factory) :
(factory((global.d3 = global.d3 || {})));
}(this, (function (exports) { 'use strict';
class Cell {
constructor(voronoi) {
this.voronoi = voronoi;
this.triangles = []; // Triangle indexes, similar to halfedges.
this.v0 = null; // Starting edge vector if hull cell.
this.vn = null; // Ending edge vector if hull cell.
}
_points() {
const {triangles, voronoi: {circumcenters}} = this;
if (triangles === null) return null;
const points = new Float64Array(triangles.length * 2);
for (let i = 0, n = triangles.length; i < n; ++i) {
const pi = i * 2;
const ti = triangles[i] * 2;
points[pi] = circumcenters[ti];
points[pi + 1] = circumcenters[ti + 1];
}
return points;
}
render(context) {
const {v0, vn} = this;
let points;
if ((points = this._points()) === null) return;
if ((points = this.voronoi._clip(points, v0, vn)) === null) return;
context.moveTo(points[0], points[1]);
for (let i = 2, n = points.length; i < n; i += 2) { // TODO Avoid last closing coordinate.
context.lineTo(points[i], points[i + 1]);
}
context.closePath();
}
contains(x, y) {
const points = this._points();
return points === null ? false
: this.v0 === null ? containsFinite(points, x, y)
: containsInfinite(points, this.v0, this.vn, x, y);
}
}
Delaunator.from = function (points, getX, getY) {
if (!getX) getX = defaultGetX;
if (!getY) getY = defaultGetY;
function containsFinite(points, x, y) {
const n = points.length;
let x0, y0, x1 = points[n - 2], y1 = points[n - 1];
for (let i = 0; i < n; i += 2) {
x0 = x1, y0 = y1, x1 = points[i], y1 = points[i + 1];
if ((x1 - x0) * (y - y0) < (y1 - y0) * (x - x0)) {
return false;
}
}
return true;
}
var n = points.length;
var coords = new Float64Array(n * 2);
function containsInfinite(points, [v0x, v0y], [vnx, vny], x, y) {
const n = points.length;
let x0, y0, x1 = points[0], y1 = points[1];
if ((x0 + v0x - x) * (y1 - y) < (y0 + v0y - y) * (x1 - x)) return false;
for (let i = 2; i < n; i += 2) {
x0 = x1, y0 = y1, x1 = points[i], y1 = points[i + 1];
if ((x0 - x) * (y1 - y) < (y0 - y) * (x1 - x)) return false;
}
if ((x0 - x) * (y1 + vny - y) < (y0 - y) * (x1 + vnx - x)) return false;
return true;
}
for (var i = 0; i < n; i++) {
var p = points[i];
coords[2 * i] = getX(p);
coords[2 * i + 1] = getY(p);
}
var delaunator = Delaunator;
var default_1 = Delaunator;
return new Delaunator(coords);
};
function Delaunator(points, getX, getY) {
function Delaunator(coords) {
if (!ArrayBuffer.isView(coords)) throw new Error('Expected coords to be a typed array.');
if (!getX) getX = defaultGetX;
if (!getY) getY = defaultGetY;
var minX = Infinity;
var minY = Infinity;
var maxX = -Infinity;
var maxY = -Infinity;
var minX = Infinity;
var minY = Infinity;
var maxX = -Infinity;
var maxY = -Infinity;
var n = coords.length >> 1;
var ids = this.ids = new Uint32Array(n);
var coords = this.coords = [];
var ids = this.ids = new Uint32Array(points.length);
this.coords = coords;
for (var i = 0; i < points.length; i++) {
var p = points[i];
var x = getX(p);
var y = getY(p);
ids[i] = i;
coords[2 * i] = x;
coords[2 * i + 1] = y;
if (x < minX) minX = x;
if (y < minY) minY = y;
if (x > maxX) maxX = x;
if (y > maxY) maxY = y;
}
for (var i = 0; i < n; i++) {
var x = coords[2 * i];
var 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;
ids[i] = i;
}
var cx = (minX + maxX) / 2;
var cy = (minY + maxY) / 2;
var cx = (minX + maxX) / 2;
var cy = (minY + maxY) / 2;
var minDist = Infinity;
var i0, i1, i2;
var minDist = Infinity;
var i0, i1, i2;
// pick a seed point close to the centroid
for (i = 0; i < points.length; i++) {
var d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]);
if (d < minDist) {
i0 = i;
minDist = d;
}
}
// pick a seed point close to the centroid
for (i = 0; i < n; i++) {
var d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]);
if (d < minDist) {
i0 = i;
minDist = d;
}
}
minDist = Infinity;
minDist = Infinity;
// find the point closest to the seed
for (i = 0; i < points.length; i++) {
if (i === i0) continue;
d = dist(coords[2 * i0], coords[2 * i0 + 1], coords[2 * i], coords[2 * i + 1]);
if (d < minDist && d > 0) {
i1 = i;
minDist = d;
}
}
// find the point closest to the seed
for (i = 0; i < n; i++) {
if (i === i0) continue;
d = dist(coords[2 * i0], coords[2 * i0 + 1], coords[2 * i], coords[2 * i + 1]);
if (d < minDist && d > 0) {
i1 = i;
minDist = d;
}
}
var minRadius = Infinity;
var minRadius = Infinity;
// find the third point which forms the smallest circumcircle with the first two
for (i = 0; i < points.length; i++) {
if (i === i0 || i === i1) continue;
// find the third point which forms the smallest circumcircle with the first two
for (i = 0; i < n; i++) {
if (i === i0 || i === i1) continue;
var r = circumradius(
coords[2 * i0], coords[2 * i0 + 1],
coords[2 * i1], coords[2 * i1 + 1],
coords[2 * i], coords[2 * i + 1]);
var r = circumradius(
coords[2 * i0], coords[2 * i0 + 1],
coords[2 * i1], coords[2 * i1 + 1],
coords[2 * i], coords[2 * i + 1]);
if (r < minRadius) {
i2 = i;
minRadius = r;
}
}
if (r < minRadius) {
i2 = i;
minRadius = r;
}
}
if (minRadius === Infinity) {
throw new Error('No Delaunay triangulation exists for this input.');
}
if (minRadius === Infinity) {
throw new Error('No Delaunay triangulation exists for this input.');
}
// swap the order of the seed points for counter-clockwise orientation
if (area(coords[2 * i0], coords[2 * i0 + 1],
coords[2 * i1], coords[2 * i1 + 1],
coords[2 * i2], coords[2 * i2 + 1]) < 0) {
// swap the order of the seed points for counter-clockwise orientation
if (area(coords[2 * i0], coords[2 * i0 + 1],
coords[2 * i1], coords[2 * i1 + 1],
coords[2 * i2], coords[2 * i2 + 1]) < 0) {
var tmp = i1;
i1 = i2;
i2 = tmp;
}
var tmp = i1;
i1 = i2;
i2 = tmp;
}
var i0x = coords[2 * i0];
var i0y = coords[2 * i0 + 1];
var i1x = coords[2 * i1];
var i1y = coords[2 * i1 + 1];
var i2x = coords[2 * i2];
var i2y = coords[2 * i2 + 1];
var i0x = coords[2 * i0];
var i0y = coords[2 * i0 + 1];
var i1x = coords[2 * i1];
var i1y = coords[2 * i1 + 1];
var i2x = coords[2 * i2];
var i2y = coords[2 * i2 + 1];
var center = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y);
this._cx = center.x;
this._cy = center.y;
var center = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y);
this._cx = center.x;
this._cy = center.y;
// sort the points by distance from the seed triangle circumcenter
quicksort(ids, coords, 0, ids.length - 1, center.x, center.y);
// sort the points by distance from the seed triangle circumcenter
quicksort(ids, coords, 0, ids.length - 1, center.x, center.y);
// initialize a hash table for storing edges of the advancing convex hull
this._hashSize = Math.ceil(Math.sqrt(points.length));
this._hash = [];
for (i = 0; i < this._hashSize; i++) this._hash[i] = null;
// initialize a hash table for storing edges of the advancing convex hull
this._hashSize = Math.ceil(Math.sqrt(n));
this._hash = [];
for (i = 0; i < this._hashSize; i++) this._hash[i] = null;
// initialize a circular doubly-linked list that will hold an advancing convex hull
var e = this.hull = insertNode(coords, i0);
this._hashEdge(e);
e.t = 0;
e = insertNode(coords, i1, e);
this._hashEdge(e);
e.t = 1;
e = insertNode(coords, i2, e);
this._hashEdge(e);
e.t = 2;
// initialize a circular doubly-linked list that will hold an advancing convex hull
var e = this.hull = insertNode(coords, i0);
this._hashEdge(e);
e.t = 0;
e = insertNode(coords, i1, e);
this._hashEdge(e);
e.t = 1;
e = insertNode(coords, i2, e);
this._hashEdge(e);
e.t = 2;
var maxTriangles = 2 * points.length - 5;
var triangles = this.triangles = new Uint32Array(maxTriangles * 3);
var halfedges = this.halfedges = new Int32Array(maxTriangles * 3);
var maxTriangles = 2 * n - 5;
var triangles = this.triangles = new Uint32Array(maxTriangles * 3);
var halfedges = this.halfedges = new Int32Array(maxTriangles * 3);
this.trianglesLen = 0;
this.trianglesLen = 0;
this._addTriangle(i0, i1, i2, -1, -1, -1);
this._addTriangle(i0, i1, i2, -1, -1, -1);
var xp, yp;
for (var k = 0; k < ids.length; k++) {
i = ids[k];
x = coords[2 * i];
y = coords[2 * i + 1];
var xp, yp;
for (var k = 0; k < ids.length; k++) {
i = ids[k];
x = coords[2 * i];
y = coords[2 * i + 1];
// skip duplicate points
if (x === xp && y === yp) continue;
xp = x;
yp = y;
// skip duplicate points
if (x === xp && y === yp) continue;
xp = x;
yp = y;
// skip seed triangle points
if ((x === i0x && y === i0y) ||
(x === i1x && y === i1y) ||
(x === i2x && y === i2y)) continue;
// skip seed triangle points
if ((x === i0x && y === i0y) ||
(x === i1x && y === i1y) ||
(x === i2x && y === i2y)) continue;
// find a visible edge on the convex hull using edge hash
var startKey = this._hashKey(x, y);
var key = startKey;
var start;
do {
start = this._hash[key];
key = (key + 1) % this._hashSize;
} while ((!start || start.removed) && key !== startKey);
// find a visible edge on the convex hull using edge hash
var startKey = this._hashKey(x, y);
var key = startKey;
var start;
do {
start = this._hash[key];
key = (key + 1) % this._hashSize;
} while ((!start || start.removed) && key !== startKey);
e = start;
while (area(x, y, e.x, e.y, e.next.x, e.next.y) >= 0) {
e = e.next;
if (e === start) {
throw new Error('Something is wrong with the input points.');
}
}
e = start;
while (area(x, y, e.x, e.y, e.next.x, e.next.y) >= 0) {
e = e.next;
if (e === start) {
throw new Error('Something is wrong with the input points.');
}
}
var walkBack = e === start;
var walkBack = e === start;
// add the first triangle from the point
var t = this._addTriangle(e.i, i, e.next.i, -1, -1, e.t);
// add the first triangle from the point
var t = this._addTriangle(e.i, i, e.next.i, -1, -1, e.t);
e.t = t; // keep track of boundary triangles on the hull
e = insertNode(coords, i, e);
e.t = t; // keep track of boundary triangles on the hull
e = insertNode(coords, i, e);
// recursively flip triangles from the point until they satisfy the Delaunay condition
e.t = this._legalize(t + 2);
if (e.prev.prev.t === halfedges[t + 1]) {
e.prev.prev.t = t + 2;
}
// recursively flip triangles from the point until they satisfy the Delaunay condition
e.t = this._legalize(t + 2);
if (e.prev.prev.t === halfedges[t + 1]) {
e.prev.prev.t = t + 2;
}
// walk forward through the hull, adding more triangles and flipping recursively
var q = e.next;
while (area(x, y, q.x, q.y, q.next.x, q.next.y) < 0) {
t = this._addTriangle(q.i, i, q.next.i, q.prev.t, -1, q.t);
q.prev.t = this._legalize(t + 2);
this.hull = removeNode(q);
q = q.next;
}
// walk forward through the hull, adding more triangles and flipping recursively
var q = e.next;
while (area(x, y, q.x, q.y, q.next.x, q.next.y) < 0) {
t = this._addTriangle(q.i, i, q.next.i, q.prev.t, -1, q.t);
q.prev.t = this._legalize(t + 2);
this.hull = removeNode(q);
q = q.next;
}
if (walkBack) {
// walk backward from the other side, adding more triangles and flipping
q = e.prev;
while (area(x, y, q.prev.x, q.prev.y, q.x, q.y) < 0) {
t = this._addTriangle(q.prev.i, i, q.i, -1, q.t, q.prev.t);
this._legalize(t + 2);
q.prev.t = t;
this.hull = removeNode(q);
q = q.prev;
}
}
if (walkBack) {
// walk backward from the other side, adding more triangles and flipping
q = e.prev;
while (area(x, y, q.prev.x, q.prev.y, q.x, q.y) < 0) {
t = this._addTriangle(q.prev.i, i, q.i, -1, q.t, q.prev.t);
this._legalize(t + 2);
q.prev.t = t;
this.hull = removeNode(q);
q = q.prev;
}
}
// save the two new edges in the hash table
this._hashEdge(e);
this._hashEdge(e.prev);
}
// save the two new edges in the hash table
this._hashEdge(e);
this._hashEdge(e.prev);
}
// trim typed triangle mesh arrays
this.triangles = triangles.subarray(0, this.trianglesLen);
this.halfedges = halfedges.subarray(0, this.trianglesLen);
}
// trim typed triangle mesh arrays
this.triangles = triangles.subarray(0, this.trianglesLen);
this.halfedges = halfedges.subarray(0, this.trianglesLen);
}
Delaunator.prototype = {
Delaunator.prototype = {
_hashEdge: function (e) {
this._hash[this._hashKey(e.x, e.y)] = e;
},
_hashEdge: function (e) {
this._hash[this._hashKey(e.x, e.y)] = e;
},
_hashKey: function (x, y) {
var dx = x - this._cx;
var dy = y - this._cy;
// use pseudo-angle: a measure that monotonically increases
// with real angle, but doesn't require expensive trigonometry
var p = 1 - dx / (Math.abs(dx) + Math.abs(dy));
return Math.floor((2 + (dy < 0 ? -p : p)) / 4 * this._hashSize);
},
_hashKey: function (x, y) {
var dx = x - this._cx;
var dy = y - this._cy;
// use pseudo-angle: a measure that monotonically increases
// with real angle, but doesn't require expensive trigonometry
var p = 1 - dx / (Math.abs(dx) + Math.abs(dy));
return Math.floor((2 + (dy < 0 ? -p : p)) / 4 * this._hashSize);
},
_legalize: function (a) {
var triangles = this.triangles;
var coords = this.coords;
var halfedges = this.halfedges;
_legalize: function (a) {
var triangles = this.triangles;
var coords = this.coords;
var halfedges = this.halfedges;
var b = halfedges[a];
var b = halfedges[a];
var a0 = a - a % 3;
var b0 = b - b % 3;
var a0 = a - a % 3;
var b0 = b - b % 3;
var al = a0 + (a + 1) % 3;
var ar = a0 + (a + 2) % 3;
var bl = b0 + (b + 2) % 3;
var al = a0 + (a + 1) % 3;
var ar = a0 + (a + 2) % 3;
var bl = b0 + (b + 2) % 3;
var p0 = triangles[ar];
var pr = triangles[a];
var pl = triangles[al];
var p1 = triangles[bl];
var p0 = triangles[ar];
var pr = triangles[a];
var pl = triangles[al];
var p1 = triangles[bl];
var 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]);
var 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;
if (illegal) {
triangles[a] = p1;
triangles[b] = p0;
this._link(a, halfedges[bl]);
this._link(b, halfedges[ar]);
this._link(ar, bl);
this._link(a, halfedges[bl]);
this._link(b, halfedges[ar]);
this._link(ar, bl);
var br = b0 + (b + 1) % 3;
var br = b0 + (b + 1) % 3;
this._legalize(a);
return this._legalize(br);
}
this._legalize(a);
return this._legalize(br);
}
return ar;
},
return ar;
},
_link: function (a, b) {
this.halfedges[a] = b;
if (b !== -1) this.halfedges[b] = a;
},
_link: function (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: function (i0, i1, i2, a, b, c) {
var t = this.trianglesLen;
// add a new triangle given vertex indices and adjacent half-edge ids
_addTriangle: function (i0, i1, i2, a, b, c) {
var t = this.trianglesLen;
this.triangles[t] = i0;
this.triangles[t + 1] = i1;
this.triangles[t + 2] = i2;
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._link(t, a);
this._link(t + 1, b);
this._link(t + 2, c);
this.trianglesLen += 3;
this.trianglesLen += 3;
return t;
}
};
return t;
}
};
function dist(ax, ay, bx, by) {
var dx = ax - bx;
var dy = ay - by;
return dx * dx + dy * dy;
}
function dist(ax, ay, bx, by) {
var dx = ax - bx;
var dy = ay - by;
return dx * dx + dy * dy;
}
function area(px, py, qx, qy, rx, ry) {
return (qy - py) * (rx - qx) - (qx - px) * (ry - qy);
}
function area(px, py, qx, qy, rx, ry) {
return (qy - py) * (rx - qx) - (qx - px) * (ry - qy);
}
function inCircle(ax, ay, bx, by, cx, cy, px, py) {
ax -= px;
ay -= py;
bx -= px;
by -= py;
cx -= px;
cy -= py;
function inCircle(ax, ay, bx, by, cx, cy, px, py) {
ax -= px;
ay -= py;
bx -= px;
by -= py;
cx -= px;
cy -= py;
var ap = ax * ax + ay * ay;
var bp = bx * bx + by * by;
var cp = cx * cx + cy * cy;
var ap = ax * ax + ay * ay;
var bp = bx * bx + by * by;
var cp = cx * cx + cy * cy;
return ax * (by * cp - bp * cy) -
ay * (bx * cp - bp * cx) +
ap * (bx * cy - by * cx) < 0;
}
return ax * (by * cp - bp * cy) -
ay * (bx * cp - bp * cx) +
ap * (bx * cy - by * cx) < 0;
}
function circumradius(ax, ay, bx, by, cx, cy) {
bx -= ax;
by -= ay;
cx -= ax;
cy -= ay;
function circumradius(ax, ay, bx, by, cx, cy) {
bx -= ax;
by -= ay;
cx -= ax;
cy -= ay;
var bl = bx * bx + by * by;
var cl = cx * cx + cy * cy;
var bl = bx * bx + by * by;
var cl = cx * cx + cy * cy;
if (bl === 0 || cl === 0) return Infinity;
if (bl === 0 || cl === 0) return Infinity;
var d = bx * cy - by * cx;
if (d === 0) return Infinity;
var d = bx * cy - by * cx;
if (d === 0) return Infinity;
var x = (cy * bl - by * cl) * 0.5 / d;
var y = (bx * cl - cx * bl) * 0.5 / d;
var x = (cy * bl - by * cl) * 0.5 / d;
var y = (bx * cl - cx * bl) * 0.5 / d;
return x * x + y * y;
}
return x * x + y * y;
}
function circumcenter(ax, ay, bx, by, cx, cy) {
bx -= ax;
by -= ay;
cx -= ax;
cy -= ay;
function circumcenter(ax, ay, bx, by, cx, cy) {
bx -= ax;
by -= ay;
cx -= ax;
cy -= ay;
var bl = bx * bx + by * by;
var cl = cx * cx + cy * cy;
var bl = bx * bx + by * by;
var cl = cx * cx + cy * cy;
var d = bx * cy - by * cx;
var d = bx * cy - by * cx;
var x = (cy * bl - by * cl) * 0.5 / d;
var y = (bx * cl - cx * bl) * 0.5 / d;
var x = (cy * bl - by * cl) * 0.5 / d;
var y = (bx * cl - cx * bl) * 0.5 / d;
return {
x: ax + x,
y: ay + y
};
}
return {
x: ax + x,
y: ay + y
};
}
// create a new node in a doubly linked list
function insertNode(coords, i, prev) {
var node = {
i: i,
x: coords[2 * i],
y: coords[2 * i + 1],
t: 0,
prev: null,
next: null,
removed: false
};
// create a new node in a doubly linked list
function insertNode(coords, i, prev) {
var node = {
i: i,
x: coords[2 * i],
y: coords[2 * i + 1],
t: 0,
prev: null,
next: null,
removed: false
};
if (!prev) {
node.prev = node;
node.next = node;
if (!prev) {
node.prev = node;
node.next = node;
} else {
node.next = prev.next;
node.prev = prev;
prev.next.prev = node;
prev.next = node;
}
return node;
}
} else {
node.next = prev.next;
node.prev = prev;
prev.next.prev = node;
prev.next = node;
}
return node;
}
function removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.removed = true;
return node.prev;
}
function removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.removed = true;
return node.prev;
}
function quicksort(ids, coords, left, right, cx, cy) {
var i, j, temp;
function quicksort(ids, coords, left, right, cx, cy) {
var i, j, temp;
if (right - left <= 20) {
for (i = left + 1; i <= right; i++) {
temp = ids[i];
j = i - 1;
while (j >= left && compare(coords, ids[j], temp, cx, cy) > 0) ids[j + 1] = ids[j--];
ids[j + 1] = temp;
}
} else {
var median = (left + right) >> 1;
i = left + 1;
j = right;
swap(ids, median, i);
if (compare(coords, ids[left], ids[right], cx, cy) > 0) swap(ids, left, right);
if (compare(coords, ids[i], ids[right], cx, cy) > 0) swap(ids, i, right);
if (compare(coords, ids[left], ids[i], cx, cy) > 0) swap(ids, left, i);
if (right - left <= 20) {
for (i = left + 1; i <= right; i++) {
temp = ids[i];
j = i - 1;
while (j >= left && compare(coords, ids[j], temp, cx, cy) > 0) ids[j + 1] = ids[j--];
ids[j + 1] = temp;
}
} else {
var median = (left + right) >> 1;
i = left + 1;
j = right;
swap(ids, median, i);
if (compare(coords, ids[left], ids[right], cx, cy) > 0) swap(ids, left, right);
if (compare(coords, ids[i], ids[right], cx, cy) > 0) swap(ids, i, right);
if (compare(coords, ids[left], ids[i], cx, cy) > 0) swap(ids, left, i);
temp = ids[i];
while (true) {
do i++; while (compare(coords, ids[i], temp, cx, cy) < 0);
do j--; while (compare(coords, ids[j], temp, cx, cy) > 0);
if (j < i) break;
swap(ids, i, j);
}
ids[left + 1] = ids[j];
ids[j] = temp;
temp = ids[i];
while (true) {
do i++; while (compare(coords, ids[i], temp, cx, cy) < 0);
do j--; while (compare(coords, ids[j], temp, cx, cy) > 0);
if (j < i) break;
swap(ids, i, j);
}
ids[left + 1] = ids[j];
ids[j] = temp;
if (right - i + 1 >= j - left) {
quicksort(ids, coords, i, right, cx, cy);
quicksort(ids, coords, left, j - 1, cx, cy);
} else {
quicksort(ids, coords, left, j - 1, cx, cy);
quicksort(ids, coords, i, right, cx, cy);
}
}
}
if (right - i + 1 >= j - left) {
quicksort(ids, coords, i, right, cx, cy);
quicksort(ids, coords, left, j - 1, cx, cy);
} else {
quicksort(ids, coords, left, j - 1, cx, cy);
quicksort(ids, coords, i, right, cx, cy);
}
}
}
function compare(coords, i, j, cx, cy) {
var d1 = dist(coords[2 * i], coords[2 * i + 1], cx, cy);
var d2 = dist(coords[2 * j], coords[2 * j + 1], cx, cy);
return (d1 - d2) || (coords[2 * i] - coords[2 * j]) || (coords[2 * i + 1] - coords[2 * j + 1]);
}
function compare(coords, i, j, cx, cy) {
var d1 = dist(coords[2 * i], coords[2 * i + 1], cx, cy);
var d2 = dist(coords[2 * j], coords[2 * j + 1], cx, cy);
return (d1 - d2) || (coords[2 * i] - coords[2 * j]) || (coords[2 * i + 1] - coords[2 * j + 1]);
}
function swap(arr, i, j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
function swap(arr, i, j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
function defaultGetX(p) {
return p[0];
}
function defaultGetY(p) {
return p[1];
}
delaunator.default = default_1;
class Voronoi {
constructor(cells, circumcenters, delaunay, xmin, ymin, xmax, ymax) {
if (!((xmax = +xmax) >= (xmin = +xmin)) || !((ymax = +ymax) >= (ymin = +ymin))) throw new Error("invalid bounds");
this.cells = cells;
this.circumcenters = circumcenters;
this.delaunay = delaunay;
this.xmax = xmax, this.xmin = xmin;
this.ymax = ymax, this.ymin = ymin;
function defaultGetX(p) {
return p[0];
}
find(x, y) {
return this.cells[this.findIndex(x, y)];
function defaultGetY(p) {
return p[1];
}
findIndex(x, y) {
const {cells, delaunay: {halfedges, points, triangles}} = this;
if (cells.length === 0 || (x = +x, x !== x) || (y = +y, y !== y)) return -1;
let c = 0, c2 = (x - points[0]) ** 2 + (y - points[1]) ** 2;
while (true) {
let d = c, d2 = c2;
for (let T = cells[c].triangles, i = 0, n = T.length; i < n; ++i) {
let k = T[i] * 3;
switch (c) {
case triangles[k]: k = triangles[k + 1]; break;
case triangles[k + 1]: k = triangles[k + 2]; break;
case triangles[k + 2]: k = triangles[k]; break;
class Voronoi {
constructor(delaunay, [xmin, ymin, xmax, ymax] = [0, 0, 960, 500]) {
if (!((xmax = +xmax) >= (xmin = +xmin)) || !((ymax = +ymax) >= (ymin = +ymin))) throw new Error("invalid bounds");
const {points, halfedges, hull, triangles} = this.delaunay = delaunay;
const circumcenters = this.circumcenters = new Float64Array(triangles.length / 3 * 2);
const edges = this.edges = new Uint32Array(halfedges.length);
const index = this.index = new Uint32Array(points.length);
const vectors = this.vectors = new Float64Array(points.length * 2);
this.xmax = xmax, this.xmin = xmin;
this.ymax = ymax, this.ymin = ymin;
// Compute cell topology.
for (let i = 0, e = 0, m = halfedges.length; i < m; ++i) {
const t = triangles[i]; // Cell vertex.
if (index[t * 2] !== index[t * 2 + 1]) continue; // Already connected.
const e0 = index[t * 2] = e;
let j = i;
do { // Walk forward.
edges[e++] = Math.floor(j / 3);
j = halfedges[j];
if (j === -1) break; // Went off the convex hull.
j = j % 3 === 2 ? j - 2 : j + 1;
if (triangles[j] !== t) break; // Bad triangulation; break early.
} while (j !== i);
if (j !== i) { // Stopped when walking forward; walk backward.
const e1 = e;
j = i;
while (true) {
j = halfedges[j % 3 === 0 ? j + 2 : j - 1];
if (j === -1 || triangles[j] !== t) break;
edges[e++] = Math.floor(j / 3);
}
if (e1 < e) {
edges.subarray(e0, e1).reverse();
edges.subarray(e0, e).reverse();
}
}
let k2 = (x - points[k * 2]) ** 2 + (y - points[k * 2 + 1]) ** 2;
if (k2 < d2) d2 = k2, d = k;
index[t * 2 + 1] = e;
}
if (d === c) return d;
c = d, c2 = d2;
// Compute circumcenters.
for (let i = 0, j = 0, n = triangles.length; 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 a2 = x1 - x2;
const a3 = x1 - x3;
const b2 = y1 - y2;
const b3 = y1 - y3;
const d1 = x1 * x1 + y1 * y1;
const d2 = d1 - x2 * x2 - y2 * y2;
const d3 = d1 - x3 * x3 - y3 * y3;
const ab = (a3 * b2 - a2 * b3) * 2;
circumcenters[j] = (b2 * d3 - b3 * d2) / ab;
circumcenters[j + 1] = (a3 * d2 - a2 * d3) / ab;
}
// Compute exterior cell rays.
for (let n = hull.length, p0, x0, y0, p1 = triangles[hull[n - 1]] * 2, x1 = points[p1], y1 = points[p1 + 1], i = 0; i < n; ++i) {
p0 = p1, x0 = x1, y0 = y1, p1 = triangles[hull[i]] * 2, x1 = points[p1], y1 = points[p1 + 1];
vectors[p0 * 2 + 2] = vectors[p1 * 2] = y0 - y1;
vectors[p0 * 2 + 3] = vectors[p1 * 2 + 1] = x1 - x0;
}
}
}
render(context) {
const {cells, circumcenters, delaunay: {halfedges, hull}} = this;
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;
context.moveTo(circumcenters[ti], circumcenters[ti + 1]);
context.lineTo(circumcenters[tj], circumcenters[tj + 1]);
render(context) {
const {delaunay: {halfedges, hull, triangles}, circumcenters, vectors} = this;
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;
context.moveTo(circumcenters[ti], circumcenters[ti + 1]);
context.lineTo(circumcenters[tj], circumcenters[tj + 1]);
}
for (let i = 0, n = hull.length; i < n; ++i) {
const t = Math.floor(hull[i] / 3) * 2;
const x = circumcenters[t];
const y = circumcenters[t + 1];
const v = triangles[hull[i]] * 4;
const p = this._project(x, y, vectors[v + 2], vectors[v + 3]);
if (p) {
context.moveTo(x, y);
context.lineTo(p[0], p[1]);
}
}
}
let node = hull;
do {
const t = Math.floor(node.t / 3) * 2;
const x = circumcenters[t];
const y = circumcenters[t + 1];
const p = this._project(x, y, cells[node.i].vn);
if (p) {
context.moveTo(x, y);
context.lineTo(p[0], p[1]);
renderBounds(context) {
context.rect(this.xmin, this.ymin, this.xmax - this.xmin, this.ymax - this.ymin);
}
renderCell(i, context) {
const points = this._clip(i);
if (points === null) return;
context.moveTo(points[0], points[1]);
for (let i = 2, n = points.length; i < n; i += 2) {
context.lineTo(points[i], points[i + 1]);
}
} while ((node = node.next) !== hull);
}
renderBounds(context) {
context.rect(this.xmin, this.ymin, this.xmax - this.xmin, this.ymax - this.ymin);
}
_clip(points, v0, vn) {
return v0 ? this._clipInfinite(points, v0, vn) : this._clipFinite(points);
}
_clipFinite(points) {
const n = points.length;
let P = null, S;
let x0, y0, x1 = points[n - 2], y1 = points[n - 1];
let c0, c1 = this._regioncode(x1, y1);
let e0, e1;
for (let i = 0; i < n; i += 2) {
x0 = x1, y0 = y1, x1 = points[i], y1 = points[i + 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 if (S = this._clipSegment(x0, y0, x1, y1, c0, c1)) {
const [sx0, sy0, sx1, sy1] = S;
if (c0) {
e0 = e1, e1 = this._edgecode(sx0, sy0);
context.closePath();
}
contains(i, x, y) {
const {vectors: V} = this;
const points = this._cell(i);
const v = i * 4;
return points === null ? false
: V[v] || V[v + 1] ? containsInfinite(points, V[v], V[v + 1], V[v + 2], V[v + 3], x, y)
: containsFinite(points, x, y);
}
find(x, y, i = 0) {
const {delaunay: {halfedges, points, triangles}, edges, index} = this;
if (points.length === 0 || (x = +x, x !== x) || (y = +y, y !== y)) return -1;
let di = (x - points[i * 2]) ** 2 + (y - points[i * 2 + 1]) ** 2;
while (true) {
const j0 = index[i * 2];
const j1 = index[i * 2 + 1];
let c = i, dc = di;
let k = edges[j0] * 3;
switch (i) { // Test previous point on triangle (for hull).
case triangles[k]: k = triangles[k + 2]; break;
case triangles[k + 1]: k = triangles[k]; break;
case triangles[k + 2]: k = triangles[k + 1]; break;
}
let dk = (x - points[k * 2]) ** 2 + (y - points[k * 2 + 1]) ** 2;
if (dk < dc) dc = dk, c = k;
for (let j = j0; j < j1; ++j) {
k = edges[j] * 3;
switch (i) { // Test next point on triangle.
case triangles[k]: k = triangles[k + 1]; break;
case triangles[k + 1]: k = triangles[k + 2]; break;
case triangles[k + 2]: k = triangles[k]; break;
}
dk = (x - points[k * 2]) ** 2 + (y - points[k * 2 + 1]) ** 2;
if (dk < dc) dc = dk, c = k;
}
if (c === i) return c;
i = c, di = dc;
}
}
_cell(i) {
const {index, edges, circumcenters} = this;
const t0 = index[i * 2];
const t1 = index[i * 2 + 1];
if (t0 === t1) return null;
const points = new Float64Array((t1 - t0) * 2);
for (let t = t0, j = 0; t < t1; ++t, j += 2) {
const ti = edges[t] * 2;
points[j] = circumcenters[ti];
points[j + 1] = circumcenters[ti + 1];
}
return points;
}
_clip(i) {
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(points, V[v], V[v + 1], V[v + 2], V[v + 3])
: this._clipFinite(points);
}
_clipFinite(points) {
const n = points.length;
let P = null, S;
let x0, y0, x1 = points[n - 2], y1 = points[n - 1];
let c0, c1 = this._regioncode(x1, y1);
let e0, e1;
for (let i = 0; i < n; i += 2) {
x0 = x1, y0 = y1, x1 = points[i], y1 = points[i + 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 if (S = this._clipSegment(x0, y0, x1, y1, c0, c1)) {
const [sx0, sy0, sx1, sy1] = S;
if (c0) {
e0 = e1, e1 = this._edgecode(sx0, sy0);
if (e0 && e1) this._edge(points, e0, e1, P);
if (P) P.push(sx0, sy0);
else P = [sx0, sy0];
}
e0 = e1, e1 = this._edgecode(sx1, sy1);
if (e0 && e1) this._edge(points, e0, e1, P);
if (P) P.push(sx0, sy0);
else P = [sx0, sy0];
if (P) P.push(sx1, sy1);
else P = [sx1, sy1];
}
e0 = e1, e1 = this._edgecode(sx1, sy1);
}
if (P) {
e0 = e1, e1 = this._edgecode(P[0], P[1]);
if (e0 && e1) this._edge(points, e0, e1, P);
if (P) P.push(sx1, sy1);
else P = [sx1, sy1];
} else if (containsFinite(points, (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;
}
if (P) {
e0 = e1, e1 = this._edgecode(P[0], P[1]);
if (e0 && e1) this._edge(points, e0, e1, P);
} else if (containsFinite(points, (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];
_clipSegment(x0, y0, x1, y1, c0, c1) {
while (true) {
if (c0 === 0 && c1 === 0) return [x0, y0, x1, y1];
if (c0 & c1) return;
let x, y, c = c0 || c1;
if (c & 0b1000) x = x0 + (x1 - x0) * (this.ymax - y0) / (y1 - y0), y = this.ymax, c ^= 0b1000;
else if (c & 0b0100) x = x0 + (x1 - x0) * (this.ymin - y0) / (y1 - y0), y = this.ymin, c ^= 0b0100;
else if (c & 0b0010) y = y0 + (y1 - y0) * (this.xmax - x0) / (x1 - x0), x = this.xmax, c ^= 0b0010;
else y = y0 + (y1 - y0) * (this.xmin - x0) / (x1 - x0), x = this.xmin, c ^= 0b0001;
if (c0) x0 = x, y0 = y, c0 = c;
else x1 = x, y1 = y, c1 = c;
}
}
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;
let x, y, c = c0 || c1;
if (c & 0b1000) x = x0 + (x1 - x0) * (this.ymax - y0) / (y1 - y0), y = this.ymax, c ^= 0b1000;
else if (c & 0b0100) x = x0 + (x1 - x0) * (this.ymin - y0) / (y1 - y0), y = this.ymin, c ^= 0b0100;
else if (c & 0b0010) y = y0 + (y1 - y0) * (this.xmax - x0) / (x1 - x0), x = this.xmax, c ^= 0b0010;
else y = y0 + (y1 - y0) * (this.xmin - x0) / (x1 - x0), x = this.xmin, c ^= 0b0001;
if (c0) x0 = x, y0 = y, c0 = c;
else x1 = x, y1 = y, c1 = c;
}
}
// TODO Consolidate corner traversal code using edge?
_clipInfinite(points, v0, vn) {
let P = Array.from(points), p;
if (p = this._project(P[0], P[1], v0)) P.unshift(p[0], p[1]);
if (p = this._project(P[P.length - 2], P[P.length - 1], vn)) P.unshift(p[0], p[1]);
if (P = this._clipFinite(P)) {
for (let i = 0, n = P.length, c0, c1 = this._edgecode(P[n - 2], P[n - 1]); i < n; i += 2) {
c0 = c1, c1 = this._edgecode(P[i], P[i + 1]);
if (c0 && c1) {
while (c0 !== c1) {
let cx, cy;
switch (c0) {
case 0b0101: c0 = 0b0100; continue; // top-left
case 0b0100: c0 = 0b0110, cx = this.xmax, cy = this.ymin; break; // top
case 0b0110: c0 = 0b0010; continue; // top-right
case 0b0010: c0 = 0b1010, cx = this.xmax, cy = this.ymax; break; // right
case 0b1010: c0 = 0b1000; continue; // bottom-right
case 0b1000: c0 = 0b1001, cx = this.xmin, cy = this.ymax; break; // bottom
case 0b1001: c0 = 0b0001; continue; // bottom-left
case 0b0001: c0 = 0b0101, cx = this.xmin, cy = this.ymin; break; // left
// TODO Consolidate corner traversal code using edge?
_clipInfinite(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.unshift(p[0], p[1]);
if (P = this._clipFinite(P)) {
for (let i = 0, n = P.length, c0, c1 = this._edgecode(P[n - 2], P[n - 1]); i < n; i += 2) {
c0 = c1, c1 = this._edgecode(P[i], P[i + 1]);
if (c0 && c1) {
while (c0 !== c1) {
let cx, cy;
switch (c0) {
case 0b0101: c0 = 0b0100; continue; // top-left
case 0b0100: c0 = 0b0110, cx = this.xmax, cy = this.ymin; break; // top
case 0b0110: c0 = 0b0010; continue; // top-right
case 0b0010: c0 = 0b1010, cx = this.xmax, cy = this.ymax; break; // right
case 0b1010: c0 = 0b1000; continue; // bottom-right
case 0b1000: c0 = 0b1001, cx = this.xmin, cy = this.ymax; break; // bottom
case 0b1001: c0 = 0b0001; continue; // bottom-left
case 0b0001: c0 = 0b0101, cx = this.xmin, cy = this.ymin; break; // left
}
if (containsInfinite(points, vx0, vy0, vxn, vyn, cx, cy)) {
P.splice(i, 0, cx, cy), n += 2, i += 2;
}
}
if (containsInfinite(points, v0, vn, cx, cy)) {
P.splice(i, 0, cx, cy), n += 2, i += 2;
}
}
}
} else if (containsInfinite(points, vx0, vy0, vxn, vyn, (this.xmin + this.xmax) / 2, (this.ymin + this.ymax) / 2)) {
P.push(this.xmin, this.ymin, this.xmax, this.ymin, this.xmax, this.ymax, this.xmin, this.ymax);
}
} else if (containsInfinite(points, v0, vn, (this.xmin + this.xmax) / 2, (this.ymin + this.ymax) / 2)) {
P.push(this.xmin, this.ymin, this.xmax, this.ymin, this.xmax, this.ymax, this.xmin, this.ymax);
return P;
}
return P;
}
// TODO Allow containsInfinite instead of contains for clipInfinite?
_edge(points, e0, e1, P) {
while (e0 !== e1) {
let cx, cy;
switch (e0) {
case 0b0101: e0 = 0b0100; continue; // top-left
case 0b0100: e0 = 0b0110, cx = this.xmax, cy = this.ymin; break; // top
case 0b0110: e0 = 0b0010; continue; // top-right
case 0b0010: e0 = 0b1010, cx = this.xmax, cy = this.ymax; break; // right
case 0b1010: e0 = 0b1000; continue; // bottom-right
case 0b1000: e0 = 0b1001, cx = this.xmin, cy = this.ymax; break; // bottom
case 0b1001: e0 = 0b0001; continue; // bottom-left
case 0b0001: e0 = 0b0101, cx = this.xmin, cy = this.ymin; break; // left
// TODO Allow containsInfinite instead of contains for clipInfinite?
_edge(points, e0, e1, P) {
while (e0 !== e1) {
let cx, cy;
switch (e0) {
case 0b0101: e0 = 0b0100; continue; // top-left
case 0b0100: e0 = 0b0110, cx = this.xmax, cy = this.ymin; break; // top
case 0b0110: e0 = 0b0010; continue; // top-right
case 0b0010: e0 = 0b1010, cx = this.xmax, cy = this.ymax; break; // right
case 0b1010: e0 = 0b1000; continue; // bottom-right
case 0b1000: e0 = 0b1001, cx = this.xmin, cy = this.ymax; break; // bottom
case 0b1001: e0 = 0b0001; continue; // bottom-left
case 0b0001: e0 = 0b0101, cx = this.xmin, cy = this.ymin; break; // left
}
if (containsFinite(points, cx, cy)) {
P.push(cx, cy);
}
}
if (containsFinite(points, cx, cy)) {
P.push(cx, cy);
}
_project(x0, y0, vx, vy) {
let t = Infinity, c, x, y;
if (vy < 0) { // top
if (y0 <= this.ymin) return;
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;
if ((c = (this.ymax - y0) / vy) < t) y = this.ymax, x = x0 + (t = c) * vx;
}
if (vx > 0) { // right
if (x0 >= this.xmax) return;
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;
if ((c = (this.xmin - x0) / vx) < t) x = this.xmin, y = y0 + (t = c) * vy;
}
return [x, y];
}
}
_project(x0, y0, [vx, vy]) {
let t = Infinity, c, x, y;
if (vy < 0) { // top
if (y0 <= this.ymin) return;
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;
if ((c = (this.ymax - y0) / vy) < t) y = this.ymax, x = x0 + (t = c) * vx;
_edgecode(x, y) {
return (x === this.xmin ? 0b0001
: x === this.xmax ? 0b0010 : 0b0000)
| (y === this.ymin ? 0b0100
: y === this.ymax ? 0b1000 : 0b0000);
}
if (vx > 0) { // right
if (x0 >= this.xmax) return;
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;
if ((c = (this.xmin - x0) / vx) < t) x = this.xmin, y = y0 + (t = c) * vy;
_regioncode(x, y) {
return (x < this.xmin ? 0b0001
: x > this.xmax ? 0b0010 : 0b0000)
| (y < this.ymin ? 0b0100
: y > this.ymax ? 0b1000 : 0b0000);
}
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);
function containsFinite(points, x, y) {
const n = points.length;
let x0, y0, x1 = points[n - 2], y1 = points[n - 1];
for (let i = 0; i < n; i += 2) {
x0 = x1, y0 = y1, x1 = points[i], y1 = points[i + 1];
if ((x1 - x0) * (y - y0) < (y1 - y0) * (x - x0)) {
return false;
}
}
return true;
}
_regioncode(x, y) {
return (x < this.xmin ? 0b0001
: x > this.xmax ? 0b0010 : 0b0000)
| (y < this.ymin ? 0b0100
: y > this.ymax ? 0b1000 : 0b0000);
function containsInfinite(points, vx0, vy0, vxn, vyn, x, y) {
const n = points.length;
let x0, y0, x1 = points[0], y1 = points[1];
if ((x0 + vx0 - x) * (y1 - y) < (y0 + vy0 - y) * (x1 - x)) return false;
for (let i = 2; i < n; i += 2) {
x0 = x1, y0 = y1, x1 = points[i], y1 = points[i + 1];
if ((x0 - x) * (y1 - y) < (y0 - y) * (x1 - x)) return false;
}
if ((x0 - x) * (y1 + vyn - y) < (y0 - y) * (x1 + vxn - x)) return false;
return true;
}
}
class Delaunay {
constructor(points, halfedges, hull, triangles) {
this.points = points;
this.halfedges = halfedges;
this.hull = hull;
this.triangles = triangles;
function pointX(p) {
return p[0];
}
voronoi([xmin, ymin, xmax, ymax] = [0, 0, 960, 500]) {
const {points, halfedges, hull, triangles} = this;
const cells = new Array(points.length / 2);
const circumcenters = new Float64Array(triangles.length / 3 * 2);
const voronoi = new Voronoi(cells, circumcenters, this, xmin, ymin, xmax, ymax);
// Compute cell topology.
for (let i = 0, n = cells.length; i < n; ++i) {
cells[i] = new Cell(voronoi);
function pointY(p) {
return p[1];
}
class Delaunay {
constructor(points) {
const {halfedges, hull, triangles} = new Delaunator(points);
this.points = points;
this.halfedges = halfedges;
this.hull = Uint32Array.from(hullIterable(hull));
this.triangles = triangles;
}
for (let i = 0, m = halfedges.length; i < m; ++i) {
const t = triangles[i]; // Cell vertex.
const T = cells[t].triangles;
if (T.length) continue; // Already connected.
let j = i;
do { // Walk forward.
T.push(Math.floor(j / 3));
j = halfedges[j];
if (j === -1) break; // Went off the convex hull.
j = j % 3 === 2 ? j - 2 : j + 1;
if (triangles[j] !== t) break; // Bad triangulation; break early.
} while (j !== i);
if (j !== i) { // Stopped when walking forward; walk backward.
j = i;
while (true) {
j = halfedges[j % 3 === 0 ? j + 2 : j - 1];
if (j === -1 || triangles[j] !== t) break;
T.unshift(Math.floor(j / 3));
}
} else {
T.push(T[0]); // Close polygon.
voronoi(bounds) {
return new Voronoi(this, bounds);
}
render(context) {
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);
}
for (let i = 0, n = cells.length; i < n; ++i) {
const cell = cells[i];
if (cell.triangles.length === 0) cell.triangles = null;
renderHull(context) {
const {points, hull, triangles} = this;
const n = hull.length;
let i0, i1 = triangles[hull[n - 1]] * 2;
for (let i = 0; i < n; ++i) {
i0 = i1, i1 = triangles[hull[i]] * 2;
context.moveTo(points[i0], points[i0 + 1]);
context.lineTo(points[i1], points[i1 + 1]);
}
}
// Compute circumcenters.
for (let i = 0, j = 0, n = triangles.length; 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 a2 = x1 - x2;
const a3 = x1 - x3;
const b2 = y1 - y2;
const b3 = y1 - y3;
const d1 = x1 * x1 + y1 * y1;
const d2 = d1 - x2 * x2 - y2 * y2;
const d3 = d1 - x3 * x3 - y3 * y3;
const ab = (a3 * b2 - a2 * b3) * 2;
circumcenters[j] = (b2 * d3 - b3 * d2) / ab;
circumcenters[j + 1] = (a3 * d2 - a2 * d3) / ab;
renderTriangle(i, context) {
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();
}
}
// Compute exterior cell rays.
{
let node = hull;
do {
const {x: x1, y: y1, t: i, next: {x: x2, y: y2, t: j}} = node;
const ci = Math.floor(i / 3) * 2;
const cx = circumcenters[ci];
const cy = circumcenters[ci + 1];
const dx = (x1 + x2) / 2 - cx;
const dy = (y1 + y2) / 2 - cy;
const k = (x2 - x1) * (cy - y1) > (y2 - y1) * (cx - x1) ? -1 : 1;
cells[triangles[i]].vn = cells[triangles[j]].v0 = [k * dx, k * dy];
} while ((node = node.next) !== hull);
Delaunay.from = function(points, fx = pointX, fy = pointY, that) {
return new Delaunay("length" in points
? flatArray(points, fx, fy, that)
: Float64Array.from(flatIterable(points, fx, fy, that)));
};
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;
}
return voronoi;
}
render(context) {
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]);
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;
}
this.renderHull(context);
}
renderHull(context) {
const {hull} = this;
function* hullIterable(hull) {
let node = hull;
do {
context.moveTo(node.x, node.y);
context.lineTo(node.next.x, node.next.y);
} while ((node = node.next) !== hull);
do yield node.t;
while ((node = node.next) !== hull);
}
renderTriangle(i, context) {
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();
}
}
Delaunay.from = function(points, fx, fy) {
const {coords, halfedges, hull, triangles} = new delaunator(points, fx, fy);
return new Delaunay(coords, halfedges, hull, triangles);
};
exports.Delaunay = Delaunay;
exports.Voronoi = Voronoi;
exports.Cell = Cell;
exports.Delaunay = Delaunay;
exports.Voronoi = Voronoi;
Object.defineProperty(exports, '__esModule', { value: true });
Object.defineProperty(exports, '__esModule', { value: true });
})));

6

dist/d3-delaunay.min.js

@@ -1,3 +0,3 @@

// https://github.com/d3/d3-delaunay Version 2.0.1. Copyright 2018 Observable, Inc.
// https://github.com/mapbox/delaunator Version 1.0.5. Copyright 2017, Mapbox, Inc.
!function(t,i){"object"==typeof exports&&"undefined"!=typeof module?i(exports):"function"==typeof define&&define.amd?define(["exports"],i):i(t.d3=t.d3||{})}(this,function(t){"use strict";class i{constructor(t){this.voronoi=t,this.triangles=[],this.v0=null,this.vn=null}_points(){const{triangles:t,voronoi:{circumcenters:i}}=this;if(null===t)return null;const e=new Float64Array(2*t.length);for(let n=0,s=t.length;n<s;++n){const s=2*n,h=2*t[n];e[s]=i[h],e[s+1]=i[h+1]}return e}render(t){const{v0:i,vn:e}=this;let n;if(null!==(n=this._points())&&null!==(n=this.voronoi._clip(n,i,e))){t.moveTo(n[0],n[1]);for(let i=2,e=n.length;i<e;i+=2)t.lineTo(n[i],n[i+1]);t.closePath()}}contains(t,i){const s=this._points();return null!==s&&(null===this.v0?e(s,t,i):n(s,this.v0,this.vn,t,i))}}function e(t,i,e){const n=t.length;let s,h,r=t[n-2],l=t[n-1];for(let o=0;o<n;o+=2)if(s=r,h=l,((r=t[o])-s)*(e-h)<((l=t[o+1])-h)*(i-s))return!1;return!0}function n(t,[i,e],[n,s],h,r){const l=t.length;let o,a,c=t[0],f=t[1];if((o+i-h)*(f-r)<(a+e-r)*(c-h))return!1;for(let i=2;i<l;i+=2)if(o=c,a=f,c=t[i],(o-h)*((f=t[i+1])-r)<(a-r)*(c-h))return!1;return!((o-h)*(f+s-r)<(a-r)*(c+n-h))}var s=r,h=r;function r(t,i,e){i||(i=g),e||(e=m);for(var n=1/0,s=1/0,h=-1/0,r=-1/0,d=this.coords=[],y=this.ids=new Uint32Array(t.length),v=0;v<t.length;v++){var _=t[v],p=i(_),w=e(_);y[v]=v,d[2*v]=p,d[2*v+1]=w,p<n&&(n=p),w<s&&(s=w),p>h&&(h=p),w>r&&(r=w)}var T,b,k,M=(n+h)/2,z=(s+r)/2,E=1/0;for(v=0;v<t.length;v++){var A=l(M,z,d[2*v],d[2*v+1]);A<E&&(T=v,E=A)}for(E=1/0,v=0;v<t.length;v++)v!==T&&(A=l(d[2*T],d[2*T+1],d[2*v],d[2*v+1]))<E&&A>0&&(b=v,E=A);var S=1/0;for(v=0;v<t.length;v++)if(v!==T&&v!==b){var j=a(d[2*T],d[2*T+1],d[2*b],d[2*b+1],d[2*v],d[2*v+1]);j<S&&(k=v,S=j)}if(S===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(o(d[2*T],d[2*T+1],d[2*b],d[2*b+1],d[2*k],d[2*k+1])<0){var F=b;b=k,k=F}var I=d[2*T],L=d[2*T+1],K=d[2*b],P=d[2*b+1],D=d[2*k],H=d[2*k+1],U=function(t,i,e,n,s,h){var r=(e-=t)*e+(n-=i)*n,l=(s-=t)*s+(h-=i)*h,o=e*h-n*s;return{x:t+.5*(h*r-n*l)/o,y:i+.5*(e*l-s*r)/o}}(I,L,K,P,D,H);for(this._cx=U.x,this._cy=U.y,function t(i,e,n,s,h,r){var l,o,a;if(s-n<=20)for(l=n+1;l<=s;l++){for(a=i[l],o=l-1;o>=n&&u(e,i[o],a,h,r)>0;)i[o+1]=i[o--];i[o+1]=a}else{var c=n+s>>1;for(o=s,x(i,c,l=n+1),u(e,i[n],i[s],h,r)>0&&x(i,n,s),u(e,i[l],i[s],h,r)>0&&x(i,l,s),u(e,i[n],i[l],h,r)>0&&x(i,n,l),a=i[l];;){do{l++}while(u(e,i[l],a,h,r)<0);do{o--}while(u(e,i[o],a,h,r)>0);if(o<l)break;x(i,l,o)}i[n+1]=i[o],i[o]=a,s-l+1>=o-n?(t(i,e,l,s,h,r),t(i,e,n,o-1,h,r)):(t(i,e,n,o-1,h,r),t(i,e,l,s,h,r))}}(y,d,0,y.length-1,U.x,U.y),this._hashSize=Math.ceil(Math.sqrt(t.length)),this._hash=[],v=0;v<this._hashSize;v++)this._hash[v]=null;var q=this.hull=c(d,T);this._hashEdge(q),q.t=0,q=c(d,b,q),this._hashEdge(q),q.t=1,q=c(d,k,q),this._hashEdge(q),q.t=2;var B,C,N=2*t.length-5,O=this.triangles=new Uint32Array(3*N),V=this.halfedges=new Int32Array(3*N);this.trianglesLen=0,this._addTriangle(T,b,k,-1,-1,-1);for(var G=0;G<y.length;G++)if(p=d[2*(v=y[G])],w=d[2*v+1],!(p===B&&w===C||(B=p,C=w,p===I&&w===L||p===K&&w===P||p===D&&w===H))){var J,Q=this._hashKey(p,w),R=Q;do{J=this._hash[R],R=(R+1)%this._hashSize}while((!J||J.removed)&&R!==Q);for(q=J;o(p,w,q.x,q.y,q.next.x,q.next.y)>=0;)if((q=q.next)===J)throw new Error("Something is wrong with the input points.");var W=q===J,X=this._addTriangle(q.i,v,q.next.i,-1,-1,q.t);q.t=X,(q=c(d,v,q)).t=this._legalize(X+2),q.prev.prev.t===V[X+1]&&(q.prev.prev.t=X+2);for(var Y=q.next;o(p,w,Y.x,Y.y,Y.next.x,Y.next.y)<0;)X=this._addTriangle(Y.i,v,Y.next.i,Y.prev.t,-1,Y.t),Y.prev.t=this._legalize(X+2),this.hull=f(Y),Y=Y.next;if(W)for(Y=q.prev;o(p,w,Y.prev.x,Y.prev.y,Y.x,Y.y)<0;)X=this._addTriangle(Y.prev.i,v,Y.i,-1,Y.t,Y.prev.t),this._legalize(X+2),Y.prev.t=X,this.hull=f(Y),Y=Y.prev;this._hashEdge(q),this._hashEdge(q.prev)}this.triangles=O.subarray(0,this.trianglesLen),this.halfedges=V.subarray(0,this.trianglesLen)}function l(t,i,e,n){var s=t-e,h=i-n;return s*s+h*h}function o(t,i,e,n,s,h){return(n-i)*(s-e)-(e-t)*(h-n)}function a(t,i,e,n,s,h){var r=(e-=t)*e+(n-=i)*n,l=(s-=t)*s+(h-=i)*h;if(0===r||0===l)return 1/0;var o=e*h-n*s;if(0===o)return 1/0;var a=.5*(h*r-n*l)/o,c=.5*(e*l-s*r)/o;return a*a+c*c}function c(t,i,e){var n={i:i,x:t[2*i],y:t[2*i+1],t:0,prev:null,next:null,removed:!1};return e?(n.next=e.next,n.prev=e,e.next.prev=n,e.next=n):(n.prev=n,n.next=n),n}function f(t){return t.prev.next=t.next,t.next.prev=t.prev,t.removed=!0,t.prev}function u(t,i,e,n,s){return l(t[2*i],t[2*i+1],n,s)-l(t[2*e],t[2*e+1],n,s)||t[2*i]-t[2*e]||t[2*i+1]-t[2*e+1]}function x(t,i,e){var n=t[i];t[i]=t[e],t[e]=n}function g(t){return t[0]}function m(t){return t[1]}r.prototype={_hashEdge:function(t){this._hash[this._hashKey(t.x,t.y)]=t},_hashKey:function(t,i){var e=t-this._cx,n=i-this._cy,s=1-e/(Math.abs(e)+Math.abs(n));return Math.floor((2+(n<0?-s:s))/4*this._hashSize)},_legalize:function(t){var i,e,n,s,h,r,l,o,a,c,f=this.triangles,u=this.coords,x=this.halfedges,g=x[t],m=t-t%3,d=g-g%3,y=m+(t+1)%3,v=m+(t+2)%3,_=d+(g+2)%3,p=f[v],w=f[t],T=f[y],b=f[_];if(i=u[2*p],e=u[2*p+1],n=u[2*w],s=u[2*w+1],h=u[2*T],r=u[2*T+1],l=u[2*b],o=u[2*b+1],a=(n-=l)*n+(s-=o)*s,c=(h-=l)*h+(r-=o)*r,(i-=l)*(s*c-a*r)-(e-=o)*(n*c-a*h)+(i*i+e*e)*(n*r-s*h)<0){f[t]=b,f[g]=p,this._link(t,x[_]),this._link(g,x[v]),this._link(v,_);var k=d+(g+1)%3;return this._legalize(t),this._legalize(k)}return v},_link:function(t,i){this.halfedges[t]=i,-1!==i&&(this.halfedges[i]=t)},_addTriangle:function(t,i,e,n,s,h){var r=this.trianglesLen;return this.triangles[r]=t,this.triangles[r+1]=i,this.triangles[r+2]=e,this._link(r,n),this._link(r+1,s),this._link(r+2,h),this.trianglesLen+=3,r}},s.default=h;class d{constructor(t,i,e,n,s,h,r){if(!((h=+h)>=(n=+n)&&(r=+r)>=(s=+s)))throw new Error("invalid bounds");this.cells=t,this.circumcenters=i,this.delaunay=e,this.xmax=h,this.xmin=n,this.ymax=r,this.ymin=s}find(t,i){return this.cells[this.findIndex(t,i)]}findIndex(t,i){const{cells:e,delaunay:{halfedges:n,points:s,triangles:h}}=this;if(0===e.length||(t=+t)!=t||(i=+i)!=i)return-1;let r=0,l=(t-s[0])**2+(i-s[1])**2;for(;;){let n=r,o=l;for(let l=e[r].triangles,a=0,c=l.length;a<c;++a){let e=3*l[a];switch(r){case h[e]:e=h[e+1];break;case h[e+1]:e=h[e+2];break;case h[e+2]:e=h[e]}let c=(t-s[2*e])**2+(i-s[2*e+1])**2;c<o&&(o=c,n=e)}if(n===r)return n;r=n,l=o}}render(t){const{cells:i,circumcenters:e,delaunay:{halfedges:n,hull:s}}=this;for(let i=0,s=n.length;i<s;++i){const s=n[i];if(s<i)continue;const h=2*Math.floor(i/3),r=2*Math.floor(s/3);t.moveTo(e[h],e[h+1]),t.lineTo(e[r],e[r+1])}let h=s;do{const n=2*Math.floor(h.t/3),s=e[n],r=e[n+1],l=this._project(s,r,i[h.i].vn);l&&(t.moveTo(s,r),t.lineTo(l[0],l[1]))}while((h=h.next)!==s)}renderBounds(t){t.rect(this.xmin,this.ymin,this.xmax-this.xmin,this.ymax-this.ymin)}_clip(t,i,e){return i?this._clipInfinite(t,i,e):this._clipFinite(t)}_clipFinite(t){const i=t.length;let n,s,h,r,l,o,a=null,c=t[i-2],f=t[i-1],u=this._regioncode(c,f);for(let e=0;e<i;e+=2)if(s=c,h=f,c=t[e],f=t[e+1],r=u,u=this._regioncode(c,f),0===r&&0===u)l=o,o=0,a?a.push(c,f):a=[c,f];else if(n=this._clipSegment(s,h,c,f,r,u)){const[i,e,s,h]=n;r&&(l=o,o=this._edgecode(i,e),l&&o&&this._edge(t,l,o,a),a?a.push(i,e):a=[i,e]),l=o,o=this._edgecode(s,h),l&&o&&this._edge(t,l,o,a),a?a.push(s,h):a=[s,h]}if(a)l=o,o=this._edgecode(a[0],a[1]),l&&o&&this._edge(t,l,o,a);else if(e(t,(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 a}_clipSegment(t,i,e,n,s,h){for(;;){if(0===s&&0===h)return[t,i,e,n];if(s&h)return;let r,l,o=s||h;8&o?(r=t+(e-t)*(this.ymax-i)/(n-i),l=this.ymax,o^=8):4&o?(r=t+(e-t)*(this.ymin-i)/(n-i),l=this.ymin,o^=4):2&o?(l=i+(n-i)*(this.xmax-t)/(e-t),r=this.xmax,o^=2):(l=i+(n-i)*(this.xmin-t)/(e-t),r=this.xmin,o^=1),s?(t=r,i=l,s=o):(e=r,n=l,h=o)}}_clipInfinite(t,i,e){let s,h=Array.from(t);if((s=this._project(h[0],h[1],i))&&h.unshift(s[0],s[1]),(s=this._project(h[h.length-2],h[h.length-1],e))&&h.unshift(s[0],s[1]),h=this._clipFinite(h)){for(let s,r=0,l=h.length,o=this._edgecode(h[l-2],h[l-1]);r<l;r+=2)if(s=o,o=this._edgecode(h[r],h[r+1]),s&&o)for(;s!==o;){let o,a;switch(s){case 5:s=4;continue;case 4:s=6,o=this.xmax,a=this.ymin;break;case 6:s=2;continue;case 2:s=10,o=this.xmax,a=this.ymax;break;case 10:s=8;continue;case 8:s=9,o=this.xmin,a=this.ymax;break;case 9:s=1;continue;case 1:s=5,o=this.xmin,a=this.ymin}n(t,i,e,o,a)&&(h.splice(r,0,o,a),l+=2,r+=2)}}else n(t,i,e,(this.xmin+this.xmax)/2,(this.ymin+this.ymax)/2)&&h.push(this.xmin,this.ymin,this.xmax,this.ymin,this.xmax,this.ymax,this.xmin,this.ymax);return h}_edge(t,i,n,s){for(;i!==n;){let n,h;switch(i){case 5:i=4;continue;case 4:i=6,n=this.xmax,h=this.ymin;break;case 6:i=2;continue;case 2:i=10,n=this.xmax,h=this.ymax;break;case 10:i=8;continue;case 8:i=9,n=this.xmin,h=this.ymax;break;case 9:i=1;continue;case 1:i=5,n=this.xmin,h=this.ymin}e(t,n,h)&&s.push(n,h)}}_project(t,i,[e,n]){let s,h,r,l=1/0;if(n<0){if(i<=this.ymin)return;(s=(this.ymin-i)/n)<l&&(r=this.ymin,h=t+(l=s)*e)}else if(n>0){if(i>=this.ymax)return;(s=(this.ymax-i)/n)<l&&(r=this.ymax,h=t+(l=s)*e)}if(e>0){if(t>=this.xmax)return;(s=(this.xmax-t)/e)<l&&(h=this.xmax,r=i+(l=s)*n)}else if(e<0){if(t<=this.xmin)return;(s=(this.xmin-t)/e)<l&&(h=this.xmin,r=i+(l=s)*n)}return[h,r]}_edgecode(t,i){return(t===this.xmin?1:t===this.xmax?2:0)|(i===this.ymin?4:i===this.ymax?8:0)}_regioncode(t,i){return(t<this.xmin?1:t>this.xmax?2:0)|(i<this.ymin?4:i>this.ymax?8:0)}}class y{constructor(t,i,e,n){this.points=t,this.halfedges=i,this.hull=e,this.triangles=n}voronoi([t,e,n,s]=[0,0,960,500]){const{points:h,halfedges:r,hull:l,triangles:o}=this,a=new Array(h.length/2),c=new Float64Array(o.length/3*2),f=new d(a,c,this,t,e,n,s);for(let t=0,e=a.length;t<e;++t)a[t]=new i(f);for(let t=0,i=r.length;t<i;++t){const i=o[t],e=a[i].triangles;if(e.length)continue;let n=t;do{if(e.push(Math.floor(n/3)),-1===(n=r[n]))break;if(o[n=n%3==2?n-2:n+1]!==i)break}while(n!==t);if(n!==t)for(n=t;-1!==(n=r[n%3==0?n+2:n-1])&&o[n]===i;)e.unshift(Math.floor(n/3));else e.push(e[0])}for(let t=0,i=a.length;t<i;++t){const i=a[t];0===i.triangles.length&&(i.triangles=null)}for(let t=0,i=0,e=o.length;t<e;t+=3,i+=2){const e=2*o[t],n=2*o[t+1],s=2*o[t+2],r=h[e],l=h[e+1],a=h[n],f=h[n+1],u=h[s],x=h[s+1],g=r-a,m=r-u,d=l-f,y=l-x,v=r*r+l*l,_=v-a*a-f*f,p=v-u*u-x*x,w=2*(m*d-g*y);c[i]=(d*p-y*_)/w,c[i+1]=(m*_-g*p)/w}{let t=l;do{const{x:i,y:e,t:n,next:{x:s,y:h,t:r}}=t,l=2*Math.floor(n/3),f=c[l],u=c[l+1],x=(i+s)/2-f,g=(e+h)/2-u,m=(s-i)*(u-e)>(h-e)*(f-i)?-1:1;a[o[n]].vn=a[o[r]].v0=[m*x,m*g]}while((t=t.next)!==l)}return f}render(t){const{points:i,halfedges:e,triangles:n}=this;for(let s=0,h=e.length;s<h;++s){const h=e[s];if(h<s)continue;const r=2*n[s],l=2*n[h];t.moveTo(i[r],i[r+1]),t.lineTo(i[l],i[l+1])}this.renderHull(t)}renderHull(t){const{hull:i}=this;let e=i;do{t.moveTo(e.x,e.y),t.lineTo(e.next.x,e.next.y)}while((e=e.next)!==i)}renderTriangle(t,i){const{points:e,triangles:n}=this,s=2*n[t*=3],h=2*n[t+1],r=2*n[t+2];i.moveTo(e[s],e[s+1]),i.lineTo(e[h],e[h+1]),i.lineTo(e[r],e[r+1]),i.closePath()}}y.from=function(t,i,e){const{coords:n,halfedges:h,hull:r,triangles:l}=new s(t,i,e);return new y(n,h,r,l)},t.Cell=i,t.Delaunay=y,t.Voronoi=d,Object.defineProperty(t,"__esModule",{value:!0})});
// https://github.com/d3/d3-delaunay Version 3.0.0-alpha.1. Copyright 2018 Observable, Inc.
// https://github.com/mapbox/delaunator Version 2.0.0. Copyright 2017, Mapbox, Inc.
!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?e(exports):"function"==typeof define&&define.amd?define(["exports"],e):e(t.d3=t.d3||{})}(this,function(t){"use strict";function e(t){if(!ArrayBuffer.isView(t))throw new Error("Expected coords to be a typed array.");var e=1/0,l=1/0,c=-1/0,f=-1/0,u=t.length>>1,x=this.ids=new Uint32Array(u);this.coords=t;for(var m=0;m<u;m++){var d=t[2*m],g=t[2*m+1];d<e&&(e=d),g<l&&(l=g),d>c&&(c=d),g>f&&(f=g),x[m]=m}var y,v,_,p=(e+c)/2,w=(l+f)/2,b=1/0;for(m=0;m<u;m++){var k=i(p,w,t[2*m],t[2*m+1]);k<b&&(y=m,b=k)}for(b=1/0,m=0;m<u;m++)m!==y&&(k=i(t[2*y],t[2*y+1],t[2*m],t[2*m+1]))<b&&k>0&&(v=m,b=k);var T=1/0;for(m=0;m<u;m++)if(m!==y&&m!==v){var A=s(t[2*y],t[2*y+1],t[2*v],t[2*v+1],t[2*m],t[2*m+1]);A<T&&(_=m,T=A)}if(T===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(n(t[2*y],t[2*y+1],t[2*v],t[2*v+1],t[2*_],t[2*_+1])<0){var E=v;v=_,_=E}var M=t[2*y],z=t[2*y+1],F=t[2*v],S=t[2*v+1],j=t[2*_],L=t[2*_+1],U=function(t,e,i,n,s,r){var h=(i-=t)*i+(n-=e)*n,a=(s-=t)*s+(r-=e)*r,o=i*r-n*s;return{x:t+.5*(r*h-n*a)/o,y:e+.5*(i*a-s*h)/o}}(M,z,F,S,j,L);for(this._cx=U.x,this._cy=U.y,function t(e,i,n,s,r,h){var l,c,f;if(s-n<=20)for(l=n+1;l<=s;l++){for(f=e[l],c=l-1;c>=n&&a(i,e[c],f,r,h)>0;)e[c+1]=e[c--];e[c+1]=f}else{var u=n+s>>1;for(c=s,o(e,u,l=n+1),a(i,e[n],e[s],r,h)>0&&o(e,n,s),a(i,e[l],e[s],r,h)>0&&o(e,l,s),a(i,e[n],e[l],r,h)>0&&o(e,n,l),f=e[l];;){do{l++}while(a(i,e[l],f,r,h)<0);do{c--}while(a(i,e[c],f,r,h)>0);if(c<l)break;o(e,l,c)}e[n+1]=e[c],e[c]=f,s-l+1>=c-n?(t(e,i,l,s,r,h),t(e,i,n,c-1,r,h)):(t(e,i,n,c-1,r,h),t(e,i,l,s,r,h))}}(x,t,0,x.length-1,U.x,U.y),this._hashSize=Math.ceil(Math.sqrt(u)),this._hash=[],m=0;m<this._hashSize;m++)this._hash[m]=null;var I=this.hull=r(t,y);this._hashEdge(I),I.t=0,I=r(t,v,I),this._hashEdge(I),I.t=1,I=r(t,_,I),this._hashEdge(I),I.t=2;var K,P,B=2*u-5,D=this.triangles=new Uint32Array(3*B),H=this.halfedges=new Int32Array(3*B);this.trianglesLen=0,this._addTriangle(y,v,_,-1,-1,-1);for(var V=0;V<x.length;V++)if(d=t[2*(m=x[V])],g=t[2*m+1],!(d===K&&g===P||(K=d,P=g,d===M&&g===z||d===F&&g===S||d===j&&g===L))){var q,C=this._hashKey(d,g),N=C;do{q=this._hash[N],N=(N+1)%this._hashSize}while((!q||q.removed)&&N!==C);for(I=q;n(d,g,I.x,I.y,I.next.x,I.next.y)>=0;)if((I=I.next)===q)throw new Error("Something is wrong with the input points.");var O=I===q,G=this._addTriangle(I.i,m,I.next.i,-1,-1,I.t);I.t=G,(I=r(t,m,I)).t=this._legalize(G+2),I.prev.prev.t===H[G+1]&&(I.prev.prev.t=G+2);for(var J=I.next;n(d,g,J.x,J.y,J.next.x,J.next.y)<0;)G=this._addTriangle(J.i,m,J.next.i,J.prev.t,-1,J.t),J.prev.t=this._legalize(G+2),this.hull=h(J),J=J.next;if(O)for(J=I.prev;n(d,g,J.prev.x,J.prev.y,J.x,J.y)<0;)G=this._addTriangle(J.prev.i,m,J.i,-1,J.t,J.prev.t),this._legalize(G+2),J.prev.t=G,this.hull=h(J),J=J.prev;this._hashEdge(I),this._hashEdge(I.prev)}this.triangles=D.subarray(0,this.trianglesLen),this.halfedges=H.subarray(0,this.trianglesLen)}function i(t,e,i,n){var s=t-i,r=e-n;return s*s+r*r}function n(t,e,i,n,s,r){return(n-e)*(s-i)-(i-t)*(r-n)}function s(t,e,i,n,s,r){var h=(i-=t)*i+(n-=e)*n,a=(s-=t)*s+(r-=e)*r;if(0===h||0===a)return 1/0;var o=i*r-n*s;if(0===o)return 1/0;var l=.5*(r*h-n*a)/o,c=.5*(i*a-s*h)/o;return l*l+c*c}function r(t,e,i){var n={i:e,x:t[2*e],y:t[2*e+1],t:0,prev:null,next:null,removed:!1};return i?(n.next=i.next,n.prev=i,i.next.prev=n,i.next=n):(n.prev=n,n.next=n),n}function h(t){return t.prev.next=t.next,t.next.prev=t.prev,t.removed=!0,t.prev}function a(t,e,n,s,r){return i(t[2*e],t[2*e+1],s,r)-i(t[2*n],t[2*n+1],s,r)||t[2*e]-t[2*n]||t[2*e+1]-t[2*n+1]}function o(t,e,i){var n=t[e];t[e]=t[i],t[i]=n}function l(t){return t[0]}function c(t){return t[1]}e.from=function(t,i,n){i||(i=l),n||(n=c);for(var s=t.length,r=new Float64Array(2*s),h=0;h<s;h++){var a=t[h];r[2*h]=i(a),r[2*h+1]=n(a)}return new e(r)},e.prototype={_hashEdge:function(t){this._hash[this._hashKey(t.x,t.y)]=t},_hashKey:function(t,e){var i=t-this._cx,n=e-this._cy,s=1-i/(Math.abs(i)+Math.abs(n));return Math.floor((2+(n<0?-s:s))/4*this._hashSize)},_legalize:function(t){var e,i,n,s,r,h,a,o,l,c,f=this.triangles,u=this.coords,x=this.halfedges,m=x[t],d=t-t%3,g=m-m%3,y=d+(t+1)%3,v=d+(t+2)%3,_=g+(m+2)%3,p=f[v],w=f[t],b=f[y],k=f[_];if(e=u[2*p],i=u[2*p+1],n=u[2*w],s=u[2*w+1],r=u[2*b],h=u[2*b+1],a=u[2*k],o=u[2*k+1],l=(n-=a)*n+(s-=o)*s,c=(r-=a)*r+(h-=o)*h,(e-=a)*(s*c-l*h)-(i-=o)*(n*c-l*r)+(e*e+i*i)*(n*h-s*r)<0){f[t]=k,f[m]=p,this._link(t,x[_]),this._link(m,x[v]),this._link(v,_);var T=g+(m+1)%3;return this._legalize(t),this._legalize(T)}return v},_link:function(t,e){this.halfedges[t]=e,-1!==e&&(this.halfedges[e]=t)},_addTriangle:function(t,e,i,n,s,r){var h=this.trianglesLen;return this.triangles[h]=t,this.triangles[h+1]=e,this.triangles[h+2]=i,this._link(h,n),this._link(h+1,s),this._link(h+2,r),this.trianglesLen+=3,h}};class f{constructor(t,[e,i,n,s]=[0,0,960,500]){if(!((n=+n)>=(e=+e)&&(s=+s)>=(i=+i)))throw new Error("invalid bounds");const{points:r,halfedges:h,hull:a,triangles:o}=this.delaunay=t,l=this.circumcenters=new Float64Array(o.length/3*2),c=this.edges=new Uint32Array(h.length),f=this.index=new Uint32Array(r.length),u=this.vectors=new Float64Array(2*r.length);this.xmax=n,this.xmin=e,this.ymax=s,this.ymin=i;for(let t=0,e=0,i=h.length;t<i;++t){const i=o[t];if(f[2*i]!==f[2*i+1])continue;const n=f[2*i]=e;let s=t;do{if(c[e++]=Math.floor(s/3),-1===(s=h[s]))break;if(o[s=s%3==2?s-2:s+1]!==i)break}while(s!==t);if(s!==t){const r=e;for(s=t;-1!==(s=h[s%3==0?s+2:s-1])&&o[s]===i;)c[e++]=Math.floor(s/3);r<e&&(c.subarray(n,r).reverse(),c.subarray(n,e).reverse())}f[2*i+1]=e}for(let t=0,e=0,i=o.length;t<i;t+=3,e+=2){const i=2*o[t],n=2*o[t+1],s=2*o[t+2],h=r[i],a=r[i+1],c=r[n],f=r[n+1],u=r[s],x=r[s+1],m=h-c,d=h-u,g=a-f,y=a-x,v=h*h+a*a,_=v-c*c-f*f,p=v-u*u-x*x,w=2*(d*g-m*y);l[e]=(g*p-y*_)/w,l[e+1]=(d*_-m*p)/w}for(let t,e,i,n=a.length,s=2*o[a[n-1]],h=r[s],l=r[s+1],c=0;c<n;++c)t=s,e=h,i=l,h=r[s=2*o[a[c]]],l=r[s+1],u[2*t+2]=u[2*s]=i-l,u[2*t+3]=u[2*s+1]=h-e}render(t){const{delaunay:{halfedges:e,hull:i,triangles:n},circumcenters:s,vectors:r}=this;for(let i=0,n=e.length;i<n;++i){const n=e[i];if(n<i)continue;const r=2*Math.floor(i/3),h=2*Math.floor(n/3);t.moveTo(s[r],s[r+1]),t.lineTo(s[h],s[h+1])}for(let e=0,h=i.length;e<h;++e){const h=2*Math.floor(i[e]/3),a=s[h],o=s[h+1],l=4*n[i[e]],c=this._project(a,o,r[l+2],r[l+3]);c&&(t.moveTo(a,o),t.lineTo(c[0],c[1]))}}renderBounds(t){t.rect(this.xmin,this.ymin,this.xmax-this.xmin,this.ymax-this.ymin)}renderCell(t,e){const i=this._clip(t);if(null!==i){e.moveTo(i[0],i[1]);for(let t=2,n=i.length;t<n;t+=2)e.lineTo(i[t],i[t+1]);e.closePath()}}contains(t,e,i){const{vectors:n}=this,s=this._cell(t),r=4*t;return null!==s&&(n[r]||n[r+1]?x(s,n[r],n[r+1],n[r+2],n[r+3],e,i):u(s,e,i))}find(t,e,i=0){const{delaunay:{halfedges:n,points:s,triangles:r},edges:h,index:a}=this;if(0===s.length||(t=+t)!=t||(e=+e)!=e)return-1;let o=(t-s[2*i])**2+(e-s[2*i+1])**2;for(;;){const n=a[2*i],l=a[2*i+1];let c=i,f=o,u=3*h[n];switch(i){case r[u]:u=r[u+2];break;case r[u+1]:u=r[u];break;case r[u+2]:u=r[u+1]}let x=(t-s[2*u])**2+(e-s[2*u+1])**2;x<f&&(f=x,c=u);for(let a=n;a<l;++a){switch(u=3*h[a],i){case r[u]:u=r[u+1];break;case r[u+1]:u=r[u+2];break;case r[u+2]:u=r[u]}(x=(t-s[2*u])**2+(e-s[2*u+1])**2)<f&&(f=x,c=u)}if(c===i)return c;i=c,o=f}}_cell(t){const{index:e,edges:i,circumcenters:n}=this,s=e[2*t],r=e[2*t+1];if(s===r)return null;const h=new Float64Array(2*(r-s));for(let t=s,e=0;t<r;++t,e+=2){const s=2*i[t];h[e]=n[s],h[e+1]=n[s+1]}return h}_clip(t){const e=this._cell(t);if(null===e)return null;const{vectors:i}=this,n=4*t;return i[n]||i[n+1]?this._clipInfinite(e,i[n],i[n+1],i[n+2],i[n+3]):this._clipFinite(e)}_clipFinite(t){const e=t.length;let i,n,s,r,h,a,o=null,l=t[e-2],c=t[e-1],f=this._regioncode(l,c);for(let u=0;u<e;u+=2)if(n=l,s=c,l=t[u],c=t[u+1],r=f,f=this._regioncode(l,c),0===r&&0===f)h=a,a=0,o?o.push(l,c):o=[l,c];else if(i=this._clipSegment(n,s,l,c,r,f)){const[e,n,s,l]=i;r&&(h=a,a=this._edgecode(e,n),h&&a&&this._edge(t,h,a,o),o?o.push(e,n):o=[e,n]),h=a,a=this._edgecode(s,l),h&&a&&this._edge(t,h,a,o),o?o.push(s,l):o=[s,l]}if(o)h=a,a=this._edgecode(o[0],o[1]),h&&a&&this._edge(t,h,a,o);else if(u(t,(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 o}_clipSegment(t,e,i,n,s,r){for(;;){if(0===s&&0===r)return[t,e,i,n];if(s&r)return;let h,a,o=s||r;8&o?(h=t+(i-t)*(this.ymax-e)/(n-e),a=this.ymax,o^=8):4&o?(h=t+(i-t)*(this.ymin-e)/(n-e),a=this.ymin,o^=4):2&o?(a=e+(n-e)*(this.xmax-t)/(i-t),h=this.xmax,o^=2):(a=e+(n-e)*(this.xmin-t)/(i-t),h=this.xmin,o^=1),s?(t=h,e=a,s=o):(i=h,n=a,r=o)}}_clipInfinite(t,e,i,n,s){let r,h=Array.from(t);if((r=this._project(h[0],h[1],e,i))&&h.unshift(r[0],r[1]),(r=this._project(h[h.length-2],h[h.length-1],n,s))&&h.unshift(r[0],r[1]),h=this._clipFinite(h)){for(let r,a=0,o=h.length,l=this._edgecode(h[o-2],h[o-1]);a<o;a+=2)if(r=l,l=this._edgecode(h[a],h[a+1]),r&&l)for(;r!==l;){let l,c;switch(r){case 5:r=4;continue;case 4:r=6,l=this.xmax,c=this.ymin;break;case 6:r=2;continue;case 2:r=10,l=this.xmax,c=this.ymax;break;case 10:r=8;continue;case 8:r=9,l=this.xmin,c=this.ymax;break;case 9:r=1;continue;case 1:r=5,l=this.xmin,c=this.ymin}x(t,e,i,n,s,l,c)&&(h.splice(a,0,l,c),o+=2,a+=2)}}else x(t,e,i,n,s,(this.xmin+this.xmax)/2,(this.ymin+this.ymax)/2)&&h.push(this.xmin,this.ymin,this.xmax,this.ymin,this.xmax,this.ymax,this.xmin,this.ymax);return h}_edge(t,e,i,n){for(;e!==i;){let i,s;switch(e){case 5:e=4;continue;case 4:e=6,i=this.xmax,s=this.ymin;break;case 6:e=2;continue;case 2:e=10,i=this.xmax,s=this.ymax;break;case 10:e=8;continue;case 8:e=9,i=this.xmin,s=this.ymax;break;case 9:e=1;continue;case 1:e=5,i=this.xmin,s=this.ymin}u(t,i,s)&&n.push(i,s)}}_project(t,e,i,n){let s,r,h,a=1/0;if(n<0){if(e<=this.ymin)return;(s=(this.ymin-e)/n)<a&&(h=this.ymin,r=t+(a=s)*i)}else if(n>0){if(e>=this.ymax)return;(s=(this.ymax-e)/n)<a&&(h=this.ymax,r=t+(a=s)*i)}if(i>0){if(t>=this.xmax)return;(s=(this.xmax-t)/i)<a&&(r=this.xmax,h=e+(a=s)*n)}else if(i<0){if(t<=this.xmin)return;(s=(this.xmin-t)/i)<a&&(r=this.xmin,h=e+(a=s)*n)}return[r,h]}_edgecode(t,e){return(t===this.xmin?1:t===this.xmax?2:0)|(e===this.ymin?4:e===this.ymax?8:0)}_regioncode(t,e){return(t<this.xmin?1:t>this.xmax?2:0)|(e<this.ymin?4:e>this.ymax?8:0)}}function u(t,e,i){const n=t.length;let s,r,h=t[n-2],a=t[n-1];for(let o=0;o<n;o+=2)if(s=h,r=a,((h=t[o])-s)*(i-r)<((a=t[o+1])-r)*(e-s))return!1;return!0}function x(t,e,i,n,s,r,h){const a=t.length;let o,l,c=t[0],f=t[1];if((o+e-r)*(f-h)<(l+i-h)*(c-r))return!1;for(let e=2;e<a;e+=2)if(o=c,l=f,c=t[e],(o-r)*((f=t[e+1])-h)<(l-h)*(c-r))return!1;return!((o-r)*(f+s-h)<(l-h)*(c+n-r))}class m{constructor(t){const{halfedges:i,hull:n,triangles:s}=new e(t);this.points=t,this.halfedges=i,this.hull=Uint32Array.from(function*(t){let e=t;do{yield e.t}while((e=e.next)!==t)}(n)),this.triangles=s}voronoi(t){return new f(this,t)}render(t){const{points:e,halfedges:i,triangles:n}=this;for(let s=0,r=i.length;s<r;++s){const r=i[s];if(r<s)continue;const h=2*n[s],a=2*n[r];t.moveTo(e[h],e[h+1]),t.lineTo(e[a],e[a+1])}this.renderHull(t)}renderHull(t){const{points:e,hull:i,triangles:n}=this,s=i.length;let r,h=2*n[i[s-1]];for(let a=0;a<s;++a)r=h,h=2*n[i[a]],t.moveTo(e[r],e[r+1]),t.lineTo(e[h],e[h+1])}renderTriangle(t,e){const{points:i,triangles:n}=this,s=2*n[t*=3],r=2*n[t+1],h=2*n[t+2];e.moveTo(i[s],i[s+1]),e.lineTo(i[r],i[r+1]),e.lineTo(i[h],i[h+1]),e.closePath()}}m.from=function(t,e=function(t){return t[0]},i=function(t){return t[1]},n){return new m("length"in t?function(t,e,i,n){const s=t.length,r=new Float64Array(2*s);for(let h=0;h<s;++h){const s=t[h];r[2*h]=e.call(n,s,h,t),r[2*h+1]=i.call(n,s,h,t)}return r}(t,e,i,n):Float64Array.from(function*(t,e,i,n){let s=0;for(const r of t)yield e.call(n,r,s,t),yield i.call(n,r,s,t),++s}(t,e,i,n)))},t.Delaunay=m,t.Voronoi=f,Object.defineProperty(t,"__esModule",{value:!0})});

18

package.json
{
"name": "d3-delaunay",
"version": "2.0.1",
"version": "3.0.0-alpha.1",
"publishConfig": {
"tag": "next"
},
"description": "Compute the Voronoi diagram of a set of two-dimensional points.",

@@ -17,11 +20,18 @@ "keywords": [

},
"contributors": [
{
"name": "Vladimir Agafonkin",
"url": "http://agafonkin.com/en/"
}
],
"main": "dist/d3-delaunay.js",
"unpkg": "dist/d3-delaunay.min.js",
"module": "src/index.js",
"dependencies": {
"delaunator": "^2.0.0"
},
"devDependencies": {
"@observablehq/tape": "~0.0.1",
"esm": "^3.0.7",
"delaunator": "^1.0.5",
"rollup": "^0.57.1",
"rollup-plugin-commonjs": "^9.1.0",
"rollup-plugin-node-resolve": "^3.3.0",

@@ -34,5 +44,5 @@ "rollup-plugin-uglify": "^3.0.0",

"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 test && yarn build",
"prepublishOnly": "yarn build && yarn test",
"test": "tape -r esm 'test/**/*-test.js'"
}
}

105

README.md

@@ -26,7 +26,15 @@ # d3-delaunay

<a href="#delaunay_from" name="delaunay_from">#</a> Delaunay.<b>from</b>(<i>points</i>[, <i>fx</i>[, <i>fy</i>]]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js "Source")
<a href="#new_Delaunay" name="new_Delaunay">#</a> new <b>Delaunay</b>(<i>points</i>) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js "Source")
Returns the Delaunay triangulation for the given array 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.
Returns the Delaunay triangulation for the given flat array [*x0*, *y0*, *x1*, *y1*, …] of *points*.
```js
const delaunay = new Delaunay(Float64Array.of(0, 0, 0, 1, 1, 0, 1, 1));
```
<a href="#delaunay_from" name="delaunay_from">#</a> Delaunay.<b>from</b>(<i>points</i>[, <i>fx</i>[, <i>fy</i>[, <i>that</i>]]]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js "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*], …]. 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.)
```js
const delaunay = Delaunay.from([[0, 0], [0, 1], [1, 0], [1, 1]]);

@@ -37,3 +45,3 @@ ```

The coordinates of the points as an array [*x0*, *y0*, *x1*, *y1*, …].
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](#new_Delaunay).

@@ -60,11 +68,13 @@ <a href="#delaunay_halfedges" name="delaunay_halfedges">#</a> <i>delaunay</i>.<b>halfedges</b>

An arbitrary starting [node](#node) of the Delaunay triangulation’s convex hull. For example, to render the exterior edges of the Delaunay triangulation:
The convex hull as an a Uint32Array [*i0*, *i1*, …] of triangle vertex indexes. For example, to render the exterior edges of the Delaunay triangulation:
```js
const {hull} = delaunay;
let node = hull;
do {
context.moveTo(node.x, node.y);
context.lineTo(node.next.x, node.next.y);
} while ((node = node.next) !== hull);
const {hull, triangles} = delaunay;
const n = hull.length;
let i0, i1 = triangles[hull[n - 1]] * 2;
for (let i = 0; i < n; ++i) {
i0 = i1, i1 = triangles[hull[i]] * 2;
context.moveTo(points[i0], points[i0 + 1]);
context.lineTo(points[i1], points[i1 + 1]);
}
```

@@ -113,44 +123,25 @@

### Node
### Voronoi
See [*delaunay*.hull](#delaunay_hull).
<a href="#voronoi_delaunay" name="voronoi_delaunay">#</a> <i>voronoi</i>.<b>delaunay</b>
<a href="#node_i" name="node_i">#</a> <i>node</i>.<b>i</b>
The Voronoi diagram’s associated [Delaunay triangulation](#delaunay).
The index of the input point corresponding to this node. Equivalent to [*delaunay*.triangles](#delaunay_triangles)[[*node*.t](#node_t)].
<a href="#voronoi_circumcenters" name="voronoi_circumcenters">#</a> <i>voronoi</i>.<b>circumcenters</b>
<a href="#node_x" name="node_x">#</a> <i>node</i>.<b>x</b>
The [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.
Equivalent to [*delaunay*.points](#delaunay_points)[2 * [*node*.i](#node_i)].
<a href="#voronoi_edges" name="voronoi_edges">#</a> <i>voronoi</i>.<b>edges</b>
<a href="#node_y" name="node_y">#</a> <i>node</i>.<b>y</b>
… 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.
Equivalent to [*delaunay*.points](#delaunay_points)[2 * [*node*.i](#node_i) + 1].
<a href="#voronoi_index" name="voronoi_index">#</a> <i>voronoi</i>.<b>index</b>
<a href="#node_t" name="node_t">#</a> <i>node</i>.<b>t</b>
… 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.
The index of the triangle vertex corresponding to this node.
<a href="#voronoi_vectors" name="voronoi_vectors">#</a> <i>voronoi</i>.<b>vectors</b>
<a href="#node_prev" name="node_prev">#</a> <i>node</i>.<b>prev</b>
… 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.
The node before this node on the convex hull.
<a href="#node_next" name="node_next">#</a> <i>node</i>.<b>next</b>
The node after this node on the convex hull.
### Voronoi
<a href="#voronoi_cells" name="voronoi_cells">#</a> <i>voronoi</i>.<b>cells</b>
The cells of the Voronoi diagram as an array of [*Cell*](#cell) instances. The *voronoi*.cells[*i*] represents the area of the plane closest to the input point *i*, *i.e.*, [*points*[2 * *i*], *points*[2 * *i* + 1]] where *points* = *voronoi*.delaunay.points.
<a href="#voronoi_circumcenters" name="voronoi_circumcenters">#</a> <i>voronoi</i>.<b>circumcenters</b>
The [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.
<a href="#voronoi_delaunay" name="voronoi_delaunay">#</a> <i>voronoi</i>.<b>delaunay</b>
The Voronoi diagram’s associated [Delaunay triangulation](#delaunay).
<a href="#voronoi_xmin" name="voronoi_xmin">#</a> <i>voronoi</i>.<b>xmin</b><br>

@@ -163,9 +154,9 @@ <a href="#voronoi_ymin" name="voronoi_ymin">#</a> <i>voronoi</i>.<b>ymin</b><br>

<a href="#voronoi_find" name="voronoi_find">#</a> <i>voronoi</i>.<b>find</b>(<i>x</i>, <i>y</i>) [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js "Source")
<a href="#voronoi_find" name="voronoi_find">#</a> <i>voronoi</i>.<b>find</b>(<i>x</i>, <i>y</i>[, <i>i</i>]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js "Source")
Returns the [cell](#cell) that contains the specified point ⟨*x*, *y*⟩. (This method is not affected by the associated Voronoi diagram’s viewport [bounds](#voronoi_xmin).)
Returns 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).)
<a href="#voronoi_findIndex" name="voronoi_findIndex">#</a> <i>voronoi</i>.<b>findIndex</b>(<i>x</i>, <i>y</i>) [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js "Source")
<a href="#voronoi_contains" name="voronoi_contains">#</a> <i>voronoi</i>.<b>contains</b>(<i>i</i>, <i>x</i>, <i>y</i>) [<>](https://github.com/d3/d3-delaunay/blob/master/src/cell.js "Source")
Returns the index of the [cell](#cell) that contains the specified point ⟨*x*, *y*⟩. (This method is not affected by the associated Voronoi diagram’s viewport [bounds](#voronoi_xmin).)
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](#voronoi_xmin).)

@@ -184,28 +175,6 @@ <a href="#voronoi_render" name="voronoi_render">#</a> <i>voronoi</i>.<b>render</b>(<i>context</i>) [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js "Source")

### Cell
<a href="#voronoi_renderCell" name="voronoi_renderCell">#</a> <i>voronoi</i>.<b>renderCell</b>(<i>i</i>, <i>context</i>) [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js "Source")
<a href="#cell_voronoi" name="cell_voronoi">#</a> <i>cell</i>.<b>voronoi</b>
The cell’s associated [Voronoi diagram](#voronoi).
<a href="#cell_triangles" name="cell_triangles">#</a> <i>cell</i>.<b>triangles</b>
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.
<a href="#cell_v0" name="cell_v0">#</a> <i>cell</i>.<b>v0</b>
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.
<a href="#cell_vn" name="cell_vn">#</a> <i>cell</i>.<b>vn</b>
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.
<a href="#cell_render" name="cell_render">#</a> <i>cell</i>.<b>render</b>(<i>context</i>) [<>](https://github.com/d3/d3-delaunay/blob/master/src/cell.js "Source")
<img alt="cell.render" src="https://raw.githubusercontent.com/d3/d3-delaunay/master/img/spectral.png">
Renders the cell 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).
<a href="#cell_contains" name="cell_contains">#</a> <i>cell</i>.<b>contains</b>(<i>x</i>, <i>y</i>) [<>](https://github.com/d3/d3-delaunay/blob/master/src/cell.js "Source")
Returns true if this cell contains the specified point ⟨*x*, *y*⟩. (This method is not affected by the associated Voronoi diagram’s viewport [bounds](#voronoi_xmin).)
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](https://www.w3.org/TR/2dcontext/#canvaspathmethods).

2

rollup.config.js

@@ -1,2 +0,1 @@

import commonjs from "rollup-plugin-commonjs";
import noderesolve from "rollup-plugin-node-resolve";

@@ -13,3 +12,2 @@ import uglify from "rollup-plugin-uglify";

plugins: [
commonjs(),
noderesolve(),

@@ -16,0 +14,0 @@ ...plugins

142

src/delaunay.js

@@ -1,91 +0,22 @@

import Cell from "./cell.js";
import Delaunator from "delaunator";
import Voronoi from "./voronoi.js";
function pointX(p) {
return p[0];
}
function pointY(p) {
return p[1];
}
export default class Delaunay {
constructor(points, halfedges, hull, triangles) {
constructor(points) {
const {halfedges, hull, triangles} = new Delaunator(points);
this.points = points;
this.halfedges = halfedges;
this.hull = hull;
this.hull = Uint32Array.from(hullIterable(hull));
this.triangles = triangles;
}
voronoi([xmin, ymin, xmax, ymax] = [0, 0, 960, 500]) {
const {points, halfedges, hull, triangles} = this;
const cells = new Array(points.length / 2);
const circumcenters = new Float64Array(triangles.length / 3 * 2);
const voronoi = new Voronoi(cells, circumcenters, this, xmin, ymin, xmax, ymax);
// Compute cell topology.
for (let i = 0, n = cells.length; i < n; ++i) {
cells[i] = new Cell(voronoi);
}
for (let i = 0, m = halfedges.length; i < m; ++i) {
const t = triangles[i]; // Cell vertex.
const T = cells[t].triangles;
if (T.length) continue; // Already connected.
let j = i;
do { // Walk forward.
T.push(Math.floor(j / 3));
j = halfedges[j];
if (j === -1) break; // Went off the convex hull.
j = j % 3 === 2 ? j - 2 : j + 1;
if (triangles[j] !== t) break; // Bad triangulation; break early.
} while (j !== i);
if (j !== i) { // Stopped when walking forward; walk backward.
j = i;
while (true) {
j = halfedges[j % 3 === 0 ? j + 2 : j - 1];
if (j === -1 || triangles[j] !== t) break;
T.unshift(Math.floor(j / 3));
}
} else {
T.push(T[0]); // Close polygon.
}
}
for (let i = 0, n = cells.length; i < n; ++i) {
const cell = cells[i];
if (cell.triangles.length === 0) cell.triangles = null;
}
// Compute circumcenters.
for (let i = 0, j = 0, n = triangles.length; 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 a2 = x1 - x2;
const a3 = x1 - x3;
const b2 = y1 - y2;
const b3 = y1 - y3;
const d1 = x1 * x1 + y1 * y1;
const d2 = d1 - x2 * x2 - y2 * y2;
const d3 = d1 - x3 * x3 - y3 * y3;
const ab = (a3 * b2 - a2 * b3) * 2;
circumcenters[j] = (b2 * d3 - b3 * d2) / ab;
circumcenters[j + 1] = (a3 * d2 - a2 * d3) / ab;
}
// Compute exterior cell rays.
{
let node = hull;
do {
const {x: x1, y: y1, t: i, next: {x: x2, y: y2, t: j}} = node;
const ci = Math.floor(i / 3) * 2;
const cx = circumcenters[ci];
const cy = circumcenters[ci + 1];
const dx = (x1 + x2) / 2 - cx;
const dy = (y1 + y2) / 2 - cy;
const k = (x2 - x1) * (cy - y1) > (y2 - y1) * (cx - x1) ? -1 : 1;
cells[triangles[i]].vn = cells[triangles[j]].v0 = [k * dx, k * dy];
} while ((node = node.next) !== hull);
}
return voronoi;
voronoi(bounds) {
return new Voronoi(this, bounds);
}

@@ -105,8 +36,10 @@ render(context) {

renderHull(context) {
const {hull} = this;
let node = hull;
do {
context.moveTo(node.x, node.y);
context.lineTo(node.next.x, node.next.y);
} while ((node = node.next) !== hull);
const {points, hull, triangles} = this;
const n = hull.length;
let i0, i1 = triangles[hull[n - 1]] * 2;
for (let i = 0; i < n; ++i) {
i0 = i1, i1 = triangles[hull[i]] * 2;
context.moveTo(points[i0], points[i0 + 1]);
context.lineTo(points[i1], points[i1 + 1]);
}
}

@@ -125,5 +58,32 @@ renderTriangle(i, context) {

Delaunay.from = function(points, fx, fy) {
const {coords, halfedges, hull, triangles} = new Delaunator(points, fx, fy);
return new Delaunay(coords, halfedges, hull, triangles);
Delaunay.from = function(points, fx = pointX, fy = pointY, that) {
return new Delaunay("length" in points
? flatArray(points, fx, fy, that)
: Float64Array.from(flatIterable(points, fx, fy, that)));
};
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;
}
}
function* hullIterable(hull) {
let node = hull;
do yield node.t;
while ((node = node.next) !== hull);
}

1

src/index.js

@@ -1,3 +0,2 @@

export {default as Cell} from "./cell.js";
export {default as Delaunay} from "./delaunay.js";
export {default as Voronoi} from "./voronoi.js";

209

src/voronoi.js

@@ -1,37 +0,76 @@

import Cell, {containsFinite, containsInfinite} from "./cell";
export default class Voronoi {
constructor(cells, circumcenters, delaunay, xmin, ymin, xmax, ymax) {
constructor(delaunay, [xmin, ymin, xmax, ymax] = [0, 0, 960, 500]) {
if (!((xmax = +xmax) >= (xmin = +xmin)) || !((ymax = +ymax) >= (ymin = +ymin))) throw new Error("invalid bounds");
this.cells = cells;
this.circumcenters = circumcenters;
this.delaunay = delaunay;
const {points, halfedges, hull, triangles} = this.delaunay = delaunay;
const circumcenters = this.circumcenters = new Float64Array(triangles.length / 3 * 2);
const edges = this.edges = new Uint32Array(halfedges.length);
const index = this.index = new Uint32Array(points.length);
const vectors = this.vectors = new Float64Array(points.length * 2);
this.xmax = xmax, this.xmin = xmin;
this.ymax = ymax, this.ymin = ymin;
}
find(x, y) {
return this.cells[this.findIndex(x, y)];
}
findIndex(x, y) {
const {cells, delaunay: {halfedges, points, triangles}} = this;
if (cells.length === 0 || (x = +x, x !== x) || (y = +y, y !== y)) return -1;
let c = 0, c2 = (x - points[0]) ** 2 + (y - points[1]) ** 2;
while (true) {
let d = c, d2 = c2;
for (let T = cells[c].triangles, i = 0, n = T.length; i < n; ++i) {
let k = T[i] * 3;
switch (c) {
case triangles[k]: k = triangles[k + 1]; break;
case triangles[k + 1]: k = triangles[k + 2]; break;
case triangles[k + 2]: k = triangles[k]; break;
// Compute cell topology.
for (let i = 0, e = 0, m = halfedges.length; i < m; ++i) {
const t = triangles[i]; // Cell vertex.
if (index[t * 2] !== index[t * 2 + 1]) continue; // Already connected.
const e0 = index[t * 2] = e;
let j = i;
do { // Walk forward.
edges[e++] = Math.floor(j / 3);
j = halfedges[j];
if (j === -1) break; // Went off the convex hull.
j = j % 3 === 2 ? j - 2 : j + 1;
if (triangles[j] !== t) break; // Bad triangulation; break early.
} while (j !== i);
if (j !== i) { // Stopped when walking forward; walk backward.
const e1 = e;
j = i;
while (true) {
j = halfedges[j % 3 === 0 ? j + 2 : j - 1];
if (j === -1 || triangles[j] !== t) break;
edges[e++] = Math.floor(j / 3);
}
let k2 = (x - points[k * 2]) ** 2 + (y - points[k * 2 + 1]) ** 2;
if (k2 < d2) d2 = k2, d = k;
if (e1 < e) {
edges.subarray(e0, e1).reverse();
edges.subarray(e0, e).reverse();
}
}
if (d === c) return d;
c = d, c2 = d2;
index[t * 2 + 1] = e;
}
// Compute circumcenters.
for (let i = 0, j = 0, n = triangles.length; 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 a2 = x1 - x2;
const a3 = x1 - x3;
const b2 = y1 - y2;
const b3 = y1 - y3;
const d1 = x1 * x1 + y1 * y1;
const d2 = d1 - x2 * x2 - y2 * y2;
const d3 = d1 - x3 * x3 - y3 * y3;
const ab = (a3 * b2 - a2 * b3) * 2;
circumcenters[j] = (b2 * d3 - b3 * d2) / ab;
circumcenters[j + 1] = (a3 * d2 - a2 * d3) / ab;
}
// Compute exterior cell rays.
for (let n = hull.length, p0, x0, y0, p1 = triangles[hull[n - 1]] * 2, x1 = points[p1], y1 = points[p1 + 1], i = 0; i < n; ++i) {
p0 = p1, x0 = x1, y0 = y1, p1 = triangles[hull[i]] * 2, x1 = points[p1], y1 = points[p1 + 1];
vectors[p0 * 2 + 2] = vectors[p1 * 2] = y0 - y1;
vectors[p0 * 2 + 3] = vectors[p1 * 2 + 1] = x1 - x0;
}
}
render(context) {
const {cells, circumcenters, delaunay: {halfedges, hull}} = this;
const {delaunay: {halfedges, hull, triangles}, circumcenters, vectors} = this;
for (let i = 0, n = halfedges.length; i < n; ++i) {

@@ -45,8 +84,8 @@ const j = halfedges[i];

}
let node = hull;
do {
const t = Math.floor(node.t / 3) * 2;
for (let i = 0, n = hull.length; i < n; ++i) {
const t = Math.floor(hull[i] / 3) * 2;
const x = circumcenters[t];
const y = circumcenters[t + 1];
const p = this._project(x, y, cells[node.i].vn);
const v = triangles[hull[i]] * 4;
const p = this._project(x, y, vectors[v + 2], vectors[v + 3]);
if (p) {

@@ -56,3 +95,3 @@ context.moveTo(x, y);

}
} while ((node = node.next) !== hull);
}
}

@@ -62,5 +101,71 @@ renderBounds(context) {

}
_clip(points, v0, vn) {
return v0 ? this._clipInfinite(points, v0, vn) : this._clipFinite(points);
renderCell(i, context) {
const points = this._clip(i);
if (points === null) return;
context.moveTo(points[0], points[1]);
for (let i = 2, n = points.length; i < n; i += 2) {
context.lineTo(points[i], points[i + 1]);
}
context.closePath();
}
contains(i, x, y) {
const {vectors: V} = this;
const points = this._cell(i);
const v = i * 4;
return points === null ? false
: V[v] || V[v + 1] ? containsInfinite(points, V[v], V[v + 1], V[v + 2], V[v + 3], x, y)
: containsFinite(points, x, y);
}
find(x, y, i = 0) {
const {delaunay: {halfedges, points, triangles}, edges, index} = this;
if (points.length === 0 || (x = +x, x !== x) || (y = +y, y !== y)) return -1;
let di = (x - points[i * 2]) ** 2 + (y - points[i * 2 + 1]) ** 2;
while (true) {
const j0 = index[i * 2];
const j1 = index[i * 2 + 1];
let c = i, dc = di;
let k = edges[j0] * 3;
switch (i) { // Test previous point on triangle (for hull).
case triangles[k]: k = triangles[k + 2]; break;
case triangles[k + 1]: k = triangles[k]; break;
case triangles[k + 2]: k = triangles[k + 1]; break;
}
let dk = (x - points[k * 2]) ** 2 + (y - points[k * 2 + 1]) ** 2;
if (dk < dc) dc = dk, c = k;
for (let j = j0; j < j1; ++j) {
k = edges[j] * 3;
switch (i) { // Test next point on triangle.
case triangles[k]: k = triangles[k + 1]; break;
case triangles[k + 1]: k = triangles[k + 2]; break;
case triangles[k + 2]: k = triangles[k]; break;
}
dk = (x - points[k * 2]) ** 2 + (y - points[k * 2 + 1]) ** 2;
if (dk < dc) dc = dk, c = k;
}
if (c === i) return c;
i = c, di = dc;
}
}
_cell(i) {
const {index, edges, circumcenters} = this;
const t0 = index[i * 2];
const t1 = index[i * 2 + 1];
if (t0 === t1) return null;
const points = new Float64Array((t1 - t0) * 2);
for (let t = t0, j = 0; t < t1; ++t, j += 2) {
const ti = edges[t] * 2;
points[j] = circumcenters[ti];
points[j + 1] = circumcenters[ti + 1];
}
return points;
}
_clip(i) {
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(points, V[v], V[v + 1], V[v + 2], V[v + 3])
: this._clipFinite(points);
}
_clipFinite(points) {

@@ -115,6 +220,6 @@ const n = points.length;

// TODO Consolidate corner traversal code using edge?
_clipInfinite(points, v0, vn) {
_clipInfinite(points, vx0, vy0, vxn, vyn) {
let P = Array.from(points), p;
if (p = this._project(P[0], P[1], v0)) P.unshift(p[0], p[1]);
if (p = this._project(P[P.length - 2], P[P.length - 1], vn)) P.unshift(p[0], p[1]);
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.unshift(p[0], p[1]);
if (P = this._clipFinite(P)) {

@@ -136,3 +241,3 @@ for (let i = 0, n = P.length, c0, c1 = this._edgecode(P[n - 2], P[n - 1]); i < n; i += 2) {

}
if (containsInfinite(points, v0, vn, cx, cy)) {
if (containsInfinite(points, vx0, vy0, vxn, vyn, cx, cy)) {
P.splice(i, 0, cx, cy), n += 2, i += 2;

@@ -143,3 +248,3 @@ }

}
} else if (containsInfinite(points, v0, vn, (this.xmin + this.xmax) / 2, (this.ymin + this.ymax) / 2)) {
} else if (containsInfinite(points, vx0, vy0, vxn, vyn, (this.xmin + this.xmax) / 2, (this.ymin + this.ymax) / 2)) {
P.push(this.xmin, this.ymin, this.xmax, this.ymin, this.xmax, this.ymax, this.xmin, this.ymax);

@@ -168,3 +273,3 @@ }

}
_project(x0, y0, [vx, vy]) {
_project(x0, y0, vx, vy) {
let t = Infinity, c, x, y;

@@ -200,1 +305,25 @@ if (vy < 0) { // top

}
function containsFinite(points, x, y) {
const n = points.length;
let x0, y0, x1 = points[n - 2], y1 = points[n - 1];
for (let i = 0; i < n; i += 2) {
x0 = x1, y0 = y1, x1 = points[i], y1 = points[i + 1];
if ((x1 - x0) * (y - y0) < (y1 - y0) * (x - x0)) {
return false;
}
}
return true;
}
function containsInfinite(points, vx0, vy0, vxn, vyn, x, y) {
const n = points.length;
let x0, y0, x1 = points[0], y1 = points[1];
if ((x0 + vx0 - x) * (y1 - y) < (y0 + vy0 - y) * (x1 - x)) return false;
for (let i = 2; i < n; i += 2) {
x0 = x1, y0 = y1, x1 = points[i], y1 = points[i + 1];
if ((x0 - x) * (y1 - y) < (y0 - y) * (x1 - x)) return false;
}
if ((x0 - x) * (y1 + vyn - y) < (y0 - y) * (x1 + vxn - x)) return false;
return true;
}
src/cell.js
SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc