D3 Examples - quadtrees, what are they good for?

xxxxxxxxxx
 
<!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="https://cdn.leafletjs.com/leaflet-0.5.1/leaflet.css" />
<title>Quadtree madness</title>
<div id="map"></div>
<script src="https://d3js.org/d3.v3.js"></script>
​
<script src="https://cdnjs.cloudflare.com/ajax/libs/leaflet/0.5.1/leaflet.min.js"></script>
<script src="https://cdn.jsdelivr.net/gh/calvinmetcalf/leaflet.markercluster/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("https://{s}.tile.stamen.com/watercolor/{z}/{x}/{y}.jpg",{minZoom:4,maxZoom:12,attribution:'Map tiles by <a href="https://stamen.com">Stamen Design</a>, <a href="https://creativecommons.org/licenses/by/3.0">CC BY 3.0</a> &mdash; Map data &copy; <a href="https://openstreetmap.org">OpenStreetMap</a> contributors, <a href="https://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>
    