Socket
Socket
Sign inDemoInstall

delaunator

Package Overview
Dependencies
Maintainers
218
Versions
19
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

delaunator - npm Package Compare versions

Comparing version 1.0.5 to 2.0.0

706

delaunator.js

@@ -1,445 +0,459 @@

(function(f){if(typeof exports==="object"&&typeof module!=="undefined"){module.exports=f()}else if(typeof define==="function"&&define.amd){define([],f)}else{var g;if(typeof window!=="undefined"){g=window}else if(typeof global!=="undefined"){g=global}else if(typeof self!=="undefined"){g=self}else{g=this}g.delaunator = f()}})(function(){var define,module,exports;return (function e(t,n,r){function s(o,u){if(!n[o]){if(!t[o]){var a=typeof require=="function"&&require;if(!u&&a)return a(o,!0);if(i)return i(o,!0);var f=new Error("Cannot find module '"+o+"'");throw f.code="MODULE_NOT_FOUND",f}var l=n[o]={exports:{}};t[o][0].call(l.exports,function(e){var n=t[o][1][e];return s(n?n:e)},l,l.exports,e,t,n,r)}return n[o].exports}var i=typeof require=="function"&&require;for(var o=0;o<r.length;o++)s(r[o]);return s})({1:[function(require,module,exports){
'use strict';
(function (global, factory) {
typeof exports === 'object' && typeof module !== 'undefined' ? module.exports = factory() :
typeof define === 'function' && define.amd ? define(factory) :
(global.Delaunator = factory());
}(this, (function () { 'use strict';
module.exports = Delaunator;
module.exports.default = Delaunator;
Delaunator.from = function (points, getX, getY) {
if (!getX) getX = defaultGetX;
if (!getY) getY = defaultGetY;
function Delaunator(points, getX, getY) {
var n = points.length;
var coords = new Float64Array(n * 2);
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);
}
var minX = Infinity;
var minY = Infinity;
var maxX = -Infinity;
var maxY = -Infinity;
return new Delaunator(coords);
};
var coords = this.coords = [];
var ids = this.ids = new Uint32Array(points.length);
function Delaunator(coords) {
if (!ArrayBuffer.isView(coords)) throw new Error('Expected coords to be a typed array.');
for (var i = 0; i < points.length; i++) {
var p = points[i];
var x = getX(p);
var y = getY(p);
ids[i] = i;
coords[2 * i] = x;
coords[2 * i + 1] = y;
if (x < minX) minX = x;
if (y < minY) minY = y;
if (x > maxX) maxX = x;
if (y > maxY) maxY = y;
}
var minX = Infinity;
var minY = Infinity;
var maxX = -Infinity;
var maxY = -Infinity;
var cx = (minX + maxX) / 2;
var cy = (minY + maxY) / 2;
var n = coords.length >> 1;
var ids = this.ids = new Uint32Array(n);
var minDist = Infinity;
var i0, i1, i2;
this.coords = coords;
// pick a seed point close to the centroid
for (i = 0; i < points.length; i++) {
var d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]);
if (d < minDist) {
i0 = i;
minDist = d;
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;
}
}
minDist = Infinity;
var cx = (minX + maxX) / 2;
var cy = (minY + maxY) / 2;
// find the point closest to the seed
for (i = 0; i < points.length; i++) {
if (i === i0) continue;
d = dist(coords[2 * i0], coords[2 * i0 + 1], coords[2 * i], coords[2 * i + 1]);
if (d < minDist && d > 0) {
i1 = i;
minDist = d;
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;
}
}
}
var minRadius = Infinity;
minDist = Infinity;
// find the third point which forms the smallest circumcircle with the first two
for (i = 0; i < points.length; i++) {
if (i === i0 || i === i1) continue;
// find the 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 r = circumradius(
coords[2 * i0], coords[2 * i0 + 1],
coords[2 * i1], coords[2 * i1 + 1],
coords[2 * i], coords[2 * i + 1]);
var minRadius = Infinity;
if (r < minRadius) {
i2 = i;
minRadius = r;
// 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]);
if (r < minRadius) {
i2 = i;
minRadius = r;
}
}
}
if (minRadius === Infinity) {
throw new Error('No Delaunay triangulation exists for this input.');
}
if (minRadius === Infinity) {
throw new Error('No Delaunay triangulation exists for this input.');
}
// swap the order of the seed points for counter-clockwise orientation
if (area(coords[2 * i0], coords[2 * i0 + 1],
coords[2 * i1], coords[2 * i1 + 1],
coords[2 * i2], coords[2 * i2 + 1]) < 0) {
// swap the order of the seed points for counter-clockwise orientation
if (area(coords[2 * i0], coords[2 * i0 + 1],
coords[2 * i1], coords[2 * i1 + 1],
coords[2 * i2], coords[2 * i2 + 1]) < 0) {
var tmp = i1;
i1 = i2;
i2 = tmp;
}
var tmp = i1;
i1 = i2;
i2 = tmp;
}
var i0x = coords[2 * i0];
var i0y = coords[2 * i0 + 1];
var i1x = coords[2 * i1];
var i1y = coords[2 * i1 + 1];
var i2x = coords[2 * i2];
var i2y = coords[2 * i2 + 1];
var i0x = coords[2 * i0];
var i0y = coords[2 * i0 + 1];
var i1x = coords[2 * i1];
var i1y = coords[2 * i1 + 1];
var i2x = coords[2 * i2];
var i2y = coords[2 * i2 + 1];
var center = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y);
this._cx = center.x;
this._cy = center.y;
var center = circumcenter(i0x, i0y, i1x, i1y, i2x, i2y);
this._cx = center.x;
this._cy = center.y;
// sort the points by distance from the seed triangle circumcenter
quicksort(ids, coords, 0, ids.length - 1, center.x, center.y);
// sort the points by distance from the seed triangle circumcenter
quicksort(ids, coords, 0, ids.length - 1, center.x, center.y);
// initialize a hash table for storing edges of the advancing convex hull
this._hashSize = Math.ceil(Math.sqrt(points.length));
this._hash = [];
for (i = 0; i < this._hashSize; i++) this._hash[i] = null;
// initialize a hash table for storing edges of the advancing convex hull
this._hashSize = Math.ceil(Math.sqrt(n));
this._hash = [];
for (i = 0; i < this._hashSize; i++) this._hash[i] = null;
// initialize a circular doubly-linked list that will hold an advancing convex hull
var e = this.hull = insertNode(coords, i0);
this._hashEdge(e);
e.t = 0;
e = insertNode(coords, i1, e);
this._hashEdge(e);
e.t = 1;
e = insertNode(coords, i2, e);
this._hashEdge(e);
e.t = 2;
// initialize a circular doubly-linked list that will hold an advancing convex hull
var e = this.hull = insertNode(coords, i0);
this._hashEdge(e);
e.t = 0;
e = insertNode(coords, i1, e);
this._hashEdge(e);
e.t = 1;
e = insertNode(coords, i2, e);
this._hashEdge(e);
e.t = 2;
var maxTriangles = 2 * points.length - 5;
var triangles = this.triangles = new Uint32Array(maxTriangles * 3);
var halfedges = this.halfedges = new Int32Array(maxTriangles * 3);
var maxTriangles = 2 * n - 5;
var triangles = this.triangles = new Uint32Array(maxTriangles * 3);
var halfedges = this.halfedges = new Int32Array(maxTriangles * 3);
this.trianglesLen = 0;
this.trianglesLen = 0;
this._addTriangle(i0, i1, i2, -1, -1, -1);
this._addTriangle(i0, i1, i2, -1, -1, -1);
var xp, yp;
for (var k = 0; k < ids.length; k++) {
i = ids[k];
x = coords[2 * i];
y = coords[2 * i + 1];
var xp, yp;
for (var k = 0; k < ids.length; k++) {
i = ids[k];
x = coords[2 * i];
y = coords[2 * i + 1];
// skip duplicate points
if (x === xp && y === yp) continue;
xp = x;
yp = y;
// skip duplicate points
if (x === xp && y === yp) continue;
xp = x;
yp = y;
// skip seed triangle points
if ((x === i0x && y === i0y) ||
(x === i1x && y === i1y) ||
(x === i2x && y === i2y)) continue;
// skip seed triangle points
if ((x === i0x && y === i0y) ||
(x === i1x && y === i1y) ||
(x === i2x && y === i2y)) continue;
// find a visible edge on the convex hull using edge hash
var startKey = this._hashKey(x, y);
var key = startKey;
var start;
do {
start = this._hash[key];
key = (key + 1) % this._hashSize;
} while ((!start || start.removed) && key !== startKey);
// find a visible edge on the convex hull using edge hash
var startKey = this._hashKey(x, y);
var key = startKey;
var start;
do {
start = this._hash[key];
key = (key + 1) % this._hashSize;
} while ((!start || start.removed) && key !== startKey);
e = start;
while (area(x, y, e.x, e.y, e.next.x, e.next.y) >= 0) {
e = e.next;
if (e === start) {
throw new Error('Something is wrong with the input points.');
e = start;
while (area(x, y, e.x, e.y, e.next.x, e.next.y) >= 0) {
e = e.next;
if (e === start) {
throw new Error('Something is wrong with the input points.');
}
}
}
var walkBack = e === start;
var walkBack = e === start;
// add the first triangle from the point
var t = this._addTriangle(e.i, i, e.next.i, -1, -1, e.t);
// add the first triangle from the point
var t = this._addTriangle(e.i, i, e.next.i, -1, -1, e.t);
e.t = t; // keep track of boundary triangles on the hull
e = insertNode(coords, i, e);
e.t = t; // keep track of boundary triangles on the hull
e = insertNode(coords, i, e);
// recursively flip triangles from the point until they satisfy the Delaunay condition
e.t = this._legalize(t + 2);
if (e.prev.prev.t === halfedges[t + 1]) {
e.prev.prev.t = t + 2;
}
// recursively flip triangles from the point until they satisfy the Delaunay condition
e.t = this._legalize(t + 2);
if (e.prev.prev.t === halfedges[t + 1]) {
e.prev.prev.t = t + 2;
}
// walk forward through the hull, adding more triangles and flipping recursively
var q = e.next;
while (area(x, y, q.x, q.y, q.next.x, q.next.y) < 0) {
t = this._addTriangle(q.i, i, q.next.i, q.prev.t, -1, q.t);
q.prev.t = this._legalize(t + 2);
this.hull = removeNode(q);
q = q.next;
}
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
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.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 = {
Delaunator.prototype = {
_hashEdge: function (e) {
this._hash[this._hashKey(e.x, e.y)] = e;
},
_hashEdge: function (e) {
this._hash[this._hashKey(e.x, e.y)] = e;
},
_hashKey: function (x, y) {
var dx = x - this._cx;
var dy = y - this._cy;
// use pseudo-angle: a measure that monotonically increases
// with real angle, but doesn't require expensive trigonometry
var p = 1 - dx / (Math.abs(dx) + Math.abs(dy));
return Math.floor((2 + (dy < 0 ? -p : p)) / 4 * this._hashSize);
},
_hashKey: function (x, y) {
var dx = x - this._cx;
var dy = y - this._cy;
// use pseudo-angle: a measure that monotonically increases
// with real angle, but doesn't require expensive trigonometry
var p = 1 - dx / (Math.abs(dx) + Math.abs(dy));
return Math.floor((2 + (dy < 0 ? -p : p)) / 4 * this._hashSize);
},
_legalize: function (a) {
var triangles = this.triangles;
var coords = this.coords;
var halfedges = this.halfedges;
_legalize: function (a) {
var triangles = this.triangles;
var coords = this.coords;
var halfedges = this.halfedges;
var b = halfedges[a];
var b = halfedges[a];
var a0 = a - a % 3;
var b0 = b - b % 3;
var a0 = a - a % 3;
var b0 = b - b % 3;
var al = a0 + (a + 1) % 3;
var ar = a0 + (a + 2) % 3;
var bl = b0 + (b + 2) % 3;
var al = a0 + (a + 1) % 3;
var ar = a0 + (a + 2) % 3;
var bl = b0 + (b + 2) % 3;
var p0 = triangles[ar];
var pr = triangles[a];
var pl = triangles[al];
var p1 = triangles[bl];
var p0 = triangles[ar];
var pr = triangles[a];
var pl = triangles[al];
var p1 = triangles[bl];
var illegal = inCircle(
coords[2 * p0], coords[2 * p0 + 1],
coords[2 * pr], coords[2 * pr + 1],
coords[2 * pl], coords[2 * pl + 1],
coords[2 * p1], coords[2 * p1 + 1]);
var illegal = inCircle(
coords[2 * p0], coords[2 * p0 + 1],
coords[2 * pr], coords[2 * pr + 1],
coords[2 * pl], coords[2 * pl + 1],
coords[2 * p1], coords[2 * p1 + 1]);
if (illegal) {
triangles[a] = p1;
triangles[b] = p0;
if (illegal) {
triangles[a] = p1;
triangles[b] = p0;
this._link(a, halfedges[bl]);
this._link(b, halfedges[ar]);
this._link(ar, bl);
this._link(a, halfedges[bl]);
this._link(b, halfedges[ar]);
this._link(ar, bl);
var br = b0 + (b + 1) % 3;
var br = b0 + (b + 1) % 3;
this._legalize(a);
return this._legalize(br);
}
this._legalize(a);
return this._legalize(br);
}
return ar;
},
return ar;
},
_link: function (a, b) {
this.halfedges[a] = b;
if (b !== -1) this.halfedges[b] = a;
},
_link: function (a, b) {
this.halfedges[a] = b;
if (b !== -1) this.halfedges[b] = a;
},
// add a new triangle given vertex indices and adjacent half-edge ids
_addTriangle: function (i0, i1, i2, a, b, c) {
var t = this.trianglesLen;
// add a new triangle given vertex indices and adjacent half-edge ids
_addTriangle: function (i0, i1, i2, a, b, c) {
var t = this.trianglesLen;
this.triangles[t] = i0;
this.triangles[t + 1] = i1;
this.triangles[t + 2] = i2;
this.triangles[t] = i0;
this.triangles[t + 1] = i1;
this.triangles[t + 2] = i2;
this._link(t, a);
this._link(t + 1, b);
this._link(t + 2, c);
this._link(t, a);
this._link(t + 1, b);
this._link(t + 2, c);
this.trianglesLen += 3;
this.trianglesLen += 3;
return t;
}
};
return t;
function dist(ax, ay, bx, by) {
var dx = ax - bx;
var dy = ay - by;
return dx * dx + dy * dy;
}
};
function dist(ax, ay, bx, by) {
var dx = ax - bx;
var dy = ay - by;
return dx * dx + dy * dy;
}
function area(px, py, qx, qy, rx, ry) {
return (qy - py) * (rx - qx) - (qx - px) * (ry - qy);
}
function area(px, py, qx, qy, rx, ry) {
return (qy - py) * (rx - qx) - (qx - px) * (ry - qy);
}
function inCircle(ax, ay, bx, by, cx, cy, px, py) {
ax -= px;
ay -= py;
bx -= px;
by -= py;
cx -= px;
cy -= py;
function inCircle(ax, ay, bx, by, cx, cy, px, py) {
ax -= px;
ay -= py;
bx -= px;
by -= py;
cx -= px;
cy -= py;
var ap = ax * ax + ay * ay;
var bp = bx * bx + by * by;
var cp = cx * cx + cy * cy;
var ap = ax * ax + ay * ay;
var bp = bx * bx + by * by;
var cp = cx * cx + cy * cy;
return ax * (by * cp - bp * cy) -
ay * (bx * cp - bp * cx) +
ap * (bx * cy - by * cx) < 0;
}
return ax * (by * cp - bp * cy) -
ay * (bx * cp - bp * cx) +
ap * (bx * cy - by * cx) < 0;
}
function circumradius(ax, ay, bx, by, cx, cy) {
bx -= ax;
by -= ay;
cx -= ax;
cy -= ay;
function circumradius(ax, ay, bx, by, cx, cy) {
bx -= ax;
by -= ay;
cx -= ax;
cy -= ay;
var bl = bx * bx + by * by;
var cl = cx * cx + cy * cy;
var bl = bx * bx + by * by;
var cl = cx * cx + cy * cy;
if (bl === 0 || cl === 0) return Infinity;
if (bl === 0 || cl === 0) return Infinity;
var d = bx * cy - by * cx;
if (d === 0) return Infinity;
var d = bx * cy - by * cx;
if (d === 0) return Infinity;
var x = (cy * bl - by * cl) * 0.5 / d;
var y = (bx * cl - cx * bl) * 0.5 / d;
var x = (cy * bl - by * cl) * 0.5 / d;
var y = (bx * cl - cx * bl) * 0.5 / d;
return x * x + y * y;
}
return x * x + y * y;
}
function circumcenter(ax, ay, bx, by, cx, cy) {
bx -= ax;
by -= ay;
cx -= ax;
cy -= ay;
function circumcenter(ax, ay, bx, by, cx, cy) {
bx -= ax;
by -= ay;
cx -= ax;
cy -= ay;
var bl = bx * bx + by * by;
var cl = cx * cx + cy * cy;
var bl = bx * bx + by * by;
var cl = cx * cx + cy * cy;
var d = bx * cy - by * cx;
var d = bx * cy - by * cx;
var x = (cy * bl - by * cl) * 0.5 / d;
var y = (bx * cl - cx * bl) * 0.5 / d;
var x = (cy * bl - by * cl) * 0.5 / d;
var y = (bx * cl - cx * bl) * 0.5 / d;
return {
x: ax + x,
y: ay + y
};
}
return {
x: ax + x,
y: ay + y
};
}
// create a new node in a doubly linked list
function insertNode(coords, i, prev) {
var node = {
i: i,
x: coords[2 * i],
y: coords[2 * i + 1],
t: 0,
prev: null,
next: null,
removed: false
};
// create a new node in a doubly linked list
function insertNode(coords, i, prev) {
var node = {
i: i,
x: coords[2 * i],
y: coords[2 * i + 1],
t: 0,
prev: null,
next: null,
removed: false
};
if (!prev) {
node.prev = node;
node.next = node;
if (!prev) {
node.prev = node;
node.next = node;
} else {
node.next = prev.next;
node.prev = prev;
prev.next.prev = node;
prev.next = node;
}
return node;
}
} else {
node.next = prev.next;
node.prev = prev;
prev.next.prev = node;
prev.next = node;
function removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.removed = true;
return node.prev;
}
return node;
}
function removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
node.removed = true;
return node.prev;
}
function quicksort(ids, coords, left, right, cx, cy) {
var i, j, temp;
function quicksort(ids, coords, left, right, cx, cy) {
var i, j, temp;
if (right - left <= 20) {
for (i = left + 1; i <= right; i++) {
temp = ids[i];
j = i - 1;
while (j >= left && compare(coords, ids[j], temp, cx, cy) > 0) ids[j + 1] = ids[j--];
ids[j + 1] = temp;
}
} else {
var median = (left + right) >> 1;
i = left + 1;
j = right;
swap(ids, median, i);
if (compare(coords, ids[left], ids[right], cx, cy) > 0) swap(ids, left, right);
if (compare(coords, ids[i], ids[right], cx, cy) > 0) swap(ids, i, right);
if (compare(coords, ids[left], ids[i], cx, cy) > 0) swap(ids, left, i);
if (right - left <= 20) {
for (i = left + 1; i <= right; i++) {
temp = ids[i];
j = i - 1;
while (j >= left && compare(coords, ids[j], temp, cx, cy) > 0) ids[j + 1] = ids[j--];
ids[j + 1] = temp;
}
} else {
var median = (left + right) >> 1;
i = left + 1;
j = right;
swap(ids, median, i);
if (compare(coords, ids[left], ids[right], cx, cy) > 0) swap(ids, left, right);
if (compare(coords, ids[i], ids[right], cx, cy) > 0) swap(ids, i, right);
if (compare(coords, ids[left], ids[i], cx, cy) > 0) swap(ids, left, i);
while (true) {
do i++; while (compare(coords, ids[i], temp, cx, cy) < 0);
do j--; while (compare(coords, ids[j], temp, cx, cy) > 0);
if (j < i) break;
swap(ids, i, j);
}
ids[left + 1] = ids[j];
ids[j] = temp;
temp = ids[i];
while (true) {
do i++; while (compare(coords, ids[i], temp, cx, cy) < 0);
do j--; while (compare(coords, ids[j], temp, cx, cy) > 0);
if (j < i) break;
swap(ids, i, j);
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);
}
}
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 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];
}
function defaultGetX(p) {
return p[0];
}
function defaultGetY(p) {
return p[1];
}
return Delaunator;
},{}]},{},[1])(1)
});
})));

2

delaunator.min.js

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

!function(t){if("object"==typeof exports&&"undefined"!=typeof module)module.exports=t();else if("function"==typeof define&&define.amd)define([],t);else{("undefined"!=typeof window?window:"undefined"!=typeof global?global:"undefined"!=typeof self?self:this).delaunator=t()}}(function(){return function t(e,r,i){function n(s,a){if(!r[s]){if(!e[s]){var o="function"==typeof require&&require;if(!a&&o)return o(s,!0);if(h)return h(s,!0);var l=new Error("Cannot find module '"+s+"'");throw l.code="MODULE_NOT_FOUND",l}var f=r[s]={exports:{}};e[s][0].call(f.exports,function(t){var r=e[s][1][t];return n(r||t)},f,f.exports,t,e,r,i)}return r[s].exports}for(var h="function"==typeof require&&require,s=0;s<i.length;s++)n(i[s]);return n}({1:[function(t,e,r){"use strict";function i(t,e,r){e||(e=u),r||(r=v);for(var i=1/0,l=1/0,f=-1/0,d=-1/0,g=this.coords=[],p=this.ids=new Uint32Array(t.length),_=0;_<t.length;_++){var x=t[_],c=e(x),y=r(x);p[_]=_,g[2*_]=c,g[2*_+1]=y,c<i&&(i=c),y<l&&(l=y),c>f&&(f=c),y>d&&(d=y)}var w,z,E,b=(i+f)/2,k=(l+d)/2,m=1/0;for(_=0;_<t.length;_++){var L=n(b,k,g[2*_],g[2*_+1]);L<m&&(w=_,m=L)}for(m=1/0,_=0;_<t.length;_++)_!==w&&(L=n(g[2*w],g[2*w+1],g[2*_],g[2*_+1]))<m&&L>0&&(z=_,m=L);var M=1/0;for(_=0;_<t.length;_++)if(_!==w&&_!==z){var T=function(t,e,r,i,n,h){var s=(r-=t)*r+(i-=e)*i,a=(n-=t)*n+(h-=e)*h;if(0===s||0===a)return 1/0;var o=r*h-i*n;if(0===o)return 1/0;var l=.5*(h*s-i*a)/o,f=.5*(r*a-n*s)/o;return l*l+f*f}(g[2*w],g[2*w+1],g[2*z],g[2*z+1],g[2*_],g[2*_+1]);T<M&&(E=_,M=T)}if(M===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(h(g[2*w],g[2*w+1],g[2*z],g[2*z+1],g[2*E],g[2*E+1])<0){var q=z;z=E,E=q}var S=g[2*w],U=g[2*w+1],A=g[2*z],D=g[2*z+1],K=g[2*E],N=g[2*E+1],O=function(t,e,r,i,n,h){var s=(r-=t)*r+(i-=e)*i,a=(n-=t)*n+(h-=e)*h,o=r*h-i*n;return{x:t+.5*(h*s-i*a)/o,y:e+.5*(r*a-n*s)/o}}(S,U,A,D,K,N);for(this._cx=O.x,this._cy=O.y,o(p,g,0,p.length-1,O.x,O.y),this._hashSize=Math.ceil(Math.sqrt(t.length)),this._hash=[],_=0;_<this._hashSize;_++)this._hash[_]=null;var j=this.hull=s(g,w);this._hashEdge(j),j.t=0,j=s(g,z,j),this._hashEdge(j),j.t=1,j=s(g,E,j),this._hashEdge(j),j.t=2;var C=2*t.length-5,F=this.triangles=new Uint32Array(3*C),I=this.halfedges=new Int32Array(3*C);this.trianglesLen=0,this._addTriangle(w,z,E,-1,-1,-1);for(var B,G,H=0;H<p.length;H++)if(_=p[H],c=g[2*_],y=g[2*_+1],!(c===B&&y===G||(B=c,G=y,c===S&&y===U||c===A&&y===D||c===K&&y===N))){var J,P=this._hashKey(c,y),Q=P;do{J=this._hash[Q],Q=(Q+1)%this._hashSize}while((!J||J.removed)&&Q!==P);for(j=J;h(c,y,j.x,j.y,j.next.x,j.next.y)>=0;)if((j=j.next)===J)throw new Error("Something is wrong with the input points.");var R=j===J,V=this._addTriangle(j.i,_,j.next.i,-1,-1,j.t);j.t=V,(j=s(g,_,j)).t=this._legalize(V+2),j.prev.prev.t===I[V+1]&&(j.prev.prev.t=V+2);for(var W=j.next;h(c,y,W.x,W.y,W.next.x,W.next.y)<0;)V=this._addTriangle(W.i,_,W.next.i,W.prev.t,-1,W.t),W.prev.t=this._legalize(V+2),this.hull=a(W),W=W.next;if(R)for(W=j.prev;h(c,y,W.prev.x,W.prev.y,W.x,W.y)<0;)V=this._addTriangle(W.prev.i,_,W.i,-1,W.t,W.prev.t),this._legalize(V+2),W.prev.t=V,this.hull=a(W),W=W.prev;this._hashEdge(j),this._hashEdge(j.prev)}this.triangles=F.subarray(0,this.trianglesLen),this.halfedges=I.subarray(0,this.trianglesLen)}function n(t,e,r,i){var n=t-r,h=e-i;return n*n+h*h}function h(t,e,r,i,n,h){return(i-e)*(n-r)-(r-t)*(h-i)}function s(t,e,r){var i={i:e,x:t[2*e],y:t[2*e+1],t:0,prev:null,next:null,removed:!1};return r?(i.next=r.next,i.prev=r,r.next.prev=i,r.next=i):(i.prev=i,i.next=i),i}function a(t){return t.prev.next=t.next,t.next.prev=t.prev,t.removed=!0,t.prev}function o(t,e,r,i,n,h){var s,a,u;if(i-r<=20)for(s=r+1;s<=i;s++){for(u=t[s],a=s-1;a>=r&&l(e,t[a],u,n,h)>0;)t[a+1]=t[a--];t[a+1]=u}else{for(a=i,f(t,r+i>>1,s=r+1),l(e,t[r],t[i],n,h)>0&&f(t,r,i),l(e,t[s],t[i],n,h)>0&&f(t,s,i),l(e,t[r],t[s],n,h)>0&&f(t,r,s),u=t[s];;){do{s++}while(l(e,t[s],u,n,h)<0);do{a--}while(l(e,t[a],u,n,h)>0);if(a<s)break;f(t,s,a)}t[r+1]=t[a],t[a]=u,i-s+1>=a-r?(o(t,e,s,i,n,h),o(t,e,r,a-1,n,h)):(o(t,e,r,a-1,n,h),o(t,e,s,i,n,h))}}function l(t,e,r,i,h){return n(t[2*e],t[2*e+1],i,h)-n(t[2*r],t[2*r+1],i,h)||t[2*e]-t[2*r]||t[2*e+1]-t[2*r+1]}function f(t,e,r){var i=t[e];t[e]=t[r],t[r]=i}function u(t){return t[0]}function v(t){return t[1]}e.exports=i,e.exports.default=i,i.prototype={_hashEdge:function(t){this._hash[this._hashKey(t.x,t.y)]=t},_hashKey:function(t,e){var r=t-this._cx,i=e-this._cy,n=1-r/(Math.abs(r)+Math.abs(i));return Math.floor((2+(i<0?-n:n))/4*this._hashSize)},_legalize:function(t){var e=this.triangles,r=this.coords,i=this.halfedges,n=i[t],h=t-t%3,s=n-n%3,a=h+(t+1)%3,o=h+(t+2)%3,l=s+(n+2)%3,f=e[o],u=e[t],v=e[a],d=e[l];if(function(t,e,r,i,n,h,s,a){var o=(r-=s)*r+(i-=a)*i,l=(n-=s)*n+(h-=a)*h;return(t-=s)*(i*l-o*h)-(e-=a)*(r*l-o*n)+(t*t+e*e)*(r*h-i*n)<0}(r[2*f],r[2*f+1],r[2*u],r[2*u+1],r[2*v],r[2*v+1],r[2*d],r[2*d+1])){e[t]=d,e[n]=f,this._link(t,i[l]),this._link(n,i[o]),this._link(o,l);var g=s+(n+1)%3;return this._legalize(t),this._legalize(g)}return o},_link:function(t,e){this.halfedges[t]=e,-1!==e&&(this.halfedges[e]=t)},_addTriangle:function(t,e,r,i,n,h){var s=this.trianglesLen;return this.triangles[s]=t,this.triangles[s+1]=e,this.triangles[s+2]=r,this._link(s,i),this._link(s+1,n),this._link(s+2,h),this.trianglesLen+=3,s}}},{}]},{},[1])(1)});
!function(t,e){"object"==typeof exports&&"undefined"!=typeof module?module.exports=e():"function"==typeof define&&define.amd?define(e):t.Delaunator=e()}(this,function(){"use strict";function t(t){if(!ArrayBuffer.isView(t))throw new Error("Expected coords to be a typed array.");var o=1/0,l=1/0,f=-1/0,u=-1/0,v=t.length>>1,d=this.ids=new Uint32Array(v);this.coords=t;for(var g=0;g<v;g++){var _=t[2*g],x=t[2*g+1];_<o&&(o=_),x<l&&(l=x),_>f&&(f=_),x>u&&(u=x),d[g]=g}var p,c,y,w=(o+f)/2,z=(l+u)/2,E=1/0;for(g=0;g<v;g++){var k=e(w,z,t[2*g],t[2*g+1]);k<E&&(p=g,E=k)}for(E=1/0,g=0;g<v;g++)g!==p&&(k=e(t[2*p],t[2*p+1],t[2*g],t[2*g+1]))<E&&k>0&&(c=g,E=k);var m=1/0;for(g=0;g<v;g++)if(g!==p&&g!==c){var b=i(t[2*p],t[2*p+1],t[2*c],t[2*c+1],t[2*g],t[2*g+1]);b<m&&(y=g,m=b)}if(m===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(r(t[2*p],t[2*p+1],t[2*c],t[2*c+1],t[2*y],t[2*y+1])<0){var A=c;c=y,y=A}var L=t[2*p],M=t[2*p+1],S=t[2*c],T=t[2*c+1],K=t[2*y],D=t[2*y+1],U=function(t,e,r,i,n,h){var s=(r-=t)*r+(i-=e)*i,a=(n-=t)*n+(h-=e)*h,o=r*h-i*n;return{x:t+.5*(h*s-i*a)/o,y:e+.5*(r*a-n*s)/o}}(L,M,S,T,K,D);for(this._cx=U.x,this._cy=U.y,function t(e,r,i,n,h,o){var l,f,u;if(n-i<=20)for(l=i+1;l<=n;l++){for(u=e[l],f=l-1;f>=i&&s(r,e[f],u,h,o)>0;)e[f+1]=e[f--];e[f+1]=u}else{var v=i+n>>1;for(f=n,a(e,v,l=i+1),s(r,e[i],e[n],h,o)>0&&a(e,i,n),s(r,e[l],e[n],h,o)>0&&a(e,l,n),s(r,e[i],e[l],h,o)>0&&a(e,i,l),u=e[l];;){do{l++}while(s(r,e[l],u,h,o)<0);do{f--}while(s(r,e[f],u,h,o)>0);if(f<l)break;a(e,l,f)}e[i+1]=e[f],e[f]=u,n-l+1>=f-i?(t(e,r,l,n,h,o),t(e,r,i,f-1,h,o)):(t(e,r,i,f-1,h,o),t(e,r,l,n,h,o))}}(d,t,0,d.length-1,U.x,U.y),this._hashSize=Math.ceil(Math.sqrt(v)),this._hash=[],g=0;g<this._hashSize;g++)this._hash[g]=null;var j=this.hull=n(t,p);this._hashEdge(j),j.t=0,j=n(t,c,j),this._hashEdge(j),j.t=1,j=n(t,y,j),this._hashEdge(j),j.t=2;var q,B,F=2*v-5,I=this.triangles=new Uint32Array(3*F),N=this.halfedges=new Int32Array(3*F);this.trianglesLen=0,this._addTriangle(p,c,y,-1,-1,-1);for(var V=0;V<d.length;V++)if(_=t[2*(g=d[V])],x=t[2*g+1],!(_===q&&x===B||(q=_,B=x,_===L&&x===M||_===S&&x===T||_===K&&x===D))){var C,G=this._hashKey(_,x),H=G;do{C=this._hash[H],H=(H+1)%this._hashSize}while((!C||C.removed)&&H!==G);for(j=C;r(_,x,j.x,j.y,j.next.x,j.next.y)>=0;)if((j=j.next)===C)throw new Error("Something is wrong with the input points.");var J=j===C,O=this._addTriangle(j.i,g,j.next.i,-1,-1,j.t);j.t=O,(j=n(t,g,j)).t=this._legalize(O+2),j.prev.prev.t===N[O+1]&&(j.prev.prev.t=O+2);for(var P=j.next;r(_,x,P.x,P.y,P.next.x,P.next.y)<0;)O=this._addTriangle(P.i,g,P.next.i,P.prev.t,-1,P.t),P.prev.t=this._legalize(O+2),this.hull=h(P),P=P.next;if(J)for(P=j.prev;r(_,x,P.prev.x,P.prev.y,P.x,P.y)<0;)O=this._addTriangle(P.prev.i,g,P.i,-1,P.t,P.prev.t),this._legalize(O+2),P.prev.t=O,this.hull=h(P),P=P.prev;this._hashEdge(j),this._hashEdge(j.prev)}this.triangles=I.subarray(0,this.trianglesLen),this.halfedges=N.subarray(0,this.trianglesLen)}function e(t,e,r,i){var n=t-r,h=e-i;return n*n+h*h}function r(t,e,r,i,n,h){return(i-e)*(n-r)-(r-t)*(h-i)}function i(t,e,r,i,n,h){var s=(r-=t)*r+(i-=e)*i,a=(n-=t)*n+(h-=e)*h;if(0===s||0===a)return 1/0;var o=r*h-i*n;if(0===o)return 1/0;var l=.5*(h*s-i*a)/o,f=.5*(r*a-n*s)/o;return l*l+f*f}function n(t,e,r){var i={i:e,x:t[2*e],y:t[2*e+1],t:0,prev:null,next:null,removed:!1};return r?(i.next=r.next,i.prev=r,r.next.prev=i,r.next=i):(i.prev=i,i.next=i),i}function h(t){return t.prev.next=t.next,t.next.prev=t.prev,t.removed=!0,t.prev}function s(t,r,i,n,h){return e(t[2*r],t[2*r+1],n,h)-e(t[2*i],t[2*i+1],n,h)||t[2*r]-t[2*i]||t[2*r+1]-t[2*i+1]}function a(t,e,r){var i=t[e];t[e]=t[r],t[r]=i}function o(t){return t[0]}function l(t){return t[1]}return t.from=function(e,r,i){r||(r=o),i||(i=l);for(var n=e.length,h=new Float64Array(2*n),s=0;s<n;s++){var a=e[s];h[2*s]=r(a),h[2*s+1]=i(a)}return new t(h)},t.prototype={_hashEdge:function(t){this._hash[this._hashKey(t.x,t.y)]=t},_hashKey:function(t,e){var r=t-this._cx,i=e-this._cy,n=1-r/(Math.abs(r)+Math.abs(i));return Math.floor((2+(i<0?-n:n))/4*this._hashSize)},_legalize:function(t){var e,r,i,n,h,s,a,o,l,f,u=this.triangles,v=this.coords,d=this.halfedges,g=d[t],_=t-t%3,x=g-g%3,p=_+(t+1)%3,c=_+(t+2)%3,y=x+(g+2)%3,w=u[c],z=u[t],E=u[p],k=u[y];if(e=v[2*w],r=v[2*w+1],i=v[2*z],n=v[2*z+1],h=v[2*E],s=v[2*E+1],a=v[2*k],o=v[2*k+1],l=(i-=a)*i+(n-=o)*n,f=(h-=a)*h+(s-=o)*s,(e-=a)*(n*f-l*s)-(r-=o)*(i*f-l*h)+(e*e+r*r)*(i*s-n*h)<0){u[t]=k,u[g]=w,this._link(t,d[y]),this._link(g,d[c]),this._link(c,y);var m=x+(g+1)%3;return this._legalize(t),this._legalize(m)}return c},_link:function(t,e){this.halfedges[t]=e,-1!==e&&(this.halfedges[e]=t)},_addTriangle:function(t,e,r,i,n,h){var s=this.trianglesLen;return this.triangles[s]=t,this.triangles[s+1]=e,this.triangles[s+2]=r,this._link(s,i),this._link(s+1,n),this._link(s+2,h),this.trianglesLen+=3,s}},t});

49

index.js

@@ -1,11 +0,21 @@

'use strict';
module.exports = Delaunator;
module.exports.default = Delaunator;
function Delaunator(points, getX, getY) {
Delaunator.from = function (points, getX, getY) {
if (!getX) getX = defaultGetX;
if (!getY) getY = defaultGetY;
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);
}
return new Delaunator(coords);
};
export default function Delaunator(coords) {
if (!ArrayBuffer.isView(coords)) throw new Error('Expected coords to be a typed array.');
var minX = Infinity;

@@ -16,12 +26,10 @@ var minY = Infinity;

var coords = this.coords = [];
var ids = this.ids = new Uint32Array(points.length);
var n = coords.length >> 1;
var ids = this.ids = new Uint32Array(n);
for (var i = 0; i < points.length; i++) {
var p = points[i];
var x = getX(p);
var y = getY(p);
ids[i] = i;
coords[2 * i] = x;
coords[2 * i + 1] = y;
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;

@@ -31,2 +39,3 @@ if (y < minY) minY = y;

if (y > maxY) maxY = y;
ids[i] = i;
}

@@ -41,3 +50,3 @@

// pick a seed point close to the centroid
for (i = 0; i < points.length; i++) {
for (i = 0; i < n; i++) {
var d = dist(cx, cy, coords[2 * i], coords[2 * i + 1]);

@@ -53,3 +62,3 @@ if (d < minDist) {

// find the point closest to the seed
for (i = 0; i < points.length; i++) {
for (i = 0; i < n; i++) {
if (i === i0) continue;

@@ -66,3 +75,3 @@ d = dist(coords[2 * i0], coords[2 * i0 + 1], coords[2 * i], coords[2 * i + 1]);

// find the third point which forms the smallest circumcircle with the first two
for (i = 0; i < points.length; i++) {
for (i = 0; i < n; i++) {
if (i === i0 || i === i1) continue;

@@ -110,3 +119,3 @@

// initialize a hash table for storing edges of the advancing convex hull
this._hashSize = Math.ceil(Math.sqrt(points.length));
this._hashSize = Math.ceil(Math.sqrt(n));
this._hash = [];

@@ -126,3 +135,3 @@ for (i = 0; i < this._hashSize; i++) this._hash[i] = null;

var maxTriangles = 2 * points.length - 5;
var maxTriangles = 2 * n - 5;
var triangles = this.triangles = new Uint32Array(maxTriangles * 3);

@@ -129,0 +138,0 @@ var halfedges = this.halfedges = new Int32Array(maxTriangles * 3);

32

package.json
{
"name": "delaunator",
"version": "1.0.5",
"version": "2.0.0",
"description": "A really fast JavaScript library for Delaunay triangulation of 2D points",
"main": "index.js",
"jsdelivr": "delaunator.js",
"unpkg": "delaunator.js",
"main": "delaunator.js",
"module": "index.js",
"jsdelivr": "delaunator.min.js",
"unpkg": "delaunator.min.js",
"dependencies": {},
"devDependencies": {
"browserify": "^14.5.0",
"eslint": "^4.0.0",
"eslint-config-mourner": "^2.0.1",
"tape": "^4.6.3",
"uglify-js": "^3.2.0"
"esm": "^3.0.8",
"rollup": "^0.57.1",
"rollup-plugin-uglify": "^3.0.0",
"tape": "^4.6.3"
},

@@ -22,9 +24,10 @@ "repository": {

"lint": "eslint index.js test.js bench.js",
"pretest": "npm run lint",
"test": "tape test.js",
"build": "browserify index.js -s delaunator -o delaunator.js",
"build-min": "browserify index.js -s delaunator | uglifyjs -c -m > delaunator.min.js",
"prepare": "npm run build && npm run build-min"
"pretest": "npm run lint && npm run build",
"test": "node test.js",
"bench": "node -r esm bench.js",
"build": "rollup -c",
"prepublishOnly": "npm test && npm run build"
},
"files": [
"index.js",
"delaunator.js",

@@ -34,3 +37,6 @@ "delaunator.min.js"

"eslintConfig": {
"extends": "mourner"
"extends": "mourner",
"parserOptions": {
"sourceType": "module"
}
},

@@ -37,0 +43,0 @@ "keywords": [

51

README.md

@@ -18,3 +18,3 @@ # delaunator

var delaunay = new Delaunator(points);
var delaunay = Delaunator.from(points);
console.log(delaunay.triangles);

@@ -24,6 +24,24 @@ // [623, 636, 619, 636, 444, 619, ...]

## Install
Install with NPM (`npm install delaunator`) or Yarn (`yarn add delaunator`), then:
```js
// import as an ES module
import Delaunator from 'delaunator';
// or require in Node / Browserify
const Delaunator = require('delaunator');
```
Or use a browser build directly:
```html
<script src="https://unpkg.com/delaunator@2.0.0/delaunator.min.js"></script> <!-- minified build -->
<script src="https://unpkg.com/delaunator@2.0.0/delaunator.js"></script> <!-- dev build -->
```
## API Reference
#### new Delaunator(points[, getX, getY])
#### Delaunator.from(points[, getX, getY])

@@ -34,2 +52,7 @@ Constructs a delaunay triangulation object given an array of points (`[x, y]` by default).

#### new Delaunator(coords)
Constructs a delaunay triangulation object given a **typed array** of point coordinates of the form:
`[x0, y0, x1, y1, ...]`.
#### delaunay.triangles

@@ -65,24 +88,12 @@

Benchmark results against four fastest other libraries
(`bench.js` on Macbook Pro Retina mid-2012, Node v7.9.0):
(`bench.js` on Macbook Pro Retina 15" 2017, Node v8.10.0):
#### Uniform distribution
library | 10,000 | 20,000 | 50,000 | 100,000 | 200,000 | 500,000 | 1,000,000
:-- | --: | --: | --: | --: | --: | --: | --:
delaunator | 25ms | 32ms | 105ms | 168ms | 350ms | 974ms | 2.46s
[faster-delaunay](https://github.com/Bathlamos/delaunay-triangulation) | 78ms | 140ms | 328ms | 776ms | 1.74s | 3.87s | 6.99s
[incremental-delaunay](https://github.com/mikolalysenko/incremental-delaunay) | 81ms | 154ms | 428ms | 874ms | 1.74s | 4.3s | 9.03s
[d3-voronoi](https://github.com/d3/d3-voronoi) | 154ms | 250ms | 534ms | 1.19s | 2.7s | 7.37s | 18.36s
[delaunay-fast](https://github.com/ironwallaby/delaunay) | 136ms | 386ms | 1.18s | 3.03s | 7.95s | 28.2s | 76.96s
delaunator | 31ms | 17ms | 59ms | 125ms | 232ms | 613ms | 1.35s
[faster-delaunay](https://github.com/Bathlamos/delaunay-triangulation) | 48ms | 88ms | 243ms | 447ms | 1.02s | 2.72s | 4.95s
[incremental-delaunay](https://github.com/mikolalysenko/incremental-delaunay) | 56ms | 131ms | 309ms | 577ms | 1.12s | 3.01s | 6.37s
[d3-voronoi](https://github.com/d3/d3-voronoi) | 132ms | 220ms | 483ms | 1s | 2.27s | 6.3s | 12.67s
[delaunay-fast](https://github.com/ironwallaby/delaunay) | 150ms | 343ms | 1.19s | 3.35s | 10.09s | 41.09s | 117.53s
#### Gaussian distribution
library | 10,000 | 20,000 | 50,000 | 100,000 | 200,000 | 500,000 | 1,000,000
:-- | --: | --: | --: | --: | --: | --: | --:
delaunator | 24ms | 27ms | 109ms | 170ms | 327ms | 941ms | 2.03s
[faster-delaunay](https://github.com/Bathlamos/delaunay-triangulation) | 76ms | 172ms | 291ms | 692ms | 1.19s | 3.46s | 6.36s
[incremental-delaunay](https://github.com/mikolalysenko/incremental-delaunay) | 74ms | 154ms | 410ms | 806ms | 1.67s | 4.27s | 8.3s
[d3-voronoi](https://github.com/d3/d3-voronoi) | 164ms | 264ms | 522ms | 1.16s | 2.67s | 7.64s | 18.62s
[delaunay-fast](https://github.com/ironwallaby/delaunay) | 152ms | 340ms | 1.19s | 3.2s | 8.37s | 30.03s | 82.05s
## Papers

@@ -89,0 +100,0 @@

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