Skip to content

Instantly share code, notes, and snippets.

@eweitnauer
Last active December 25, 2015 07:49
Show Gist options
  • Save eweitnauer/6941810 to your computer and use it in GitHub Desktop.
Save eweitnauer/6941810 to your computer and use it in GitHub Desktop.
Quadtree 2

This example demonstrates how to take the size of objects into account when selecting objects efficiently with a quadtree. Selected objects are shown in red, visited but not selected objects are shown in yellow. The efficiency depends on the size of the biggest object. It is assumed that the objects are square-shaped.

Example series:

Based on Mike Bostock's quadtree example.

<!DOCTYPE html>
<meta charset="utf-8">
<title>Quadtree</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;
shape-rendering: crispEdges;
}
.brush .extent {
stroke: #fff;
fill-opacity: .125;
shape-rendering: crispEdges;
}
</style>
<body>
<script src="http://d3js.org/d3.v3.min.js"></script>
<script>
var width = 960,
height = 500,
max_r = 30;
var data = d3.range(1000).map(function() {
return [Math.random() * width, Math.random() * width, Math.random() * max_r];
});
var quadtree = d3.geom.quadtree()
.extent([[-1, -1], [width + 1, height + 1]])
(data);
var brush = d3.svg.brush()
.x(d3.scale.identity().domain([0, width]))
.y(d3.scale.identity().domain([0, height]))
.extent([[100, 100], [200, 200]])
.on("brush", brushed);
var svg = d3.select("body").append("svg")
.attr("width", width)
.attr("height", height);
svg.selectAll(".node")
.data(nodes(quadtree))
.enter().append("rect")
.attr("class", "node")
.attr("x", function(d) { return d.x; })
.attr("y", function(d) { return d.y; })
.attr("width", function(d) { return d.width; })
.attr("height", function(d) { return d.height; });
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", function (d) { return d[2]; });
svg.append("g")
.attr("class", "brush")
.call(brush);
brushed();
function brushed() {
var extent = brush.extent();
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("scanned", function(d) { return d.scanned; });
point.classed("selected", function(d) { return d.selected; });
}
// Collapse the quadtree into an array of rectangles.
function nodes(quadtree) {
var nodes = [];
quadtree.visit(function(node, x1, y1, x2, y2) {
nodes.push({x: x1, y: y1, width: x2 - x1, height: y2 - y1});
});
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]+p[2] >= x0) && (p[0]-p[2] < x3) && (p[1]+p[2] >= y0) && (p[1]-p[2] < y3);
}
return x1-max_r >= x3 || y1-max_r >= y3 || x2+max_r < x0 || y2+max_r < y0;
});
}
</script>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment