generate reference dataset
diff --git a/generate-reference-triangles/README.md b/generate-reference-triangles/README.md
new file mode 100644
index 0000000..39be18e
--- /dev/null
+++ b/generate-reference-triangles/README.md
@@ -0,0 +1,9 @@
+
+Generating reference datasets using original https://github.com/mapbox/delaunator
+
+## Usage
+
+```
+npm i
+./index.js ../test-files/playgrounds-1356-epsg-3857.geojson ../test-files/playgrounds-1356-triangles.json
+```
\ No newline at end of file
diff --git a/generate-reference-triangles/index.js b/generate-reference-triangles/index.js
new file mode 100755
index 0000000..0e1e09b
--- /dev/null
+++ b/generate-reference-triangles/index.js
@@ -0,0 +1,27 @@
+#!/usr/bin/env node
+
+/**
+ * generates triangles indices from delaunator;
+ */
+
+const {readFileSync, writeFileSync} = require('fs');
+const Delaunator = require('delaunator');
+const inputFile = process.argv[2];
+const outputFile = process.argv[3];
+const geoJson = JSON.parse(readFileSync(inputFile));
+
+const n = geoJson.features.length;
+const coords = new Float64Array(n * 2);
+for(let i = 0; i < n; i++) {
+ const f = geoJson.features[i];
+ coords[2 * i] = f.geometry.coordinates[0];
+ coords[2 * i + 1] = f.geometry.coordinates[1];
+}
+
+console.time('Delaunator');
+const delaunator = new Delaunator(coords);
+console.timeEnd('Delaunator');
+
+const trianglesAr = Array.from(delaunator.triangles);
+writeFileSync(outputFile, JSON.stringify(trianglesAr));
+
diff --git a/generate-reference-triangles/node_modules/delaunator/LICENSE b/generate-reference-triangles/node_modules/delaunator/LICENSE
new file mode 100644
index 0000000..6f4f868
--- /dev/null
+++ b/generate-reference-triangles/node_modules/delaunator/LICENSE
@@ -0,0 +1,15 @@
+ISC License
+
+Copyright (c) 2017, Mapbox
+
+Permission to use, copy, modify, and/or distribute this software for any purpose
+with or without fee is hereby granted, provided that the above copyright notice
+and this permission notice appear in all copies.
+
+THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES WITH
+REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND
+FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT,
+INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS
+OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
+TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
+THIS SOFTWARE.
diff --git a/generate-reference-triangles/node_modules/delaunator/README.md b/generate-reference-triangles/node_modules/delaunator/README.md
new file mode 100644
index 0000000..8fb9079
--- /dev/null
+++ b/generate-reference-triangles/node_modules/delaunator/README.md
@@ -0,0 +1,102 @@
+# delaunator
+
+A really fast JavaScript library for
+[Delaunay triangulation](https://en.wikipedia.org/wiki/Delaunay_triangulation) of 2D points.
+
+- [Interactive Demo](https://mapbox.github.io/delaunator/demo.html)
+- [Guide to data structures](https://mapbox.github.io/delaunator/)
+
+[](https://travis-ci.org/mapbox/delaunator)
+[](https://github.com/mourner/projects)
+
+
+
+## Example
+
+```js
+const points = [[168, 180], [168, 178], [168, 179], [168, 181], [168, 183], ...];
+
+const delaunay = Delaunator.from(points);
+console.log(delaunay.triangles);
+// [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.1/delaunator.min.js"></script> <!-- minified build -->
+<script src="https://unpkg.com/delaunator@2.0.1/delaunator.js"></script> <!-- dev build -->
+```
+
+## API Reference
+
+#### Delaunator.from(points[, getX, getY])
+
+Constructs a delaunay triangulation object given an array of points (`[x, y]` by default).
+`getX` and `getY` are optional functions of the form `(point) => value` for custom point formats.
+Duplicate points are skipped.
+
+#### new Delaunator(coords)
+
+Constructs a delaunay triangulation object given a **typed array** of point coordinates of the form:
+`[x0, y0, x1, y1, ...]`.
+
+#### delaunay.triangles
+
+A flat `Int32Array` array of triangle vertex indices (each group of three numbers forms a triangle).
+All triangles are directed counterclockwise.
+
+To get the coordinates of all triangles, use:
+
+```js
+for (let i = 0; i < triangles.length; i += 3) {
+ coordinates.push([
+ points[triangles[i]],
+ points[triangles[i + 1]],
+ points[triangles[i + 2]]
+ ]);
+}
+```
+
+#### delaunay.halfedges
+
+A flat `Int32Array` array of triangle half-edge indices that allows you to traverse the triangulation.
+`i`-th half-edge in the array corresponds to vertex `triangles[i]` the half-edge is coming from.
+`halfedges[i]` is the index of a twin half-edge in an adjacent triangle
+(or `-1` for outer half-edges on the convex hull).
+
+The flat array-based data structures might be counterintuitive,
+but they're one of the key reasons this library is fast.
+
+## Performance
+
+Benchmark results against four fastest other libraries
+(`npm run bench` on Macbook Pro Retina 15" 2017, Node v8.10.0):
+
+library | 10,000 | 20,000 | 50,000 | 100,000 | 200,000 | 500,000 | 1,000,000
+:-- | --: | --: | --: | --: | --: | --: | --:
+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
+
+## Papers
+
+The algorithm is based on ideas from the following papers:
+
+- [A simple sweep-line Delaunay triangulation algorithm](http://www.academicpub.org/jao/paperInfo.aspx?paperid=15630), 2013, Liu Yonghe, Feng Jinming and Shao Yuehong
+- [S-hull: a fast radial sweep-hull routine for Delaunay triangulation](http://www.s-hull.org/paper/s_hull.pdf), 2010, David Sinclair
+- [A faster circle-sweep Delaunay triangulation algorithm](http://cglab.ca/~biniaz/papers/Sweep%20Circle.pdf), 2011, Ahmad Biniaz and Gholamhossein Dastghaibyfard
diff --git a/generate-reference-triangles/node_modules/delaunator/delaunator.js b/generate-reference-triangles/node_modules/delaunator/delaunator.js
new file mode 100644
index 0000000..3f552a2
--- /dev/null
+++ b/generate-reference-triangles/node_modules/delaunator/delaunator.js
@@ -0,0 +1,475 @@
+(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';
+
+ var Delaunator = function Delaunator(coords) {
+ var this$1 = this;
+
+ var minX = Infinity;
+ var minY = Infinity;
+ var maxX = -Infinity;
+ var maxY = -Infinity;
+
+ var n = coords.length >> 1;
+ var ids = this.ids = new Uint32Array(n);
+
+ if (n > 0 && typeof coords[0] !== 'number') { throw new Error('Expected coords to contain numbers.'); }
+
+ 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;
+ }
+
+ var cx = (minX + maxX) / 2;
+ var cy = (minY + maxY) / 2;
+
+ var minDist = Infinity;
+ var i0, i1, i2;
+
+ // pick a seed point close to the centroid
+ for (var i$1 = 0; i$1 < n; i$1++) {
+ var d = dist(cx, cy, coords[2 * i$1], coords[2 * i$1 + 1]);
+ if (d < minDist) {
+ i0 = i$1;
+ minDist = d;
+ }
+ }
+
+ minDist = Infinity;
+
+ // find the point closest to the seed
+ for (var i$2 = 0; i$2 < n; i$2++) {
+ if (i$2 === i0) { continue; }
+ var d$1 = dist(coords[2 * i0], coords[2 * i0 + 1], coords[2 * i$2], coords[2 * i$2 + 1]);
+ if (d$1 < minDist && d$1 > 0) {
+ i1 = i$2;
+ minDist = d$1;
+ }
+ }
+
+ var minRadius = Infinity;
+
+ // find the third point which forms the smallest circumcircle with the first two
+ for (var i$3 = 0; i$3 < n; i$3++) {
+ if (i$3 === i0 || i$3 === i1) { continue; }
+
+ var r = circumradius(
+ coords[2 * i0], coords[2 * i0 + 1],
+ coords[2 * i1], coords[2 * i1 + 1],
+ coords[2 * i$3], coords[2 * i$3 + 1]);
+
+ if (r < minRadius) {
+ i2 = i$3;
+ minRadius = r;
+ }
+ }
+
+ 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) {
+
+ 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 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);
+
+ // initialize a hash table for storing edges of the advancing convex hull
+ this._hashSize = Math.ceil(Math.sqrt(n));
+ this._hash = [];
+ for (var i$4 = 0; i$4 < this._hashSize; i$4++) { this$1._hash[i$4] = 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;
+
+ 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._addTriangle(i0, i1, i2, -1, -1, -1);
+
+ for (var k = 0, xp = (void 0), yp = (void 0); k < ids.length; k++) {
+ var i$5 = ids[k];
+ var x$1 = coords[2 * i$5];
+ var y$1 = coords[2 * i$5 + 1];
+
+ // skip duplicate points
+ if (x$1 === xp && y$1 === yp) { continue; }
+ xp = x$1;
+ yp = y$1;
+
+ // skip seed triangle points
+ if ((x$1 === i0x && y$1 === i0y) ||
+ (x$1 === i1x && y$1 === i1y) ||
+ (x$1 === i2x && y$1 === i2y)) { continue; }
+
+ // find a visible edge on the convex hull using edge hash
+ var startKey = this$1._hashKey(x$1, y$1);
+ var key = startKey;
+ var start = (void 0);
+ do {
+ start = this$1._hash[key];
+ key = (key + 1) % this$1._hashSize;
+ } while ((!start || start.removed) && key !== startKey);
+
+ e = start;
+ while (area(x$1, y$1, 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;
+
+ // add the first triangle from the point
+ var t = this$1._addTriangle(e.i, i$5, e.next.i, -1, -1, e.t);
+
+ e.t = t; // keep track of boundary triangles on the hull
+ e = insertNode(coords, i$5, e);
+
+ // recursively flip triangles from the point until they satisfy the Delaunay condition
+ e.t = this$1._legalize(t + 2);
+
+ // walk forward through the hull, adding more triangles and flipping recursively
+ var q = e.next;
+ while (area(x$1, y$1, q.x, q.y, q.next.x, q.next.y) < 0) {
+ t = this$1._addTriangle(q.i, i$5, q.next.i, q.prev.t, -1, q.t);
+ q.prev.t = this$1._legalize(t + 2);
+ this$1.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$1, y$1, q.prev.x, q.prev.y, q.x, q.y) < 0) {
+ t = this$1._addTriangle(q.prev.i, i$5, q.i, -1, q.t, q.prev.t);
+ this$1._legalize(t + 2);
+ q.prev.t = t;
+ this$1.hull = removeNode(q);
+ q = q.prev;
+ }
+ }
+
+ // save the two new edges in the hash table
+ this$1._hashEdge(e);
+ this$1._hashEdge(e.prev);
+ }
+
+ // trim typed triangle mesh arrays
+ this.triangles = triangles.subarray(0, this.trianglesLen);
+ this.halfedges = halfedges.subarray(0, this.trianglesLen);
+ };
+
+ Delaunator.from = function from (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);
+ };
+
+ Delaunator.prototype._hashEdge = function _hashEdge (e) {
+ this._hash[this._hashKey(e.x, e.y)] = e;
+ };
+
+ Delaunator.prototype._hashKey = function _hashKey (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);
+ };
+
+ Delaunator.prototype._legalize = function _legalize (a) {
+ var ref = this;
+ var triangles = ref.triangles;
+ var coords = ref.coords;
+ var halfedges = ref.halfedges;
+
+ var b = halfedges[a];
+
+ /* if the pair of triangles doesn't satisfy the Delaunay condition
+ * (p1 is inside the circumcircle of [p0, pl, pr]), flip them,
+ * then do the same check/flip recursively for the new pair of triangles
+ *
+ * pl pl
+ * /||\ / \
+ * al/ || \bl al/\a
+ * / || \ / \
+ * / a||b \flip/___ar___\
+ * p0\ || /p1 => p0\---bl---/p1
+ * \ || / \ /
+ * ar\ || /br b\/br
+ * \||/ \ /
+ * pr pr
+ */
+ 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 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]);
+
+ if (illegal) {
+ triangles[a] = p1;
+ triangles[b] = p0;
+
+ var hbl = halfedges[bl];
+
+ // edge swapped on the other side of the hull (rare); fix the halfedge reference
+ if (hbl === -1) {
+ var 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;
+
+ this._legalize(a);
+ return this._legalize(br);
+ }
+
+ return ar;
+ };
+
+ Delaunator.prototype._link = function _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
+ Delaunator.prototype._addTriangle = function _addTriangle (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._link(t, a);
+ this._link(t + 1, b);
+ this._link(t + 2, c);
+
+ this.trianglesLen += 3;
+
+ return t;
+ };
+
+ 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 inCircle(ax, ay, bx, by, cx, cy, px, py) {
+ var dx = ax - px;
+ var dy = ay - py;
+ var ex = bx - px;
+ var ey = by - py;
+ var fx = cx - px;
+ var fy = cy - py;
+
+ var ap = dx * dx + dy * dy;
+ var bp = ex * ex + ey * ey;
+ var cp = fx * fx + fy * fy;
+
+ return dx * (ey * cp - bp * fy) -
+ dy * (ex * cp - bp * fx) +
+ ap * (ex * fy - ey * fx) < 0;
+ }
+
+ function circumradius(ax, ay, bx, by, cx, cy) {
+ var dx = bx - ax;
+ var dy = by - ay;
+ var ex = cx - ax;
+ var ey = cy - ay;
+
+ var bl = dx * dx + dy * dy;
+ var cl = ex * ex + ey * ey;
+ var d = dx * ey - dy * ex;
+
+ var x = (ey * bl - dy * cl) * 0.5 / d;
+ var y = (dx * cl - ex * bl) * 0.5 / d;
+
+ return bl && cl && d && (x * x + y * y) || Infinity;
+ }
+
+ function circumcenter(ax, ay, bx, by, cx, cy) {
+ var dx = bx - ax;
+ var dy = by - ay;
+ var ex = cx - ax;
+ var ey = cy - ay;
+
+ var bl = dx * dx + dy * dy;
+ var cl = ex * ex + ey * ey;
+ var d = dx * ey - dy * ex;
+
+ var x = ax + (ey * bl - dy * cl) * 0.5 / d;
+ var y = ay + (dx * cl - ex * bl) * 0.5 / d;
+
+ return {x: x, y: 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
+ };
+
+ 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;
+ }
+
+ 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;
+
+ if (right - left <= 20) {
+ for (i = left + 1; i <= right; i++) {
+ temp = ids[i];
+ j = i - 1;
+ while (j >= left && compare(coords, ids[j], temp, cx, cy) > 0) { ids[j + 1] = ids[j--]; }
+ ids[j + 1] = temp;
+ }
+ } else {
+ var median = (left + right) >> 1;
+ i = left + 1;
+ j = right;
+ swap(ids, median, i);
+ if (compare(coords, ids[left], ids[right], cx, cy) > 0) { swap(ids, left, right); }
+ if (compare(coords, ids[i], ids[right], cx, cy) > 0) { swap(ids, i, right); }
+ if (compare(coords, ids[left], ids[i], cx, cy) > 0) { swap(ids, left, i); }
+
+ temp = ids[i];
+ while (true) {
+ do { i++; } while (compare(coords, ids[i], temp, cx, cy) < 0);
+ do { j--; } while (compare(coords, ids[j], temp, cx, cy) > 0);
+ if (j < i) { break; }
+ swap(ids, i, j);
+ }
+ ids[left + 1] = ids[j];
+ ids[j] = temp;
+
+ 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 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];
+ }
+
+ return Delaunator;
+
+})));
diff --git a/generate-reference-triangles/node_modules/delaunator/delaunator.min.js b/generate-reference-triangles/node_modules/delaunator/delaunator.min.js
new file mode 100644
index 0000000..0b1287d
--- /dev/null
+++ b/generate-reference-triangles/node_modules/delaunator/delaunator.min.js
@@ -0,0 +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";var t=function(t){var o=1/0,l=1/0,f=-1/0,v=-1/0,u=t.length>>1,d=this.ids=new Uint32Array(u);if(u>0&&"number"!=typeof t[0])throw new Error("Expected coords to contain numbers.");this.coords=t;for(var g=0;g<u;g++){var _=t[2*g],p=t[2*g+1];_<o&&(o=_),p<l&&(l=p),_>f&&(f=_),p>v&&(v=p),d[g]=g}for(var x,c,y,w=(o+f)/2,m=(l+v)/2,z=1/0,E=0;E<u;E++){var b=e(w,m,t[2*E],t[2*E+1]);b<z&&(x=E,z=b)}z=1/0;for(var k=0;k<u;k++)if(k!==x){var L=e(t[2*x],t[2*x+1],t[2*k],t[2*k+1]);L<z&&L>0&&(c=k,z=L)}for(var M=1/0,S=0;S<u;S++)if(S!==x&&S!==c){var T=i(t[2*x],t[2*x+1],t[2*c],t[2*c+1],t[2*S],t[2*S+1]);T<M&&(y=S,M=T)}if(M===1/0)throw new Error("No Delaunay triangulation exists for this input.");if(r(t[2*x],t[2*x+1],t[2*c],t[2*c+1],t[2*y],t[2*y+1])<0){var A=c;c=y,y=A}var K=t[2*x],D=t[2*x+1],U=t[2*c],j=t[2*c+1],q=t[2*y],F=t[2*y+1],I=function(t,e,r,i,n,h){var s=r-t,a=i-e,o=n-t,l=h-e,f=s*s+a*a,v=o*o+l*l,u=s*l-a*o;return{x:t+.5*(l*f-a*v)/u,y:e+.5*(s*v-o*f)/u}}(K,D,U,j,q,F);this._cx=I.x,this._cy=I.y,function t(e,r,i,n,h,o){var l,f,v;if(n-i<=20)for(l=i+1;l<=n;l++){for(v=e[l],f=l-1;f>=i&&s(r,e[f],v,h,o)>0;)e[f+1]=e[f--];e[f+1]=v}else{var u=i+n>>1;for(f=n,a(e,u,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),v=e[l];;){do{l++}while(s(r,e[l],v,h,o)<0);do{f--}while(s(r,e[f],v,h,o)>0);if(f<l)break;a(e,l,f)}e[i+1]=e[f],e[f]=v,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,I.x,I.y),this._hashSize=Math.ceil(Math.sqrt(u)),this._hash=[];for(var N=0;N<this._hashSize;N++)this._hash[N]=null;var B=this.hull=n(t,x);this._hashEdge(B),B.t=0,B=n(t,c,B),this._hashEdge(B),B.t=1,B=n(t,y,B),this._hashEdge(B),B.t=2;var C=2*u-5,G=this.triangles=new Uint32Array(3*C),H=this.halfedges=new Int32Array(3*C);this.trianglesLen=0,this._addTriangle(x,c,y,-1,-1,-1);for(var J=0,O=void 0,P=void 0;J<d.length;J++){var Q=d[J],R=t[2*Q],V=t[2*Q+1];if((R!==O||V!==P)&&(O=R,P=V,!(R===K&&V===D||R===U&&V===j||R===q&&V===F))){var W=this._hashKey(R,V),X=W,Y=void 0;do{Y=this._hash[X],X=(X+1)%this._hashSize}while((!Y||Y.removed)&&X!==W);for(B=Y;r(R,V,B.x,B.y,B.next.x,B.next.y)>=0;)if((B=B.next)===Y)throw new Error("Something is wrong with the input points.");var Z=B===Y,$=this._addTriangle(B.i,Q,B.next.i,-1,-1,B.t);B.t=$,(B=n(t,Q,B)).t=this._legalize($+2);for(var tt=B.next;r(R,V,tt.x,tt.y,tt.next.x,tt.next.y)<0;)$=this._addTriangle(tt.i,Q,tt.next.i,tt.prev.t,-1,tt.t),tt.prev.t=this._legalize($+2),this.hull=h(tt),tt=tt.next;if(Z)for(tt=B.prev;r(R,V,tt.prev.x,tt.prev.y,tt.x,tt.y)<0;)$=this._addTriangle(tt.prev.i,Q,tt.i,-1,tt.t,tt.prev.t),this._legalize($+2),tt.prev.t=$,this.hull=h(tt),tt=tt.prev;this._hashEdge(B),this._hashEdge(B.prev)}}this.triangles=G.subarray(0,this.trianglesLen),this.halfedges=H.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,a=i-e,o=n-t,l=h-e,f=s*s+a*a,v=o*o+l*l,u=s*l-a*o,d=.5*(l*f-a*v)/u,g=.5*(s*v-o*f)/u;return f&&v&&u&&d*d+g*g||1/0}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},t.prototype._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)},t.prototype._legalize=function(t){var e,r,i,n,h,s,a,o,l,f,v,u,d,g,_,p,x=this.triangles,c=this.coords,y=this.halfedges,w=y[t],m=t-t%3,z=w-w%3,E=m+(t+1)%3,b=m+(t+2)%3,k=z+(w+2)%3,L=x[b],M=x[t],S=x[E],T=x[k];if(e=c[2*L],r=c[2*L+1],i=c[2*M],n=c[2*M+1],h=c[2*S],s=c[2*S+1],a=c[2*T],o=c[2*T+1],(l=e-a)*((u=n-o)*(p=(d=h-a)*d+(g=s-o)*g)-(_=(v=i-a)*v+u*u)*g)-(f=r-o)*(v*p-_*d)+(l*l+f*f)*(v*g-u*d)<0){x[t]=T,x[w]=L;var A=y[k];if(-1===A){var K=this.hull;do{if(K.t===k){K.t=t;break}K=K.next}while(K!==this.hull)}this._link(t,A),this._link(w,y[b]),this._link(b,k);var D=z+(w+1)%3;return this._legalize(t),this._legalize(D)}return b},t.prototype._link=function(t,e){this.halfedges[t]=e,-1!==e&&(this.halfedges[e]=t)},t.prototype._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});
diff --git a/generate-reference-triangles/node_modules/delaunator/index.js b/generate-reference-triangles/node_modules/delaunator/index.js
new file mode 100644
index 0000000..e0dfa30
--- /dev/null
+++ b/generate-reference-triangles/node_modules/delaunator/index.js
@@ -0,0 +1,464 @@
+
+export default class Delaunator {
+
+ static from(points, getX, getY) {
+ if (!getX) getX = defaultGetX;
+ if (!getY) getY = defaultGetY;
+
+ const n = points.length;
+ const coords = new Float64Array(n * 2);
+
+ for (let i = 0; i < n; i++) {
+ const p = points[i];
+ coords[2 * i] = getX(p);
+ coords[2 * i + 1] = getY(p);
+ }
+
+ return new Delaunator(coords);
+ }
+
+ constructor(coords) {
+ let minX = Infinity;
+ let minY = Infinity;
+ let maxX = -Infinity;
+ let maxY = -Infinity;
+
+ const n = coords.length >> 1;
+ const ids = this.ids = new Uint32Array(n);
+
+ if (n > 0 && typeof coords[0] !== 'number') throw new Error('Expected coords to contain numbers.');
+
+ 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;
+ }
+
+ const cx = (minX + maxX) / 2;
+ const cy = (minY + maxY) / 2;
+
+ let minDist = Infinity;
+ let i0, i1, i2;
+
+ // 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;
+
+ // 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;
+ }
+ }
+
+ let minRadius = Infinity;
+
+ // find the third point which forms the smallest circumcircle with the first two
+ for (let i = 0; i < n; i++) {
+ if (i === i0 || i === i1) continue;
+
+ const r = circumradius(
+ 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.');
+ }
+
+ // 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) {
+
+ const tmp = i1;
+ i1 = i2;
+ i2 = tmp;
+ }
+
+ 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];
+
+ 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);
+
+ // 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
+ 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;
+
+ 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._addTriangle(i0, i1, i2, -1, -1, -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 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
+ 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.');
+ }
+ }
+
+ const walkBack = e === start;
+
+ // 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);
+
+ // 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
+ 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.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);
+ }
+
+ // trim typed triangle mesh arrays
+ this.triangles = triangles.subarray(0, this.trianglesLen);
+ this.halfedges = halfedges.subarray(0, this.trianglesLen);
+ }
+
+ _hashEdge(e) {
+ this._hash[this._hashKey(e.x, e.y)] = e;
+ }
+
+ _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
+ const p = 1 - dx / (Math.abs(dx) + Math.abs(dy));
+ return Math.floor((2 + (dy < 0 ? -p : p)) / 4 * this._hashSize);
+ }
+
+ _legalize(a) {
+ const {triangles, coords, halfedges} = this;
+
+ const b = halfedges[a];
+
+ /* if the pair of triangles doesn't satisfy the Delaunay condition
+ * (p1 is inside the circumcircle of [p0, pl, pr]), flip them,
+ * then do the same check/flip recursively for the new pair of triangles
+ *
+ * pl pl
+ * /||\ / \
+ * al/ || \bl al/ \a
+ * / || \ / \
+ * / a||b \ flip /___ar___\
+ * p0\ || /p1 => p0\---bl---/p1
+ * \ || / \ /
+ * ar\ || /br b\ /br
+ * \||/ \ /
+ * pr pr
+ */
+ const a0 = a - a % 3;
+ const b0 = b - b % 3;
+
+ const al = a0 + (a + 1) % 3;
+ const ar = a0 + (a + 2) % 3;
+ const bl = b0 + (b + 2) % 3;
+
+ const p0 = triangles[ar];
+ const pr = triangles[a];
+ const pl = triangles[al];
+ const p1 = triangles[bl];
+
+ const illegal = inCircle(
+ coords[2 * p0], coords[2 * p0 + 1],
+ coords[2 * pr], coords[2 * pr + 1],
+ coords[2 * pl], coords[2 * pl + 1],
+ coords[2 * p1], coords[2 * p1 + 1]);
+
+ if (illegal) {
+ triangles[a] = p1;
+ triangles[b] = p0;
+
+ const hbl = halfedges[bl];
+
+ // edge swapped on the other side of the hull (rare); fix the halfedge reference
+ if (hbl === -1) {
+ let e = this.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);
+
+ const br = b0 + (b + 1) % 3;
+
+ this._legalize(a);
+ return this._legalize(br);
+ }
+
+ return ar;
+ }
+
+ _link(a, b) {
+ this.halfedges[a] = b;
+ if (b !== -1) this.halfedges[b] = a;
+ }
+
+ // add a new triangle given vertex indices and adjacent half-edge ids
+ _addTriangle(i0, i1, i2, a, b, c) {
+ const t = this.trianglesLen;
+
+ this.triangles[t] = i0;
+ this.triangles[t + 1] = i1;
+ this.triangles[t + 2] = i2;
+
+ this._link(t, a);
+ this._link(t + 1, b);
+ this._link(t + 2, c);
+
+ this.trianglesLen += 3;
+
+ return t;
+ }
+}
+
+function dist(ax, ay, bx, by) {
+ const dx = ax - bx;
+ const 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 inCircle(ax, ay, bx, by, cx, cy, px, py) {
+ const dx = ax - px;
+ const dy = ay - py;
+ const ex = bx - px;
+ const ey = by - py;
+ const fx = cx - px;
+ const fy = cy - py;
+
+ const ap = dx * dx + dy * dy;
+ const bp = ex * ex + ey * ey;
+ const cp = fx * fx + fy * fy;
+
+ return dx * (ey * cp - bp * fy) -
+ dy * (ex * cp - bp * fx) +
+ ap * (ex * fy - ey * fx) < 0;
+}
+
+function circumradius(ax, ay, bx, by, cx, cy) {
+ const dx = bx - ax;
+ const dy = by - ay;
+ const ex = cx - ax;
+ const ey = cy - ay;
+
+ const bl = dx * dx + dy * dy;
+ const cl = ex * ex + ey * ey;
+ const d = dx * ey - dy * ex;
+
+ const x = (ey * bl - dy * cl) * 0.5 / d;
+ const y = (dx * cl - ex * bl) * 0.5 / d;
+
+ return bl && cl && d && (x * x + y * y) || Infinity;
+}
+
+function circumcenter(ax, ay, bx, by, cx, cy) {
+ const dx = bx - ax;
+ const dy = by - ay;
+ const ex = cx - ax;
+ const ey = cy - ay;
+
+ const bl = dx * dx + dy * dy;
+ const cl = ex * ex + ey * ey;
+ const d = dx * ey - dy * ex;
+
+ const x = ax + (ey * bl - dy * cl) * 0.5 / d;
+ const y = ay + (dx * cl - ex * bl) * 0.5 / d;
+
+ return {x, y};
+}
+
+// create a new node in a doubly linked list
+function insertNode(coords, i, prev) {
+ const node = {
+ 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;
+
+ } else {
+ node.next = prev.next;
+ node.prev = prev;
+ prev.next.prev = node;
+ prev.next = node;
+ }
+ return node;
+}
+
+function removeNode(node) {
+ node.prev.next = node.next;
+ node.next.prev = node.prev;
+ node.removed = true;
+ return node.prev;
+}
+
+function quicksort(ids, coords, left, right, cx, cy) {
+ let 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 {
+ const median = (left + right) >> 1;
+ i = left + 1;
+ j = right;
+ swap(ids, median, i);
+ if (compare(coords, ids[left], ids[right], cx, cy) > 0) swap(ids, left, right);
+ if (compare(coords, ids[i], ids[right], cx, cy) > 0) swap(ids, i, right);
+ if (compare(coords, ids[left], ids[i], cx, cy) > 0) swap(ids, left, i);
+
+ temp = ids[i];
+ while (true) {
+ do i++; while (compare(coords, ids[i], temp, cx, cy) < 0);
+ do j--; while (compare(coords, ids[j], temp, cx, cy) > 0);
+ if (j < i) break;
+ swap(ids, i, j);
+ }
+ ids[left + 1] = ids[j];
+ ids[j] = temp;
+
+ 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) {
+ 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]);
+}
+
+function swap(arr, i, j) {
+ const tmp = arr[i];
+ arr[i] = arr[j];
+ arr[j] = tmp;
+}
+
+function defaultGetX(p) {
+ return p[0];
+}
+function defaultGetY(p) {
+ return p[1];
+}
diff --git a/generate-reference-triangles/node_modules/delaunator/package.json b/generate-reference-triangles/node_modules/delaunator/package.json
new file mode 100644
index 0000000..61c717d
--- /dev/null
+++ b/generate-reference-triangles/node_modules/delaunator/package.json
@@ -0,0 +1,88 @@
+{
+ "_args": [
+ [
+ "delaunator@2.0.2",
+ "/Users/delfrrr/dev/delaunator-cpp/generate-reference-triangles"
+ ]
+ ],
+ "_from": "delaunator@2.0.2",
+ "_id": "delaunator@2.0.2",
+ "_inBundle": false,
+ "_integrity": "sha512-b/M9/hu3wcGByyjqsLplB6ZyU7ZcMWTj79Kava6eSmQ2Ih2BbJR3KbqfpmyabTdkIyI9kKZS6+3nZOs+eTYXMQ==",
+ "_location": "/delaunator",
+ "_phantomChildren": {},
+ "_requested": {
+ "type": "version",
+ "registry": true,
+ "raw": "delaunator@2.0.2",
+ "name": "delaunator",
+ "escapedName": "delaunator",
+ "rawSpec": "2.0.2",
+ "saveSpec": null,
+ "fetchSpec": "2.0.2"
+ },
+ "_requiredBy": [
+ "/"
+ ],
+ "_resolved": "https://registry.npmjs.org/delaunator/-/delaunator-2.0.2.tgz",
+ "_spec": "2.0.2",
+ "_where": "/Users/delfrrr/dev/delaunator-cpp/generate-reference-triangles",
+ "author": {
+ "name": "Vladimir Agafonkin"
+ },
+ "bugs": {
+ "url": "https://github.com/mapbox/delaunator/issues"
+ },
+ "dependencies": {},
+ "description": "A really fast JavaScript library for Delaunay triangulation of 2D points",
+ "devDependencies": {
+ "eslint": "^5.4.0",
+ "eslint-config-mourner": "^3.0.0",
+ "esm": "^3.0.80",
+ "rollup": "^0.65.0",
+ "rollup-plugin-buble": "^0.19.2",
+ "rollup-plugin-terser": "^1.0.1",
+ "tape": "^4.9.1"
+ },
+ "eslintConfig": {
+ "extends": "mourner",
+ "parserOptions": {
+ "sourceType": "module"
+ },
+ "rules": {
+ "no-var": "error",
+ "prefer-const": "error"
+ }
+ },
+ "files": [
+ "index.js",
+ "delaunator.js",
+ "delaunator.min.js"
+ ],
+ "homepage": "https://github.com/mapbox/delaunator#readme",
+ "jsdelivr": "delaunator.min.js",
+ "keywords": [
+ "delaunay triangulation",
+ "computational geometry",
+ "algorithms"
+ ],
+ "license": "ISC",
+ "main": "delaunator.js",
+ "module": "index.js",
+ "name": "delaunator",
+ "repository": {
+ "type": "git",
+ "url": "git+https://github.com/mapbox/delaunator.git"
+ },
+ "scripts": {
+ "bench": "node -r esm bench.js",
+ "build": "rollup -c",
+ "lint": "eslint index.js test.js bench.js rollup.config.js",
+ "prepublishOnly": "npm test && npm build",
+ "pretest": "npm run lint",
+ "start": "rollup -cw",
+ "test": "node -r esm test.js"
+ },
+ "unpkg": "delaunator.min.js",
+ "version": "2.0.2"
+}
diff --git a/generate-reference-triangles/package-lock.json b/generate-reference-triangles/package-lock.json
new file mode 100644
index 0000000..93b0d08
--- /dev/null
+++ b/generate-reference-triangles/package-lock.json
@@ -0,0 +1,12 @@
+{
+ "name": "generate-reference-triangles",
+ "requires": true,
+ "lockfileVersion": 1,
+ "dependencies": {
+ "delaunator": {
+ "version": "2.0.2",
+ "resolved": "https://registry.npmjs.org/delaunator/-/delaunator-2.0.2.tgz",
+ "integrity": "sha512-b/M9/hu3wcGByyjqsLplB6ZyU7ZcMWTj79Kava6eSmQ2Ih2BbJR3KbqfpmyabTdkIyI9kKZS6+3nZOs+eTYXMQ=="
+ }
+ }
+}
diff --git a/generate-reference-triangles/package.json b/generate-reference-triangles/package.json
new file mode 100644
index 0000000..41094b5
--- /dev/null
+++ b/generate-reference-triangles/package.json
@@ -0,0 +1,8 @@
+{
+ "name": "generate-reference-triangles",
+ "private": true,
+ "main": "index.js",
+ "dependencies": {
+ "delaunator": "^2.0.2"
+ }
+}
diff --git a/test-files/playgrounds-1356-triangles.json b/test-files/playgrounds-1356-triangles.json
new file mode 100644
index 0000000..7cde3cf
--- /dev/null
+++ b/test-files/playgrounds-1356-triangles.json
@@ -0,0 +1 @@
+[935,53,798,935,931,53,47,743,53,53,755,798,798,936,935,743,927,53,743,49,927,1325,936,798,931,1012,53,743,47,49,48,47,53,1012,48,53,1012,926,48,931,354,1012,1012,354,926,1233,1234,931,755,53,927,49,755,927,354,1190,926,926,1238,48,755,1325,798,755,563,1325,354,829,1190,697,829,354,988,1238,585,48,1238,47,47,310,49,49,574,755,1238,926,585,1325,349,936,563,349,1325,536,349,563,1234,242,931,931,242,354,1238,310,47,310,203,49,930,536,563,599,203,310,242,697,354,1233,931,935,242,705,697,1233,935,1266,1266,935,936,1233,761,1234,1234,1291,242,379,761,1233,697,699,829,700,699,706,699,700,829,706,699,697,930,563,755,349,451,936,298,705,242,705,706,697,1238,599,310,985,988,585,700,698,829,985,986,988,706,698,700,988,987,1238,988,986,987,987,599,1238,926,1190,585,451,1266,936,574,930,755,598,599,987,585,1190,541,536,451,349,761,1291,1234,705,704,706,706,704,698,379,1291,761,1266,1173,1233,660,1173,1266,598,987,638,203,574,49,638,987,986,985,638,986,599,762,203,754,762,573,541,1190,829,985,33,638,1173,379,1233,1291,298,242,442,298,1291,298,704,705,762,574,203,754,574,762,1173,660,379,1265,660,1266,451,1265,1266,2,1265,451,704,703,698,1147,541,829,701,703,704,298,701,704,701,702,703,703,918,698,585,33,985,638,577,598,573,762,599,1265,2,660,570,2,1268,701,918,702,702,918,703,1227,918,1097,458,829,698,585,380,33,573,599,598,574,1249,930,918,458,698,401,573,717,930,569,536,570,339,2,554,1249,574,2,340,660,660,970,379,339,340,2,717,573,598,34,380,585,754,554,574,573,401,754,577,638,33,918,1227,458,1097,918,701,298,1097,701,442,1097,298,340,970,660,2,451,1268,339,341,340,570,341,339,541,34,585,1147,199,541,458,1147,829,588,200,450,199,200,541,1249,569,930,817,321,1249,200,34,541,380,578,33,458,333,1147,1227,1226,458,1097,1226,1227,341,970,340,442,857,1097,774,451,536,1226,923,458,570,970,341,401,554,754,717,554,401,321,569,1249,450,200,199,200,588,34,569,772,536,588,578,34,34,578,380,1147,450,199,853,577,578,772,774,536,1194,774,772,1194,772,569,321,921,569,0,921,321,578,577,33,853,578,1257,577,717,598,817,0,321,774,54,451,1075,54,774,54,1268,451,570,1071,970,817,1249,554,921,1194,569,1250,817,554,73,1250,554,717,73,554,1226,958,923,923,653,458,1147,333,450,957,958,857,958,1226,857,857,1226,1097,854,853,1257,577,886,717,538,226,73,1256,1194,921,442,1291,379,853,856,577,1257,578,588,854,855,853,856,855,854,855,856,853,1258,856,854,450,1257,588,1257,1258,854,1259,1258,1257,1268,1071,570,970,442,379,1258,1259,856,450,1259,1257,0,5,921,383,5,0,383,0,817,957,663,958,958,653,923,857,663,957,507,383,817,226,817,1250,648,653,958,553,597,1259,1231,886,856,856,886,577,876,442,970,873,858,663,1194,1075,774,54,198,1268,1268,513,1071,1076,1075,452,73,226,1250,538,73,717,663,647,958,873,663,857,647,648,958,1259,597,856,553,1259,450,858,647,663,1075,1076,54,452,1075,1194,1256,452,1194,493,921,5,858,215,647,747,873,857,383,1148,5,226,507,817,1077,198,54,507,1148,383,653,333,458,648,708,653,215,708,648,1191,708,197,1076,1077,54,146,1077,1076,605,747,857,1066,876,970,1196,876,1066,1187,333,653,886,1245,717,226,571,507,1251,1245,886,1245,538,717,198,1223,1268,149,1153,198,1153,1223,198,1224,1223,1153,19,493,5,452,146,1076,1223,1224,1268,149,1224,1153,493,1256,921,876,1196,442,1066,970,1071,625,396,538,538,396,226,333,553,450,1303,1187,653,493,1255,1256,1148,19,5,1162,149,1077,1077,149,198,1256,1255,452,19,1255,493,597,1231,856,605,857,442,873,747,858,1196,884,442,471,884,1196,513,1066,1071,1262,1251,886,1245,625,538,1261,553,333,125,1229,1231,1246,146,452,1231,1262,886,825,571,396,396,571,226,507,712,1148,1148,712,19,625,1245,1251,1224,513,1268,976,513,1224,215,648,647,877,605,442,146,938,1077,149,1182,1224,605,604,747,1172,604,108,1335,1182,149,1162,1335,149,938,1162,1077,1160,1161,1162,1162,1161,1335,884,1150,442,471,1150,884,877,1150,471,938,1160,1162,1161,1349,1335,586,712,507,448,1246,826,632,938,146,632,1350,938,708,1191,653,215,858,747,1187,1261,333,908,1261,1187,1146,215,747,1262,684,1251,1319,684,1262,938,1350,1160,1160,1084,1161,1335,1349,1182,1246,452,1255,1246,1255,826,969,1319,1262,206,1262,1231,1350,1084,1160,1182,976,1224,632,1084,1350,215,197,708,712,295,19,304,295,712,1229,206,1231,125,1231,126,1084,1349,1161,959,632,146,206,969,1262,622,625,684,684,625,1251,1247,969,206,197,1112,1191,215,1112,197,1146,1112,215,1180,1303,1191,1191,1303,653,1112,1180,1191,1348,1349,1084,487,1348,1084,1349,356,1182,126,1231,124,1230,1247,206,1231,597,124,76,908,1187,1261,359,553,909,1247,1230,124,597,564,632,487,1084,959,1339,632,911,684,1319,571,586,507,1339,487,632,462,1334,1118,537,586,571,625,825,396,861,359,860,359,239,553,860,359,1261,969,911,1319,206,1229,1230,295,279,19,304,279,295,126,124,125,564,597,523,1247,909,969,1230,1229,880,880,1229,125,861,239,359,908,860,1261,586,304,712,863,239,861,462,356,1348,1348,356,1349,513,1046,1066,31,976,1182,860,862,861,863,862,860,976,1046,513,862,863,861,360,863,469,1172,1146,747,225,940,1180,1172,747,604,1040,1041,893,487,462,1348,462,487,1334,959,146,1246,1230,911,909,909,911,969,725,724,825,686,911,1310,279,280,19,304,284,279,628,284,304,586,186,304,537,186,586,284,280,279,108,604,605,186,628,304,284,178,280,976,1041,1046,471,1196,355,31,1182,356,826,1255,19,621,619,625,859,537,571,462,1058,356,1118,1058,462,178,305,628,628,305,284,1334,487,1339,1150,877,442,355,1066,1046,859,571,825,165,178,628,1041,1040,1046,893,1041,976,725,825,625,622,621,625,911,622,684,448,959,1246,181,620,621,621,620,619,1058,31,356,1118,1117,1058,1165,1117,1118,959,1334,1339,1120,1059,1117,1117,1059,1058,523,597,553,124,880,125,448,449,959,826,449,448,1334,1165,1118,1318,1165,1334,1318,1334,959,725,619,620,725,625,619,726,725,620,239,523,553,376,523,239,225,1180,1112,1180,940,1303,1303,76,1187,225,1112,1146,787,225,1146,1172,218,1146,852,218,1172,461,1058,1059,461,31,1058,355,1196,1066,1239,893,976,1165,1120,1117,1355,1318,959,153,726,620,725,726,724,724,726,825,893,1039,1040,1045,1039,893,911,1163,622,622,1163,621,686,1163,911,1043,1046,1040,788,835,218,1119,461,1059,1044,1045,188,153,859,726,726,859,825,1318,1120,1165,1166,1355,1167,1039,1043,1040,1045,1043,1039,218,835,1146,1355,1120,1318,564,55,124,750,565,564,1163,181,621,667,911,1230,1355,1166,1120,1167,1355,959,225,473,940,940,473,1303,979,473,386,835,786,1146,789,786,835,1166,1168,1120,1175,1167,959,1239,976,31,1127,1168,1123,1167,1168,1166,1119,1107,461,786,787,1146,788,789,835,788,218,400,280,826,19,476,1175,959,178,826,280,1119,1059,1120,461,1177,31,565,55,564,750,55,565,1152,1119,1127,1070,1177,1107,1107,1177,461,108,605,877,789,787,786,788,787,789,476,959,449,1127,1119,1120,1045,1044,1043,1043,355,1046,188,1045,893,398,476,449,1175,1174,1167,1119,1129,1107,468,1174,1175,686,181,1163,1310,181,686,375,967,123,1127,1120,1168,1053,1239,31,1123,1168,1167,1127,1126,1152,1124,1123,1167,1123,1126,1127,1174,1124,1167,1125,1126,1123,1128,1129,1152,1152,1129,1119,523,750,564,55,566,124,1007,1106,1124,1124,1125,1123,476,468,1175,398,468,476,305,178,284,165,628,186,165,186,537,1126,1125,1152,1106,1125,1124,355,392,471,375,355,967,1053,31,1177,967,355,1043,1129,1070,1107,1158,1128,1152,1239,188,893,1086,188,641,1128,1070,1129,1062,1070,237,408,165,71,181,153,620,750,566,55,375,392,355,967,1049,1038,967,1043,1049,172,165,408,473,998,1303,469,863,860,979,998,473,1244,190,1295,788,388,787,237,1070,1063,1070,1062,1177,1106,1152,1125,76,1037,908,863,376,239,523,250,750,1007,1124,1174,1062,1053,1177,237,1053,1062,1063,1070,1128,566,880,124,131,880,566,1248,131,407,131,1248,880,407,131,566,237,1237,1053,1053,1178,1239,1063,1237,237,967,948,123,1049,1043,1044,1049,1044,1050,132,881,880,667,1310,911,822,821,153,1064,1063,1158,1106,1151,1152,1159,1151,1347,1050,1044,1086,998,76,1303,667,1230,880,881,667,880,1248,132,880,731,132,661,165,172,178,525,486,826,398,1174,468,165,537,71,1038,266,967,22,392,375,1049,266,1038,1158,1063,1128,1063,238,1237,1237,1178,1053,1042,948,967,1151,1158,1152,1181,1158,1151,120,119,76,386,473,225,1065,238,1064,1159,1181,1151,266,1042,967,84,1042,266,108,852,1172,787,453,225,108,189,852,1304,1244,1295,108,190,1244,1065,1064,1158,1064,238,1063,469,908,1037,469,860,908,750,407,566,982,469,1037,1244,189,108,108,877,922,1049,84,266,1086,1044,188,238,1178,1237,1304,1305,1244,922,877,495,22,375,123,1181,1159,1158,238,1065,1178,1007,1151,1106,398,449,826,1159,1065,1158,317,863,360,317,376,863,318,317,360,1295,1305,1304,190,1305,1295,376,25,523,533,318,360,317,533,376,990,398,826,132,667,881,731,667,132,495,877,471,1050,84,1049,641,188,1239,1110,1239,1178,852,400,218,399,400,879,1305,189,1244,922,190,108,76,119,1037,469,533,360,120,76,78,400,388,788,879,400,852,119,982,1037,78,76,998,398,1007,1174,1253,479,1065,524,990,826,640,189,1305,189,97,852,1065,479,1178,1110,479,1254,153,821,859,822,153,181,822,181,1310,25,250,523,74,250,25,74,25,376,399,388,400,156,388,399,68,537,859,44,822,1310,1200,74,1202,318,533,317,209,533,469,479,1110,1178,1253,1065,1159,749,495,471,922,955,190,190,107,1305,1201,1198,250,250,1198,750,1201,250,1200,948,22,123,392,749,471,1156,22,948,1156,948,1155,979,878,998,98,878,979,495,955,922,879,852,97,667,910,1310,407,132,1248,22,21,392,84,948,1042,831,407,750,945,98,979,879,156,399,879,97,568,1198,831,750,228,831,1198,568,97,567,1086,748,1050,641,748,1086,1156,21,22,955,107,190,748,84,1050,1156,1155,21,1263,1155,948,731,910,667,661,910,731,990,1007,398,1007,1347,1151,1110,114,1239,1347,1253,1159,1253,1254,479,52,1254,1253,639,640,107,107,640,1305,639,107,109,567,97,1020,109,107,955,878,78,998,1242,1202,1353,113,78,878,639,110,640,110,109,1193,109,955,184,831,315,407,1200,250,74,525,826,178,137,1347,1007,68,859,1085,837,114,1110,748,85,84,114,641,1239,1202,74,376,97,189,1020,879,32,156,1220,1198,1201,1220,228,1198,62,1220,1201,1197,1199,228,228,1199,831,220,661,132,568,32,879,1020,189,110,1085,859,821,69,68,848,68,71,537,68,70,71,848,68,236,227,1197,228,1200,61,1201,69,70,68,71,514,408,1199,315,831,234,228,1220,567,420,568,110,189,640,62,1219,1220,1020,420,567,1219,234,1220,1219,227,234,61,62,1201,60,62,61,220,132,407,1085,821,824,221,220,407,453,787,388,453,388,720,847,72,70,70,72,71,32,388,156,1200,60,61,59,227,1219,234,227,228,1202,60,1200,69,848,70,821,822,824,848,847,70,72,514,71,533,1202,376,982,119,120,59,1219,62,1197,315,1199,59,62,60,229,59,60,1347,1252,1253,837,1006,114,137,1252,1347,137,1007,1016,848,514,847,824,822,735,524,1007,990,975,32,568,453,386,225,719,386,453,109,110,639,1020,975,420,719,720,32,184,955,495,427,315,1197,137,52,1252,1252,52,1253,98,1036,878,78,345,120,945,1036,98,114,559,641,837,1110,1254,1085,236,68,824,236,1085,719,32,1072,32,720,388,1061,837,1254,113,345,78,525,178,172,137,1016,52,525,464,550,486,230,826,230,524,826,144,982,120,1036,113,878,386,945,979,579,945,841,486,219,230,230,480,524,482,525,550,579,113,1036,661,222,910,220,222,661,221,222,220,525,482,486,525,172,464,982,981,469,112,981,982,112,982,144,44,1310,910,482,219,486,315,221,407,481,480,219,483,550,484,514,72,847,837,253,1006,52,1061,1254,559,960,641,641,85,748,84,474,948,559,114,1006,981,209,469,144,120,345,676,184,495,749,392,21,236,514,848,6,514,236,253,559,1006,110,1192,1020,184,1193,109,481,219,482,219,480,230,524,1016,1007,1260,965,964,550,481,482,483,481,550,576,144,345,113,576,345,945,579,1036,841,945,386,720,719,453,975,568,420,227,427,1197,315,427,221,59,229,227,1202,229,60,1111,229,1202,481,1114,480,484,1113,485,484,550,1113,1061,253,837,253,965,1260,1113,464,1116,484,485,483,483,1114,481,559,783,960,960,85,641,782,783,559,485,1114,483,1113,550,464,177,1192,110,302,841,154,205,576,113,506,85,960,1155,1263,21,229,427,227,1242,1111,1202,913,1263,474,1113,1114,485,443,1016,524,464,172,408,1115,1114,1113,783,506,960,216,782,559,1116,1115,1113,603,1115,1116,1192,975,1020,1263,749,21,749,676,495,358,678,749,678,191,749,175,177,1193,678,81,191,191,676,749,358,81,678,80,676,191,1054,466,1192,689,44,910,1104,1105,514,735,44,736,81,80,191,358,80,81,841,302,579,154,841,386,154,386,719,80,679,676,753,358,665,782,506,783,253,216,559,1111,427,229,736,44,916,177,110,1193,675,679,80,1192,466,975,975,1072,32,353,184,352,44,735,822,910,222,689,465,464,408,1115,603,1114,464,603,1116,1114,758,480,474,1263,948,980,506,1013,247,113,579,361,154,1149,735,736,824,689,222,221,464,166,603,974,465,408,665,358,749,474,84,85,679,13,676,1029,13,679,506,971,85,1013,506,782,358,675,80,680,675,358,352,184,676,352,676,13,135,352,13,675,677,679,680,677,675,514,1105,408,1104,6,548,216,1013,782,1260,1013,216,1260,216,253,980,971,506,1013,972,980,972,971,980,1329,1327,1326,175,1193,184,1149,154,719,12,1054,1192,353,1026,184,352,135,353,802,135,13,135,1026,353,603,166,1114,465,166,464,549,166,465,753,680,358,677,1029,679,1111,1313,427,1353,1202,1352,362,1027,1026,1026,1027,184,362,1026,135,1242,1241,1111,1243,1241,1242,1352,1202,533,209,981,112,1241,1243,1111,1353,1243,1242,1105,974,408,185,180,177,177,180,1192,680,1029,677,665,749,1263,240,1029,680,1027,175,184,753,240,680,913,665,1263,665,664,753,1121,1122,974,548,6,7,247,579,302,208,209,112,1329,474,85,913,778,665,1329,85,971,1329,971,1327,208,112,1341,154,361,302,1072,975,466,23,1072,466,180,12,1192,740,12,180,23,466,1054,1341,112,144,175,176,177,710,176,504,504,711,673,1329,1326,474,1327,971,1328,1326,1328,474,1328,971,500,176,185,177,1327,1328,1326,500,971,972,1353,1324,1243,709,1352,533,1243,1313,1111,1312,1313,1324,427,95,221,542,95,427,1313,542,427,1324,1313,1243,196,618,224,778,240,664,576,1341,144,437,1030,209,209,1030,533,176,710,185,185,11,180,278,3,1072,710,504,673,1013,1260,972,1016,1061,52,1312,542,1313,872,1324,1353,778,664,665,664,240,753,808,802,13,710,11,185,176,175,504,974,968,465,1121,974,518,1122,968,974,1072,3,719,23,1054,771,443,524,929,758,1114,166,771,1054,12,673,11,710,504,175,1027,1311,542,1312,1035,66,18,549,758,166,1122,1121,968,518,974,517,914,689,688,142,689,221,1104,514,6,549,465,968,361,247,302,444,437,432,746,247,361,808,13,1029,689,572,44,101,221,95,802,807,135,1121,549,968,802,799,807,809,808,1029,804,799,802,240,809,1029,805,809,806,437,209,208,1149,746,361,23,278,1072,556,278,23,1352,683,1353,1316,1311,1312,733,683,1352,914,572,689,803,799,804,807,362,135,572,916,44,683,872,1353,809,805,808,806,809,240,804,802,808,799,803,807,805,804,808,866,806,240,800,804,866,1316,1312,1324,192,778,913,210,196,224,204,196,210,801,807,803,801,362,807,1277,101,95,914,690,572,1284,95,542,1260,500,972,618,913,224,965,253,1092,1092,253,1061,1121,600,549,549,1215,758,517,974,548,192,913,618,800,801,803,800,803,804,804,805,866,196,204,618,913,474,224,964,281,1260,965,281,964,540,281,965,711,11,673,504,1035,711,1035,504,66,866,805,806,518,600,1121,548,974,1105,278,556,3,771,556,23,1317,1316,872,872,1316,1324,1016,1092,1061,929,524,480,204,194,618,224,607,606,1287,542,1289,1287,1288,542,1030,709,533,683,1317,872,101,142,221,572,695,916,1290,142,101,1288,1284,542,1289,542,1311,1035,11,711,1287,1286,1288,773,1289,944,1289,1286,1287,773,1284,1286,1286,1284,1288,210,195,204,608,195,210,1035,18,11,66,504,1027,66,1027,682,682,490,491,195,194,204,1104,548,1105,6,824,329,758,929,480,1209,1215,1214,1215,1206,1213,29,740,11,11,740,180,1289,773,1286,1284,1277,95,944,1289,1279,195,193,194,224,474,607,740,771,12,1316,1317,1311,994,1317,683,800,865,801,865,866,240,865,240,781,1270,1277,1274,866,865,800,277,240,778,1215,1209,758,600,518,517,1274,1277,1284,1277,1276,101,1274,1284,1280,1270,1276,1277,522,600,517,194,192,618,608,193,195,1270,1271,1276,1280,1284,773,142,688,689,916,695,736,690,688,105,1206,1215,549,1213,1214,1215,1209,1208,758,1212,1203,1214,1204,1206,549,1276,1290,101,1272,1271,1273,1206,1212,1213,600,1204,549,1030,438,709,1341,437,208,307,1341,576,193,192,194,607,612,610,224,608,210,1273,1271,1270,944,1280,773,1273,1270,1274,1271,1290,1276,1281,1273,1274,691,690,105,1203,1209,1214,1203,1208,1209,247,205,113,688,690,914,1290,1271,1272,606,608,224,612,474,611,616,608,606,1281,1290,1272,1281,1272,1273,1212,1214,1213,1208,378,758,1212,1206,1204,192,277,778,1280,1281,1274,1283,944,1279,1210,1212,1216,1275,1281,1280,692,691,105,690,691,572,692,832,694,692,695,572,607,616,606,608,610,193,780,277,776,610,616,607,1212,1210,1203,1203,1207,1208,1216,1212,1204,1205,1207,1203,1211,1205,1210,405,522,517,247,819,205,1149,719,3,674,3,556,691,692,572,539,142,1290,1210,1205,1203,718,378,1208,1216,1204,600,18,29,11,682,1027,362,1297,1216,600,281,500,1260,596,500,285,718,1207,1205,718,1208,1207,1216,1211,1210,546,1211,1216,546,718,1205,378,929,758,1033,1092,1016,1281,1275,1290,539,1275,1280,1283,1280,944,522,1297,600,548,405,517,277,781,240,682,497,66,780,781,277,277,192,636,1279,1289,1311,548,547,405,6,236,824,1100,1279,1311,66,497,18,35,423,771,362,490,682,695,870,736,693,696,695,693,695,692,362,801,490,733,994,683,1100,1278,1279,733,1352,709,781,780,865,636,192,193,1275,539,1290,1283,539,1280,1282,539,1283,771,423,556,35,771,740,949,733,709,694,693,692,1278,1282,1279,1279,1282,1283,693,832,696,832,692,105,1100,1311,1317,1282,1278,539,546,378,718,546,929,378,558,823,1092,870,824,736,915,949,709,733,467,994,7,547,548,1297,546,1216,1211,546,1205,545,547,7,437,438,1030,444,438,437,696,870,695,694,832,693,105,688,142,687,467,997,994,687,1317,1297,522,405,432,437,1341,444,440,438,950,63,952,612,607,474,616,610,608,490,801,865,752,751,497,29,35,740,326,214,328,547,526,405,434,545,7,444,441,440,440,308,438,29,18,497,312,490,865,545,544,547,526,544,1095,870,868,824,869,868,870,562,997,733,915,63,950,915,709,63,444,439,441,432,439,444,29,497,751,422,674,556,205,307,576,819,307,205,868,329,824,329,869,327,929,626,443,546,1024,929,915,950,949,308,912,63,715,626,929,709,308,63,307,432,1341,497,682,752,1024,1023,929,715,1023,716,1023,1024,716,950,952,949,438,308,709,746,819,247,422,556,423,746,904,819,500,596,1328,669,596,285,951,63,912,997,467,733,539,105,142,344,105,539,1169,636,193,780,312,865,1023,715,929,716,1024,546,713,716,714,63,951,952,440,441,308,308,441,744,752,491,490,752,682,491,751,319,29,319,752,490,733,949,562,467,687,994,1278,314,539,949,952,562,202,1100,1317,1100,1195,1278,202,1099,1100,544,526,547,1095,544,434,610,1169,193,611,474,1328,1099,1195,1100,202,201,1099,674,1149,3,526,24,405,1095,24,526,636,776,277,251,776,636,434,544,545,869,329,868,6,434,7,520,329,327,869,214,326,1095,10,24,1217,434,6,716,713,715,715,335,626,714,716,546,963,443,626,335,714,334,674,1225,1149,1052,1225,674,329,907,6,870,214,869,202,1195,201,562,952,951,870,213,214,24,1297,405,434,10,1095,35,1333,423,15,1333,35,15,35,29,326,327,869,912,561,951,744,441,439,326,328,327,870,696,213,1092,823,965,962,1016,443,662,823,558,201,1195,1099,202,1317,687,1333,422,423,10,1297,24,311,1297,10,1195,314,1278,954,202,687,561,562,951,520,907,329,434,311,10,327,907,520,328,907,327,268,907,328,285,500,281,596,611,1328,314,344,539,1195,343,314,139,343,1195,823,540,965,343,344,314,612,920,610,668,611,596,562,954,997,308,561,912,540,285,281,432,426,439,1189,954,561,424,426,432,424,431,419,1342,670,669,669,668,596,670,668,669,1225,320,1149,1149,904,746,159,1052,674,426,744,439,425,424,419,213,696,338,424,425,426,419,431,416,214,274,328,907,1217,6,752,319,751,1240,319,490,214,267,274,261,254,255,425,428,426,416,431,415,267,268,274,274,268,328,419,417,425,418,417,419,424,432,431,261,267,214,416,418,419,417,414,425,415,418,416,431,432,430,905,904,1300,121,430,1302,418,414,417,415,414,418,429,414,415,430,432,307,670,1346,668,285,1342,669,540,351,285,823,662,540,962,443,963,904,905,819,320,904,1149,431,429,415,785,430,121,213,261,214,267,270,268,261,213,338,335,715,713,1343,1342,285,617,920,611,259,270,267,268,269,907,351,1343,285,1052,320,1225,422,159,674,651,159,422,152,422,1333,414,428,425,428,429,785,714,335,713,334,714,337,962,1033,1016,775,963,626,954,687,997,343,139,344,335,775,626,337,714,546,261,255,267,338,696,832,136,1345,1343,1343,1345,1342,1342,1346,670,1345,1346,1342,334,336,335,336,337,546,260,269,270,270,269,268,14,15,29,259,260,270,258,338,832,338,254,261,148,320,1052,727,1033,962,259,267,255,159,148,1052,262,148,159,1345,1344,1346,617,611,668,136,1344,1345,256,259,255,256,255,254,429,428,414,785,429,431,785,431,430,202,139,1195,615,1285,105,258,254,338,257,256,254,561,954,562,1189,561,308,258,257,254,272,260,259,272,1018,260,258,832,1028,15,1331,1333,15,16,1331,319,14,29,1285,832,105,1033,558,1092,662,351,540,337,336,334,1297,336,546,164,351,1031,14,16,15,187,16,738,650,422,152,650,651,422,152,1333,1331,1330,152,1331,615,105,344,272,256,257,272,259,256,260,1018,269,269,1018,907,1021,1018,477,954,756,202,202,756,139,828,1189,308,421,784,650,650,784,651,651,784,159,148,262,320,1025,1217,907,1297,1022,336,611,920,612,776,312,780,999,668,1346,251,312,776,187,1331,16,430,307,1302,428,744,426,421,511,784,784,511,159,320,1300,904,1018,1021,907,272,257,258,785,433,428,1344,1000,1346,351,136,1343,164,136,351,1021,1025,907,271,272,258,272,477,1018,850,478,477,477,478,1021,963,727,962,1033,1296,558,336,775,335,920,211,610,617,211,920,136,4,1344,1093,4,136,1296,662,558,4,1000,1344,4,999,1000,1000,999,1346,421,262,511,511,262,159,732,421,650,1235,650,152,775,727,963,1093,1307,999,272,850,477,478,1025,1021,1028,271,258,187,1330,1331,16,14,738,849,850,272,271,849,272,738,14,319,727,1034,1033,775,1034,727,143,615,344,1028,472,271,143,344,139,1078,756,954,297,1235,1330,1330,1235,152,187,1332,1330,37,738,510,1048,143,139,271,472,849,849,472,850,850,472,478,1028,832,1285,737,739,187,738,737,187,211,1169,610,977,1169,211,1307,617,668,1034,1296,1033,732,925,421,421,925,262,737,1332,739,739,1332,187,312,1240,490,296,301,158,293,297,296,39,1240,312,1235,732,650,145,732,300,472,275,478,659,1028,1285,373,744,428,1067,138,1069,373,428,433,372,373,433,372,433,791,143,489,615,756,1048,139,138,1048,756,1028,275,472,999,1307,668,1031,351,662,1296,1031,662,104,1031,844,262,1300,320,812,307,819,925,174,262,145,174,925,164,1093,136,163,160,164,1028,276,275,275,276,478,1031,163,164,163,161,160,160,161,164,162,161,163,812,819,905,1093,999,4,161,1093,164,1031,162,163,162,1093,161,121,8,785,973,828,744,791,433,785,1169,251,636,977,251,1169,732,145,925,174,1300,262,297,732,1235,435,977,211,435,211,617,744,828,308,973,744,373,162,1056,1093,1093,1056,1307,8,791,785,342,790,8,813,812,838,121,342,8,276,1025,478,790,791,8,812,816,307,812,813,816,814,838,810,815,1302,816,816,1302,307,1294,372,791,436,435,617,436,617,1307,813,814,816,1302,1308,121,814,813,838,814,815,816,885,77,977,885,436,1307,346,1308,1302,297,350,296,1332,297,1330,615,666,1285,1028,654,276,138,489,143,815,1301,1302,814,1301,815,810,1301,814,836,973,373,836,373,372,836,372,1294,791,790,1323,342,121,1308,1301,346,1302,838,812,905,1048,138,143,521,954,1189,810,811,1301,818,838,905,838,811,810,489,666,615,244,666,489,346,342,1308,1240,58,319,39,58,1240,296,158,291,297,290,732,836,779,973,1323,1294,791,293,290,297,470,818,17,811,346,1301,838,818,811,1082,174,145,293,289,290,293,294,289,301,288,158,828,521,1189,207,521,828,992,828,973,291,294,293,299,290,289,292,300,290,290,300,732,294,299,289,296,291,293,1332,350,297,292,299,294,775,1221,1034,1034,844,1296,1031,104,162,336,1221,775,1102,1221,623,311,434,1217,342,1323,790,792,1323,342,795,346,811,291,158,294,299,292,290,1332,37,350,993,779,836,991,779,993,138,1067,489,1069,138,1068,158,292,294,1080,145,300,1080,1082,145,1068,138,1078,1082,1300,174,1082,1081,1300,1081,1080,117,794,795,811,346,445,342,993,836,1294,794,811,818,795,445,346,445,793,446,1069,1068,1067,1067,244,489,1078,138,756,117,1080,300,1080,1081,1082,992,207,828,521,1078,954,1025,311,1217,292,288,300,158,288,292,1332,737,37,1025,1314,311,276,654,1025,659,654,1028,779,992,973,993,1294,591,37,737,738,794,445,795,445,794,793,991,992,779,993,992,991,591,1294,1323,1300,9,905,1081,9,1300,117,9,1081,445,792,342,92,794,818,231,92,818,288,937,300,350,301,296,543,1078,521,322,792,446,446,792,445,92,793,794,91,231,818,231,90,92,94,91,470,251,39,312,510,738,1015,46,39,77,39,251,77,301,613,288,1047,613,301,1047,301,350,91,90,231,94,90,91,792,322,1323,793,322,446,90,87,92,470,91,818,510,1015,509,654,1103,1025,580,1103,654,89,87,90,89,90,94,613,937,288,1047,937,613,87,793,92,88,89,94,17,818,905,88,87,89,1091,793,87,937,117,300,470,88,94,793,796,322,37,501,350,738,319,1015,1090,1091,93,88,1091,87,1056,104,1307,46,20,39,162,104,1056,844,1031,1296,1221,1102,1034,623,1221,336,93,1091,88,1091,1090,793,510,508,37,1015,319,58,470,93,88,1090,1088,793,1087,93,1232,93,1089,1090,509,508,510,39,20,58,509,65,508,46,77,395,42,543,521,917,543,42,521,207,42,93,1088,1089,1089,1088,1090,322,591,1323,56,65,509,501,1047,350,666,659,1285,243,659,316,937,235,117,501,37,508,93,1087,1088,1088,1087,793,993,1019,992,1232,93,470,659,243,654,316,659,666,283,591,1,1103,1314,1025,243,580,654,65,501,508,745,1015,58,65,64,501,591,282,993,1,591,322,283,282,591,1022,623,336,151,235,937,117,681,9,17,1232,470,151,937,1047,1015,56,509,57,56,1015,17,905,9,157,151,593,150,151,157,56,655,65,655,57,1015,543,917,1078,1078,1322,1068,42,1145,1144,311,1022,1297,42,207,1145,842,844,1034,842,1034,1102,842,1102,833,833,903,1336,1087,796,793,283,1,282,150,117,235,251,977,77,657,655,658,42,1130,917,1145,207,992,151,150,235,151,64,593,681,17,9,1019,1145,992,57,655,56,456,58,20,460,681,117,842,843,844,649,1102,623,330,1137,1019,1232,796,1087,891,924,741,796,797,322,244,316,666,243,594,580,1322,1067,1068,1022,649,623,150,460,117,460,157,593,796,1,797,797,1,322,282,1,741,760,885,1307,844,1264,104,531,1264,844,455,456,20,827,843,842,903,833,1102,1336,1337,833,883,1338,1337,1337,1338,833,46,455,20,917,1322,1078,1130,1322,917,1130,42,1137,655,657,65,658,655,642,745,58,456,455,454,456,827,833,1338,827,842,833,657,656,65,658,656,657,316,594,243,580,1314,1103,311,557,1022,1336,883,1337,1298,903,1102,883,827,1338,157,460,150,151,1047,64,64,1047,501,903,883,1336,827,906,843,656,64,65,642,655,1015,885,435,436,843,531,844,248,531,843,633,244,1067,1315,1314,595,454,745,456,1132,1130,1134,1137,1133,1134,745,642,1015,394,642,745,919,26,43,658,64,656,1130,1138,1322,1131,1132,1135,1132,1131,1130,1130,1137,1134,42,1144,1137,1134,1135,1132,1137,1144,1145,1137,1145,1019,331,1135,1133,1133,1135,1134,1131,1136,1130,1137,331,1133,331,1136,1135,1135,1136,1131,883,906,827,903,906,883,1298,906,903,331,332,1136,1137,332,331,330,332,1137,1315,557,311,1022,672,649,649,1298,1102,332,330,1136,1138,633,1322,1019,993,282,672,1298,649,454,394,745,233,232,658,455,394,454,46,395,455,977,435,885,395,394,455,741,36,282,1,891,741,36,1019,282,1306,741,924,36,1306,1019,906,252,843,1298,252,906,594,1314,580,1314,594,313,1307,104,760,395,529,394,681,26,17,17,492,1232,1340,26,681,681,460,182,1314,1315,311,313,594,316,252,248,843,760,104,1264,26,40,17,40,492,17,759,313,707,1315,595,557,313,595,1314,557,672,1022,1298,742,252,961,882,248,26,919,40,40,919,492,1,1009,891,182,460,593,741,1306,36,1142,1136,330,1009,888,891,313,867,595,707,313,316,760,1264,531,1322,633,1067,244,707,316,1138,1130,1136,589,760,531,248,882,531,742,248,252,1306,1222,1019,891,888,889,1098,742,1298,882,589,531,924,1222,1306,1142,1140,1136,595,834,557,557,834,672,759,867,313,77,99,395,394,27,642,182,593,366,984,99,77,644,77,885,924,324,1222,796,1009,1,891,323,924,796,1232,1009,890,888,1009,325,182,366,593,64,366,888,890,889,889,892,891,1009,1232,492,890,892,889,1009,892,890,892,323,891,241,324,323,323,324,924,943,1009,492,892,241,323,182,1340,681,919,942,492,867,834,595,760,644,885,589,1032,760,672,389,1298,845,389,672,742,1014,248,882,629,589,1098,1014,742,330,1019,624,1142,51,1141,99,529,395,527,529,99,1143,1142,1141,671,1139,1140,1140,1139,1136,1142,1143,1140,1141,51,50,671,1138,1139,1139,1138,1136,1143,671,1140,182,1164,1340,348,1164,182,1143,1141,671,671,1141,1138,223,1019,1222,1032,644,760,530,527,99,956,961,248,646,1309,1032,897,898,364,325,1079,182,1218,111,1079,366,897,364,366,370,325,1060,707,1171,759,147,867,366,371,370,370,365,325,364,371,366,1079,348,182,79,43,1340,1340,43,26,111,348,1079,79,1340,1164,371,365,370,371,368,365,365,363,325,232,64,658,363,368,371,364,363,371,368,363,365,961,629,882,635,629,961,369,367,363,363,367,325,179,79,67,43,1228,919,38,1164,348,367,512,325,364,369,363,141,369,364,324,387,1222,1009,241,892,387,241,643,614,956,1014,1014,956,248,233,658,642,233,637,217,233,642,637,1218,1079,325,527,587,529,966,530,99,956,635,961,111,38,348,512,1218,325,530,528,527,966,528,530,1108,38,111,67,38,1108,369,512,367,898,141,364,141,516,369,141,140,516,516,512,369,899,140,141,515,512,516,140,515,516,902,515,140,528,587,527,100,587,528,241,387,324,643,241,1009,79,734,43,67,79,1164,67,1164,38,846,1218,512,515,846,512,897,366,896,232,875,64,874,875,232,874,217,978,896,366,64,1188,874,978,898,899,141,895,899,898,897,895,898,896,64,1188,902,899,895,902,140,899,902,846,515,179,734,79,41,734,179,900,902,895,111,1218,173,1051,67,28,902,900,846,897,896,895,1188,64,875,387,223,1222,896,900,895,896,901,900,900,901,846,67,1154,179,1051,1154,67,1154,1157,179,1108,111,173,1051,1157,1154,28,1157,1051,475,309,734,734,309,43,874,1188,875,1321,173,582,874,232,217,217,232,233,1157,685,179,28,685,1157,41,475,734,496,1228,43,637,642,27,685,41,179,173,1218,582,1218,846,582,1185,41,1186,846,901,582,217,519,978,27,394,529,28,67,1108,1183,1185,1186,41,1185,475,496,43,309,264,309,475,582,901,403,173,1321,1108,96,1183,1186,1185,1183,475,1186,41,457,1183,96,475,1320,28,939,939,28,1108,28,457,685,263,264,551,96,264,475,1228,1179,919,1299,1179,1228,377,496,309,496,1299,1228,1179,942,919,264,263,309,551,264,1057,552,1186,457,1321,447,1108,403,901,1101,403,1101,404,582,447,1321,552,457,1184,502,377,309,496,1008,1299,502,309,382,582,939,447,447,939,1108,1057,96,1186,1057,264,96,41,685,457,644,1017,77,871,413,777,494,413,411,1184,1057,552,552,1057,1186,382,309,263,413,1017,644,457,28,1320,382,263,381,45,27,529,45,529,587,263,551,381,377,1008,496,390,503,502,502,503,377,1017,984,77,494,983,1017,494,1017,413,103,45,100,411,413,871,646,589,629,381,551,286,551,1057,286,286,1057,1184,382,167,502,635,614,629,956,614,635,941,614,402,939,457,1320,575,457,939,707,147,759,1171,707,244,1171,244,633,457,286,1184,381,286,382,499,217,637,984,1017,983,457,287,286,286,287,382,265,167,287,287,167,382,503,631,377,457,265,287,1008,347,989,390,631,503,1299,757,1179,631,1008,377,1008,631,347,494,412,983,410,411,871,820,942,1179,387,643,223,1008,989,1299,347,631,505,901,896,1101,582,403,939,390,167,129,390,502,167,942,943,492,393,943,942,390,129,1293,167,265,129,411,412,494,602,505,631,505,1073,347,106,757,989,390,602,631,601,602,1293,602,601,505,989,757,1299,1293,602,390,1073,989,347,601,1073,505,411,410,412,412,984,983,413,1309,777,834,845,672,402,614,1014,867,845,834,1010,845,867,129,265,457,601,106,1073,1073,106,989,410,409,412,851,409,410,590,1171,633,1138,155,633,50,155,1138,50,1138,1141,763,643,1009,51,1142,624,463,106,601,757,820,1179,403,404,939,1101,896,303,896,519,303,413,644,1309,896,1188,519,1293,463,601,584,129,583,871,851,410,409,984,412,777,851,871,614,941,629,1098,1298,389,583,129,1354,1101,303,404,519,1188,978,767,763,1009,763,764,643,763,765,764,764,652,643,766,765,763,765,770,764,769,766,763,943,767,1009,851,984,409,767,769,763,768,769,767,768,770,766,766,770,765,769,768,766,996,768,767,768,996,770,943,996,767,1019,223,624,1142,330,624,627,1176,155,624,223,643,770,652,764,996,652,770,393,652,996,1060,147,707,830,147,1060,851,953,984,1309,644,1032,129,592,1293,106,820,757,129,457,575,652,624,643,584,592,129,130,592,584,155,590,633,590,1176,1074,575,939,404,583,130,584,463,820,106,86,115,130,1109,575,122,777,953,851,646,1032,589,575,1354,129,928,1098,389,1176,590,155,627,155,50,115,592,130,463,1293,592,943,393,996,86,130,1109,130,583,1109,583,1354,1109,115,116,592,115,118,116,1109,1354,575,845,928,389,86,118,115,116,463,592,581,1109,122,1109,118,86,1098,402,1014,953,722,721,488,402,1098,402,488,941,995,488,1098,374,463,134,499,519,217,122,575,1236,645,637,102,1267,721,1094,984,966,99,463,374,820,134,463,116,118,75,116,1109,581,118,575,404,1055,581,273,118,133,122,212,953,966,984,122,273,581,133,273,122,273,75,118,133,134,75,75,134,116,102,637,27,102,27,103,273,133,75,384,404,303,374,1003,820,820,393,942,1001,1003,374,1001,183,1002,1001,374,183,1002,1004,1003,1003,1004,820,1002,1003,1001,1004,1005,820,183,374,134,1002,1005,1004,645,499,637,1002,183,1005,840,183,134,840,393,1005,1005,393,820,103,27,45,645,397,499,498,397,645,397,498,499,730,306,519,102,498,645,306,384,303,133,840,134,1055,384,306,845,1083,928,928,995,1098,1010,1083,845,459,1010,867,1351,887,498,100,45,587,384,1055,404,1236,1055,168,1010,127,1083,1083,128,928,995,128,127,127,128,1083,966,100,528,953,1267,966,1267,953,721,723,722,953,30,100,966,51,385,50,624,385,51,839,385,894,385,624,894,1171,830,1060,147,459,867,609,830,1171,1267,30,966,777,723,953,777,1309,723,721,1269,1094,1094,1269,1267,721,1096,1269,723,1309,1011,722,1292,721,646,629,941,1010,995,127,128,995,928,459,995,1010,1055,1236,575,183,840,1005,249,1236,168,1236,212,122,385,627,50,590,609,1171,1236,249,212,555,840,133,306,303,519,728,519,499,169,168,1055,1170,646,941,306,169,1055,168,171,249,171,170,169,169,170,168,249,634,212,406,634,249,555,133,212,170,171,168,306,171,169,646,1011,1309,723,1292,722,830,459,147,498,887,499,1351,498,102,1351,102,103,1011,1292,723,1269,30,1267,1074,609,590,830,560,459,1292,1096,721,634,555,212,630,555,634,609,560,830,887,728,499,306,406,171,728,730,519,729,730,728,245,391,306,246,729,728,171,406,249,82,406,306,1096,30,1269,100,1351,103,627,1074,1176,385,839,627,894,624,652,894,652,393,887,246,728,30,1351,100,839,934,627,932,933,934,934,933,627,894,932,934,532,1074,627,532,627,933,840,894,393,839,894,934,1011,947,1292,1292,947,1096,1096,946,30,646,1170,1011,488,1170,941,406,630,634,83,82,391,82,306,391,1351,246,887,82,630,406,306,730,245,245,730,729,391,630,83,83,630,82,246,245,729,864,245,246,1170,357,1011,488,357,1170,894,532,932,932,532,933,357,947,1011,30,946,1351,947,946,1096,357,946,947,245,534,391,391,534,630,1351,864,246,535,534,245,630,534,555,555,535,840,534,535,555,864,535,245,1351,535,864]
\ No newline at end of file
