Skip to content

Instantly share code, notes, and snippets.

@mbostock
Last active March 13, 2018 17:09
Show Gist options
  • Save mbostock/9078690 to your computer and use it in GitHub Desktop.
Save mbostock/9078690 to your computer and use it in GitHub Desktop.
Quadtree Search
license: gpl-3.0

This demonstrates finding the closest point to the mouse by searching a quadtree. As you descend into the quadtree, you track the closest point yet found and avoid searching cells that cannot contain closer points. Importantly, you must descend preferentially into closer cells so as to restrict the search more quickly.

Patrick Surry implemented a similar solution months earlier!

<!DOCTYPE html>
<meta charset="utf-8">
<style>
.point {
fill: #000;
fill-opacity: 0.4;
}
.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").on("mousemove", mousemoved),
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);
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);
function mousemoved() {
var m = d3.mouse(this), p = quadtree.find(m[0], m[1]);
point.classed("point--selected", function(d) { return d === p; });
}
// 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>
@cotarmanach
Copy link

  1. Trying to understand "mousemoved" and how points can become "scanned"
    point.each(function(d) { d.scanned = false; }); => so for each datum, scanned is false

How can point.classed("scanned", function(d) { return d.scanned; }); return something else than false.

I see orange points, so obviously I'm missing something. Thanks for your help.

  1. wondering whether x and y have not been mixed here
    .attr("width", function(d) { return d.y1 - d.y0; }) // and not x
    .attr("height", function(d) { return d.x1 - d.x0; }); // and not y

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