(function () { function r(e, n, t) { function o(i, f) { if (!n[i]) { if (!e[i]) { var c = "function" == typeof require && require; if (!f && c) return c(i, !0); if (u) return u(i, !0); var a = new Error("Cannot find module '" + i + "'"); throw a.code = "MODULE_NOT_FOUND", a } var p = n[i] = { exports: {} }; e[i][0].call(p.exports, function (r) { var n = e[i][1][r]; return o(n || r) }, p, p.exports, r, e, n, t) } return n[i].exports } for (var u = "function" == typeof require && require, i = 0; i < t.length; i++)o(t[i]); return o } return r })()({

1: [function (require, module, exports) {

(function (global, factory) {

typeof exports === 'object' && typeof module !== 'undefined' ? module.exports = factory() :

typeof define === 'function' && define.amd ? define(factory) :

(global = global || self, global.TinyQueue = factory());

}(this, function () {

'use strict';

var TinyQueue = function TinyQueue(data, compare) {

if (data === void 0) data = [];

if (compare === void 0) compare = defaultCompare;

this.data = data;

this.length = this.data.length;

this.compare = compare;

if (this.length > 0) {

for (var i = (this.length >> 1) - 1; i >= 0; i--) { this._down(i); }

}

};

TinyQueue.prototype.push = function push(item) {

this.data.push(item);

this.length++;

this._up(this.length - 1);

};

TinyQueue.prototype.pop = function pop() {

if (this.length === 0) { return undefined; }

var top = this.data[0];

var bottom = this.data.pop();

this.length--;

if (this.length > 0) {

this.data[0] = bottom;

this._down(0);

}

return top;

};

TinyQueue.prototype.peek = function peek() {

return this.data[0];

};

TinyQueue.prototype._up = function _up(pos) {

var ref = this;

var data = ref.data;

var compare = ref.compare;

var item = data[pos];

while (pos > 0) {

var parent = (pos - 1) >> 1;

var current = data[parent];

if (compare(item, current) >= 0) { break; }

data[pos] = current;

pos = parent;

}

data[pos] = item;

};

TinyQueue.prototype._down = function _down(pos) {

var ref = this;

var data = ref.data;

var compare = ref.compare;

var halfLength = this.length >> 1;

var item = data[pos];

while (pos < halfLength) {

var left = (pos << 1) + 1;

var best = data[left];

var right = left + 1;

if (right < this.length && compare(data[right], best) < 0) {

left = right;

best = data[right];

}

if (compare(best, item) >= 0) { break; }

data[pos] = best;

pos = left;

}

data[pos] = item;

};

function defaultCompare(a, b) {

return a < b ? -1 : a > b ? 1 : 0;

}

return TinyQueue;

}));

}, {}], 2: [function (require, module, exports) {

'use strict';

var Queue = require('tinyqueue');

module.exports = polylabel;

module.exports.default = polylabel;

function polylabel(polygon, precision, debug) {

precision = precision || 1.0;

// find the bounding box of the outer ring

var minX, minY, maxX, maxY;

for (var i = 0; i < polygon[0].length; i++) {

var p = polygon[0][i];

if (!i || p[0] < minX) minX = p[0];

if (!i || p[1] < minY) minY = p[1];

if (!i || p[0] > maxX) maxX = p[0];

if (!i || p[1] > maxY) maxY = p[1];

}

var width = maxX - minX;

var height = maxY - minY;

var cellSize = Math.min(width, height);

var h = cellSize / 2;

if (cellSize === 0) return [minX, minY];

// a priority queue of cells in order of their "potential" (max distance to polygon)

var cellQueue = new Queue(undefined, compareMax);

// cover polygon with initial cells

for (var x = minX; x < maxX; x += cellSize) {

for (var y = minY; y < maxY; y += cellSize) {

cellQueue.push(new Cell(x + h, y + h, h, polygon));

}

}

// take centroid as the first best guess

var bestCell = getCentroidCell(polygon);

// special case for rectangular polygons

var bboxCell = new Cell(minX + width / 2, minY + height / 2, 0, polygon);

if (bboxCell.d > bestCell.d) bestCell = bboxCell;

var numProbes = cellQueue.length;

while (cellQueue.length) {

// pick the most promising cell from the queue

var cell = cellQueue.pop();

// update the best cell if we found a better one

if (cell.d > bestCell.d) {

bestCell = cell;

if (debug) console.log('found best %d after %d probes', Math.round(1e4 * cell.d) / 1e4, numProbes);

}

// do not drill down further if there's no chance of a better solution

if (cell.max - bestCell.d <= precision) continue;

// split the cell into four cells

h = cell.h / 2;

cellQueue.push(new Cell(cell.x - h, cell.y - h, h, polygon));

cellQueue.push(new Cell(cell.x + h, cell.y - h, h, polygon));

cellQueue.push(new Cell(cell.x - h, cell.y + h, h, polygon));

cellQueue.push(new Cell(cell.x + h, cell.y + h, h, polygon));

numProbes += 4;

}

if (debug) {

console.log('num probes: ' + numProbes);

console.log('best distance: ' + bestCell.d);

}

return [bestCell.x, bestCell.y];

}

function compareMax(a, b) {

return b.max - a.max;

}

function Cell(x, y, h, polygon) {

this.x = x; // cell center x

this.y = y; // cell center y

this.h = h; // half the cell size

this.d = pointToPolygonDist(x, y, polygon); // distance from cell center to polygon

this.max = this.d + this.h * Math.SQRT2; // max distance to polygon within a cell

}

// signed distance from point to polygon outline (negative if point is outside)

function pointToPolygonDist(x, y, polygon) {

var inside = false;

var minDistSq = Infinity;

for (var k = 0; k < polygon.length; k++) {

var ring = polygon[k];

for (var i = 0, len = ring.length, j = len - 1; i < len; j = i++) {

var a = ring[i];

var b = ring[j];

if ((a[1] > y !== b[1] > y) &&

(x < (b[0] - a[0]) * (y - a[1]) / (b[1] - a[1]) + a[0])) inside = !inside;

minDistSq = Math.min(minDistSq, getSegDistSq(x, y, a, b));

}

}

return (inside ? 1 : -1) * Math.sqrt(minDistSq);

}

// get polygon centroid

function getCentroidCell(polygon) {

var area = 0;

var x = 0;

var y = 0;

var points = polygon[0];

for (var i = 0, len = points.length, j = len - 1; i < len; j = i++) {

var a = points[i];

var b = points[j];

var f = a[0] * b[1] - b[0] * a[1];

x += (a[0] + b[0]) * f;

y += (a[1] + b[1]) * f;

area += f * 3;

}

if (area === 0) return new Cell(points[0][0], points[0][1], 0, polygon);

return new Cell(x / area, y / area, 0, polygon);

}

// get squared distance from a point to a segment

function getSegDistSq(px, py, a, b) {

var x = a[0];

var y = a[1];

var dx = b[0] - x;

var dy = b[1] - y;

if (dx !== 0 || dy !== 0) {

var t = ((px - x) * dx + (py - y) * dy) / (dx * dx + dy * dy);

if (t > 1) {

x = b[0];

y = b[1];

} else if (t > 0) {

x += dx * t;

y += dy * t;

}

}

dx = px - x;

dy = py - y;

return dx * dx + dy * dy;

}

}, { "tinyqueue": 1 }]

}, {}, [2]);