D3 Examples - Point Quadtrees

xxxxxxxxxx
 
<!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>
​
<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) {
​
  var x = node.x;
  var y = node.y;
  var sx = root.x, sy = root.y, right = x >= sx, bottom = y >= sy, i = (bottom << 1) + right;
  console.log(right,bottom,i);
  if (root.links[i] != null) {
    insertNode(root.links[i],node);
  } else {
    //should calculate extent
    if (right)  {x0=root.x;x1=root.x1;} else {x0 =root.x0;x1=root.x;}
    if (bottom) {y0=root.y;y1=root.y1;} else {y0 =root.y0;y1=root.y;}
    node.x0=x0;
    node.y0=y0;
    node.x1=x1;
    node.y1=y1;
    root.links[i] = node;
    node.parent = root;
  }
}
​
​
//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>
​
    