Building Quadtree

This shows the building of the quadtree as points are added. The animation shows the traversal of the tree. A margin test is used to determine the good leaf to choose.

<!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; });

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; });

});
  gp++;
}

});
}

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>

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

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