// ISC License
// Copyright (c) 2016 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 ISC DISCLAIMS ALL WARRANTIES WITH REGARD TO
// THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
// IN NO EVENT SHALL ISC 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.

(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.polylabel=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";var Queue=require("tinyqueue");module.exports=polylabel;module.exports.default=polylabel;function polylabel(polygon,precision,debug){precision=precision||1;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;var cellQueue=new Queue(null,compareMax);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))}}var bestCell=getCentroidCell(polygon);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){var cell=cellQueue.pop();if(cell.d>bestCell.d){bestCell=cell;if(debug)console.log("found best %d after %d probes",Math.round(1e4*cell.d)/1e4,numProbes)}if(cell.max-bestCell.d<=precision)continue;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;this.y=y;this.h=h;this.d=pointToPolygonDist(x,y,polygon);this.max=this.d+this.h*Math.SQRT2}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)}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}return new Cell(x/area,y/area,0,polygon)}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:2}],2:[function(require,module,exports){"use strict";module.exports=TinyQueue;function TinyQueue(data,compare){if(!(this instanceof TinyQueue))return new TinyQueue(data,compare);this.data=data||[];this.length=this.data.length;this.compare=compare||defaultCompare;if(data)for(var i=Math.floor(this.length/2);i>=0;i--)this._down(i)}function defaultCompare(a,b){return a<b?-1:a>b?1:0}TinyQueue.prototype={push:function(item){this.data.push(item);this.length++;this._up(this.length-1)},pop:function(){var top=this.data[0];this.data[0]=this.data[this.length-1];this.length--;this.data.pop();this._down(0);return top},peek:function(){return this.data[0]},_up:function(pos){var data=this.data,compare=this.compare;while(pos>0){var parent=Math.floor((pos-1)/2);if(compare(data[pos],data[parent])<0){swap(data,parent,pos);pos=parent}else break}},_down:function(pos){var data=this.data,compare=this.compare,len=this.length;while(true){var left=2*pos+1,right=left+1,min=pos;if(left<len&&compare(data[left],data[min])<0)min=left;if(right<len&&compare(data[right],data[min])<0)min=right;if(min===pos)return;swap(data,min,pos);pos=min}}};function swap(data,i,j){var tmp=data[i];data[i]=data[j];data[j]=tmp}},{}]},{},[1])(1)});