Skip to content

Instantly share code, notes, and snippets.

@chabb

chabb/README.md

Last active August 29, 2015 14:04
Show Gist options
  • Save chabb/8e569d673ac4b94a1dfd to your computer and use it in GitHub Desktop.
Save chabb/8e569d673ac4b94a1dfd to your computer and use it in GitHub Desktop.
Download ZIP
Building Quadtree
Raw
README.md

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.

Raw
index.html
<!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="http://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 http://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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment