So hit the button in the bottom left to start adding points, then if you hold down shift and draw a box it'll running a bounding box query on that area and limit the map to that.
Created
February 15, 2013 18:51
-
-
Save calvinmetcalf/4962455 to your computer and use it in GitHub Desktop.
quadtrees, what are they good for?
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
<!DOCTYPE html> | |
<meta charset="utf-8"> | |
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1"> | |
<meta name="viewport" content="width=1024, user-scalable=no"> | |
<style> | |
html { height: 100% } | |
body { height: 100%; margin: 0; padding: 0;} | |
#map{ height: 100% } | |
.leaflet-cluster-anim .leaflet-marker-icon, .leaflet-cluster-anim .leaflet-marker-shadow { | |
-webkit-transition: -webkit-transform 0.25s ease-out, opacity 0.25s ease-in; | |
-moz-transition: -moz-transform 0.25s ease-out, opacity 0.25s ease-in; | |
-o-transition: -o-transform 0.25s ease-out, opacity 0.25s ease-in; | |
transition: transform 0.25s ease-out, opacity 0.25s ease-in; | |
} | |
.marker-cluster-small { | |
background-color: rgba(181, 226, 140, 0.6); | |
} | |
.marker-cluster-small div { | |
background-color: rgba(110, 204, 57, 0.6); | |
} | |
.marker-cluster-medium { | |
background-color: rgba(241, 211, 87, 0.6); | |
} | |
.marker-cluster-medium div { | |
background-color: rgba(240, 194, 12, 0.6); | |
} | |
.marker-cluster-large { | |
background-color: rgba(253, 156, 115, 0.6); | |
} | |
.marker-cluster-large div { | |
background-color: rgba(241, 128, 23, 0.6); | |
} | |
.marker-cluster { | |
background-clip: padding-box; | |
border-radius: 20px; | |
} | |
.marker-cluster div { | |
width: 30px; | |
height: 30px; | |
margin-left: 5px; | |
margin-top: 5px; | |
text-align: center; | |
border-radius: 15px; | |
font: 12px "Helvetica Neue", Arial, Helvetica, sans-serif; | |
} | |
.marker-cluster span { | |
line-height: 30px; | |
} | |
</style> | |
<link rel="stylesheet" href="http://cdn.leafletjs.com/leaflet-0.5.1/leaflet.css" /> | |
<title>Quadtree madness</title> | |
<div id="map"></div> | |
<script src="http://d3js.org/d3.v3.js"></script> | |
<script src="http://cdn.leafletjs.com/leaflet-0.5.1/leaflet.js"></script> | |
<script src="https://raw.github.com/calvinmetcalf/Leaflet.markercluster/master/dist/leaflet.markercluster.js"></script> | |
<script> | |
function Quadtree(points){ | |
points = points || []; | |
var p=points; | |
var quadtree = d3.geom.quadtree(p.map(function(v,i){return {x:v[0],y:v[1],all:v};})); | |
this.add = function(pts){ | |
p = p.concat(pts); | |
quadtree = d3.geom.quadtree(p.map(function(v,i){return {x:v[0],y:v[1],all:v};})); | |
}; | |
this.bbox=function(blat1,blng1,blat2,blng2){ | |
if(!blat1){ | |
return p; | |
} | |
var out = []; | |
quadtree.visit(function(quad, lat1, lng1, lat2, lng2){ | |
if(((blat1>lat2)&&(blat2>lat2))||((blat1<lat1)&&(blat2<lat1))||((blng1>lng2)&&(blng2>lng2))||((blng1<lng1)&&(blng2<lng1))){ | |
return true; | |
}else if(((blat2>=lat2)&&(blng2>=lng2)&&(blat1<=lat1)&&(blng1<=lng1))){ | |
out.push(quad); | |
return true; | |
} | |
}); | |
var pts = []; | |
function getPt(quad){ | |
if(quad.point){ | |
pts.push(quad.point.all); | |
} | |
if(!quad.leaf&&quad.nodes.length>0){ | |
quad.nodes.forEach(getPt); | |
} | |
} | |
out.forEach(getPt); | |
return pts; | |
}; | |
} | |
var m = L.map("map").setView([42.3164, -71.7],9); | |
//make the map | |
L.tileLayer("http://{s}.tile.stamen.com/watercolor/{z}/{x}/{y}.jpg",{minZoom:4,maxZoom:12,attribution:'Map tiles by <a href="http://stamen.com">Stamen Design</a>, <a href="http://creativecommons.org/licenses/by/3.0">CC BY 3.0</a> — Map data © <a href="http://openstreetmap.org">OpenStreetMap</a> contributors, <a href="http://creativecommons.org/licenses/by-sa/2.0/">CC-BY-SA</a>'} | |
).addTo(m); | |
//add a tileset | |
//generate 60k random points | |
var pts = new L.MarkerClusterGroup(); | |
pts.addTo(m); | |
var qt; | |
var bbox; | |
function morePoints(lat,lng){ | |
var randomLat = d3.random.normal(lat, .15), | |
randomLng = d3.random.normal(lng, .5); | |
var points = d3.range(2000).map(function() { return [randomLat(), randomLng()]; }); | |
if(!qt){ | |
qt = new Quadtree(points); | |
}else{ | |
qt.add(points); | |
} | |
redoBox(bbox); | |
} | |
var BoxSelect = L.Handler.extend({ | |
initialize: function (map) { | |
this._map = map; | |
this._container = map._container; | |
this._pane = map._panes.overlayPane; | |
}, | |
addHooks: function () { | |
L.DomEvent.on(this._container, 'mousedown', this._onMouseDown, this); | |
}, | |
removeHooks: function () { | |
L.DomEvent.off(this._container, 'mousedown', this._onMouseDown); | |
}, | |
_onMouseDown: function (e) { | |
if (!e.shiftKey || ((e.which !== 1) && (e.button !== 1))) { return false; } | |
L.DomUtil.disableTextSelection(); | |
this._startLayerPoint = this._map.mouseEventToLayerPoint(e); | |
this._box = L.DomUtil.create('div', 'leaflet-zoom-box', this._pane); | |
L.DomUtil.setPosition(this._box, this._startLayerPoint); | |
//TODO refactor: move cursor to styles | |
this._container.style.cursor = 'crosshair'; | |
L.DomEvent | |
.on(document, 'mousemove', this._onMouseMove, this) | |
.on(document, 'mouseup', this._onMouseUp, this) | |
.preventDefault(e); | |
this._map.fire("boxselectstart"); | |
}, | |
_onMouseMove: function (e) { | |
var startPoint = this._startLayerPoint, | |
box = this._box, | |
layerPoint = this._map.mouseEventToLayerPoint(e), | |
offset = layerPoint.subtract(startPoint), | |
newPos = new L.Point( | |
Math.min(layerPoint.x, startPoint.x), | |
Math.min(layerPoint.y, startPoint.y)); | |
L.DomUtil.setPosition(box, newPos); | |
// TODO refactor: remove hardcoded 4 pixels | |
box.style.width = (Math.max(0, Math.abs(offset.x) - 4)) + 'px'; | |
box.style.height = (Math.max(0, Math.abs(offset.y) - 4)) + 'px'; | |
}, | |
_onMouseUp: function (e) { | |
this._pane.removeChild(this._box); | |
this._container.style.cursor = ''; | |
L.DomUtil.enableTextSelection(); | |
L.DomEvent | |
.off(document, 'mousemove', this._onMouseMove) | |
.off(document, 'mouseup', this._onMouseUp); | |
var map = this._map, | |
layerPoint = map.mouseEventToLayerPoint(e); | |
if (this._startLayerPoint.equals(layerPoint)) { return; } | |
var bounds = new L.LatLngBounds( | |
map.layerPointToLatLng(this._startLayerPoint), | |
map.layerPointToLatLng(layerPoint)); | |
map.fire("boxselectend", { | |
boxSelectBounds: [bounds.getSouthWest().lat,bounds.getSouthWest().lng,bounds.getNorthEast().lat,bounds.getNorthEast().lng] | |
}); | |
} | |
}); | |
m.boxZoom.disable(); | |
var boxSelect = new BoxSelect(m); | |
boxSelect.enable(); | |
m.on("boxselectend",function(e){redoBox(e.boxSelectBounds);}); | |
function redoBox(p){ | |
p=p||[]; | |
pts.clearLayers(); | |
bbox=p; | |
pts.addLayers(qt.bbox.apply(qt,p).map(function(v){return L.marker(v).bindPopup(JSON.stringify(v))})); | |
} | |
m.on("contextmenu",function(){redoBox()}); | |
var AddButton= L.Control.extend({ | |
options: { | |
position: 'bottomleft' | |
}, | |
onAdd: function (map) { | |
// create the control container with a particular class name | |
var div = L.DomUtil.create('div','bgroup'); | |
var addButton = L.DomUtil.create('button', 'addStuff',div); | |
addButton.type="button"; | |
addButton.innerHTML="Add More Points"; | |
L.DomEvent.addListener(addButton,"click",function(){ | |
morePoints(map.getCenter().lat,map.getCenter().lng); | |
}); | |
var allButton = L.DomUtil.create('button', 'allStuff',div); | |
allButton.type="button"; | |
allButton.innerHTML="ShowAll"; | |
L.DomEvent.addListener(allButton,"click",function(){ | |
redoBox(); | |
}); | |
return div; | |
} | |
}); | |
m.addControl(new AddButton()); | |
</script> |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment