Point Quadtrees

D3.js uses a PR Quadtree, which subdivides space in four congruent block.

This is a small example of a point quadtree, where space is divised into four quadrants centered on the inserted points

<!DOCTYPE html>
<meta charset="utf-8">
<title>Quadtree</title>
<style>

.point {
  fill: orange;
  fill-opacity: 1;
  stroke: brown;
}

.node {
  fill: none;
  stroke: #ccc;
  shape-rendering: crispEdges;
}

.new {
  stroke-width: 5px;
}

</style>
<body>
<script src="https://d3js.org/d3.v3.min.js"></script>

// setup scene
var width = 500,
    height = 500, np,gp = 0;
var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height);

// i putted lesser extent and it mess stuff
root = { links:[], x:100,y:300,x0:0,y0:0,x1:500,y1:500};
for (var i=0;i<15;i++) {
  var cn = { x:Math.random()*440+60,y:Math.random()*440+60,links:[]};
  insertNode(root,cn);
}

var datas = [];
visit(root,datas);

var zones = svg.selectAll(".points")
  .data(datas)
  .enter()
  .append("g").classed("points",true);

zones.append("circle")
  .classed("point",true)
  .attr("cx",function(d){return d.x})
  .attr("cy",function(d){return d.y})
  .attr("r" , 5)

// extrapole all nodes
zones.append("line")
  .classed("node",true)
  .classed("nodeA",true)
  .attr("x1",function(d){return d.x})
  .attr("y1",function(d){return d.y0})
  .attr("x2",function(d){return d.x})
  .attr("y2",function(d){return d.y1})

zones.append("line")
  .classed("node",true)
  .classed("nodeB",true)
  .attr("x1",function(d){return d.x0})
  .attr("y1",function(d){return d.y})
  .attr("x2",function(d){return d.x1})
  .attr("y2",function(d){return d.y})

setInterval(function(){
// DO STUFF
  console.log('Doing stuff..');
  // do heap snapshots to verify is things are properly garbage collected
  root = { links:[], x:100,y:300,x0:0,y0:0,x1:500,y1:500};
  for (var i=0;i<15;i++) {
    var cn = { x:Math.random()*440+60,y:Math.random()*440+60,links:[]};
    insertNode(root,cn);
  }

var datas = [];
  visit(root,datas);
  var newJoin = zones.data(datas);
  newJoin.select("circle").transition()
  .attr("cx",function(d){return d.x})
  .attr("cy",function(d){return d.y})
  .attr("r" , 5);

newJoin.select("line.nodeA").transition()
  .attr("x1",function(d){return d.x})
  .attr("y1",function(d){return d.y0})
  .attr("x2",function(d){return d.x})
  .attr("y2",function(d){return d.y1})

newJoin.select("line.nodeB").transition()
  .attr("x1",function(d){return d.x0})
  .attr("y1",function(d){return d.y})
  .attr("x2",function(d){return d.x1})
  .attr("y2",function(d){return d.y})

},1000);
// NODE HAS 4 CHILDREN
// node xy => point
// node x1/y1/x2/y2 => extent
function insertNode(root,node) {

//PREORDER TRAVERSAL
function visit(root,array) {
    array.push(root);
    if (root.links.length == 0) return;
    for (var i=0;i<4;i++) {
      console.log('visiting i',i,root.links.length);
      if (root.links[i]!= null) {
        visit(root.links[i],array);
      }
    }
}
</script>

Modified http://d3js.org/d3.v3.min.js to a secure url

https://d3js.org/d3.v3.min.js