Skip to content

Instantly share code, notes, and snippets.

@calvinmetcalf
Created February 15, 2013 18:51
Show Gist options
  • Save calvinmetcalf/4962455 to your computer and use it in GitHub Desktop.
Save calvinmetcalf/4962455 to your computer and use it in GitHub Desktop.
quadtrees, what are they good for?

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.

<!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> &mdash; Map data &copy; <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