d3-delaunay - npm Package Compare versions

Comparing version 4.1.1 to 4.1.2

dist/d3-delaunay.js

@@ -1,3 +0,3 @@
-// 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.
+// https://github.com/d3/d3-delaunay v4.1.2 Copyright 2018 Mike Bostock
+// https://github.com/mapbox/delaunator v2.0.2. Copyright 2017 Mapbox, Inc.
 (function (global, factory) {
@@ -9,250 +9,259 @@ typeof exports === 'object' && typeof module !== 'undefined' ? factory(exports) :
 
-Delaunator.from = function (points, getX, getY) {
-    if (!getX) getX = defaultGetX;
-    if (!getY) getY = defaultGetY;
+class Delaunator {
 
-    var n = points.length;
-    var coords = new Float64Array(n * 2);
+    static from(points, getX, getY) {
+        if (!getX) getX = defaultGetX;
+        if (!getY) getY = defaultGetY;
 
-    for (var i = 0; i < n; i++) {
-        var p = points[i];
-        coords[2 * i] = getX(p);
-        coords[2 * i + 1] = getY(p);
+        const n = points.length;
+        const coords = new Float64Array(n * 2);
+
+        for (let i = 0; i < n; i++) {
+            const p = points[i];
+            coords[2 * i] = getX(p);
+            coords[2 * i + 1] = getY(p);
+        }
+
+        return new Delaunator(coords);
     }
 
-    return new Delaunator(coords);
-};
+    constructor(coords) {
+        let minX = Infinity;
+        let minY = Infinity;
+        let maxX = -Infinity;
+        let maxY = -Infinity;
 
-function Delaunator(coords) {
-    if (!ArrayBuffer.isView(coords)) throw new Error('Expected coords to be a typed array.');
+        const n = coords.length >> 1;
+        const ids = this.ids = new Uint32Array(n);
 
-    var minX = Infinity;
-    var minY = Infinity;
-    var maxX = -Infinity;
-    var maxY = -Infinity;
+        if (n > 0 && typeof coords[0] !== 'number') throw new Error('Expected coords to contain numbers.');
 
-    var n = coords.length >> 1;
-    var ids = this.ids = new Uint32Array(n);
+        this.coords = coords;
 
-    this.coords = coords;
+        for (let i = 0; i < n; i++) {
+            const x = coords[2 * i];
+            const y = coords[2 * i + 1];
+            if (x < minX) minX = x;
+            if (y < minY) minY = y;
+            if (x > maxX) maxX = x;
+            if (y > maxY) maxY = y;
+            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;
-    }
+        const cx = (minX + maxX) / 2;
+        const cy = (minY + maxY) / 2;
 
-    var cx = (minX + maxX) / 2;
-    var cy = (minY + maxY) / 2;
+        let minDist = Infinity;
+        let 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 (let i = 0; i < n; i++) {
+            const d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]);
+            if (d < minDist) {
+                i0 = i;
+                minDist = d;
+            }
         }
-    }
 
-    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 (let i = 0; i < n; i++) {
+            if (i === i0) continue;
+            const 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;
+        let 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 (let 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]);
+            const 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;
-    }
+            const 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];
+        const i0x = coords[2 * i0];
+        const i0y = coords[2 * i0 + 1];
+        const i1x = coords[2 * i1];
+        const i1y = coords[2 * i1 + 1];
+        const i2x = coords[2 * i2];
+        const i2y = coords[2 * i2 + 1];
 
-    var center = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y);
-    this._cx = center.x;
-    this._cy = center.y;
+        const 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 (let 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
+        let 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);
+        const maxTriangles = 2 * n - 5;
+        const triangles = this.triangles = new Uint32Array(maxTriangles * 3);
+        const 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];
+        for (let k = 0, xp, yp; k < ids.length; k++) {
+            const i = ids[k];
+            const x = coords[2 * i];
+            const 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
+            const startKey = this._hashKey(x, y);
+            let key = startKey;
+            let 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;
+            const 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
+            let 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);
 
-        // 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;
+            // walk forward through the hull, adding more triangles and flipping recursively
+            let 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.prev;
+                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;
+                }
+            }
+
+            // 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 = {
-
-    _hashEdge: function (e) {
+    _hashEdge(e) {
         this._hash[this._hashKey(e.x, e.y)] = e;
-    },
+    }
 
-    _hashKey: function (x, y) {
-        var dx = x - this._cx;
-        var dy = y - this._cy;
+    _hashKey(x, y) {
+        const dx = x - this._cx;
+        const 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));
+        const 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(a) {
+        const {triangles, coords, halfedges} = this;
 
-        var b = halfedges[a];
+        const b = halfedges[a];
 
-        var a0 = a - a % 3;
-        var b0 = b - b % 3;
+        /* if the pair of triangles doesn't satisfy the Delaunay condition
+         * (p1 is inside the circumcircle of [p0, pl, pr]), flip them,
+         * then do the same check/flip recursively for the new pair of triangles
+         *
+         *           pl                    pl
+         *          /||\                  /  \
+         *       al/ || \bl            al/    \a
+         *        /  ||  \              /      \
+         *       /  a||b  \    flip    /___ar___\
+         *     p0\   ||   /p1   =>   p0\---bl---/p1
+         *        \  ||  /              \      /
+         *       ar\ || /br             b\    /br
+         *          \||/                  \  /
+         *           pr                    pr
+         */
+        const a0 = a - a % 3;
+        const b0 = b - b % 3;
 
-        var al = a0 + (a + 1) % 3;
-        var ar = a0 + (a + 2) % 3;
-        var bl = b0 + (b + 2) % 3;
+        const al = a0 + (a + 1) % 3;
+        const ar = a0 + (a + 2) % 3;
+        const bl = b0 + (b + 2) % 3;
 
-        var p0 = triangles[ar];
-        var pr = triangles[a];
-        var pl = triangles[al];
-        var p1 = triangles[bl];
+        const p0 = triangles[ar];
+        const pr = triangles[a];
+        const pl = triangles[al];
+        const p1 = triangles[bl];
 
-        var illegal = inCircle(
+        const illegal = inCircle(
             coords[2 * p0], coords[2 * p0 + 1],
@@ -267,7 +276,20 @@ coords[2 * pr], coords[2 * pr + 1],
 
-            this._link(a, halfedges[bl]);
+            const hbl = halfedges[bl];
+
+            // edge swapped on the other side of the hull (rare); fix the halfedge reference
+            if (hbl === -1) {
+                let e = this.hull;
+                do {
+                    if (e.t === bl) {
+                        e.t = a;
+                        break;
+                    }
+                    e = e.next;
+                } while (e !== this.hull);
+            }
+            this._link(a, hbl);
             this._link(b, halfedges[ar]);
             this._link(ar, bl);
 
-            var br = b0 + (b + 1) % 3;
+            const br = b0 + (b + 1) % 3;
 
@@ -279,12 +301,12 @@ this._legalize(a);
         return ar;
-    },
+    }
 
-    _link: function (a, b) {
+    _link(a, b) {
         this.halfedges[a] = b;
         if (b !== -1) this.halfedges[b] = a;
-    },
+    }
 
     // add a new triangle given vertex indices and adjacent half-edge ids
-    _addTriangle: function (i0, i1, i2, a, b, c) {
-        var t = this.trianglesLen;
+    _addTriangle(i0, i1, i2, a, b, c) {
+        const t = this.trianglesLen;
 
@@ -303,7 +325,7 @@ this.triangles[t] = i0;
     }
-};
+}
 
 function dist(ax, ay, bx, by) {
-    var dx = ax - bx;
-    var dy = ay - by;
+    const dx = ax - bx;
+    const dy = ay - by;
     return dx * dx + dy * dy;
@@ -317,56 +339,48 @@ }
 function inCircle(ax, ay, bx, by, cx, cy, px, py) {
-    ax -= px;
-    ay -= py;
-    bx -= px;
-    by -= py;
-    cx -= px;
-    cy -= py;
+    const dx = ax - px;
+    const dy = ay - py;
+    const ex = bx - px;
+    const ey = by - py;
+    const fx = cx - px;
+    const fy = cy - py;
 
-    var ap = ax * ax + ay * ay;
-    var bp = bx * bx + by * by;
-    var cp = cx * cx + cy * cy;
+    const ap = dx * dx + dy * dy;
+    const bp = ex * ex + ey * ey;
+    const cp = fx * fx + fy * fy;
 
-    return ax * (by * cp - bp * cy) -
-           ay * (bx * cp - bp * cx) +
-           ap * (bx * cy - by * cx) < 0;
+    return dx * (ey * cp - bp * fy) -
+           dy * (ex * cp - bp * fx) +
+           ap * (ex * fy - ey * fx) < 0;
 }
 
 function circumradius(ax, ay, bx, by, cx, cy) {
-    bx -= ax;
-    by -= ay;
-    cx -= ax;
-    cy -= ay;
+    const dx = bx - ax;
+    const dy = by - ay;
+    const ex = cx - ax;
+    const ey = cy - ay;
 
-    var bl = bx * bx + by * by;
-    var cl = cx * cx + cy * cy;
+    const bl = dx * dx + dy * dy;
+    const cl = ex * ex + ey * ey;
+    const d = dx * ey - dy * ex;
 
-    if (bl === 0 || cl === 0) return Infinity;
+    const x = (ey * bl - dy * cl) * 0.5 / d;
+    const y = (dx * cl - ex * bl) * 0.5 / d;
 
-    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;
-
-    return x * x + y * y;
+    return bl && cl && d && (x * x + y * y) || Infinity;
 }
 
 function circumcenter(ax, ay, bx, by, cx, cy) {
-    bx -= ax;
-    by -= ay;
-    cx -= ax;
-    cy -= ay;
+    const dx = bx - ax;
+    const dy = by - ay;
+    const ex = cx - ax;
+    const ey = cy - ay;
 
-    var bl = bx * bx + by * by;
-    var cl = cx * cx + cy * cy;
+    const bl = dx * dx + dy * dy;
+    const cl = ex * ex + ey * ey;
+    const d = dx * ey - dy * ex;
 
-    var d = bx * cy - by * cx;
+    const x = ax + (ey * bl - dy * cl) * 0.5 / d;
+    const y = ay + (dx * cl - ex * 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, y};
 }
@@ -376,4 +390,4 @@
 function insertNode(coords, i, prev) {
-    var node = {
-        i: i,
+    const node = {
+        i,
         x: coords[2 * i],
@@ -408,3 +422,3 @@ y: coords[2 * i + 1],
 function quicksort(ids, coords, left, right, cx, cy) {
-    var i, j, temp;
+    let i, j, temp;
 
@@ -419,3 +433,3 @@ if (right - left <= 20) {
     } else {
-        var median = (left + right) >> 1;
+        const median = (left + right) >> 1;
         i = left + 1;
@@ -449,4 +463,4 @@ j = right;
 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);
+    const d1 = dist(coords[2 * i], coords[2 * i + 1], cx, cy);
+    const 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]);
@@ -456,3 +470,3 @@ }
 function swap(arr, i, j) {
-    var tmp = arr[i];
+    const tmp = arr[i];
     arr[i] = arr[j];
@@ -459,0 +473,0 @@ arr[j] = tmp;

dist/d3-delaunay.min.js

@@ -1,3 +0,3 @@
-// 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})});
+// https://github.com/d3/d3-delaunay v4.1.2 Copyright 2018 Mike Bostock
+// https://github.com/mapbox/delaunator v2.0.2. 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";class e{static from(t,i,n){i||(i=a),n||(n=c);const s=t.length,h=new Float64Array(2*s);for(let e=0;e<s;e++){const s=t[e];h[2*e]=i(s),h[2*e+1]=n(s)}return new e(h)}constructor(t){let e=1/0,a=1/0,c=-1/0,u=-1/0;const f=t.length>>1,x=this.ids=new Uint32Array(f);if(f>0&&"number"!=typeof t[0])throw new Error("Expected coords to contain numbers.");this.coords=t;for(let i=0;i<f;i++){const n=t[2*i],s=t[2*i+1];n<e&&(e=n),s<a&&(a=s),n>c&&(c=n),s>u&&(u=s),x[i]=i}const g=(e+c)/2,d=(a+u)/2;let _,y,m,p=1/0;for(let e=0;e<f;e++){const n=i(g,d,t[2*e],t[2*e+1]);n<p&&(_=e,p=n)}p=1/0;for(let e=0;e<f;e++){if(e===_)continue;const n=i(t[2*_],t[2*_+1],t[2*e],t[2*e+1]);n<p&&n>0&&(y=e,p=n)}let v=1/0;for(let e=0;e<f;e++){if(e===_||e===y)continue;const i=s(t[2*_],t[2*_+1],t[2*y],t[2*y+1],t[2*e],t[2*e+1]);i<v&&(m=e,v=i)}if(v===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(n(t[2*_],t[2*_+1],t[2*y],t[2*y+1],t[2*m],t[2*m+1])<0){const t=y;y=m,m=t}const w=t[2*_],T=t[2*_+1],b=t[2*y],$=t[2*y+1],M=t[2*m],P=t[2*m+1],k=function(t,e,i,n,s,h){const r=i-t,l=n-e,o=s-t,a=h-e,c=r*r+l*l,u=o*o+a*a,f=r*a-l*o;return{x:t+.5*(a*c-l*u)/f,y:e+.5*(r*u-o*c)/f}}(w,T,b,$,M,P);this._cx=k.x,this._cy=k.y,function t(e,i,n,s,h,r){let a,c,u;if(s-n<=20)for(a=n+1;a<=s;a++){for(u=e[a],c=a-1;c>=n&&l(i,e[c],u,h,r)>0;)e[c+1]=e[c--];e[c+1]=u}else{const f=n+s>>1;for(c=s,o(e,f,a=n+1),l(i,e[n],e[s],h,r)>0&&o(e,n,s),l(i,e[a],e[s],h,r)>0&&o(e,a,s),l(i,e[n],e[a],h,r)>0&&o(e,n,a),u=e[a];;){do{a++}while(l(i,e[a],u,h,r)<0);do{c--}while(l(i,e[c],u,h,r)>0);if(c<a)break;o(e,a,c)}e[n+1]=e[c],e[c]=u,s-a+1>=c-n?(t(e,i,a,s,h,r),t(e,i,n,c-1,h,r)):(t(e,i,n,c-1,h,r),t(e,i,a,s,h,r))}}(x,t,0,x.length-1,k.x,k.y),this._hashSize=Math.ceil(Math.sqrt(f)),this._hash=[];for(let t=0;t<this._hashSize;t++)this._hash[t]=null;let A=this.hull=h(t,_);this._hashEdge(A),A.t=0,A=h(t,y,A),this._hashEdge(A),A.t=1,A=h(t,m,A),this._hashEdge(A),A.t=2;const E=2*f-5,S=this.triangles=new Uint32Array(3*E),z=this.halfedges=new Int32Array(3*E);this.trianglesLen=0,this._addTriangle(_,y,m,-1,-1,-1);for(let e,i,s=0;s<x.length;s++){const l=x[s],o=t[2*l],a=t[2*l+1];if(o===e&&a===i)continue;if(e=o,i=a,o===w&&a===T||o===b&&a===$||o===M&&a===P)continue;const c=this._hashKey(o,a);let u,f=c;do{u=this._hash[f],f=(f+1)%this._hashSize}while((!u||u.removed)&&f!==c);for(A=u;n(o,a,A.x,A.y,A.next.x,A.next.y)>=0;)if((A=A.next)===u)throw new Error("Something is wrong with the input points.");const g=A===u;let d=this._addTriangle(A.i,l,A.next.i,-1,-1,A.t);A.t=d,(A=h(t,l,A)).t=this._legalize(d+2);let _=A.next;for(;n(o,a,_.x,_.y,_.next.x,_.next.y)<0;)d=this._addTriangle(_.i,l,_.next.i,_.prev.t,-1,_.t),_.prev.t=this._legalize(d+2),this.hull=r(_),_=_.next;if(g)for(_=A.prev;n(o,a,_.prev.x,_.prev.y,_.x,_.y)<0;)d=this._addTriangle(_.prev.i,l,_.i,-1,_.t,_.prev.t),this._legalize(d+2),_.prev.t=d,this.hull=r(_),_=_.prev;this._hashEdge(A),this._hashEdge(A.prev)}this.triangles=S.subarray(0,this.trianglesLen),this.halfedges=z.subarray(0,this.trianglesLen)}_hashEdge(t){this._hash[this._hashKey(t.x,t.y)]=t}_hashKey(t,e){const 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(t){const{triangles:e,coords:i,halfedges:n}=this,s=n[t],h=t-t%3,r=s-s%3,l=h+(t+1)%3,o=h+(t+2)%3,a=r+(s+2)%3,c=e[o],u=e[t],f=e[l],x=e[a];if(function(t,e,i,n,s,h,r,l){const o=t-r,a=e-l,c=i-r,u=n-l,f=s-r,x=h-l,g=c*c+u*u,d=f*f+x*x;return o*(u*d-g*x)-a*(c*d-g*f)+(o*o+a*a)*(c*x-u*f)<0}(i[2*c],i[2*c+1],i[2*u],i[2*u+1],i[2*f],i[2*f+1],i[2*x],i[2*x+1])){e[t]=x,e[s]=c;const i=n[a];if(-1===i){let e=this.hull;do{if(e.t===a){e.t=t;break}e=e.next}while(e!==this.hull)}this._link(t,i),this._link(s,n[o]),this._link(o,a);const h=r+(s+1)%3;return this._legalize(t),this._legalize(h)}return o}_link(t,e){this.halfedges[t]=e,-1!==e&&(this.halfedges[e]=t)}_addTriangle(t,e,i,n,s,h){const r=this.trianglesLen;return this.triangles[r]=t,this.triangles[r+1]=e,this.triangles[r+2]=i,this._link(r,n),this._link(r+1,s),this._link(r+2,h),this.trianglesLen+=3,r}}function i(t,e,i,n){const s=t-i,h=e-n;return s*s+h*h}function n(t,e,i,n,s,h){return(n-e)*(s-i)-(i-t)*(h-n)}function s(t,e,i,n,s,h){const r=i-t,l=n-e,o=s-t,a=h-e,c=r*r+l*l,u=o*o+a*a,f=r*a-l*o,x=.5*(a*c-l*u)/f,g=.5*(r*u-o*c)/f;return c&&u&&f&&x*x+g*g||1/0}function h(t,e,i){const 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 r(t){return t.prev.next=t.next,t.next.prev=t.prev,t.removed=!0,t.prev}function l(t,e,n,s,h){return i(t[2*e],t[2*e+1],s,h)-i(t[2*n],t[2*n+1],s,h)||t[2*e]-t[2*n]||t[2*e+1]-t[2*n+1]}function o(t,e,i){const n=t[e];t[e]=t[i],t[i]=n}function a(t){return t[0]}function c(t){return t[1]}const u=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)>u||Math.abs(this._y1-s)>u)&&(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:h,hull:r,triangles:l}=this.delaunay=t,o=this.circumcenters=new Float64Array(l.length/3*2),a=this.vectors=new Float64Array(2*h.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],r=h[i],a=h[i+1],c=h[n],u=h[n+1],f=h[s],x=h[s+1],g=r-c,d=r-f,_=a-u,y=a-x,m=r*r+a*a,p=m-c*c-u*u,v=m-f*f-x*x,w=2*(d*_-g*y);o[e]=(_*v-y*p)/w,o[e+1]=(d*p-g*v)/w}let c,u,f,x=r,g=4*x.i,d=x.x,_=x.y;do{c=g,u=d,f=_,g=4*(x=x.next).i,d=x.x,_=x.y,a[c+2]=a[g]=f-_,a[c+3]=a[g+1]=d-u}while(x!==r)}render(t){const e=null==t?t=new f:void 0,{delaunay:{halfedges:i,hull:n},circumcenters:s,vectors:h}=this;for(let e=0,n=i.length;e<n;++e){const n=i[e];if(n<e)continue;const h=2*Math.floor(e/3),r=2*Math.floor(n/3),l=s[h],o=s[h+1],a=s[r],c=s[r+1];this._renderSegment(l,o,a,c,t)}let r=n;do{r=r.next;const e=2*Math.floor(r.t/3),i=s[e],n=s[e+1],l=4*r.i,o=this._project(i,n,h[l+2],h[l+3]);o&&this._renderSegment(i,n,o[0],o[1],t)}while(r!==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 h;const r=this._regioncode(t,e),l=this._regioncode(i,n);0===r&&0===l?(s.moveTo(t,e),s.lineTo(i,n)):(h=this._clipSegment(t,e,i,n,r,l))&&(s.moveTo(h[0],h[1]),s.lineTo(h[2],h[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,h=i[t];if(-1===h)return null;const r=[];let l=h;do{const i=Math.floor(l/3);if(r.push(e[2*i],e[2*i+1]),s[l=l%3==2?l-2:l+1]!==t)break;l=n[l]}while(l!==h&&-1!==l);return r}_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,h,r,l,o=null,a=e[i-2],c=e[i-1],u=this._regioncode(a,c);for(let f=0;f<i;f+=2)if(n=a,s=c,a=e[f],c=e[f+1],h=u,u=this._regioncode(a,c),0===h&&0===u)r=l,l=0,o?o.push(a,c):o=[a,c];else{let e,i,f,x,g;if(0===h){if(null===(e=this._clipSegment(n,s,a,c,h,u)))continue;[i,f,x,g]=e}else{if(null===(e=this._clipSegment(a,c,n,s,u,h)))continue;[x,g,i,f]=e,r=l,l=this._edgecode(i,f),r&&l&&this._edge(t,r,l,o,o.length),o?o.push(i,f):o=[i,f]}r=l,l=this._edgecode(x,g),r&&l&&this._edge(t,r,l,o,o.length),o?o.push(x,g):o=[x,g]}if(o)r=l,l=this._edgecode(o[0],o[1]),r&&l&&this._edge(t,r,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,h){for(;;){if(0===s&&0===h)return[t,e,i,n];if(s&h)return null;let r,l,o=s||h;8&o?(r=t+(i-t)*(this.ymax-e)/(n-e),l=this.ymax):4&o?(r=t+(i-t)*(this.ymin-e)/(n-e),l=this.ymin):2&o?(l=e+(n-e)*(this.xmax-t)/(i-t),r=this.xmax):(l=e+(n-e)*(this.xmin-t)/(i-t),r=this.xmin),s?(t=r,e=l,s=this._regioncode(t,e)):(i=r,n=l,h=this._regioncode(i,n))}}_clipInfinite(t,e,i,n,s,h){let r,l=Array.from(e);if((r=this._project(l[0],l[1],i,n))&&l.unshift(r[0],r[1]),(r=this._project(l[l.length-2],l[l.length-1],s,h))&&l.push(r[0],r[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,h;switch(e){case 5:e=4;continue;case 4:e=6,i=this.xmax,h=this.ymin;break;case 6:e=2;continue;case 2:e=10,i=this.xmax,h=this.ymax;break;case 10:e=8;continue;case 8:e=9,i=this.xmin,h=this.ymax;break;case 9:e=1;continue;case 1:e=5,i=this.xmin,h=this.ymin}n[s]===i&&n[s+1]===h||!this.contains(t,i,h)||(n.splice(s,0,i,h),s+=2)}return s}_project(t,e,i,n){let s,h,r,l=1/0;if(n<0){if(e<=this.ymin)return null;(s=(this.ymin-e)/n)<l&&(r=this.ymin,h=t+(l=s)*i)}else if(n>0){if(e>=this.ymax)return null;(s=(this.ymax-e)/n)<l&&(r=this.ymax,h=t+(l=s)*i)}if(i>0){if(t>=this.xmax)return null;(s=(this.xmax-t)/i)<l&&(h=this.xmax,r=e+(l=s)*n)}else if(i<0){if(t<=this.xmin)return null;(s=(this.xmin-t)/i)<l&&(h=this.xmin,r=e+(l=s)*n)}return[h,r]}_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 h=this.inedges=new Int32Array(t.length/2).fill(-1),r=this.outedges=new Int32Array(t.length/2).fill(-1);for(let t=0,e=i.length;t<e;++t)h[s[t%3==2?t-2:t+1]]=t;let l,o=n;do{l=o,h[(o=o.next).i]=l.t,r[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,h=e[t];if(-1===h)return;let r=h;do{if(yield s[r],s[r=r%3==2?r-2:r+1]!==t)return;if(-1===(r=n[r]))return yield s[i[t]]}while(r!==h)}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 h=t,r=(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<r&&(r=t,h=n)}return h}render(t){const e=null==t?t=new f:void 0,{points:i,halfedges:n,triangles:s}=this;for(let e=0,h=n.length;e<h;++e){const h=n[e];if(h<e)continue;const r=2*s[e],l=2*s[h];t.moveTo(i[r],i[r+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],h=n[i+1];t.moveTo(s+e,h),t.arc(s,h,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,h=2*s[t*=3],r=2*s[t+1],l=2*s[t+2];return e.moveTo(n[h],n[h+1]),e.lineTo(n[r],n[r+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,h=new Float64Array(2*s);for(let r=0;r<s;++r){const s=t[r];h[2*r]=e.call(n,s,r,t),h[2*r+1]=i.call(n,s,r,t)}return h}(t,e,i,n):Float64Array.from(function*(t,e,i,n){let s=0;for(const h of t)yield e.call(n,h,s,t),yield i.call(n,h,s,t),++s}(t,e,i,n)))},t.Delaunay=_,t.Voronoi=g,Object.defineProperty(t,"__esModule",{value:!0})});

package.json

 {
   "name": "d3-delaunay",
-  "version": "4.1.1",
+  "version": "4.1.2",
   "description": "Compute the Voronoi diagram of a set of two-dimensional points.",
@@ -33,3 +33,3 @@ "keywords": [
     "esm": "3",
-    "rollup": "0.64",
+    "rollup": "0.65",
     "rollup-plugin-node-resolve": "3",
@@ -36,0 +36,0 @@ "rollup-plugin-terser": "1",

No alert changes

Improved metrics

Total package byte prevSize

111792

increased by1.69%

Lines of code

1405

increased by1.15%

No dependency changes