!function(e){if("object"==typeof exports)module.exports=e();else if("function"==typeof define&&define.amd)define(e);else{var n;"undefined"!=typeof window?n=window:"undefined"!=typeof global?n=global:"undefined"!=typeof self&&(n=self),n.RTree=e()}}(function(){return function e(n,t,r){function o(a,s){if(!t[a]){if(!n[a]){var h="function"==typeof require&&require;if(!s&&h)return h(a,!0);if(i)return i(a,!0);throw new Error("Cannot find module '"+a+"'")}var c=t[a]={exports:{}};n[a][0].call(c.exports,function(e){return o(n[a][1][e]||e)},c,c.exports,e,n,t,r)}return t[a].exports}for(var i="function"==typeof require&&require,a=0;a<r.length;a++)o(r[a]);return o}({1:[function(e,n,t){"use strict";var r=e("./rectangle"),o=function(e,n){if(n&&n.bbox)return{leaf:n,x:n.bbox[0],y:n.bbox[1],w:n.bbox[2]-n.bbox[0],h:n.bbox[3]-n.bbox[1]};for(var t=e.length,r=0,o=new Array(t);r<t;)o[r]=[e[r][0],e[r][1]],r++;var i=o[0];t=o.length,r=1;for(var a={min:[].concat(i),max:[].concat(i)};r<t;)o[r][0]<a.min[0]?a.min[0]=o[r][0]:o[r][0]>a.max[0]&&(a.max[0]=o[r][0]),o[r][1]<a.min[1]?a.min[1]=o[r][1]:o[r][1]>a.max[1]&&(a.max[1]=o[r][1]),r++;var s={x:a.min[0],y:a.min[1],w:a.max[0]-a.min[0],h:a.max[1]-a.min[1]};return n&&(s.leaf=n),s},i={point:function(e,n){return n.insertSubtree({x:e.geometry.coordinates[0],y:e.geometry.coordinates[1],w:0,h:0,leaf:e},n.root)},multiPointLineString:function(e,n){return n.insertSubtree(o(e.geometry.coordinates,e),n.root)},multiLineStringPolygon:function(e,n){return n.insertSubtree(o(Array.prototype.concat.apply([],e.geometry.coordinates),e),n.root)},multiPolygon:function(e,n){return n.insertSubtree(o(Array.prototype.concat.apply([],Array.prototype.concat.apply([],e.geometry.coordinates)),e),n.root)},makeRec:function(e){return r(e.x,e.y,e.w,e.h)},geometryCollection:function(e,n){if(e.bbox)return n.insertSubtree({leaf:e,x:e.bbox[0],y:e.bbox[1],w:e.bbox[2]-e.bbox[0],h:e.bbox[3]-e.bbox[1]},n.root);for(var t,r=e.geometry.geometries,a=0,s=r.length,h=[];a<s;){switch((t=r[a]).type){case"Point":h.push(i.makeRec({x:t.coordinates[0],y:t.coordinates[1],w:0,h:0}));break;case"MultiPoint":case"LineString":h.push(i.makeRec(o(t.coordinates)));break;case"MultiLineString":case"Polygon":h.push(i.makeRec(o(Array.prototype.concat.apply([],t.coordinates))));break;case"MultiPolygon":h.push(i.makeRec(o(Array.prototype.concat.apply([],Array.prototype.concat.apply([],t.coordinates)))));break;case"GeometryCollection":s=(r=r.concat(t.geometries)).length}a++}var c=h[0];for(a=1,s=h.length;a<s;)c.expand(h[a]),a++;return n.insertSubtree({leaf:e,x:c.x(),y:c.y(),h:c.h(),w:c.w()},n.root)}};t.geoJSON=function(e){var n,t;if(Array.isArray(e))n=e.slice();else if(e.features&&Array.isArray(e.features))n=e.features.slice();else{if(!(e instanceof Object))throw"this isn't what we're looking for";n=[e]}for(var r=n.length,o=0;o<r;){if("Feature"===(t=n[o]).type)switch(t.geometry.type){case"Point":i.point(t,this);break;case"MultiPoint":case"LineString":i.multiPointLineString(t,this);break;case"MultiLineString":case"Polygon":i.multiLineStringPolygon(t,this);break;case"MultiPolygon":i.multiPolygon(t,this);break;case"GeometryCollection":i.geometryCollection(t,this)}o++}},t.bbox=function(){var e,n,t,r;switch(arguments.length){case 1:e=arguments[0][0][0],n=arguments[0][0][1],t=arguments[0][1][0],r=arguments[0][1][1];break;case 2:e=arguments[0][0],n=arguments[0][1],t=arguments[1][0],r=arguments[1][1];break;case 4:e=arguments[0],n=arguments[1],t=arguments[2],r=arguments[3]}return this.search({x:e,y:n,w:t-e,h:r-n})}},{"./rectangle":3}],2:[function(e,n,t){"use strict";var r=e("./rtree"),o=e("./geojson");r.prototype.bbox=o.bbox,r.prototype.geoJSON=o.geoJSON,r.Rectangle=e("./rectangle"),n.exports=r},{"./geojson":1,"./rectangle":3,"./rtree":4}],3:[function(e,n,t){"use strict";function r(e,n,t,o){if(!(this instanceof r))return new r(e,n,t,o);var i,a,s;e.x?(t=e.w,o=e.h,n=e.y,0!==e.w&&!e.w&&e.x2?(t=e.x2-e.x,o=e.y2-e.y):(t=e.w,o=e.h),i=(e=e.x)+t,a=n+o,s=!(o+t)):(i=e+t,a=n+o,s=!(o+t)),this.x1=this.x=function(){return e},this.y1=this.y=function(){return n},this.x2=function(){return i},this.y2=function(){return a},this.w=function(){return t},this.h=function(){return o},this.p=function(){return s},this.overlap=function(t){return s||t.p()?e<=t.x2()&&i>=t.x()&&n<=t.y2()&&a>=t.y():e<t.x2()&&i>t.x()&&n<t.y2()&&a>t.y()},this.expand=function(r){var s,h,c=r.x(),u=r.y(),l=r.x2(),f=r.y2();return s=e>c?c:e,h=n>u?u:n,t=i>l?i-s:l-s,o=a>f?a-h:f-h,e=s,n=h,this}}r.overlapRectangle=function(e,n){return 0===e.h&&0===e.w||0===n.h&&0===n.w?e.x<=n.x+n.w&&e.x+e.w>=n.x&&e.y<=n.y+n.h&&e.y+e.h>=n.y:e.x<n.x+n.w&&e.x+e.w>n.x&&e.y<n.y+n.h&&e.y+e.h>n.y},r.containsRectangle=function(e,n){return e.x+e.w<=n.x+n.w&&e.x>=n.x&&e.y+e.h<=n.y+n.h&&e.y>=n.y},r.expandRectangle=function(e,n){var t,r,o=e.x+e.w,i=n.x+n.w,a=e.y+e.h,s=n.y+n.h;return t=e.x>n.x?n.x:e.x,r=e.y>n.y?n.y:e.y,e.w=o>i?o-t:i-t,e.h=a>s?a-r:s-r,e.x=t,e.y=r,e},r.makeMBR=function(e,n){if(!e.length)return{x:0,y:0,w:0,h:0};(n=n||{}).x=e[0].x,n.y=e[0].y,n.w=e[0].w,n.h=e[0].h;for(var t=1,o=e.length;t<o;t++)r.expandRectangle(n,e[t]);return n},r.squarifiedRatio=function(e,n,t){var r=(e+n)/2,o=e*n;return o*t/(o/(r*r))},n.exports=r},{}],4:[function(e,n,t){"use strict";var r=e("./rectangle");function o(e){if(!(this instanceof o))return new o(e);var n=3,t=6;isNaN(e)||(n=Math.floor(e/2),t=e);var i={x:0,y:0,w:0,h:0,id:"root",nodes:[]};this.root=i;var a=function(e){for(var n,t=e.slice(),r=[];t.length;)(n=t.pop()).nodes?t=t.concat(n.nodes):n.leaf&&r.push(n);return r},s=function(e,t,o){var i,s,h,c=[],u=[],y=[];if(!e||!r.overlapRectangle(e,o))return y;var x={x:e.x,y:e.y,w:e.w,h:e.h,target:t};for(u.push(o.nodes.length),c.push(o);c.length>0;)if(i=c.pop(),s=u.pop()-1,"target"in x)for(;s>=0;){if(r.overlapRectangle(x,h=i.nodes[s])){if(x.target&&"leaf"in h&&h.leaf===x.target||!x.target&&("leaf"in h||r.containsRectangle(h,x))){y="nodes"in h?a(i.nodes.splice(s,1)):i.nodes.splice(s,1),r.makeMBR(i.nodes,i),delete x.target;break}"nodes"in h&&(u.push(s),c.push(i),i=h,s=h.nodes.length)}s--}else if("nodes"in x){i.nodes.splice(s+1,1),i.nodes.length>0&&r.makeMBR(i.nodes,i);for(var p=0;p<x.nodes.length;p++)f(x.nodes[p],i);x.nodes=[],0===c.length&&i.nodes.length<=1?(x.nodes=l(i,!0,x.nodes,i),i.nodes=[],c.push(i),u.push(1)):c.length>0&&i.nodes.length<n?(x.nodes=l(i,!0,x.nodes,i),i.nodes=[]):delete x.nodes}else r.makeMBR(i.nodes,i);return y},h=function(e){for(var n=u(e);e.length>0;)c(e,n[0],n[1]);return n},c=function(e,t,o){for(var i,a,s,h=r.squarifiedRatio(t.w,t.h,t.nodes.length+1),c=r.squarifiedRatio(o.w,o.h,o.nodes.length+1),u=e.length-1;u>=0;u--){var l=e[u],f={};f.x=Math.min(t.x,l.x),f.y=Math.min(t.y,l.y),f.w=Math.max(t.x+t.w,l.x+l.w)-f.x,f.h=Math.max(t.y+t.h,l.y+l.h)-f.y;var y=Math.abs(r.squarifiedRatio(f.w,f.h,t.nodes.length+2)-h),x={};x.x=Math.min(o.x,l.x),x.y=Math.min(o.y,l.y),x.w=Math.max(o.x+o.w,l.x+l.w)-x.x,x.h=Math.max(o.y+o.h,l.y+l.h)-x.y;var p=Math.abs(r.squarifiedRatio(x.w,x.h,o.nodes.length+2)-c);(!a||!i||Math.abs(p-y)<i)&&(a=u,i=Math.abs(p-y),s=p<y?o:t)}var g=e.splice(a,1)[0];t.nodes.length+e.length+1<=n?(t.nodes.push(g),r.expandRectangle(t,g)):o.nodes.length+e.length+1<=n?(o.nodes.push(g),r.expandRectangle(o,g)):(s.nodes.push(g),r.expandRectangle(s,g))},u=function(e){for(var n,t,r=e.length-1,o=0,i=e.length-1,a=0,s=e.length-2;s>=0;s--){var h=e[s];h.x>e[o].x?o=s:h.x+h.w<e[r].x+e[r].w&&(r=s),h.y>e[a].y?a=s:h.y+h.h<e[i].y+e[i].h&&(i=s)}return Math.abs(e[r].x+e[r].w-e[o].x)>Math.abs(e[i].y+e[i].h-e[a].y)?r>o?(n=e.splice(r,1)[0],t=e.splice(o,1)[0]):(t=e.splice(o,1)[0],n=e.splice(r,1)[0]):i>a?(n=e.splice(i,1)[0],t=e.splice(a,1)[0]):(t=e.splice(a,1)[0],n=e.splice(i,1)[0]),[{x:n.x,y:n.y,w:n.w,h:n.h,nodes:[n]},{x:t.x,y:t.y,w:t.w,h:t.h,nodes:[t]}]},l=function(e,n,t,o){var i=[];if(!r.overlapRectangle(e,o))return t;for(i.push(o.nodes);i.length>0;)for(var a=i.pop(),s=a.length-1;s>=0;s--){var h=a[s];r.overlapRectangle(e,h)&&("nodes"in h?i.push(h.nodes):"leaf"in h&&t.push(n?h:h.leaf))}return t},f=function(e,n){var o;if(0===n.nodes.length)return n.x=e.x,n.y=e.y,n.w=e.w,n.h=e.h,void n.nodes.push(e);for(var i,a=function(e,n){var t,o=-1,i=[],a=!0;i.push(n);for(var s=n.nodes;a||-1!==o;){a?a=!1:(i.push(s[o]),s=s[o].nodes,o=-1);for(var h=s.length-1;h>=0;h--){var c=s[h];if("leaf"in c){o=-1;break}var u=r.squarifiedRatio(c.w,c.h,c.nodes.length+1),l=Math.max(c.x+c.w,e.x+e.w)-Math.min(c.x,e.x),f=Math.max(c.y+c.h,e.y+e.h)-Math.min(c.y,e.y),y=r.squarifiedRatio(l,f,c.nodes.length+2);(o<0||Math.abs(y-u)<t)&&(t=Math.abs(y-u),o=h)}}return i}(e,n),s=e;a.length>0;){if(o&&"nodes"in o&&0===o.nodes.length){i=o,o=a.pop();for(var c=0;c<o.nodes.length;c++)if(o.nodes[c]===i||0===o.nodes[c].nodes.length){o.nodes.splice(c,1);break}}else o=a.pop();if("leaf"in s||"nodes"in s||Array.isArray(s)){if(Array.isArray(s)){for(var u=0;u<s.length;u++)r.expandRectangle(o,s[u]);o.nodes=o.nodes.concat(s)}else r.expandRectangle(o,s),o.nodes.push(s);if(o.nodes.length<=t)s={x:o.x,y:o.y,w:o.w,h:o.h};else{var l=h(o.nodes);s=l,a.length<1&&(o.nodes.push(l[0]),a.push(o),s=l[1])}}else r.expandRectangle(o,s),s={x:o.x,y:o.y,w:o.w,h:o.h}}};this.insertSubtree=f,this.getTree=function(){return i},this.setTree=function(e,n){return n||(n=i),(t=n).nodes=(r=e).nodes,t.x=r.x,t.y=r.y,t.w=r.w,t.h=r.h,t;var t,r},this.search=function(e,n,t){return l(e,n,t=t||[],i)},this.remove=function(e,n){return n&&"function"!=typeof n?function(e,n){return s(e,n,i)}(e,n):function(e){for(var n,t=1,r=[];t>0;)t=(n=s(e,!1,i)).length,r=r.concat(n);return r}(e)},this.insert=function(e,n){return f({x:e.x,y:e.y,w:e.w,h:e.h,leaf:n},i)}}o.prototype.toJSON=function(e){return JSON.stringify(this.root,!1,e)},o.fromJSON=function(e){var n=new o;return n.setTree(JSON.parse(e)),n},n.exports=o,"function"!=typeof Array.isArray&&(Array.isArray=function(e){return"object"==typeof e&&"[object Array]"==={}.toString.call(e)})},{"./rectangle":3}]},{},[2])(2)});