Skip to content

Instantly share code, notes, and snippets.

@eweitnauer
Created October 11, 2013 21:03
Show Gist options
  • Save eweitnauer/6941997 to your computer and use it in GitHub Desktop.
Save eweitnauer/6941997 to your computer and use it in GitHub Desktop.
Quadtree 3

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 biggest width and biggest height among all object. It is assumed that all objects are rectangle-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,
min_w = 5, max_w = 50, // half of maximum element width
min_h = 5, max_h = 35; // half of maximum element height
var data = d3.range(1000).map(function() {
return [Math.random() * width, Math.random() * width
,min_w+Math.random()*(max_w-min_w)
,min_h+Math.random() * (max_h-min_h)];
});
var max_w = d3.max(data, function (d) { return d[2] })
,max_h = d3.max(data, function (d) { return d[3] });
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("rect")
.attr("class", "point")
.attr("x", function (d) { return d[0]-d[2]; })
.attr("y", function (d) { return d[1]-d[3]; })
.attr("width", function (d) { return d[2]*2; })
.attr("height", function (d) { return d[3]*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[3] >= y0) && (p[1]-p[3] < y3);
}
return x1-max_w >= x3 || y1-max_h >= y3 || x2+max_w < x0 || y2+max_h < y0;
});
}
</script>
@nullstd
Copy link

nullstd commented Jan 25, 2019

This is awesome for Hit-Testing! Thanks!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment