D3 Examples - How a Quadtree is created

How a Quadtree is created
This demo shows an animation explaining how a Quadtree is created using D3: "A quadtree is a two-dimensional recursive spatial subdivision. This implementation uses square partitions, dividing each square into four equally-sized squares."
The demo was inspired by the article on Visualizing Algorithms. To draw the points and the quadtree squares I took some code from this Example. The tree basically reuses the code of this Example.
xxxxxxxxxx
 
<!DOCTYPE html>
<meta charset="utf-8">
<title>Quadtree - nearest neighbor</title>
<style>
​
.point {
  fill: #999;
  stroke: #fff;
}
​
.point.scanned {
  fill: orange;
  fill-opacity: 1;
  stroke: brown;
}
​
.point.selected {
  fill: red;
  fill-opacity: 1;
}
​
.node {
  fill: none;
  stroke: #ccc;
  cursor: pointer;
}
  
.brush .extent {
  stroke: #fff;
  fill-opacity: .125;
  shape-rendering: crispEdges;
}
​
.node circle {
  fill: #fff;
  stroke: steelblue;
  stroke-width: 1.5px;
}
​
.node text {
  font: 10px sans-serif;
}
​
.link {
  fill: none;
  stroke: #ccc;
  stroke-width: 1.5px;
}
</style>
<body>
<script src="https://d3js.org/d3.v3.js"></script>
<script>
​
var width = 310,
    height = 310;
​
var data = d3.range(20).map(function(n) {
    return [Math.random() * width, Math.random() * height];
});
var quadtree = d3.geom.quadtree()
    .extent([[-1, -1], [width + 1, height + 1]])
    (data);
​
​
function nodes(quadtree) {
    var nodes = [],count=0,leaves = [];
    quadtree.depth = 0; // root
    quadtree.visit(function(node, x1, y1, x2, y2) {
        node.x1 = x1;
        node.y1 = y1;
        node.x2 = x2;
        node.y2 = y2;
        node.c=count++;
        node.classes= (node.depth==0)? "square_0" : node.classes+" square_"+node.c;
​
        node.verified=false;
        nodes.push(node);
        for (var i=0; i<4; i++) {
            if (node.nodes[i]){
                node.nodes[i].depth = node.depth+1;
                node.nodes[i].classes = node.classes;
            }
        }
        if (node.leaf)  leaves.push(node);
    });
    return {nodes:nodes,leaves:leaves};
}
​
nodes =nodes(quadtree);
root = quadtree;
duration = 750;
​
</script>
​
<script src="paint_quadtree.js"></script>
<script src="paint_tree.js"></script>
​
​
<script>
​
// Action to highlight the active node. It triggers the next action in the waiting list once the animation finishes
function highlight_node(d) {
    d.verified=true;
    d3.selectAll("#node_tree_"+d.id+" circle")
        .transition()
        .duration(duration)
        .style("fill","red")
        .attr("r",6.5)
        .each("end", function(){
            action_square(d,false);
            nextAction();
            d3.selectAll("#node_tree_"+d.id+" circle")
                .attr("r", function(d) { return (d.leaf || d._children || d.children)?4.5:0; })
                .style("fill", function(d) { return d.leaf?"orange":(d._children ? "lightsteelblue" :"#fff"); });
        })
    action_square(d,true);
}
​
// Action to highlight the active square in the graphic including the points that it covers
function action_square(d,highlight) {
    d3.selectAll("#node_"+d.c)
        .style("fill",highlight?"lightsteelblue":null)
        .style("opacity",highlight?0.4:null);
    d3.selectAll(".square_"+d.c)
        .style("fill",function() { return highlight ?"red": ( d.leaf?"orange":null); }) 
        .attr("r",highlight ? 4 : 3);
}
​
// Action to expand a node in the tree. It adds actions to highlight and expand its children and then triggers the next action
function expand_node(d){
    if (d._children) {
        d.children = d._children;
        d._children = null;
        update(d);
    }
    if (d.children) {
        for (var i=0;i<4;i++){
            addAction({action:highlight_node,node:d.children[i], parent:d});
            addAction({action:expand_node,node:d.children[i], parent:d});
        }
    }
    nextAction();
}
​
// Adds an action into the waiting list, preserving the hierarchical order of calls.
// i.e. It tries to add it after its first sibling, then it checks if is a child of the current action, other wise it's added at the end.
function addAction(action){
    var i=actions.length;
    while (--i>=0){
        if (actions[i].node==action.parent || actions[i].parent==action.parent){
            actions.splice(i+1,0,action);
            return;
        }
    }
    if (currentAction.node==action.parent || currentAction.parent==action.parent){
        actions.splice(0,0,action);
        return;
    }
    actions.push(action);
}
​
// Pointer to the action that is currently been executed. null if none.
var currentAction=null;
​
// Executes the next action in the list.
function nextAction(){
    var action = actions.shift();
    if (action){
        currentAction=action;
        action.action.call(this,action.node,action.index);
        currentAction=null;
    }
}
​
// cList of actions to execute. It is initialised by highlighting the root and then expanding it.
var actions=[];
    actions.push({action:highlight_node,node:root,parent:null});
    actions.push({action:expand_node,node:root,parent:null});
​
// Start the simulation!
nextAction();
​
</script>
<script type="text/javascript">
    // Hack to make this example display correctly in an iframe on bl.ocks.org
    d3.select(self.frameElement).style("height", "320px");
</script> 
    