!function(e){if("object"==typeof exports)module.exports=e();else if("function"==typeof define&&define.amd)define(e);else{var f;"undefined"!=typeof window?f=window:"undefined"!=typeof global?f=global:"undefined"!=typeof self&&(f=self),f.RTree=e()}}(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);throw new Error("Cannot find module '"+o+"'")}var f=n[o]={exports:{}};t[o][0].call(f.exports,function(e){var n=t[o][1][e];return s(n?n:e)},f,f.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(_dereq_,module,exports){"use strict";var rectangle=_dereq_("./rectangle");var bbox=function(ar,obj){if(obj&&obj.bbox){return{leaf:obj,x:obj.bbox[0],y:obj.bbox[1],w:obj.bbox[2]-obj.bbox[0],h:obj.bbox[3]-obj.bbox[1]}}var len=ar.length;var i=0;var a=new Array(len);while(i<len){a[i]=[ar[i][0],ar[i][1]];i++}var first=a[0];len=a.length;i=1;var temp={min:[].concat(first),max:[].concat(first)};while(i<len){if(a[i][0]<temp.min[0]){temp.min[0]=a[i][0]}else if(a[i][0]>temp.max[0]){temp.max[0]=a[i][0]}if(a[i][1]<temp.min[1]){temp.min[1]=a[i][1]}else if(a[i][1]>temp.max[1]){temp.max[1]=a[i][1]}i++}var out={x:temp.min[0],y:temp.min[1],w:temp.max[0]-temp.min[0],h:temp.max[1]-temp.min[1]};if(obj){out.leaf=obj}return out};var geoJSON={};geoJSON.point=function(obj,self){return self.insertSubtree({x:obj.geometry.coordinates[0],y:obj.geometry.coordinates[1],w:0,h:0,leaf:obj},self.root)};geoJSON.multiPointLineString=function(obj,self){return self.insertSubtree(bbox(obj.geometry.coordinates,obj),self.root)};geoJSON.multiLineStringPolygon=function(obj,self){return self.insertSubtree(bbox(Array.prototype.concat.apply([],obj.geometry.coordinates),obj),self.root)};geoJSON.multiPolygon=function(obj,self){return self.insertSubtree(bbox(Array.prototype.concat.apply([],Array.prototype.concat.apply([],obj.geometry.coordinates)),obj),self.root)};geoJSON.makeRec=function(obj){return rectangle(obj.x,obj.y,obj.w,obj.h)};geoJSON.geometryCollection=function(obj,self){if(obj.bbox){return self.insertSubtree({leaf:obj,x:obj.bbox[0],y:obj.bbox[1],w:obj.bbox[2]-obj.bbox[0],h:obj.bbox[3]-obj.bbox[1]},self.root)}var geos=obj.geometry.geometries;var i=0;var len=geos.length;var temp=[];var g;while(i<len){g=geos[i];switch(g.type){case"Point":temp.push(geoJSON.makeRec({x:g.coordinates[0],y:g.coordinates[1],w:0,h:0}));break;case"MultiPoint":temp.push(geoJSON.makeRec(bbox(g.coordinates)));break;case"LineString":temp.push(geoJSON.makeRec(bbox(g.coordinates)));break;case"MultiLineString":temp.push(geoJSON.makeRec(bbox(Array.prototype.concat.apply([],g.coordinates))));break;case"Polygon":temp.push(geoJSON.makeRec(bbox(Array.prototype.concat.apply([],g.coordinates))));break;case"MultiPolygon":temp.push(geoJSON.makeRec(bbox(Array.prototype.concat.apply([],Array.prototype.concat.apply([],g.coordinates)))));break;case"GeometryCollection":geos=geos.concat(g.geometries);len=geos.length;break}i++}var first=temp[0];i=1;len=temp.length;while(i<len){first.expand(temp[i]);i++}return self.insertSubtree({leaf:obj,x:first.x(),y:first.y(),h:first.h(),w:first.w()},self.root)};exports.geoJSON=function(prelim){var that=this;var features,feature;if(Array.isArray(prelim)){features=prelim.slice()}else if(prelim.features&&Array.isArray(prelim.features)){features=prelim.features.slice()}else if(prelim instanceof Object){features=[prelim]}else{throw"this isn't what we're looking for"}var len=features.length;var i=0;while(i<len){feature=features[i];if(feature.type==="Feature"){switch(feature.geometry.type){case"Point":geoJSON.point(feature,that);break;case"MultiPoint":geoJSON.multiPointLineString(feature,that);break;case"LineString":geoJSON.multiPointLineString(feature,that);break;case"MultiLineString":geoJSON.multiLineStringPolygon(feature,that);break;case"Polygon":geoJSON.multiLineStringPolygon(feature,that);break;case"MultiPolygon":geoJSON.multiPolygon(feature,that);break;case"GeometryCollection":geoJSON.geometryCollection(feature,that);break}}i++}};exports.bbox=function(){var x1,y1,x2,y2;switch(arguments.length){case 1:x1=arguments[0][0][0];y1=arguments[0][0][1];x2=arguments[0][1][0];y2=arguments[0][1][1];break;case 2:x1=arguments[0][0];y1=arguments[0][1];x2=arguments[1][0];y2=arguments[1][1];break;case 4:x1=arguments[0];y1=arguments[1];x2=arguments[2];y2=arguments[3];break}return this.search({x:x1,y:y1,w:x2-x1,h:y2-y1})}},{"./rectangle":3}],2:[function(_dereq_,module,exports){"use strict";var RTree=_dereq_("./rtree");var geojson=_dereq_("./geojson");RTree.prototype.bbox=geojson.bbox;RTree.prototype.geoJSON=geojson.geoJSON;RTree.Rectangle=_dereq_("./rectangle");module.exports=RTree},{"./geojson":1,"./rectangle":3,"./rtree":4}],3:[function(_dereq_,module,exports){"use strict";function Rectangle(x,y,w,h){if(!(this instanceof Rectangle)){return new Rectangle(x,y,w,h)}var x2,y2,p;if(x.x){w=x.w;h=x.h;y=x.y;if(x.w!==0&&!x.w&&x.x2){w=x.x2-x.x;h=x.y2-x.y}else{w=x.w;h=x.h}x=x.x;x2=x+w;y2=y+h;p=h+w?false:true}else{x2=x+w;y2=y+h;p=h+w?false:true}this.x1=this.x=function(){return x};this.y1=this.y=function(){return y};this.x2=function(){return x2};this.y2=function(){return y2};this.w=function(){return w};this.h=function(){return h};this.p=function(){return p};this.overlap=function(a){if(p||a.p()){return x<=a.x2()&&x2>=a.x()&&y<=a.y2()&&y2>=a.y()}return x<a.x2()&&x2>a.x()&&y<a.y2()&&y2>a.y()};this.expand=function(a){var nx,ny;var ax=a.x();var ay=a.y();var ax2=a.x2();var ay2=a.y2();if(x>ax){nx=ax}else{nx=x}if(y>ay){ny=ay}else{ny=y}if(x2>ax2){w=x2-nx}else{w=ax2-nx}if(y2>ay2){h=y2-ny}else{h=ay2-ny}x=nx;y=ny;return this}}Rectangle.overlapRectangle=function(a,b){if(a.h===0&&a.w===0||b.h===0&&b.w===0){return a.x<=b.x+b.w&&a.x+a.w>=b.x&&a.y<=b.y+b.h&&a.y+a.h>=b.y}else{return a.x<b.x+b.w&&a.x+a.w>b.x&&a.y<b.y+b.h&&a.y+a.h>b.y}};Rectangle.containsRectangle=function(a,b){return a.x+a.w<=b.x+b.w&&a.x>=b.x&&a.y+a.h<=b.y+b.h&&a.y>=b.y};Rectangle.expandRectangle=function(a,b){var nx,ny;var axw=a.x+a.w;var bxw=b.x+b.w;var ayh=a.y+a.h;var byh=b.y+b.h;if(a.x>b.x){nx=b.x}else{nx=a.x}if(a.y>b.y){ny=b.y}else{ny=a.y}if(axw>bxw){a.w=axw-nx}else{a.w=bxw-nx}if(ayh>byh){a.h=ayh-ny}else{a.h=byh-ny}a.x=nx;a.y=ny;return a};Rectangle.makeMBR=function(nodes,rect){if(!nodes.length){return{x:0,y:0,w:0,h:0}}rect=rect||{};rect.x=nodes[0].x;rect.y=nodes[0].y;rect.w=nodes[0].w;rect.h=nodes[0].h;for(var i=1,len=nodes.length;i<len;i++){Rectangle.expandRectangle(rect,nodes[i])}return rect};Rectangle.squarifiedRatio=function(l,w,fill){var lperi=(l+w)/2;var larea=l*w;var lgeo=larea/(lperi*lperi);return larea*fill/lgeo};module.exports=Rectangle},{}],4:[function(_dereq_,module,exports){"use strict";var rectangle=_dereq_("./rectangle");function RTree(width){if(!(this instanceof RTree)){return new RTree(width)}var minWidth=3;var maxWidth=6;if(!isNaN(width)){minWidth=Math.floor(width/2);maxWidth=width}var rootTree={x:0,y:0,w:0,h:0,id:"root",nodes:[]};this.root=rootTree;var flatten=function(tree){var todo=tree.slice();var done=[];var current;while(todo.length){current=todo.pop();if(current.nodes){todo=todo.concat(current.nodes)}else if(current.leaf){done.push(current)}}return done};var removeSubtree=function(rect,obj,root){var hitStack=[];var countStack=[];var retArray=[];var currentDepth=1;var tree,i,ltree;if(!rect||!rectangle.overlapRectangle(rect,root)){return retArray}var retObj={x:rect.x,y:rect.y,w:rect.w,h:rect.h,target:obj};countStack.push(root.nodes.length);hitStack.push(root);while(hitStack.length>0){tree=hitStack.pop();i=countStack.pop()-1;if("target"in retObj){while(i>=0){ltree=tree.nodes[i];if(rectangle.overlapRectangle(retObj,ltree)){if(retObj.target&&"leaf"in ltree&&ltree.leaf===retObj.target||!retObj.target&&("leaf"in ltree||rectangle.containsRectangle(ltree,retObj))){if("nodes"in ltree){retArray=flatten(tree.nodes.splice(i,1))}else{retArray=tree.nodes.splice(i,1)}rectangle.makeMBR(tree.nodes,tree);delete retObj.target;break}else if("nodes"in ltree){currentDepth++;countStack.push(i);hitStack.push(tree);tree=ltree;i=ltree.nodes.length}}i--}}else if("nodes"in retObj){tree.nodes.splice(i+1,1);if(tree.nodes.length>0){rectangle.makeMBR(tree.nodes,tree)}for(var t=0;t<retObj.nodes.length;t++){insertSubtree(retObj.nodes[t],tree)}retObj.nodes=[];if(hitStack.length===0&&tree.nodes.length<=1){retObj.nodes=searchSubtree(tree,true,retObj.nodes,tree);tree.nodes=[];hitStack.push(tree);countStack.push(1)}else if(hitStack.length>0&&tree.nodes.length<minWidth){retObj.nodes=searchSubtree(tree,true,retObj.nodes,tree);tree.nodes=[]}else{delete retObj.nodes}}else{rectangle.makeMBR(tree.nodes,tree)}currentDepth-=1}return retArray};var chooseLeafSubtree=function(rect,root){var bestChoiceIndex=-1;var bestChoiceStack=[];var bestChoiceArea;var first=true;bestChoiceStack.push(root);var nodes=root.nodes;while(first||bestChoiceIndex!==-1){if(first){first=false}else{bestChoiceStack.push(nodes[bestChoiceIndex]);nodes=nodes[bestChoiceIndex].nodes;bestChoiceIndex=-1}for(var i=nodes.length-1;i>=0;i--){var ltree=nodes[i];if("leaf"in ltree){bestChoiceIndex=-1;break}var oldLRatio=rectangle.squarifiedRatio(ltree.w,ltree.h,ltree.nodes.length+1);var nw=Math.max(ltree.x+ltree.w,rect.x+rect.w)-Math.min(ltree.x,rect.x);var nh=Math.max(ltree.y+ltree.h,rect.y+rect.h)-Math.min(ltree.y,rect.y);var lratio=rectangle.squarifiedRatio(nw,nh,ltree.nodes.length+2);if(bestChoiceIndex<0||Math.abs(lratio-oldLRatio)<bestChoiceArea){bestChoiceArea=Math.abs(lratio-oldLRatio);bestChoiceIndex=i}}}return bestChoiceStack};var linearSplit=function(nodes){var n=pickLinear(nodes);while(nodes.length>0){pickNext(nodes,n[0],n[1])}return n};var pickNext=function(nodes,a,b){var areaA=rectangle.squarifiedRatio(a.w,a.h,a.nodes.length+1);var areaB=rectangle.squarifiedRatio(b.w,b.h,b.nodes.length+1);var highAreaDelta;var highAreaNode;var lowestGrowthGroup;for(var i=nodes.length-1;i>=0;i--){var l=nodes[i];var newAreaA={};newAreaA.x=Math.min(a.x,l.x);newAreaA.y=Math.min(a.y,l.y);newAreaA.w=Math.max(a.x+a.w,l.x+l.w)-newAreaA.x;newAreaA.h=Math.max(a.y+a.h,l.y+l.h)-newAreaA.y;var changeNewAreaA=Math.abs(rectangle.squarifiedRatio(newAreaA.w,newAreaA.h,a.nodes.length+2)-areaA);var newAreaB={};newAreaB.x=Math.min(b.x,l.x);newAreaB.y=Math.min(b.y,l.y);newAreaB.w=Math.max(b.x+b.w,l.x+l.w)-newAreaB.x;newAreaB.h=Math.max(b.y+b.h,l.y+l.h)-newAreaB.y;var changeNewAreaB=Math.abs(rectangle.squarifiedRatio(newAreaB.w,newAreaB.h,b.nodes.length+2)-areaB);if(!highAreaNode||!highAreaDelta||Math.abs(changeNewAreaB-changeNewAreaA)<highAreaDelta){highAreaNode=i;highAreaDelta=Math.abs(changeNewAreaB-changeNewAreaA);lowestGrowthGroup=changeNewAreaB<changeNewAreaA?b:a}}var tempNode=nodes.splice(highAreaNode,1)[0];if(a.nodes.length+nodes.length+1<=minWidth){a.nodes.push(tempNode);rectangle.expandRectangle(a,tempNode)}else if(b.nodes.length+nodes.length+1<=minWidth){b.nodes.push(tempNode);rectangle.expandRectangle(b,tempNode)}else{lowestGrowthGroup.nodes.push(tempNode);rectangle.expandRectangle(lowestGrowthGroup,tempNode)}};var pickLinear=function(nodes){var lowestHighX=nodes.length-1;var highestLowX=0;var lowestHighY=nodes.length-1;var highestLowY=0;var t1,t2;for(var i=nodes.length-2;i>=0;i--){var l=nodes[i];if(l.x>nodes[highestLowX].x){highestLowX=i}else if(l.x+l.w<nodes[lowestHighX].x+nodes[lowestHighX].w){lowestHighX=i}if(l.y>nodes[highestLowY].y){highestLowY=i}else if(l.y+l.h<nodes[lowestHighY].y+nodes[lowestHighY].h){lowestHighY=i}}var dx=Math.abs(nodes[lowestHighX].x+nodes[lowestHighX].w-nodes[highestLowX].x);var dy=Math.abs(nodes[lowestHighY].y+nodes[lowestHighY].h-nodes[highestLowY].y);if(dx>dy){if(lowestHighX>highestLowX){t1=nodes.splice(lowestHighX,1)[0];t2=nodes.splice(highestLowX,1)[0]}else{t2=nodes.splice(highestLowX,1)[0];t1=nodes.splice(lowestHighX,1)[0]}}else{if(lowestHighY>highestLowY){t1=nodes.splice(lowestHighY,1)[0];t2=nodes.splice(highestLowY,1)[0]}else{t2=nodes.splice(highestLowY,1)[0];t1=nodes.splice(lowestHighY,1)[0]}}return[{x:t1.x,y:t1.y,w:t1.w,h:t1.h,nodes:[t1]},{x:t2.x,y:t2.y,w:t2.w,h:t2.h,nodes:[t2]}]};var attachData=function(node,moreTree){node.nodes=moreTree.nodes;node.x=moreTree.x;node.y=moreTree.y;node.w=moreTree.w;node.h=moreTree.h;return node};var searchSubtree=function(rect,returnNode,returnArray,root){var hitStack=[];if(!rectangle.overlapRectangle(rect,root)){return returnArray}hitStack.push(root.nodes);while(hitStack.length>0){var nodes=hitStack.pop();for(var i=nodes.length-1;i>=0;i--){var ltree=nodes[i];if(rectangle.overlapRectangle(rect,ltree)){if("nodes"in ltree){hitStack.push(ltree.nodes)}else if("leaf"in ltree){if(!returnNode){returnArray.push(ltree.leaf)}else{returnArray.push(ltree)}}}}}return returnArray};var insertSubtree=function(node,root){var bc;if(root.nodes.length===0){root.x=node.x;root.y=node.y;root.w=node.w;root.h=node.h;root.nodes.push(node);return}var treeStack=chooseLeafSubtree(node,root);var retObj=node;var pbc;while(treeStack.length>0){if(bc&&"nodes"in bc&&bc.nodes.length===0){pbc=bc;bc=treeStack.pop();for(var t=0;t<bc.nodes.length;t++){if(bc.nodes[t]===pbc||bc.nodes[t].nodes.length===0){bc.nodes.splice(t,1);break}}}else{bc=treeStack.pop()}if("leaf"in retObj||"nodes"in retObj||Array.isArray(retObj)){if(Array.isArray(retObj)){for(var ai=0;ai<retObj.length;ai++){rectangle.expandRectangle(bc,retObj[ai])}bc.nodes=bc.nodes.concat(retObj)}else{rectangle.expandRectangle(bc,retObj);bc.nodes.push(retObj)}if(bc.nodes.length<=maxWidth){retObj={x:bc.x,y:bc.y,w:bc.w,h:bc.h}}else{var a=linearSplit(bc.nodes);retObj=a;if(treeStack.length<1){bc.nodes.push(a[0]);treeStack.push(bc);retObj=a[1]}}}else{rectangle.expandRectangle(bc,retObj);retObj={x:bc.x,y:bc.y,w:bc.w,h:bc.h}}}};this.insertSubtree=insertSubtree;this.getTree=function(){return rootTree};this.setTree=function(newTree,where){if(!where){where=rootTree}return attachData(where,newTree)};this.search=function(rect,returnNode,returnArray){returnArray=returnArray||[];return searchSubtree(rect,returnNode,returnArray,rootTree)};var removeArea=function(rect){var numberDeleted=1,retArray=[],deleted;while(numberDeleted>0){deleted=removeSubtree(rect,false,rootTree);numberDeleted=deleted.length;retArray=retArray.concat(deleted)}return retArray};var removeObj=function(rect,obj){var retArray=removeSubtree(rect,obj,rootTree);return retArray};this.remove=function(rect,obj){if(!obj||typeof obj==="function"){return removeArea(rect,obj)}else{return removeObj(rect,obj)}};this.insert=function(rect,obj){var retArray=insertSubtree({x:rect.x,y:rect.y,w:rect.w,h:rect.h,leaf:obj},rootTree);return retArray}}RTree.prototype.toJSON=function(printing){return JSON.stringify(this.root,false,printing)};RTree.fromJSON=function(json){var rt=new RTree;rt.setTree(JSON.parse(json));return rt};module.exports=RTree;if(typeof Array.isArray!=="function"){Array.isArray=function(a){return typeof a==="object"&&{}.toString.call(a)==="[object Array]"}}},{"./rectangle":3}]},{},[2])(2)});