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 4.1.0 to 4.1.1

.eslintrc.json
yarn.lock

1600

dist/d3-delaunay.js

@@ -1,928 +0,930 @@

// https://github.com/d3/d3-delaunay Version 4.1.0. Copyright 2018 Observable, Inc.
// https://github.com/mapbox/delaunator Version 2.0.0. Copyright 2017, Mapbox, Inc.
// https://github.com/d3/d3-delaunay v4.1.1 Copyright 2018 Mike Bostock
// https://github.com/mapbox/delaunator v2.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';
Delaunator.from = function (points, getX, getY) {
if (!getX) getX = defaultGetX;
if (!getY) getY = defaultGetY;
Delaunator.from = function (points, getX, getY) {
if (!getX) getX = defaultGetX;
if (!getY) getY = defaultGetY;
var n = points.length;
var coords = new Float64Array(n * 2);
var n = points.length;
var coords = new Float64Array(n * 2);
for (var i = 0; i < n; i++) {
var p = points[i];
coords[2 * i] = getX(p);
coords[2 * i + 1] = getY(p);
}
for (var i = 0; i < n; i++) {
var p = points[i];
coords[2 * i] = getX(p);
coords[2 * i + 1] = getY(p);
}
return new Delaunator(coords);
};
return new Delaunator(coords);
};
function Delaunator(coords) {
if (!ArrayBuffer.isView(coords)) throw new Error('Expected coords to be a typed array.');
function Delaunator(coords) {
if (!ArrayBuffer.isView(coords)) throw new Error('Expected coords to be a typed array.');
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 n = coords.length >> 1;
var ids = this.ids = new Uint32Array(n);
this.coords = coords;
this.coords = coords;
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;
}
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 < n; 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 < 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;
}
// 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 < n; 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(n));
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 * n - 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);
// 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.next;
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);
}
// trim typed triangle mesh arrays
this.triangles = triangles.subarray(0, this.trianglesLen);
this.halfedges = halfedges.subarray(0, this.trianglesLen);
// save the two new edges in the hash table
this._hashEdge(e);
this._hashEdge(e.prev);
}
Delaunator.prototype = {
// trim typed triangle mesh arrays
this.triangles = triangles.subarray(0, this.trianglesLen);
this.halfedges = halfedges.subarray(0, this.trianglesLen);
}
_hashEdge: function (e) {
this._hash[this._hashKey(e.x, e.y)] = e;
},
Delaunator.prototype = {
_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);
},
_hashEdge: function (e) {
this._hash[this._hashKey(e.x, e.y)] = e;
},
_legalize: function (a) {
var triangles = this.triangles;
var coords = this.coords;
var halfedges = this.halfedges;
_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);
},
var b = halfedges[a];
_legalize: function (a) {
var triangles = this.triangles;
var coords = this.coords;
var halfedges = this.halfedges;
var a0 = a - a % 3;
var b0 = b - b % 3;
var b = halfedges[a];
var al = a0 + (a + 1) % 3;
var ar = a0 + (a + 2) % 3;
var bl = b0 + (b + 2) % 3;
var a0 = a - a % 3;
var b0 = b - b % 3;
var p0 = triangles[ar];
var pr = triangles[a];
var pl = triangles[al];
var p1 = triangles[bl];
var al = a0 + (a + 1) % 3;
var ar = a0 + (a + 2) % 3;
var bl = b0 + (b + 2) % 3;
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 p0 = triangles[ar];
var pr = triangles[a];
var pl = triangles[al];
var p1 = triangles[bl];
if (illegal) {
triangles[a] = p1;
triangles[b] = p0;
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]);
this._link(a, halfedges[bl]);
this._link(b, halfedges[ar]);
this._link(ar, bl);
if (illegal) {
triangles[a] = p1;
triangles[b] = p0;
var br = b0 + (b + 1) % 3;
this._link(a, halfedges[bl]);
this._link(b, halfedges[ar]);
this._link(ar, bl);
this._legalize(a);
return this._legalize(br);
}
var br = b0 + (b + 1) % 3;
return ar;
},
this._legalize(a);
return this._legalize(br);
}
_link: function (a, b) {
this.halfedges[a] = b;
if (b !== -1) this.halfedges[b] = a;
},
return ar;
},
// add a new triangle given vertex indices and adjacent half-edge ids
_addTriangle: function (i0, i1, i2, a, b, c) {
var t = this.trianglesLen;
_link: function (a, b) {
this.halfedges[a] = b;
if (b !== -1) this.halfedges[b] = a;
},
this.triangles[t] = i0;
this.triangles[t + 1] = i1;
this.triangles[t + 2] = i2;
// 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._link(t, a);
this._link(t + 1, b);
this._link(t + 2, c);
this.triangles[t] = i0;
this.triangles[t + 1] = i1;
this.triangles[t + 2] = i2;
this.trianglesLen += 3;
this._link(t, a);
this._link(t + 1, b);
this._link(t + 2, c);
return t;
}
};
this.trianglesLen += 3;
function dist(ax, ay, bx, by) {
var dx = ax - bx;
var dy = ay - by;
return dx * dx + dy * dy;
return t;
}
};
function area(px, py, qx, qy, rx, ry) {
return (qy - py) * (rx - qx) - (qx - px) * (ry - qy);
}
function dist(ax, ay, bx, by) {
var dx = ax - bx;
var dy = ay - by;
return dx * dx + dy * dy;
}
function inCircle(ax, ay, bx, by, cx, cy, px, py) {
ax -= px;
ay -= py;
bx -= px;
by -= py;
cx -= px;
cy -= py;
function area(px, py, qx, qy, rx, ry) {
return (qy - py) * (rx - qx) - (qx - px) * (ry - qy);
}
var ap = ax * ax + ay * ay;
var bp = bx * bx + by * by;
var cp = cx * cx + cy * cy;
function inCircle(ax, ay, bx, by, cx, cy, px, py) {
ax -= px;
ay -= py;
bx -= px;
by -= py;
cx -= px;
cy -= py;
return ax * (by * cp - bp * cy) -
ay * (bx * cp - bp * cx) +
ap * (bx * cy - by * cx) < 0;
}
var ap = ax * ax + ay * ay;
var bp = bx * bx + by * by;
var cp = cx * cx + cy * cy;
function circumradius(ax, ay, bx, by, cx, cy) {
bx -= ax;
by -= ay;
cx -= ax;
cy -= ay;
return ax * (by * cp - bp * cy) -
ay * (bx * cp - bp * cx) +
ap * (bx * cy - by * cx) < 0;
}
var bl = bx * bx + by * by;
var cl = cx * cx + cy * cy;
function circumradius(ax, ay, bx, by, cx, cy) {
bx -= ax;
by -= ay;
cx -= ax;
cy -= ay;
if (bl === 0 || cl === 0) return Infinity;
var bl = bx * bx + by * by;
var cl = cx * cx + cy * cy;
var d = bx * cy - by * cx;
if (d === 0) return Infinity;
if (bl === 0 || cl === 0) return Infinity;
var x = (cy * bl - by * cl) * 0.5 / d;
var y = (bx * cl - cx * bl) * 0.5 / d;
var d = bx * cy - by * cx;
if (d === 0) return Infinity;
return x * x + y * y;
}
var x = (cy * bl - by * cl) * 0.5 / d;
var y = (bx * cl - cx * bl) * 0.5 / d;
function circumcenter(ax, ay, bx, by, cx, cy) {
bx -= ax;
by -= ay;
cx -= ax;
cy -= ay;
return x * x + y * y;
}
var bl = bx * bx + by * by;
var cl = cx * cx + cy * cy;
function circumcenter(ax, ay, bx, by, cx, cy) {
bx -= ax;
by -= ay;
cx -= ax;
cy -= ay;
var d = bx * cy - by * cx;
var bl = bx * bx + by * by;
var cl = cx * cx + cy * cy;
var x = (cy * bl - by * cl) * 0.5 / d;
var y = (bx * cl - cx * bl) * 0.5 / d;
var d = bx * cy - by * cx;
return {
x: ax + x,
y: ay + y
};
}
var x = (cy * bl - by * cl) * 0.5 / d;
var y = (bx * cl - cx * bl) * 0.5 / d;
// 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
};
return {
x: ax + x,
y: ay + y
};
}
if (!prev) {
node.prev = node;
node.next = node;
// 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
};
} else {
node.next = prev.next;
node.prev = prev;
prev.next.prev = node;
prev.next = node;
}
return node;
}
if (!prev) {
node.prev = node;
node.next = node;
function removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.removed = true;
return node.prev;
} else {
node.next = prev.next;
node.prev = prev;
prev.next.prev = node;
prev.next = node;
}
return node;
}
function quicksort(ids, coords, left, right, cx, cy) {
var i, j, temp;
function removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.removed = true;
return node.prev;
}
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);
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];
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;
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 - 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);
}
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);
}
}
}
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 defaultGetX(p) {
return p[0];
}
function defaultGetY(p) {
return p[1];
}
const epsilon = 1e-6;
class Path {
constructor() {
this._x0 = this._y0 = // start of current subpath
this._x1 = this._y1 = null; // end of current subpath
this._ = "";
}
moveTo(x, y) {
this._ += `M${this._x0 = this._x1 = +x},${this._y0 = this._y1 = +y}`;
}
closePath() {
if (this._x1 !== null) {
this._x1 = this._x0, this._y1 = this._y0;
this._ += "Z";
}
}
lineTo(x, y) {
this._ += `L${this._x1 = +x},${this._y1 = +y}`;
}
arc(x, y, r) {
x = +x, y = +y, r = +r;
const x0 = x + r;
const y0 = y;
if (r < 0) throw new Error("negative radius");
if (this._x1 === null) this._ += `M${x0},${y0}`;
else if (Math.abs(this._x1 - x0) > epsilon || Math.abs(this._y1 - y0) > epsilon) this._ += "L" + x0 + "," + y0;
if (!r) return;
this._ += `A${r},${r},0,1,1,${x - r},${y}A${r},${r},0,1,1,${this._x1 = x0},${this._y1 = y0}`;
}
rect(x, y, w, h) {
this._ += `M${this._x0 = this._x1 = +x},${this._y0 = this._y1 = +y}h${+w}v${+h}h${-w}Z`;
}
value() {
return this._ || null;
}
}
function swap(arr, i, j) {
var tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
class Polygon {
constructor() {
this._ = [];
}
moveTo(x, y) {
this._.push([x, y]);
}
closePath() {
this._.push(this._[0].slice());
}
lineTo(x, y) {
this._.push([x, y]);
}
value() {
return this._.length ? this._ : null;
}
}
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, hull, triangles} = this.delaunay = delaunay;
const circumcenters = this.circumcenters = new Float64Array(triangles.length / 3 * 2);
const vectors = this.vectors = new Float64Array(points.length * 2);
this.xmax = xmax, this.xmin = xmin;
this.ymax = ymax, this.ymin = ymin;
// 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;
}
function defaultGetX(p) {
return p[0];
// Compute exterior cell rays.
let node = hull;
let p0, p1 = node.i * 4;
let x0, x1 = node.x;
let y0, y1 = node.y;
do {
node = node.next, p0 = p1, x0 = x1, y0 = y1, p1 = node.i * 4, x1 = node.x, y1 = node.y;
vectors[p0 + 2] = vectors[p1] = y0 - y1;
vectors[p0 + 3] = vectors[p1 + 1] = x1 - x0;
} while (node !== hull);
}
render(context) {
const buffer = context == null ? context = new Path : undefined;
const {delaunay: {halfedges, hull}, 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;
const xi = circumcenters[ti];
const yi = circumcenters[ti + 1];
const xj = circumcenters[tj];
const yj = circumcenters[tj + 1];
this._renderSegment(xi, yi, xj, yj, context);
}
function defaultGetY(p) {
return p[1];
let node = hull;
do {
node = node.next;
const t = Math.floor(node.t / 3) * 2;
const x = circumcenters[t];
const y = circumcenters[t + 1];
const v = node.i * 4;
const p = this._project(x, y, vectors[v + 2], vectors[v + 3]);
if (p) this._renderSegment(x, y, p[0], p[1], context);
} while (node !== hull);
return buffer && buffer.value();
}
renderBounds(context) {
const buffer = context == null ? context = new Path : undefined;
context.rect(this.xmin, this.ymin, this.xmax - this.xmin, this.ymax - this.ymin);
return buffer && buffer.value();
}
renderCell(i, context) {
const buffer = context == null ? context = new Path : undefined;
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]);
}
class Path {
constructor() {
this._x0 = this._y0 = // start of current subpath
this._x1 = this._y1 = null; // end of current subpath
this._ = "";
}
moveTo(x, y) {
this._ += `M${this._x0 = this._x1 = +x},${this._y0 = this._y1 = +y}`;
}
closePath() {
if (this._x1 !== null) {
this._x1 = this._x0, this._y1 = this._y0;
this._ += "Z";
}
}
lineTo(x, y) {
this._ += `L${this._x1 = +x},${this._y1 = +y}`;
}
arc(x, y, r) {
x = +x, y = +y, r = +r;
const x0 = x + r;
const y0 = y;
if (r < 0) throw new Error("negative radius");
if (this._x1 === null) this._ += `M${x0},${y0}`;
else if (Math.abs(this._x1 - x0) > epsilon || Math.abs(this._y1 - y0) > epsilon) this._ += "L" + x0 + "," + y0;
if (!r) return;
this._ += `A${r},${r},0,1,1,${x - r},${y}A${r},${r},0,1,1,${this._x1 = x0},${this._y1 = y0}`;
}
rect(x, y, w, h) {
this._ += `M${this._x0 = this._x1 = +x},${this._y0 = this._y1 = +y}h${+w}v${+h}h${-w}Z`;
}
value() {
return this._ || null;
}
context.closePath();
return buffer && buffer.value();
}
*cellPolygons() {
const {delaunay: {points}} = this;
for (let i = 0, n = points.length / 2; i < n; ++i) {
const cell = this.cellPolygon(i);
if (cell) yield cell;
}
class Polygon {
constructor() {
this._ = [];
}
moveTo(x, y) {
this._.push([x, y]);
}
closePath() {
this._.push(this._[0].slice());
}
lineTo(x, y) {
this._.push([x, y]);
}
value() {
return this._.length ? this._ : null;
}
}
cellPolygon(i) {
const polygon = new Polygon;
this.renderCell(i, polygon);
return polygon.value();
}
_renderSegment(x0, y0, x1, y1, context) {
let S;
const c0 = this._regioncode(x0, y0);
const c1 = this._regioncode(x1, y1);
if (c0 === 0 && c1 === 0) {
context.moveTo(x0, y0);
context.lineTo(x1, y1);
} else if (S = this._clipSegment(x0, y0, x1, y1, c0, c1)) {
context.moveTo(S[0], S[1]);
context.lineTo(S[2], S[3]);
}
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, hull, triangles} = this.delaunay = delaunay;
const circumcenters = this.circumcenters = new Float64Array(triangles.length / 3 * 2);
const vectors = this.vectors = new Float64Array(points.length * 2);
this.xmax = xmax, this.xmin = xmin;
this.ymax = ymax, this.ymin = ymin;
// 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;
let p0, p1 = node.i * 4;
let x0, x1 = node.x;
let y0, y1 = node.y;
do {
node = node.next, p0 = p1, x0 = x1, y0 = y1, p1 = node.i * 4, x1 = node.x, y1 = node.y;
vectors[p0 + 2] = vectors[p1] = y0 - y1;
vectors[p0 + 3] = vectors[p1 + 1] = x1 - x0;
} while (node !== hull);
}
render(context) {
const buffer = context == null ? context = new Path : undefined;
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;
const xi = circumcenters[ti];
const yi = circumcenters[ti + 1];
const xj = circumcenters[tj];
const yj = circumcenters[tj + 1];
this._renderSegment(xi, yi, xj, yj, context);
}
let node = hull;
do {
node = node.next;
const t = Math.floor(node.t / 3) * 2;
const x = circumcenters[t];
const y = circumcenters[t + 1];
const v = node.i * 4;
const p = this._project(x, y, vectors[v + 2], vectors[v + 3]);
if (p) this._renderSegment(x, y, p[0], p[1], context);
} while (node !== hull);
return buffer && buffer.value();
}
renderBounds(context) {
const buffer = context == null ? context = new Path : undefined;
context.rect(this.xmin, this.ymin, this.xmax - this.xmin, this.ymax - this.ymin);
return buffer && buffer.value();
}
renderCell(i, context) {
const buffer = context == null ? context = new Path : undefined;
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();
return buffer && buffer.value();
}
*cellPolygons() {
const {delaunay: {points}} = this;
for (let i = 0, n = points.length / 2; i < n; ++i) {
const cell = this.cellPolygon(i);
if (cell) yield cell;
}
}
cellPolygon(i) {
const polygon = new Polygon;
this.renderCell(i, polygon);
return polygon.value();
}
_renderSegment(x0, y0, x1, y1, context) {
let S;
const c0 = this._regioncode(x0, y0);
const c1 = this._regioncode(x1, y1);
if (c0 === 0 && c1 === 0) {
context.moveTo(x0, y0);
context.lineTo(x1, y1);
} else if (S = this._clipSegment(x0, y0, x1, y1, c0, c1)) {
context.moveTo(S[0], S[1]);
context.lineTo(S[2], S[3]);
}
}
contains(i, x, y) {
if ((x = +x, x !== x) || (y = +y, y !== y)) return false;
return this.delaunay._step(i, x, y) === i;
}
_cell(i) {
const {circumcenters, delaunay: {inedges, halfedges, triangles}} = this;
const e0 = inedges[i];
if (e0 === -1) return null; // coincident point
const points = [];
let e = e0;
do {
const t = Math.floor(e / 3);
points.push(circumcenters[t * 2], circumcenters[t * 2 + 1]);
e = e % 3 === 2 ? e - 2 : e + 1;
if (triangles[e] !== i) break; // bad triangulation
e = halfedges[e];
} while (e !== e0 && e !== -1);
return points;
}
_clip(i) {
const points = this._cell(i);
if (points === null) return null;
const {vectors: V} = this;
const v = i * 4;
return V[v] || V[v + 1]
? this._clipInfinite(i, points, V[v], V[v + 1], V[v + 2], V[v + 3])
: this._clipFinite(i, points);
}
_clipFinite(i, points) {
const n = points.length;
let P = null;
let x0, y0, x1 = points[n - 2], y1 = points[n - 1];
let c0, c1 = this._regioncode(x1, y1);
let e0, e1;
for (let j = 0; j < n; j += 2) {
x0 = x1, y0 = y1, x1 = points[j], y1 = points[j + 1];
c0 = c1, c1 = this._regioncode(x1, y1);
if (c0 === 0 && c1 === 0) {
e0 = e1, e1 = 0;
if (P) P.push(x1, y1);
else P = [x1, y1];
} else {
let S, sx0, sy0, sx1, sy1;
if (c0 === 0) {
if ((S = this._clipSegment(x0, y0, x1, y1, c0, c1)) === null) continue;
[sx0, sy0, sx1, sy1] = S;
} else {
if ((S = this._clipSegment(x1, y1, x0, y0, c1, c0)) === null) continue;
[sx1, sy1, sx0, sy0] = S;
e0 = e1, e1 = this._edgecode(sx0, sy0);
if (e0 && e1) this._edge(i, e0, e1, P, P.length);
if (P) P.push(sx0, sy0);
else P = [sx0, sy0];
}
e0 = e1, e1 = this._edgecode(sx1, sy1);
if (e0 && e1) this._edge(i, e0, e1, P, P.length);
if (P) P.push(sx1, sy1);
else P = [sx1, sy1];
}
}
if (P) {
e0 = e1, e1 = this._edgecode(P[0], P[1]);
}
contains(i, x, y) {
if ((x = +x, x !== x) || (y = +y, y !== y)) return false;
return this.delaunay._step(i, x, y) === i;
}
_cell(i) {
const {circumcenters, delaunay: {inedges, halfedges, triangles}} = this;
const e0 = inedges[i];
if (e0 === -1) return null; // coincident point
const points = [];
let e = e0;
do {
const t = Math.floor(e / 3);
points.push(circumcenters[t * 2], circumcenters[t * 2 + 1]);
e = e % 3 === 2 ? e - 2 : e + 1;
if (triangles[e] !== i) break; // bad triangulation
e = halfedges[e];
} while (e !== e0 && e !== -1);
return points;
}
_clip(i) {
const points = this._cell(i);
if (points === null) return null;
const {vectors: V} = this;
const v = i * 4;
return V[v] || V[v + 1]
? this._clipInfinite(i, points, V[v], V[v + 1], V[v + 2], V[v + 3])
: this._clipFinite(i, points);
}
_clipFinite(i, points) {
const n = points.length;
let P = null;
let x0, y0, x1 = points[n - 2], y1 = points[n - 1];
let c0, c1 = this._regioncode(x1, y1);
let e0, e1;
for (let j = 0; j < n; j += 2) {
x0 = x1, y0 = y1, x1 = points[j], y1 = points[j + 1];
c0 = c1, c1 = this._regioncode(x1, y1);
if (c0 === 0 && c1 === 0) {
e0 = e1, e1 = 0;
if (P) P.push(x1, y1);
else P = [x1, y1];
} else {
let S, sx0, sy0, sx1, sy1;
if (c0 === 0) {
if ((S = this._clipSegment(x0, y0, x1, y1, c0, c1)) === null) continue;
[sx0, sy0, sx1, sy1] = S;
} else {
if ((S = this._clipSegment(x1, y1, x0, y0, c1, c0)) === null) continue;
[sx1, sy1, sx0, sy0] = S;
e0 = e1, e1 = this._edgecode(sx0, sy0);
if (e0 && e1) this._edge(i, e0, e1, P, P.length);
} else if (this.contains(i, (this.xmin + this.xmax) / 2, (this.ymin + this.ymax) / 2)) {
return [this.xmax, this.ymin, this.xmax, this.ymax, this.xmin, this.ymax, this.xmin, this.ymin];
if (P) P.push(sx0, sy0);
else P = [sx0, sy0];
}
return P;
e0 = e1, e1 = this._edgecode(sx1, sy1);
if (e0 && e1) this._edge(i, e0, e1, P, P.length);
if (P) P.push(sx1, sy1);
else P = [sx1, sy1];
}
_clipSegment(x0, y0, x1, y1, c0, c1) {
while (true) {
if (c0 === 0 && c1 === 0) return [x0, y0, x1, y1];
if (c0 & c1) return null;
let x, y, c = c0 || c1;
if (c & 0b1000) x = x0 + (x1 - x0) * (this.ymax - y0) / (y1 - y0), y = this.ymax;
else if (c & 0b0100) x = x0 + (x1 - x0) * (this.ymin - y0) / (y1 - y0), y = this.ymin;
else if (c & 0b0010) y = y0 + (y1 - y0) * (this.xmax - x0) / (x1 - x0), x = this.xmax;
else y = y0 + (y1 - y0) * (this.xmin - x0) / (x1 - x0), x = this.xmin;
if (c0) x0 = x, y0 = y, c0 = this._regioncode(x0, y0);
else x1 = x, y1 = y, c1 = this._regioncode(x1, y1);
}
}
if (P) {
e0 = e1, e1 = this._edgecode(P[0], P[1]);
if (e0 && e1) this._edge(i, e0, e1, P, P.length);
} else if (this.contains(i, (this.xmin + this.xmax) / 2, (this.ymin + this.ymax) / 2)) {
return [this.xmax, this.ymin, this.xmax, this.ymax, this.xmin, this.ymax, this.xmin, this.ymin];
}
return P;
}
_clipSegment(x0, y0, x1, y1, c0, c1) {
while (true) {
if (c0 === 0 && c1 === 0) return [x0, y0, x1, y1];
if (c0 & c1) return null;
let x, y, c = c0 || c1;
if (c & 0b1000) x = x0 + (x1 - x0) * (this.ymax - y0) / (y1 - y0), y = this.ymax;
else if (c & 0b0100) x = x0 + (x1 - x0) * (this.ymin - y0) / (y1 - y0), y = this.ymin;
else if (c & 0b0010) y = y0 + (y1 - y0) * (this.xmax - x0) / (x1 - x0), x = this.xmax;
else y = y0 + (y1 - y0) * (this.xmin - x0) / (x1 - x0), x = this.xmin;
if (c0) x0 = x, y0 = y, c0 = this._regioncode(x0, y0);
else x1 = x, y1 = y, c1 = this._regioncode(x1, y1);
}
}
_clipInfinite(i, points, vx0, vy0, vxn, vyn) {
let P = Array.from(points), p;
if (p = this._project(P[0], P[1], vx0, vy0)) P.unshift(p[0], p[1]);
if (p = this._project(P[P.length - 2], P[P.length - 1], vxn, vyn)) P.push(p[0], p[1]);
if (P = this._clipFinite(i, P)) {
for (let j = 0, n = P.length, c0, c1 = this._edgecode(P[n - 2], P[n - 1]); j < n; j += 2) {
c0 = c1, c1 = this._edgecode(P[j], P[j + 1]);
if (c0 && c1) j = this._edge(i, c0, c1, P, j), n = P.length;
}
_clipInfinite(i, points, vx0, vy0, vxn, vyn) {
let P = Array.from(points), p;
if (p = this._project(P[0], P[1], vx0, vy0)) P.unshift(p[0], p[1]);
if (p = this._project(P[P.length - 2], P[P.length - 1], vxn, vyn)) P.push(p[0], p[1]);
if (P = this._clipFinite(i, P)) {
for (let j = 0, n = P.length, c0, c1 = this._edgecode(P[n - 2], P[n - 1]); j < n; j += 2) {
c0 = c1, c1 = this._edgecode(P[j], P[j + 1]);
if (c0 && c1) j = this._edge(i, c0, c1, P, j), n = P.length;
}
} else if (this.contains(i, (this.xmin + this.xmax) / 2, (this.ymin + this.ymax) / 2)) {
P = [this.xmin, this.ymin, this.xmax, this.ymin, this.xmax, this.ymax, this.xmin, this.ymax];
}
return P;
} else if (this.contains(i, (this.xmin + this.xmax) / 2, (this.ymin + this.ymax) / 2)) {
P = [this.xmin, this.ymin, this.xmax, this.ymin, this.xmax, this.ymax, this.xmin, this.ymax];
}
return P;
}
_edge(i, e0, e1, P, j) {
while (e0 !== e1) {
let x, y;
switch (e0) {
case 0b0101: e0 = 0b0100; continue; // top-left
case 0b0100: e0 = 0b0110, x = this.xmax, y = this.ymin; break; // top
case 0b0110: e0 = 0b0010; continue; // top-right
case 0b0010: e0 = 0b1010, x = this.xmax, y = this.ymax; break; // right
case 0b1010: e0 = 0b1000; continue; // bottom-right
case 0b1000: e0 = 0b1001, x = this.xmin, y = this.ymax; break; // bottom
case 0b1001: e0 = 0b0001; continue; // bottom-left
case 0b0001: e0 = 0b0101, x = this.xmin, y = this.ymin; break; // left
}
_edge(i, e0, e1, P, j) {
while (e0 !== e1) {
let x, y;
switch (e0) {
case 0b0101: e0 = 0b0100; continue; // top-left
case 0b0100: e0 = 0b0110, x = this.xmax, y = this.ymin; break; // top
case 0b0110: e0 = 0b0010; continue; // top-right
case 0b0010: e0 = 0b1010, x = this.xmax, y = this.ymax; break; // right
case 0b1010: e0 = 0b1000; continue; // bottom-right
case 0b1000: e0 = 0b1001, x = this.xmin, y = this.ymax; break; // bottom
case 0b1001: e0 = 0b0001; continue; // bottom-left
case 0b0001: e0 = 0b0101, x = this.xmin, y = this.ymin; break; // left
}
if ((P[j] !== x || P[j + 1] !== y) && this.contains(i, x, y)) {
P.splice(j, 0, x, y), j += 2;
}
}
return j;
if ((P[j] !== x || P[j + 1] !== y) && this.contains(i, x, y)) {
P.splice(j, 0, x, y), j += 2;
}
_project(x0, y0, vx, vy) {
let t = Infinity, c, x, y;
if (vy < 0) { // top
if (y0 <= this.ymin) return null;
if ((c = (this.ymin - y0) / vy) < t) y = this.ymin, x = x0 + (t = c) * vx;
} else if (vy > 0) { // bottom
if (y0 >= this.ymax) return null;
if ((c = (this.ymax - y0) / vy) < t) y = this.ymax, x = x0 + (t = c) * vx;
}
if (vx > 0) { // right
if (x0 >= this.xmax) return null;
if ((c = (this.xmax - x0) / vx) < t) x = this.xmax, y = y0 + (t = c) * vy;
} else if (vx < 0) { // left
if (x0 <= this.xmin) return null;
if ((c = (this.xmin - x0) / vx) < t) x = this.xmin, y = y0 + (t = c) * vy;
}
return [x, y];
}
_edgecode(x, y) {
return (x === this.xmin ? 0b0001
: x === this.xmax ? 0b0010 : 0b0000)
| (y === this.ymin ? 0b0100
: y === this.ymax ? 0b1000 : 0b0000);
}
_regioncode(x, y) {
return (x < this.xmin ? 0b0001
: x > this.xmax ? 0b0010 : 0b0000)
| (y < this.ymin ? 0b0100
: y > this.ymax ? 0b1000 : 0b0000);
}
}
const tau = 2 * Math.PI;
function pointX(p) {
return p[0];
return j;
}
_project(x0, y0, vx, vy) {
let t = Infinity, c, x, y;
if (vy < 0) { // top
if (y0 <= this.ymin) return null;
if ((c = (this.ymin - y0) / vy) < t) y = this.ymin, x = x0 + (t = c) * vx;
} else if (vy > 0) { // bottom
if (y0 >= this.ymax) return null;
if ((c = (this.ymax - y0) / vy) < t) y = this.ymax, x = x0 + (t = c) * vx;
}
function pointY(p) {
return p[1];
if (vx > 0) { // right
if (x0 >= this.xmax) return null;
if ((c = (this.xmax - x0) / vx) < t) x = this.xmax, y = y0 + (t = c) * vy;
} else if (vx < 0) { // left
if (x0 <= this.xmin) return null;
if ((c = (this.xmin - x0) / vx) < t) x = this.xmin, y = y0 + (t = c) * vy;
}
return [x, y];
}
_edgecode(x, y) {
return (x === this.xmin ? 0b0001
: x === this.xmax ? 0b0010 : 0b0000)
| (y === this.ymin ? 0b0100
: y === this.ymax ? 0b1000 : 0b0000);
}
_regioncode(x, y) {
return (x < this.xmin ? 0b0001
: x > this.xmax ? 0b0010 : 0b0000)
| (y < this.ymin ? 0b0100
: y > this.ymax ? 0b1000 : 0b0000);
}
}
class Delaunay {
constructor(points) {
const {halfedges, hull, triangles} = new Delaunator(points);
this.points = points;
this.halfedges = halfedges;
this.hull = hull;
this.triangles = triangles;
const inedges = this.inedges = new Int32Array(points.length / 2).fill(-1);
const outedges = this.outedges = new Int32Array(points.length / 2).fill(-1);
const tau = 2 * Math.PI;
// Compute an index from each point to an (arbitrary) incoming halfedge.
for (let e = 0, n = halfedges.length; e < n; ++e) {
inedges[triangles[e % 3 === 2 ? e - 2 : e + 1]] = e;
}
function pointX(p) {
return p[0];
}
// For points on the hull, index both the incoming and outgoing halfedges.
let node0, node1 = hull;
do {
node0 = node1, node1 = node1.next;
inedges[node1.i] = node0.t;
outedges[node0.i] = node1.t;
} while (node1 !== hull);
}
voronoi(bounds) {
return new Voronoi(this, bounds);
}
*neighbors(i) {
const {inedges, outedges, halfedges, triangles} = this;
const e0 = inedges[i];
if (e0 === -1) return; // coincident point
let e = e0;
do {
yield triangles[e];
e = e % 3 === 2 ? e - 2 : e + 1;
if (triangles[e] !== i) return; // bad triangulation
e = halfedges[e];
if (e === -1) return yield triangles[outedges[i]];
} while (e !== e0);
}
find(x, y, i = 0) {
if ((x = +x, x !== x) || (y = +y, y !== y)) return -1;
let c;
while ((c = this._step(i, x, y)) >= 0 && c !== i) i = c;
return c;
}
_step(i, x, y) {
const {inedges, points} = this;
if (inedges[i] === -1) return -1; // coincident point
let c = i;
let dc = (x - points[i * 2]) ** 2 + (y - points[i * 2 + 1]) ** 2;
for (const t of this.neighbors(i)) {
const dt = (x - points[t * 2]) ** 2 + (y - points[t * 2 + 1]) ** 2;
if (dt < dc) dc = dt, c = t;
}
return c;
}
render(context) {
const buffer = context == null ? context = new Path : undefined;
const {points, halfedges, triangles} = this;
for (let i = 0, n = halfedges.length; i < n; ++i) {
const j = halfedges[i];
if (j < i) continue;
const ti = triangles[i] * 2;
const tj = triangles[j] * 2;
context.moveTo(points[ti], points[ti + 1]);
context.lineTo(points[tj], points[tj + 1]);
}
this.renderHull(context);
return buffer && buffer.value();
}
renderPoints(context, r = 2) {
const buffer = context == null ? context = new Path : undefined;
const {points} = this;
for (let i = 0, n = points.length; i < n; i += 2) {
const x = points[i], y = points[i + 1];
context.moveTo(x + r, y);
context.arc(x, y, r, 0, tau);
}
return buffer && buffer.value();
}
renderHull(context) {
const buffer = context == null ? context = new Path : undefined;
const {hull} = this;
let node = hull;
context.moveTo(node.x, node.y);
while (node = node.next, node !== hull) context.lineTo(node.x, node.y);
context.closePath();
return buffer && buffer.value();
}
hullPolygon() {
const polygon = new Polygon;
this.renderHull(polygon);
return polygon.value();
}
renderTriangle(i, context) {
const buffer = context == null ? context = new Path : undefined;
const {points, triangles} = this;
const t0 = triangles[i *= 3] * 2;
const t1 = triangles[i + 1] * 2;
const t2 = triangles[i + 2] * 2;
context.moveTo(points[t0], points[t0 + 1]);
context.lineTo(points[t1], points[t1 + 1]);
context.lineTo(points[t2], points[t2 + 1]);
context.closePath();
return buffer && buffer.value();
}
*trianglePolygons() {
const {triangles} = this;
for (let i = 0, n = triangles.length / 3; i < n; ++i) {
yield this.trianglePolygon(i);
}
}
trianglePolygon(i) {
const polygon = new Polygon;
this.renderTriangle(i, polygon);
return polygon.value();
}
}
function pointY(p) {
return p[1];
}
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)));
};
class Delaunay {
constructor(points) {
const {halfedges, hull, triangles} = new Delaunator(points);
this.points = points;
this.halfedges = halfedges;
this.hull = hull;
this.triangles = triangles;
const inedges = this.inedges = new Int32Array(points.length / 2).fill(-1);
const outedges = this.outedges = new Int32Array(points.length / 2).fill(-1);
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;
// Compute an index from each point to an (arbitrary) incoming halfedge.
for (let e = 0, n = halfedges.length; e < n; ++e) {
inedges[triangles[e % 3 === 2 ? e - 2 : e + 1]] = e;
}
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;
}
// For points on the hull, index both the incoming and outgoing halfedges.
let node0, node1 = hull;
do {
node0 = node1, node1 = node1.next;
inedges[node1.i] = node0.t;
outedges[node0.i] = node1.t;
} while (node1 !== hull);
}
voronoi(bounds) {
return new Voronoi(this, bounds);
}
*neighbors(i) {
const {inedges, outedges, halfedges, triangles} = this;
const e0 = inedges[i];
if (e0 === -1) return; // coincident point
let e = e0;
do {
yield triangles[e];
e = e % 3 === 2 ? e - 2 : e + 1;
if (triangles[e] !== i) return; // bad triangulation
e = halfedges[e];
if (e === -1) return yield triangles[outedges[i]];
} while (e !== e0);
}
find(x, y, i = 0) {
if ((x = +x, x !== x) || (y = +y, y !== y)) return -1;
let c;
while ((c = this._step(i, x, y)) >= 0 && c !== i) i = c;
return c;
}
_step(i, x, y) {
const {inedges, points} = this;
if (inedges[i] === -1) return -1; // coincident point
let c = i;
let dc = (x - points[i * 2]) ** 2 + (y - points[i * 2 + 1]) ** 2;
for (const t of this.neighbors(i)) {
const dt = (x - points[t * 2]) ** 2 + (y - points[t * 2 + 1]) ** 2;
if (dt < dc) dc = dt, c = t;
}
return c;
}
render(context) {
const buffer = context == null ? context = new Path : undefined;
const {points, halfedges, triangles} = this;
for (let i = 0, n = halfedges.length; i < n; ++i) {
const j = halfedges[i];
if (j < i) continue;
const ti = triangles[i] * 2;
const tj = triangles[j] * 2;
context.moveTo(points[ti], points[ti + 1]);
context.lineTo(points[tj], points[tj + 1]);
}
this.renderHull(context);
return buffer && buffer.value();
}
renderPoints(context, r = 2) {
const buffer = context == null ? context = new Path : undefined;
const {points} = this;
for (let i = 0, n = points.length; i < n; i += 2) {
const x = points[i], y = points[i + 1];
context.moveTo(x + r, y);
context.arc(x, y, r, 0, tau);
}
return buffer && buffer.value();
}
renderHull(context) {
const buffer = context == null ? context = new Path : undefined;
const {hull} = this;
let node = hull;
context.moveTo(node.x, node.y);
while (node = node.next, node !== hull) context.lineTo(node.x, node.y);
context.closePath();
return buffer && buffer.value();
}
hullPolygon() {
const polygon = new Polygon;
this.renderHull(polygon);
return polygon.value();
}
renderTriangle(i, context) {
const buffer = context == null ? context = new Path : undefined;
const {points, triangles} = this;
const t0 = triangles[i *= 3] * 2;
const t1 = triangles[i + 1] * 2;
const t2 = triangles[i + 2] * 2;
context.moveTo(points[t0], points[t0 + 1]);
context.lineTo(points[t1], points[t1 + 1]);
context.lineTo(points[t2], points[t2 + 1]);
context.closePath();
return buffer && buffer.value();
}
*trianglePolygons() {
const {triangles} = this;
for (let i = 0, n = triangles.length / 3; i < n; ++i) {
yield this.trianglePolygon(i);
}
}
trianglePolygon(i) {
const polygon = new Polygon;
this.renderTriangle(i, polygon);
return polygon.value();
}
}
exports.Delaunay = Delaunay;
exports.Voronoi = Voronoi;
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)));
};
Object.defineProperty(exports, '__esModule', { value: true });
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;
}
}
exports.Delaunay = Delaunay;
exports.Voronoi = Voronoi;
Object.defineProperty(exports, '__esModule', { value: true });
})));

6

dist/d3-delaunay.min.js

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

// https://github.com/d3/d3-delaunay Version 4.1.0. 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,a=1/0,u=-1/0,c=-1/0,f=t.length>>1,x=this.ids=new Uint32Array(f);this.coords=t;for(var g=0;g<f;g++){var d=t[2*g],_=t[2*g+1];d<e&&(e=d),_<a&&(a=_),d>u&&(u=d),_>c&&(c=_),x[g]=g}var y,m,v,p=(e+u)/2,w=(a+c)/2,T=1/0;for(g=0;g<f;g++){var $=i(p,w,t[2*g],t[2*g+1]);$<T&&(y=g,T=$)}for(T=1/0,g=0;g<f;g++)g!==y&&($=i(t[2*y],t[2*y+1],t[2*g],t[2*g+1]))<T&&$>0&&(m=g,T=$);var b=1/0;for(g=0;g<f;g++)if(g!==y&&g!==m){var M=s(t[2*y],t[2*y+1],t[2*m],t[2*m+1],t[2*g],t[2*g+1]);M<b&&(v=g,b=M)}if(b===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(n(t[2*y],t[2*y+1],t[2*m],t[2*m+1],t[2*v],t[2*v+1])<0){var P=m;m=v,v=P}var A=t[2*y],k=t[2*y+1],E=t[2*m],S=t[2*m+1],z=t[2*v],F=t[2*v+1],L=function(t,e,i,n,s,r){var h=(i-=t)*i+(n-=e)*n,l=(s-=t)*s+(r-=e)*r,o=i*r-n*s;return{x:t+.5*(r*h-n*l)/o,y:e+.5*(i*l-s*h)/o}}(A,k,E,S,z,F);for(this._cx=L.x,this._cy=L.y,function t(e,i,n,s,r,h){var a,u,c;if(s-n<=20)for(a=n+1;a<=s;a++){for(c=e[a],u=a-1;u>=n&&l(i,e[u],c,r,h)>0;)e[u+1]=e[u--];e[u+1]=c}else{var f=n+s>>1;for(u=s,o(e,f,a=n+1),l(i,e[n],e[s],r,h)>0&&o(e,n,s),l(i,e[a],e[s],r,h)>0&&o(e,a,s),l(i,e[n],e[a],r,h)>0&&o(e,n,a),c=e[a];;){do{a++}while(l(i,e[a],c,r,h)<0);do{u--}while(l(i,e[u],c,r,h)>0);if(u<a)break;o(e,a,u)}e[n+1]=e[u],e[u]=c,s-a+1>=u-n?(t(e,i,a,s,r,h),t(e,i,n,u-1,r,h)):(t(e,i,n,u-1,r,h),t(e,i,a,s,r,h))}}(x,t,0,x.length-1,L.x,L.y),this._hashSize=Math.ceil(Math.sqrt(f)),this._hash=[],g=0;g<this._hashSize;g++)this._hash[g]=null;var j=this.hull=r(t,y);this._hashEdge(j),j.t=0,j=r(t,m,j),this._hashEdge(j),j.t=1,j=r(t,v,j),this._hashEdge(j),j.t=2;var I,H,K=2*f-5,B=this.triangles=new Uint32Array(3*K),C=this.halfedges=new Int32Array(3*K);this.trianglesLen=0,this._addTriangle(y,m,v,-1,-1,-1);for(var D=0;D<x.length;D++)if(d=t[2*(g=x[D])],_=t[2*g+1],!(d===I&&_===H||(I=d,H=_,d===A&&_===k||d===E&&_===S||d===z&&_===F))){var U,V=this._hashKey(d,_),Z=V;do{U=this._hash[Z],Z=(Z+1)%this._hashSize}while((!U||U.removed)&&Z!==V);for(j=U;n(d,_,j.x,j.y,j.next.x,j.next.y)>=0;)if((j=j.next)===U)throw new Error("Something is wrong with the input points.");var q=j===U,N=this._addTriangle(j.i,g,j.next.i,-1,-1,j.t);j.t=N,(j=r(t,g,j)).t=this._legalize(N+2),j.prev.prev.t===C[N+1]&&(j.prev.prev.t=N+2);for(var O=j.next;n(d,_,O.x,O.y,O.next.x,O.next.y)<0;)N=this._addTriangle(O.i,g,O.next.i,O.prev.t,-1,O.t),O.prev.t=this._legalize(N+2),this.hull=h(O),O=O.next;if(q)for(O=j.prev;n(d,_,O.prev.x,O.prev.y,O.x,O.y)<0;)N=this._addTriangle(O.prev.i,g,O.i,-1,O.t,O.prev.t),this._legalize(N+2),O.prev.t=N,this.hull=h(O),O=O.prev;this._hashEdge(j),this._hashEdge(j.prev)}this.triangles=B.subarray(0,this.trianglesLen),this.halfedges=C.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,l=(s-=t)*s+(r-=e)*r;if(0===h||0===l)return 1/0;var o=i*r-n*s;if(0===o)return 1/0;var a=.5*(r*h-n*l)/o,u=.5*(i*l-s*h)/o;return a*a+u*u}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 l(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 a(t){return t[0]}function u(t){return t[1]}e.from=function(t,i,n){i||(i=a),n||(n=u);for(var s=t.length,r=new Float64Array(2*s),h=0;h<s;h++){var l=t[h];r[2*h]=i(l),r[2*h+1]=n(l)}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,l,o,a,u,c=this.triangles,f=this.coords,x=this.halfedges,g=x[t],d=t-t%3,_=g-g%3,y=d+(t+1)%3,m=d+(t+2)%3,v=_+(g+2)%3,p=c[m],w=c[t],T=c[y],$=c[v];if(e=f[2*p],i=f[2*p+1],n=f[2*w],s=f[2*w+1],r=f[2*T],h=f[2*T+1],l=f[2*$],o=f[2*$+1],a=(n-=l)*n+(s-=o)*s,u=(r-=l)*r+(h-=o)*h,(e-=l)*(s*u-a*h)-(i-=o)*(n*u-a*r)+(e*e+i*i)*(n*h-s*r)<0){c[t]=$,c[g]=p,this._link(t,x[v]),this._link(g,x[m]),this._link(m,v);var b=_+(g+1)%3;return this._legalize(t),this._legalize(b)}return m},_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 c{constructor(){this._x0=this._y0=this._x1=this._y1=null,this._=""}moveTo(t,e){this._+=`M${this._x0=this._x1=+t},${this._y0=this._y1=+e}`}closePath(){null!==this._x1&&(this._x1=this._x0,this._y1=this._y0,this._+="Z")}lineTo(t,e){this._+=`L${this._x1=+t},${this._y1=+e}`}arc(t,e,i){const n=(t=+t)+(i=+i),s=e=+e;if(i<0)throw new Error("negative radius");null===this._x1?this._+=`M${n},${s}`:(Math.abs(this._x1-n)>epsilon||Math.abs(this._y1-s)>epsilon)&&(this._+="L"+n+","+s),i&&(this._+=`A${i},${i},0,1,1,${t-i},${e}A${i},${i},0,1,1,${this._x1=n},${this._y1=s}`)}rect(t,e,i,n){this._+=`M${this._x0=this._x1=+t},${this._y0=this._y1=+e}h${+i}v${+n}h${-i}Z`}value(){return this._||null}}class f{constructor(){this._=[]}moveTo(t,e){this._.push([t,e])}closePath(){this._.push(this._[0].slice())}lineTo(t,e){this._.push([t,e])}value(){return this._.length?this._:null}}class x{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,hull:h,triangles:l}=this.delaunay=t,o=this.circumcenters=new Float64Array(l.length/3*2),a=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=l.length;t<i;t+=3,e+=2){const i=2*l[t],n=2*l[t+1],s=2*l[t+2],h=r[i],a=r[i+1],u=r[n],c=r[n+1],f=r[s],x=r[s+1],g=h-u,d=h-f,_=a-c,y=a-x,m=h*h+a*a,v=m-u*u-c*c,p=m-f*f-x*x,w=2*(d*_-g*y);o[e]=(_*p-y*v)/w,o[e+1]=(d*v-g*p)/w}let u,c,f,x=h,g=4*x.i,d=x.x,_=x.y;do{u=g,c=d,f=_,g=4*(x=x.next).i,d=x.x,_=x.y,a[u+2]=a[g]=f-_,a[u+3]=a[g+1]=d-c}while(x!==h)}render(t){const e=null==t?t=new c:void 0,{delaunay:{halfedges:i,hull:n,triangles:s},circumcenters:r,vectors:h}=this;for(let e=0,n=i.length;e<n;++e){const n=i[e];if(n<e)continue;const s=2*Math.floor(e/3),h=2*Math.floor(n/3),l=r[s],o=r[s+1],a=r[h],u=r[h+1];this._renderSegment(l,o,a,u,t)}let l=n;do{l=l.next;const e=2*Math.floor(l.t/3),i=r[e],n=r[e+1],s=4*l.i,o=this._project(i,n,h[s+2],h[s+3]);o&&this._renderSegment(i,n,o[0],o[1],t)}while(l!==n);return e&&e.value()}renderBounds(t){const e=null==t?t=new c:void 0;return t.rect(this.xmin,this.ymin,this.xmax-this.xmin,this.ymax-this.ymin),e&&e.value()}renderCell(t,e){const i=null==e?e=new c:void 0,n=this._clip(t);if(null!==n){e.moveTo(n[0],n[1]);for(let t=2,i=n.length;t<i;t+=2)e.lineTo(n[t],n[t+1]);return e.closePath(),i&&i.value()}}*cellPolygons(){const{delaunay:{points:t}}=this;for(let e=0,i=t.length/2;e<i;++e){const t=this.cellPolygon(e);t&&(yield t)}}cellPolygon(t){const e=new f;return this.renderCell(t,e),e.value()}_renderSegment(t,e,i,n,s){let r;const h=this._regioncode(t,e),l=this._regioncode(i,n);0===h&&0===l?(s.moveTo(t,e),s.lineTo(i,n)):(r=this._clipSegment(t,e,i,n,h,l))&&(s.moveTo(r[0],r[1]),s.lineTo(r[2],r[3]))}contains(t,e,i){return(e=+e)==e&&(i=+i)==i&&this.delaunay._step(t,e,i)===t}_cell(t){const{circumcenters:e,delaunay:{inedges:i,halfedges:n,triangles:s}}=this,r=i[t];if(-1===r)return null;const h=[];let l=r;do{const i=Math.floor(l/3);if(h.push(e[2*i],e[2*i+1]),s[l=l%3==2?l-2:l+1]!==t)break;l=n[l]}while(l!==r&&-1!==l);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(t,e,i[n],i[n+1],i[n+2],i[n+3]):this._clipFinite(t,e)}_clipFinite(t,e){const i=e.length;let n,s,r,h,l,o=null,a=e[i-2],u=e[i-1],c=this._regioncode(a,u);for(let f=0;f<i;f+=2)if(n=a,s=u,a=e[f],u=e[f+1],r=c,c=this._regioncode(a,u),0===r&&0===c)h=l,l=0,o?o.push(a,u):o=[a,u];else{let e,i,f,x,g;if(0===r){if(null===(e=this._clipSegment(n,s,a,u,r,c)))continue;[i,f,x,g]=e}else{if(null===(e=this._clipSegment(a,u,n,s,c,r)))continue;[x,g,i,f]=e,h=l,l=this._edgecode(i,f),h&&l&&this._edge(t,h,l,o,o.length),o?o.push(i,f):o=[i,f]}h=l,l=this._edgecode(x,g),h&&l&&this._edge(t,h,l,o,o.length),o?o.push(x,g):o=[x,g]}if(o)h=l,l=this._edgecode(o[0],o[1]),h&&l&&this._edge(t,h,l,o,o.length);else if(this.contains(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 null;let h,l,o=s||r;8&o?(h=t+(i-t)*(this.ymax-e)/(n-e),l=this.ymax):4&o?(h=t+(i-t)*(this.ymin-e)/(n-e),l=this.ymin):2&o?(l=e+(n-e)*(this.xmax-t)/(i-t),h=this.xmax):(l=e+(n-e)*(this.xmin-t)/(i-t),h=this.xmin),s?(t=h,e=l,s=this._regioncode(t,e)):(i=h,n=l,r=this._regioncode(i,n))}}_clipInfinite(t,e,i,n,s,r){let h,l=Array.from(e);if((h=this._project(l[0],l[1],i,n))&&l.unshift(h[0],h[1]),(h=this._project(l[l.length-2],l[l.length-1],s,r))&&l.push(h[0],h[1]),l=this._clipFinite(t,l))for(let e,i=0,n=l.length,s=this._edgecode(l[n-2],l[n-1]);i<n;i+=2)e=s,s=this._edgecode(l[i],l[i+1]),e&&s&&(i=this._edge(t,e,s,l,i),n=l.length);else this.contains(t,(this.xmin+this.xmax)/2,(this.ymin+this.ymax)/2)&&(l=[this.xmin,this.ymin,this.xmax,this.ymin,this.xmax,this.ymax,this.xmin,this.ymax]);return l}_edge(t,e,i,n,s){for(;e!==i;){let i,r;switch(e){case 5:e=4;continue;case 4:e=6,i=this.xmax,r=this.ymin;break;case 6:e=2;continue;case 2:e=10,i=this.xmax,r=this.ymax;break;case 10:e=8;continue;case 8:e=9,i=this.xmin,r=this.ymax;break;case 9:e=1;continue;case 1:e=5,i=this.xmin,r=this.ymin}n[s]===i&&n[s+1]===r||!this.contains(t,i,r)||(n.splice(s,0,i,r),s+=2)}return s}_project(t,e,i,n){let s,r,h,l=1/0;if(n<0){if(e<=this.ymin)return null;(s=(this.ymin-e)/n)<l&&(h=this.ymin,r=t+(l=s)*i)}else if(n>0){if(e>=this.ymax)return null;(s=(this.ymax-e)/n)<l&&(h=this.ymax,r=t+(l=s)*i)}if(i>0){if(t>=this.xmax)return null;(s=(this.xmax-t)/i)<l&&(r=this.xmax,h=e+(l=s)*n)}else if(i<0){if(t<=this.xmin)return null;(s=(this.xmin-t)/i)<l&&(r=this.xmin,h=e+(l=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)}}const g=2*Math.PI;class d{constructor(t){const{halfedges:i,hull:n,triangles:s}=new e(t);this.points=t,this.halfedges=i,this.hull=n,this.triangles=s;const r=this.inedges=new Int32Array(t.length/2).fill(-1),h=this.outedges=new Int32Array(t.length/2).fill(-1);for(let t=0,e=i.length;t<e;++t)r[s[t%3==2?t-2:t+1]]=t;let l,o=n;do{l=o,r[(o=o.next).i]=l.t,h[l.i]=o.t}while(o!==n)}voronoi(t){return new x(this,t)}*neighbors(t){const{inedges:e,outedges:i,halfedges:n,triangles:s}=this,r=e[t];if(-1===r)return;let h=r;do{if(yield s[h],s[h=h%3==2?h-2:h+1]!==t)return;if(-1===(h=n[h]))return yield s[i[t]]}while(h!==r)}find(t,e,i=0){if((t=+t)!=t||(e=+e)!=e)return-1;let n;for(;(n=this._step(i,t,e))>=0&&n!==i;)i=n;return n}_step(t,e,i){const{inedges:n,points:s}=this;if(-1===n[t])return-1;let r=t,h=(e-s[2*t])**2+(i-s[2*t+1])**2;for(const n of this.neighbors(t)){const t=(e-s[2*n])**2+(i-s[2*n+1])**2;t<h&&(h=t,r=n)}return r}render(t){const e=null==t?t=new c:void 0,{points:i,halfedges:n,triangles:s}=this;for(let e=0,r=n.length;e<r;++e){const r=n[e];if(r<e)continue;const h=2*s[e],l=2*s[r];t.moveTo(i[h],i[h+1]),t.lineTo(i[l],i[l+1])}return this.renderHull(t),e&&e.value()}renderPoints(t,e=2){const i=null==t?t=new c:void 0,{points:n}=this;for(let i=0,s=n.length;i<s;i+=2){const s=n[i],r=n[i+1];t.moveTo(s+e,r),t.arc(s,r,e,0,g)}return i&&i.value()}renderHull(t){const e=null==t?t=new c:void 0,{hull:i}=this;let n=i;for(t.moveTo(n.x,n.y);(n=n.next)!==i;)t.lineTo(n.x,n.y);return t.closePath(),e&&e.value()}hullPolygon(){const t=new f;return this.renderHull(t),t.value()}renderTriangle(t,e){const i=null==e?e=new c:void 0,{points:n,triangles:s}=this,r=2*s[t*=3],h=2*s[t+1],l=2*s[t+2];return e.moveTo(n[r],n[r+1]),e.lineTo(n[h],n[h+1]),e.lineTo(n[l],n[l+1]),e.closePath(),i&&i.value()}*trianglePolygons(){const{triangles:t}=this;for(let e=0,i=t.length/3;e<i;++e)yield this.trianglePolygon(e)}trianglePolygon(t){const e=new f;return this.renderTriangle(t,e),e.value()}}d.from=function(t,e=function(t){return t[0]},i=function(t){return t[1]},n){return new d("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=d,t.Voronoi=x,Object.defineProperty(t,"__esModule",{value:!0})});
// https://github.com/d3/d3-delaunay v4.1.1 Copyright 2018 Mike Bostock
// https://github.com/mapbox/delaunator v2.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,a=1/0,u=-1/0,c=-1/0,f=t.length>>1,x=this.ids=new Uint32Array(f);this.coords=t;for(var g=0;g<f;g++){var d=t[2*g],_=t[2*g+1];d<e&&(e=d),_<a&&(a=_),d>u&&(u=d),_>c&&(c=_),x[g]=g}var y,m,v,p=(e+u)/2,w=(a+c)/2,T=1/0;for(g=0;g<f;g++){var $=i(p,w,t[2*g],t[2*g+1]);$<T&&(y=g,T=$)}for(T=1/0,g=0;g<f;g++)g!==y&&($=i(t[2*y],t[2*y+1],t[2*g],t[2*g+1]))<T&&$>0&&(m=g,T=$);var b=1/0;for(g=0;g<f;g++)if(g!==y&&g!==m){var M=s(t[2*y],t[2*y+1],t[2*m],t[2*m+1],t[2*g],t[2*g+1]);M<b&&(v=g,b=M)}if(b===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(n(t[2*y],t[2*y+1],t[2*m],t[2*m+1],t[2*v],t[2*v+1])<0){var P=m;m=v,v=P}var A=t[2*y],k=t[2*y+1],E=t[2*m],S=t[2*m+1],z=t[2*v],F=t[2*v+1],L=function(t,e,i,n,s,r){var h=(i-=t)*i+(n-=e)*n,l=(s-=t)*s+(r-=e)*r,o=i*r-n*s;return{x:t+.5*(r*h-n*l)/o,y:e+.5*(i*l-s*h)/o}}(A,k,E,S,z,F);for(this._cx=L.x,this._cy=L.y,function t(e,i,n,s,r,h){var a,u,c;if(s-n<=20)for(a=n+1;a<=s;a++){for(c=e[a],u=a-1;u>=n&&l(i,e[u],c,r,h)>0;)e[u+1]=e[u--];e[u+1]=c}else{var f=n+s>>1;for(u=s,o(e,f,a=n+1),l(i,e[n],e[s],r,h)>0&&o(e,n,s),l(i,e[a],e[s],r,h)>0&&o(e,a,s),l(i,e[n],e[a],r,h)>0&&o(e,n,a),c=e[a];;){do{a++}while(l(i,e[a],c,r,h)<0);do{u--}while(l(i,e[u],c,r,h)>0);if(u<a)break;o(e,a,u)}e[n+1]=e[u],e[u]=c,s-a+1>=u-n?(t(e,i,a,s,r,h),t(e,i,n,u-1,r,h)):(t(e,i,n,u-1,r,h),t(e,i,a,s,r,h))}}(x,t,0,x.length-1,L.x,L.y),this._hashSize=Math.ceil(Math.sqrt(f)),this._hash=[],g=0;g<this._hashSize;g++)this._hash[g]=null;var j=this.hull=r(t,y);this._hashEdge(j),j.t=0,j=r(t,m,j),this._hashEdge(j),j.t=1,j=r(t,v,j),this._hashEdge(j),j.t=2;var I,H,K=2*f-5,B=this.triangles=new Uint32Array(3*K),C=this.halfedges=new Int32Array(3*K);this.trianglesLen=0,this._addTriangle(y,m,v,-1,-1,-1);for(var D=0;D<x.length;D++)if(d=t[2*(g=x[D])],_=t[2*g+1],!(d===I&&_===H||(I=d,H=_,d===A&&_===k||d===E&&_===S||d===z&&_===F))){var U,V=this._hashKey(d,_),Z=V;do{U=this._hash[Z],Z=(Z+1)%this._hashSize}while((!U||U.removed)&&Z!==V);for(j=U;n(d,_,j.x,j.y,j.next.x,j.next.y)>=0;)if((j=j.next)===U)throw new Error("Something is wrong with the input points.");var q=j===U,N=this._addTriangle(j.i,g,j.next.i,-1,-1,j.t);j.t=N,(j=r(t,g,j)).t=this._legalize(N+2),j.prev.prev.t===C[N+1]&&(j.prev.prev.t=N+2);for(var O=j.next;n(d,_,O.x,O.y,O.next.x,O.next.y)<0;)N=this._addTriangle(O.i,g,O.next.i,O.prev.t,-1,O.t),O.prev.t=this._legalize(N+2),this.hull=h(O),O=O.next;if(q)for(O=j.prev;n(d,_,O.prev.x,O.prev.y,O.x,O.y)<0;)N=this._addTriangle(O.prev.i,g,O.i,-1,O.t,O.prev.t),this._legalize(N+2),O.prev.t=N,this.hull=h(O),O=O.prev;this._hashEdge(j),this._hashEdge(j.prev)}this.triangles=B.subarray(0,this.trianglesLen),this.halfedges=C.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,l=(s-=t)*s+(r-=e)*r;if(0===h||0===l)return 1/0;var o=i*r-n*s;if(0===o)return 1/0;var a=.5*(r*h-n*l)/o,u=.5*(i*l-s*h)/o;return a*a+u*u}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 l(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 a(t){return t[0]}function u(t){return t[1]}e.from=function(t,i,n){i||(i=a),n||(n=u);for(var s=t.length,r=new Float64Array(2*s),h=0;h<s;h++){var l=t[h];r[2*h]=i(l),r[2*h+1]=n(l)}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,l,o,a,u,c=this.triangles,f=this.coords,x=this.halfedges,g=x[t],d=t-t%3,_=g-g%3,y=d+(t+1)%3,m=d+(t+2)%3,v=_+(g+2)%3,p=c[m],w=c[t],T=c[y],$=c[v];if(e=f[2*p],i=f[2*p+1],n=f[2*w],s=f[2*w+1],r=f[2*T],h=f[2*T+1],l=f[2*$],o=f[2*$+1],a=(n-=l)*n+(s-=o)*s,u=(r-=l)*r+(h-=o)*h,(e-=l)*(s*u-a*h)-(i-=o)*(n*u-a*r)+(e*e+i*i)*(n*h-s*r)<0){c[t]=$,c[g]=p,this._link(t,x[v]),this._link(g,x[m]),this._link(m,v);var b=_+(g+1)%3;return this._legalize(t),this._legalize(b)}return m},_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}};const c=1e-6;class f{constructor(){this._x0=this._y0=this._x1=this._y1=null,this._=""}moveTo(t,e){this._+=`M${this._x0=this._x1=+t},${this._y0=this._y1=+e}`}closePath(){null!==this._x1&&(this._x1=this._x0,this._y1=this._y0,this._+="Z")}lineTo(t,e){this._+=`L${this._x1=+t},${this._y1=+e}`}arc(t,e,i){const n=(t=+t)+(i=+i),s=e=+e;if(i<0)throw new Error("negative radius");null===this._x1?this._+=`M${n},${s}`:(Math.abs(this._x1-n)>c||Math.abs(this._y1-s)>c)&&(this._+="L"+n+","+s),i&&(this._+=`A${i},${i},0,1,1,${t-i},${e}A${i},${i},0,1,1,${this._x1=n},${this._y1=s}`)}rect(t,e,i,n){this._+=`M${this._x0=this._x1=+t},${this._y0=this._y1=+e}h${+i}v${+n}h${-i}Z`}value(){return this._||null}}class x{constructor(){this._=[]}moveTo(t,e){this._.push([t,e])}closePath(){this._.push(this._[0].slice())}lineTo(t,e){this._.push([t,e])}value(){return this._.length?this._:null}}class g{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,hull:h,triangles:l}=this.delaunay=t,o=this.circumcenters=new Float64Array(l.length/3*2),a=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=l.length;t<i;t+=3,e+=2){const i=2*l[t],n=2*l[t+1],s=2*l[t+2],h=r[i],a=r[i+1],u=r[n],c=r[n+1],f=r[s],x=r[s+1],g=h-u,d=h-f,_=a-c,y=a-x,m=h*h+a*a,v=m-u*u-c*c,p=m-f*f-x*x,w=2*(d*_-g*y);o[e]=(_*p-y*v)/w,o[e+1]=(d*v-g*p)/w}let u,c,f,x=h,g=4*x.i,d=x.x,_=x.y;do{u=g,c=d,f=_,g=4*(x=x.next).i,d=x.x,_=x.y,a[u+2]=a[g]=f-_,a[u+3]=a[g+1]=d-c}while(x!==h)}render(t){const e=null==t?t=new f:void 0,{delaunay:{halfedges:i,hull:n},circumcenters:s,vectors:r}=this;for(let e=0,n=i.length;e<n;++e){const n=i[e];if(n<e)continue;const r=2*Math.floor(e/3),h=2*Math.floor(n/3),l=s[r],o=s[r+1],a=s[h],u=s[h+1];this._renderSegment(l,o,a,u,t)}let h=n;do{h=h.next;const e=2*Math.floor(h.t/3),i=s[e],n=s[e+1],l=4*h.i,o=this._project(i,n,r[l+2],r[l+3]);o&&this._renderSegment(i,n,o[0],o[1],t)}while(h!==n);return e&&e.value()}renderBounds(t){const e=null==t?t=new f:void 0;return t.rect(this.xmin,this.ymin,this.xmax-this.xmin,this.ymax-this.ymin),e&&e.value()}renderCell(t,e){const i=null==e?e=new f:void 0,n=this._clip(t);if(null!==n){e.moveTo(n[0],n[1]);for(let t=2,i=n.length;t<i;t+=2)e.lineTo(n[t],n[t+1]);return e.closePath(),i&&i.value()}}*cellPolygons(){const{delaunay:{points:t}}=this;for(let e=0,i=t.length/2;e<i;++e){const t=this.cellPolygon(e);t&&(yield t)}}cellPolygon(t){const e=new x;return this.renderCell(t,e),e.value()}_renderSegment(t,e,i,n,s){let r;const h=this._regioncode(t,e),l=this._regioncode(i,n);0===h&&0===l?(s.moveTo(t,e),s.lineTo(i,n)):(r=this._clipSegment(t,e,i,n,h,l))&&(s.moveTo(r[0],r[1]),s.lineTo(r[2],r[3]))}contains(t,e,i){return(e=+e)==e&&(i=+i)==i&&this.delaunay._step(t,e,i)===t}_cell(t){const{circumcenters:e,delaunay:{inedges:i,halfedges:n,triangles:s}}=this,r=i[t];if(-1===r)return null;const h=[];let l=r;do{const i=Math.floor(l/3);if(h.push(e[2*i],e[2*i+1]),s[l=l%3==2?l-2:l+1]!==t)break;l=n[l]}while(l!==r&&-1!==l);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(t,e,i[n],i[n+1],i[n+2],i[n+3]):this._clipFinite(t,e)}_clipFinite(t,e){const i=e.length;let n,s,r,h,l,o=null,a=e[i-2],u=e[i-1],c=this._regioncode(a,u);for(let f=0;f<i;f+=2)if(n=a,s=u,a=e[f],u=e[f+1],r=c,c=this._regioncode(a,u),0===r&&0===c)h=l,l=0,o?o.push(a,u):o=[a,u];else{let e,i,f,x,g;if(0===r){if(null===(e=this._clipSegment(n,s,a,u,r,c)))continue;[i,f,x,g]=e}else{if(null===(e=this._clipSegment(a,u,n,s,c,r)))continue;[x,g,i,f]=e,h=l,l=this._edgecode(i,f),h&&l&&this._edge(t,h,l,o,o.length),o?o.push(i,f):o=[i,f]}h=l,l=this._edgecode(x,g),h&&l&&this._edge(t,h,l,o,o.length),o?o.push(x,g):o=[x,g]}if(o)h=l,l=this._edgecode(o[0],o[1]),h&&l&&this._edge(t,h,l,o,o.length);else if(this.contains(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 null;let h,l,o=s||r;8&o?(h=t+(i-t)*(this.ymax-e)/(n-e),l=this.ymax):4&o?(h=t+(i-t)*(this.ymin-e)/(n-e),l=this.ymin):2&o?(l=e+(n-e)*(this.xmax-t)/(i-t),h=this.xmax):(l=e+(n-e)*(this.xmin-t)/(i-t),h=this.xmin),s?(t=h,e=l,s=this._regioncode(t,e)):(i=h,n=l,r=this._regioncode(i,n))}}_clipInfinite(t,e,i,n,s,r){let h,l=Array.from(e);if((h=this._project(l[0],l[1],i,n))&&l.unshift(h[0],h[1]),(h=this._project(l[l.length-2],l[l.length-1],s,r))&&l.push(h[0],h[1]),l=this._clipFinite(t,l))for(let e,i=0,n=l.length,s=this._edgecode(l[n-2],l[n-1]);i<n;i+=2)e=s,s=this._edgecode(l[i],l[i+1]),e&&s&&(i=this._edge(t,e,s,l,i),n=l.length);else this.contains(t,(this.xmin+this.xmax)/2,(this.ymin+this.ymax)/2)&&(l=[this.xmin,this.ymin,this.xmax,this.ymin,this.xmax,this.ymax,this.xmin,this.ymax]);return l}_edge(t,e,i,n,s){for(;e!==i;){let i,r;switch(e){case 5:e=4;continue;case 4:e=6,i=this.xmax,r=this.ymin;break;case 6:e=2;continue;case 2:e=10,i=this.xmax,r=this.ymax;break;case 10:e=8;continue;case 8:e=9,i=this.xmin,r=this.ymax;break;case 9:e=1;continue;case 1:e=5,i=this.xmin,r=this.ymin}n[s]===i&&n[s+1]===r||!this.contains(t,i,r)||(n.splice(s,0,i,r),s+=2)}return s}_project(t,e,i,n){let s,r,h,l=1/0;if(n<0){if(e<=this.ymin)return null;(s=(this.ymin-e)/n)<l&&(h=this.ymin,r=t+(l=s)*i)}else if(n>0){if(e>=this.ymax)return null;(s=(this.ymax-e)/n)<l&&(h=this.ymax,r=t+(l=s)*i)}if(i>0){if(t>=this.xmax)return null;(s=(this.xmax-t)/i)<l&&(r=this.xmax,h=e+(l=s)*n)}else if(i<0){if(t<=this.xmin)return null;(s=(this.xmin-t)/i)<l&&(r=this.xmin,h=e+(l=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)}}const d=2*Math.PI;class _{constructor(t){const{halfedges:i,hull:n,triangles:s}=new e(t);this.points=t,this.halfedges=i,this.hull=n,this.triangles=s;const r=this.inedges=new Int32Array(t.length/2).fill(-1),h=this.outedges=new Int32Array(t.length/2).fill(-1);for(let t=0,e=i.length;t<e;++t)r[s[t%3==2?t-2:t+1]]=t;let l,o=n;do{l=o,r[(o=o.next).i]=l.t,h[l.i]=o.t}while(o!==n)}voronoi(t){return new g(this,t)}*neighbors(t){const{inedges:e,outedges:i,halfedges:n,triangles:s}=this,r=e[t];if(-1===r)return;let h=r;do{if(yield s[h],s[h=h%3==2?h-2:h+1]!==t)return;if(-1===(h=n[h]))return yield s[i[t]]}while(h!==r)}find(t,e,i=0){if((t=+t)!=t||(e=+e)!=e)return-1;let n;for(;(n=this._step(i,t,e))>=0&&n!==i;)i=n;return n}_step(t,e,i){const{inedges:n,points:s}=this;if(-1===n[t])return-1;let r=t,h=(e-s[2*t])**2+(i-s[2*t+1])**2;for(const n of this.neighbors(t)){const t=(e-s[2*n])**2+(i-s[2*n+1])**2;t<h&&(h=t,r=n)}return r}render(t){const e=null==t?t=new f:void 0,{points:i,halfedges:n,triangles:s}=this;for(let e=0,r=n.length;e<r;++e){const r=n[e];if(r<e)continue;const h=2*s[e],l=2*s[r];t.moveTo(i[h],i[h+1]),t.lineTo(i[l],i[l+1])}return this.renderHull(t),e&&e.value()}renderPoints(t,e=2){const i=null==t?t=new f:void 0,{points:n}=this;for(let i=0,s=n.length;i<s;i+=2){const s=n[i],r=n[i+1];t.moveTo(s+e,r),t.arc(s,r,e,0,d)}return i&&i.value()}renderHull(t){const e=null==t?t=new f:void 0,{hull:i}=this;let n=i;for(t.moveTo(n.x,n.y);(n=n.next)!==i;)t.lineTo(n.x,n.y);return t.closePath(),e&&e.value()}hullPolygon(){const t=new x;return this.renderHull(t),t.value()}renderTriangle(t,e){const i=null==e?e=new f:void 0,{points:n,triangles:s}=this,r=2*s[t*=3],h=2*s[t+1],l=2*s[t+2];return e.moveTo(n[r],n[r+1]),e.lineTo(n[h],n[h+1]),e.lineTo(n[l],n[l+1]),e.closePath(),i&&i.value()}*trianglePolygons(){const{triangles:t}=this;for(let e=0,i=t.length/3;e<i;++e)yield this.trianglePolygon(e)}trianglePolygon(t){const e=new x;return this.renderTriangle(t,e),e.value()}}_.from=function(t,e=function(t){return t[0]},i=function(t){return t[1]},n){return new _("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=_,t.Voronoi=g,Object.defineProperty(t,"__esModule",{value:!0})});

18

package.json
{
"name": "d3-delaunay",
"version": "4.1.0",
"version": "4.1.1",
"description": "Compute the Voronoi diagram of a set of two-dimensional points.",

@@ -31,14 +31,14 @@ "keywords": [

"@observablehq/tape": "~0.0.1",
"esm": "^3.0.7",
"rollup": "^0.57.1",
"rollup-plugin-node-resolve": "^3.3.0",
"rollup-plugin-uglify": "^3.0.0",
"eslint": "5",
"esm": "3",
"rollup": "0.64",
"rollup-plugin-node-resolve": "3",
"rollup-plugin-terser": "1",
"tape": "4"
},
"scripts": {
"build": "rm -rf dist && mkdir dist && rollup -c",
"postpublish": "git push && git push --tags && zip -j dist/d3-delaunay.zip -- LICENSE README.md dist/d3-delaunay.js dist/d3-delaunay.min.js",
"prepublishOnly": "yarn build && yarn test",
"test": "tape -r esm 'test/**/*-test.js'"
"test": "tape -r esm 'test/**/*-test.js' && eslint src",
"prepublishOnly": "yarn test && rm -rf dist && rollup -c",
"postpublish": "git push && git push --tags && zip -j dist/${npm_package_name}.zip -- LICENSE README.md dist/${npm_package_name}.js dist/${npm_package_name}.min.js"
}
}

61

README.md

@@ -48,3 +48,3 @@ # d3-delaunay

The half-edge indexes as an Int32Array [*j0*, *j1*, …]. For each index 0 ≤ *i* < *halfedges*.length, there is a half-edge from triangle vertex *j* = *halfedges*[*i*] to triangle vertex *i*. Equivalently, this means that triangle ⌊*i* / 3⌋ is adjacent to triangle ⌊*j* / 3⌋. If *j* is negative, then triangle ⌊*i* / 3⌋ is an exterior triangle on the [convex hull](#delaunay_hull). For example, to render the internal edges of the Delaunay triangulation:
The halfedge indexes as an Int32Array [*j0*, *j1*, …]. For each index 0 ≤ *i* < *halfedges*.length, there is a halfedge from triangle vertex *j* = *halfedges*[*i*] to triangle vertex *i*. Equivalently, this means that triangle ⌊*i* / 3⌋ is adjacent to triangle ⌊*j* / 3⌋. If *j* is negative, then triangle ⌊*i* / 3⌋ is an exterior triangle on the [convex hull](#delaunay_hull). For example, to render the internal edges of the Delaunay triangulation:

@@ -56,6 +56,6 @@ ```js

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]);
const ti = triangles[i];
const tj = triangles[j];
context.moveTo(points[ti * 2], points[ti * 2 + 1]);
context.lineTo(points[tj * 2], points[tj * 2 + 1]);
}

@@ -68,4 +68,11 @@ ```

TODO …
An arbitrary *node* on the convex hull. The convex hull is represented as a linked list of nodes, which each *node* being an object with the following properties:
* *node*.i - the index of the associated point
* *node*.x - the *x*-coordinate of the associated point
* *node*.y - the *y*-coordinate of the associated point
* *node*.t - the index of the (incoming or outgoing?) associated halfedge
* *node*.next - the next *node* on the hull
* *node*.prev - the previous *node* on the hull
See also [*delaunay*.renderHull](#delaunay_renderHull).

@@ -75,12 +82,12 @@

The triangle vertex indexes as an Int32Array [*i0*, *j0*, *k0*, *i1*, *j1*, *k1*, …]. Each contiguous triplet of indexes *i*, *j*, *k* forms a counterclockwise triangle. The coordinates of the triangle’s points can be found by going through [*delaunay*.points](#delaunay_points). For example, to render triangle *i*:
The triangle vertex indexes as an Uint32Array [*i0*, *j0*, *k0*, *i1*, *j1*, *k1*, …]. Each contiguous triplet of indexes *i*, *j*, *k* forms a counterclockwise triangle. The coordinates of the triangle’s points can be found by going through [*delaunay*.points](#delaunay_points). For example, to render triangle *i*:
```js
const {points, triangles} = delaunay;
const t0 = triangles[i * 3 + 0] * 2;
const t1 = triangles[i * 3 + 1] * 2;
const t2 = triangles[i * 3 + 2] * 2;
context.moveTo(points[t0], points[t0 + 1]);
context.lineTo(points[t1], points[t1 + 1]);
context.lineTo(points[t2], points[t2 + 1]);
const t0 = triangles[i * 3 + 0];
const t1 = triangles[i * 3 + 1];
const t2 = triangles[i * 3 + 2];
context.moveTo(points[t0 * 2], points[t0 * 2 + 1]);
context.lineTo(points[t1 * 2], points[t1 * 2 + 1]);
context.lineTo(points[t2 * 2], points[t2 * 2 + 1]);
context.closePath();

@@ -93,7 +100,7 @@ ```

TODO …
The incoming halfedge indexes as a Int32Array [*e0*, *e1*, *e2*, …]. For each point *i*, *inedges*[*i*] is the halfedge index *e* of an incoming halfedge. For coincident points, the halfedge index is -1; for points on the convex hull, the incoming halfedge is on the convex hull; for other points, the choice of incoming halfedge is arbitrary. The *inedges* table can be used to traverse the Delaunay triangulation; see also [*delaunay*.neighbors](#delaunay_neighbors).
<a href="#delaunay_outedges" name="delaunay_outedges">#</a> <i>delaunay</i>.<b>outedges</b>
TODO …
The outgoing halfedge indexes as a Int32Array [*e0*, *e1*, *e2*, …]. For each point *i* on the convex hull, *outedges*[*i*] is the halfedge index *e* of the corresponding outgoing halfedge; for other points, the halfedge index is -1. The *outedges* table can be used to traverse the Delaunay triangulation; see also [*delaunay*.neighbors](#delaunay_neighbors).

@@ -104,2 +111,6 @@ <a href="#delaunay_find" name="delaunay_find">#</a> <i>delaunay</i>.<b>find</b>(<i>x</i>, <i>y</i>[, <i>i</i>]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js "Source")

<a href="#delaunay_neighbors" name="delaunay_neighbors">#</a> <i>delaunay</i>.<b>neighbors</b>(<i>i</i>) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js "Source")
Returns an iterable over the indexes of the neighboring points to the specified point *i*. The iterable is empty if *i* is a coincident point.
<a href="#delaunay_render" name="delaunay_render">#</a> <i>delaunay</i>.<b>render</b>([<i>context</i>]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js "Source")

@@ -127,2 +138,14 @@

<a href="#delaunay_hullPolygon" name="delaunay_hullPolygon">#</a> <i>delaunay</i>.<b>hullPolygon()</b> [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js "Source")
Returns the closed polygon [[*x0*, *y0*], [*x1*, *y1*], …, [*x0*, *y0*]] representing the convex hull.
<a href="#delaunay_trianglePolygons" name="delaunay_trianglePolygons">#</a> <i>delaunay</i>.<b>trianglePolygons()</b> [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js "Source")
Returns an iterable over the [polygons for each triangle](#delaunay_trianglePolygon), in order.
<a href="#delaunay_trianglePolygon" name="delaunay_trianglePolygon">#</a> <i>delaunay</i>.<b>trianglePolygon(<i>i</i>)</b> [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js "Source")
Returns the closed polygon [[*x0*, *y0*], [*x1*, *y1*], [*x2*, *y2*], [*x0*, *y0*]] representing the triangle *i*.
<a href="#delaunay_voronoi" name="delaunay_voronoi">#</a> <i>delaunay</i>.<b>voronoi</b>([<i>bounds</i>]) [<>](https://github.com/d3/d3-delaunay/blob/master/src/delaunay.js "Source")

@@ -174,1 +197,9 @@

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). If a *context* is not specified, an SVG path string is returned instead.
<a href="#voronoi_cellPolygons" name="voronoi_cellPolygons">#</a> <i>voronoi</i>.<b>cellPolygons</b>() [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js "Source")
Returns an iterable over the [polygons for each cell](#voronoi_cellPolygon), in order.
<a href="#voronoi_cellPolygon" name="voronoi_cellPolygon">#</a> <i>voronoi</i>.<b>cellPolygon</b>(<i>i</i>) [<>](https://github.com/d3/d3-delaunay/blob/master/src/voronoi.js "Source")
Returns the convex, closed polygon [[*x0*, *y0*], [*x1*, *y1*], …, [*x0*, *y0*]] representing the cell for the specified point *i*.

51

rollup.config.js
import noderesolve from "rollup-plugin-node-resolve";
import uglify from "rollup-plugin-uglify";
import {terser} from "rollup-plugin-terser";
import * as meta from "./package.json";
const definition = require("./package.json");
const name = definition.name;
const banner = `// ${definition.homepage} Version ${definition.version}. Copyright 2018 Observable, Inc.
// https://github.com/mapbox/delaunator Version ${require("delaunator/package.json").version}. Copyright 2017, Mapbox, Inc.`;
const config = (file, ...plugins) => ({
const config = {
input: "src/index.js",
plugins: [
noderesolve(),
...plugins
],
external: Object.keys(meta.dependencies || {}).filter(key => /^d3-/.test(key)),
output: {
banner,
file: `dist/${meta.name}.js`,
name: "d3",
format: "umd",
indent: false,
extend: true,
file: `dist/${file}`,
format: "umd",
name: "d3"
}
});
banner: `// ${meta.homepage} v${meta.version} Copyright ${(new Date).getFullYear()} ${meta.author.name}
// https://github.com/mapbox/delaunator v${require("delaunator/package.json").version}. Copyright 2017 Mapbox, Inc.`,
globals: Object.assign({}, ...Object.keys(meta.dependencies || {}).filter(key => /^d3-/.test(key)).map(key => ({[key]: "d3"})))
},
plugins: [
noderesolve()
]
};
export default [
config(`${name}.js`),
config(`${name}.min.js`, uglify({output: {preamble: banner}}))
config,
{
...config,
output: {
...config.output,
file: `dist/${meta.name}.min.js`
},
plugins: [
...config.plugins,
terser({
output: {
preamble: config.output.banner
}
})
]
}
];

2

src/path.js

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

const epsilon = 1e-6;
export default class Path {

@@ -2,0 +4,0 @@ constructor() {

2

src/voronoi.js

@@ -49,3 +49,3 @@ import Path from "./path.js";

const buffer = context == null ? context = new Path : undefined;
const {delaunay: {halfedges, hull, triangles}, circumcenters, vectors} = this;
const {delaunay: {halfedges, hull}, circumcenters, vectors} = this;
for (let i = 0, n = halfedges.length; i < n; ++i) {

@@ -52,0 +52,0 @@ const j = halfedges[i];

yarn-error.log
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