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.

<!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>

// 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>

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

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