Skip to content

Instantly share code, notes, and snippets.

@4ndr01d3
Last active November 23, 2016 05:25
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save 4ndr01d3/727175afbdc58c3626b8 to your computer and use it in GitHub Desktop.
Save 4ndr01d3/727175afbdc58c3626b8 to your computer and use it in GitHub Desktop.
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.

<!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="http://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>
var color = d3.scale.linear()
.domain([0, 8]) // max depth of quadtree
.range(["#efe", "#060"]);
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
var rect = svg.selectAll(".node")
.data(nodes.nodes)
.enter().append("rect")
.attr("id", function(d) { return "node_"+d.c; })
.attr("class", "node")
.attr("x", function(d) { return d.x1; })
.attr("y", function(d) { return d.y1; })
.attr("width", function(d) { return d.x2 - d.x1; })
.attr("height", function(d) { return d.y2 - d.y1; })
.style("opacity",0);
var count=0;
var point = svg.selectAll(".point")
.data(nodes.leaves)
.enter().append("circle")
.attr("class", function(d) { return "point "+d.classes; })
.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; })
.attr("r", 3);
// PDS Collect a list of nodes to draw rectangles, adding extent and depth data
var margin = {top: 20, right: 20, bottom: 20, left: 20},
width = 410 - margin.right - margin.left,
height = 310 - margin.top - margin.bottom;
var i = 0;
var tree = d3.layout.tree()
.size([height, width]);
var diagonal = d3.svg.diagonal()
.projection(function(d) { return [d.y, d.x]; });
var svg = d3.select("body").append("svg")
.attr("width", width + margin.right + margin.left)
.attr("height", height + margin.top + margin.bottom)
.append("g")
.attr("transform", "translate(" + margin.left + "," + margin.top + ")");
root.x0 = height / 2;
root.y0 = 0;
function collapse(d) {
if (typeof d.nodes=="undefined") return;
d.children=(d.nodes.length==0)?null:d.nodes;
if (d.children!=null){
if (typeof d.children[0]=="undefined") d.children[0] ={c:d.c+"_"+0};
if (typeof d.children[1]=="undefined") d.children[1] ={c:d.c+"_"+1};
if (typeof d.children[2]=="undefined") d.children[2] ={c:d.c+"_"+2};
if (typeof d.children[3]=="undefined") d.children[3] ={c:d.c+"_"+3};
}
if (d.children) {
d._children = d.children;
d._children.forEach(collapse);
d.children = null;
}
}
root.children=root.nodes;
root.children.forEach(collapse);
collapse(root)
update(root);
d3.select(self.frameElement).style("height", "800px");
function update(source,delay) {
delay = typeof delay=="undefined" ? 0 : delay;
// Compute the new tree layout.
var nodes = tree.nodes(root).reverse(),
links = tree.links(nodes);
// Normalize for fixed-depth.
nodes.forEach(function(d) { d.y = d.depth * 50; });
// Update the nodes…
var node = svg.selectAll("g.node")
.data(nodes, function(d) { return d.id || (d.id = ++i); });
// Enter any new nodes at the parent's previous position.
var nodeEnter = node.enter().append("g")
.attr("id", function(d) { return "node_tree_"+d.id; })
.attr("class", "node")
.attr("transform", function(d) { return "translate(" + source.y0 + "," + source.x0 + ")"; })
.on("click", click)
.on("mouseover",function(d){
d3.selectAll("#node_"+d.c)
.style("fill","lightsteelblue")
.style("opacity",0.4);
d3.selectAll(".square_"+d.c)
.style("stroke","red")
.attr("r",5) ;
})
.on("mouseout",function(d){
d3.selectAll("#node_"+d.c)
.style("fill",null)
.style("opacity",null);
d3.selectAll(".square_"+d.c)
.style("stroke",null)
.attr("r",3) ;
});
nodeEnter.append("circle")
.attr("r", 1e-6)
.style("fill", function(d) {
if (d.verified)
return d.leaf?"orange":(d._children ? "lightsteelblue" :"#fff");
return "steelblue";
});
nodeEnter.append("text")
.attr("x", function(d) { return d.children || d._children ? -10 : 10; })
.attr("dy", ".35em")
.attr("text-anchor", function(d) { return d.children || d._children ? "end" : "start"; })
.text(function(d) { return d.name; })
.style("fill-opacity", 1e-6);
// Transition nodes to their new position.
var nodeUpdate = node.transition().delay(delay)
.duration(duration)
.attr("transform", function(d) { return "translate(" + d.y + "," + d.x + ")"; });
nodeUpdate.select("circle")
.attr("r", function(d) { return (!d.verified || d.leaf || d._children || d.children)?4.5:0; })
.style("fill", function(d) {
if (d.verified)
return d.leaf?"orange":(d._children ? "lightsteelblue" :"#fff");
return "steelblue";
});
nodeUpdate.select("text")
.style("fill-opacity", 1);
// Transition exiting nodes to the parent's new position.
var nodeExit = node.exit().transition().delay(delay)
.duration(duration)
.attr("transform", function(d) { return "translate(" + source.y + "," + source.x + ")"; })
.remove();
nodeExit.select("circle")
.attr("r", 1e-6);
nodeExit.select("text")
.style("fill-opacity", 1e-6);
// Update the links…
var link = svg.selectAll("path.link")
.data(links, function(d) { return d.target.id; });
// Enter any new links at the parent's previous position.
link.enter().insert("path", "g")
.attr("class", "link")
.attr("d", function(d) {
var o = {x: source.x0, y: source.y0};
return diagonal({source: o, target: o});
});
// Transition links to their new position.
link.transition()
.duration(duration).delay(delay)
.attr("d", diagonal);
// Transition exiting nodes to the parent's new position.
link.exit().transition()
.duration(duration).delay(delay)
.attr("d", function(d) {
var o = {x: source.x, y: source.y};
return diagonal({source: o, target: o});
})
.remove();
// Stash the old positions for transition.
nodes.forEach(function(d) {
d.x0 = d.x;
d.y0 = d.y;
});
}
// Toggle children on click.
function click(d) {
if (d.children) {
d._children = d.children;
d.children = null;
} else {
d.children = d._children;
d._children = null;
}
update(d);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment