Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Quadtree

This example demonstrates accelerated two-dimensional filtering enabled by d3-quadtree. A quadtree recursively subdivides square cells into four equal-sized subcells. Each leaf node of the quadtree contains a single point. If a given quadtree cell does not intersect the brush extent, then none of the points contained in that subtree can be selected, and thus do not need to be scanned. Above, orange indicates points that are scanned but not selected. Without a quadtree, all points would need to be scanned!

<!DOCTYPE html>
<style>
.point {
fill: #000;
fill-opacity: 0.4;
}
.point--scanned {
fill: orange;
fill-opacity: 1;
stroke: orange;
stroke-width: 3px;
}
.point--selected {
fill: red;
fill-opacity: 1;
stroke: red;
stroke-width: 5px;
}
.node {
fill: none;
stroke: #ccc;
shape-rendering: crispEdges;
}
</style>
<svg width="960" height="500"></svg>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>
var svg = d3.select("svg"),
width = +svg.attr("width"),
height = +svg.attr("height"),
selected;
var random = Math.random,
data = d3.range(2500).map(function() { return [random() * width, random() * height]; });
var quadtree = d3.quadtree()
.extent([[-1, -1], [width + 1, height + 1]])
.addAll(data);
var brush = d3.brush()
.on("brush", brushed);
svg.selectAll(".node")
.data(nodes(quadtree))
.enter().append("rect")
.attr("class", "node")
.attr("x", function(d) { return d.x0; })
.attr("y", function(d) { return d.y0; })
.attr("width", function(d) { return d.y1 - d.y0; })
.attr("height", function(d) { return d.x1 - d.x0; });
var point = svg.selectAll(".point")
.data(data)
.enter().append("circle")
.attr("class", "point")
.attr("cx", function(d) { return d[0]; })
.attr("cy", function(d) { return d[1]; })
.attr("r", 2);
svg.append("g")
.attr("class", "brush")
.call(brush)
.call(brush.move, [[100, 100], [200, 200]]);
function brushed() {
var extent = d3.event.selection;
point.each(function(d) { d.scanned = d.selected = false; });
search(quadtree, extent[0][0], extent[0][1], extent[1][0], extent[1][1]);
point.classed("point--scanned", function(d) { return d.scanned; });
point.classed("point--selected", function(d) { return d.selected; });
}
// Find the nodes within the specified rectangle.
function search(quadtree, x0, y0, x3, y3) {
quadtree.visit(function(node, x1, y1, x2, y2) {
if (!node.length) {
do {
var d = node.data;
d.scanned = true;
d.selected = (d[0] >= x0) && (d[0] < x3) && (d[1] >= y0) && (d[1] < y3);
} while (node = node.next);
}
return x1 >= x3 || y1 >= y3 || x2 < x0 || y2 < y0;
});
}
// Collapse the quadtree into an array of rectangles.
function nodes(quadtree) {
var nodes = [];
quadtree.visit(function(node, x0, y0, x1, y1) {
node.x0 = x0, node.y0 = y0;
node.x1 = x1, node.y1 = y1;
nodes.push(node);
});
return nodes;
}
</script>
@dribnet

This comment has been minimized.

Copy link

@dribnet dribnet commented Dec 29, 2012

Found initialization typo bug at line 43 - almost half the nodes are out of the view area. Fix available here: https://gist.github.com/4409108

@dribnet

This comment has been minimized.

Copy link

@dribnet dribnet commented Aug 23, 2013

Interesting revision a few days ago updating the quadtree accessor function + changing the data from maps to arrays - is that more efficient? Another potential optimization is not instantiating a few thousand svg elements outside of the view area. Just sayin'. :-)

@patricksurry

This comment has been minimized.

Copy link

@patricksurry patricksurry commented Sep 7, 2013

I forked to create a little demo of finding nearest neighbor of a new point in the quadtree. See http://bl.ocks.org/patricksurry/6478178.

It's much more efficient with a data-dependent ordering of child traversal.

Also couldn't see a way of getting a node's extent (or depth) in my custom visit() routine - am I missing something?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.