'use strict';
var polylabel = (function(){
    var Queue = (function () {
    
        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;
        
    })();
    
    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) {
            var degeneratePoleOfInaccessibility = [minX, minY];
            degeneratePoleOfInaccessibility.distance = 0;
            return degeneratePoleOfInaccessibility;
        }
    
        // 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);
        }
    
        var poleOfInaccessibility = [bestCell.x, bestCell.y];
        poleOfInaccessibility.distance = bestCell.d;
        return poleOfInaccessibility;
    }
    
    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 minDistSq === 0 ? 0 : (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;
    }
    return polylabel
})()
