D3 Examples - Building Quadtree

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>
​
var width = 960,
    height = 500, np,gp = 0;
​
​
var data = d3.range(35).map(function() {
  return [Math.random() * width, Math.random() * height];
});
​
var quadtree = d3.geom.quadtree()
    .extent([[-1, -1], [width + 1, height + 1]])
    (data);
var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height);
var _nodes = nodes(quadtree);
​
svg.selectAll(".node")
    .data(_nodes)
  .enter().append("rect")
    .attr("class", "node")
    .attr("x", function(d) { return d.x1; })
    .attr("y", function(d) { return d.y1; })
    .attr("width", function(d) { return d.width; })
    .attr("height", function(d) { return d.height; });
​
var point = svg.selectAll(".point")
    .data(data,function(d,i) { return i; })
  .enter().append("circle")
    .attr("class", "point")
    .attr("cx", function(d) { return d[0]; })
    .attr("cy", function(d) { return d[1]; })
    .attr("r", 4);
​
addPoint();
function addPoint() {
  var newPoint =  [Math.random() * width, Math.random() * height];
  var cPoint;
  data.push(newPoint);
  quadtree.add(newPoint);
  _nodes = nodes(quadtree);
  var start = [0,0];
  cpoint = { xy: start, iteration:1,end:newPoint,id:gp};
  //cpoint.iteration = 0;
​
  np = svg.selectAll(".point")
    .data(data)
  ;
  svg.selectAll(".node")
    .data(_nodes)
    .attr("x", function(d) { return d.x1; })
    .attr("y", function(d) { return d.y1; })
    .attr("width", function(d) { return d.width; })
    .attr("height", function(d) { return d.height; })
    .enter().append("rect")
    .attr("class", "node")
    .attr("x", function(d) { return d.x1; })
    .attr("y", function(d) { return d.y1; })
    .attr("width", function(d) { return d.width; })
    .attr("height", function(d) { return d.height; });
​
​
​
  var added = np.enter().append("circle")
    .attr("class", "point")
    .attr("cx", function(d) { return start[0]; })
    .attr("cy", function(d) { return start[1]; })
    .attr("r", 10);
  searchNextCenter.iteration = 0;
  searchNextCenter.finished = false;
  searchNextCenter(cpoint.end[0],cpoint.end[1],_nodes[0],0);
  added.transition().duration(400)
   .attr("cx", function(d) { return cpoint.nextXY[0]; })
   .attr("cy", function(d) { return cpoint.nextXY[1]; })
   .each("end",function()
   {
      console.log('s');
      cpoint.iteration = +1;
      searchNextCenter.finished = false;
      //TODO dont start from top node, restart from last node
      searchNextCenter(cpoint.end[0],cpoint.end[1],_nodes[0],0);
      chainTransition(this,cpoint);
​
  });
  gp++;
}
​
function chainTransition(transition,cpoint) {
  console.log("IT",transition,"TRANS",cpoint);
  d3.select(transition).transition().duration(400)
   .attr("cx", function(d) { return cpoint.nextXY[0]; })
   .attr("cy", function(d) { return cpoint.nextXY[1]; })
   .each("end",function(){
      cpoint.iteration = +1;
      if (cpoint.final) { addPoint(); return };
      searchNextCenter.iteration = 0;
      searchNextCenter.finished = false;
      //TODO dont start from top node, restart from last node
      searchNextCenter(cpoint.end[0],cpoint.end[1],_nodes[0],0);
      chainTransition(this,cpoint);
​
   });
}
​
function searchNextCenter(x,y,node,depth) {
​
​
  //console.log("==>",depth,node,x,y,cpoint,searchNextCenter.finished,gp);
  if (node.point) console.log(node.point.x,x,(node.point.x==x));
  if (searchNextCenter.finished) return;
​
  if (node.point && node.point[0] == x && node.point[1] == y ) {
    console.log("FOUND POINT ??")
    cpoint.nextXY = [x,y];
    searchNextCenter.finished = true;
    cpoint.final = true;
    return;
  } else {
    if (!node.visited[gp]) {
      node.visited[gp] = true;
      //console.log('Find something',node);
      cpoint.nextXY = node.center;
      searchNextCenter.finished = true;
      return;
    } else {
        var kids = node.nodes;
        var x1 = node.x1,x2=node.x2,y1=node.y1,y2=node.y2;
        var rl = (2*x > x2+x1), bt = (2*y > y2+y1);
        console.log(x,x1,y,y1);
        // DIG de https://bl.ocks.org/patricksurry/6478178
        if (kids[bt*2+rl])          searchNextCenter(x, y,kids[bt*2+rl],depth);
        if (kids[bt*2+(1-rl)])      searchNextCenter(x, y, kids[bt*2+(1-rl)],depth);
        if (kids[(1-bt)*2+rl])      searchNextCenter(x, y, kids[(1-bt)*2+rl],depth);
        if (kids[(1-bt)*2+(1-rl)])  searchNextCenter(x, y,  kids[(1-bt)*2+(1-rl)],depth);
    }
  }
​
}
// Collapse the quadtree into an array of rectangles.
function nodes(quadtree) {
  var nodes = [];
​
  quadtree.visit(function(node, x1, y1, x2, y2) {
    // en fait on peut pas rajouter les coordonées des rect directement, on les génère en visitant l'arbre
    node.x1 = x1;
    node.y1 = y1;
    node.x2 = x2;
    node.y2 = y2;
    node.width = x2-x1;
    node.height = y2-y1;
    node.visited = {};
    node.center = [x1 + (x2-x1)/2, y1+(y2-y1)/2];
    nodes.push(node);
​
  });
  return nodes;
}
​
// Find the nodes within the specified rectangle.
function _search(quadtree, x0, y0, x3, y3) {
  quadtree.visit(function(node, x1, y1, x2, y2) {
    var p = node.point;
    if (p) {
      p.scanned = true;
      p.selected = (p[0] >= x0) && (p[0] < x3) && (p[1] >= y0) && (p[1] < y3);
    }
    return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0;
  });
}
​
</script>
​
    