// used for the demo, see below for an actual function you can reuse
function findInCircleMark(quadtree, x, y, radius) {
const result = [];
// this function will be called for all accepted nodes
function accept(d) {
result.push(d);
}
// Visit the quadtree from the top, recursively
quadtree.visit(function(node, x1, y1, x2, y2) {
if (node.length) {
// this node is not a leaf: mark that we visited it
node.visited = true;
// if ⟨x,y⟩ is outside the quad + a margin of radius, we know that there is no point
// in that quad’s hierarchy that is at a distance < radius: eliminate the quad by returning truthy
return (
x1 >= x + radius ||
y1 >= y + radius ||
x2 < x - radius ||
y2 < y - radius
);
}
// this is a leaf node: it contains 1 point in node.data
do {
// mark that we visited it
const d = node.data;
d.visited = true;
// measure its euclidian distance to <x,y> and accept it if < radius
if (Math.hypot(d[0] - x, d[1] - y) < radius) accept(d);
} while ((node = node.next));
// the do...while chained call is used to test coincident points—which would belong
// to the same leaf node; in our case with random points, however, this test is useless
// as the probability of coincident points is 0.
});
return result;
}
function findInCircle(quadtree, x, y, radius, filter) {
const result = [],
radius2 = radius * radius,
accept = filter
? d => filter(d) && result.push(d)
: d => result.push(d);
quadtree.visit(function(node, x1, y1, x2, y2) {
if (node.length) {
return x1 >= x + radius || y1 >= y + radius || x2 < x - radius || y2 < y - radius;
}
const dx = +quadtree._x.call(null, node.data) - x,
dy = +quadtree._y.call(null, node.data) - y;
if (dx * dx + dy * dy < radius2) {
do { accept(node.data); } while (node = node.next);
}
});
return result;
}
quadtree = d3
.quadtree()
.extent([[-1, -1], [width + 1, height + 1]])
.addAll(data)
function chart() {
const svg = d3
.create("svg")
.attr("viewBox", [0, 0, width, height])
.style("cursor", "crosshair"),
quad = svg
.selectAll(".node")
.data(materialize(quadtree))
.enter()
.append("rect")
.attr("class", "node")
.attr("x", d => d.x0)
.attr("y", d => d.y0)
.attr("width", d => d.y1 - d.y0)
.attr("height", d => d.x1 - d.x0),
circle = svg
.selectAll(".radius")
.data([radius])
.join("circle")
.attr("r", d => d)
.attr("class", "radius")
.attr("stroke", "orange"),
point = svg
.selectAll("circle")
.data(data)
.enter()
.append("circle")
.attr("cx", d => d[0])
.attr("cy", d => d[1])
.attr("r", 2);
svg.on("mousemove click", move);
move();
return svg.node();
function move(event) {
const [x, y] = this ? d3.pointer(event, this) : [200, 200];
// reset the visited property
quad.each(q => (q.node.visited = false));
point.each(d => (d.visited = false));
// search (will set visited on the traversed nodes)
const one = quadtree.find(x, y, radius),
all = findInCircleMark(quadtree, x, y, radius);
// add the relevant classes on the svg marks
quad.classed("visited", d => d.node.visited);
point
.classed("visited", d => d.visited)
.classed("all", d => all.includes(d))
.classed("find", d => d === one);
// move the radius circle
circle.attr("cx", x).attr("cy", y);
}
}
// Materialize the quadtree into an array of rectangles.
function materialize(quadtree) {
const rects = [];
quadtree.visit((node, x0, y0, x1, y1) => {
rects.push({ x0, y0, x1, y1, node });
});
return rects;
}
data = {
const randomx = d3.randomUniform(0, width),
randomy = d3.randomUniform(0, height);
return Array.from({ length: 2500 }, () => [randomx(), randomy()]);
}
html`
<style>
circle {
fill: #777;
fill-opacity: 0.1;
}
circle.visited {
fill-opacity: 1;
stroke-width: 2px;
}
circle.all {
fill: orange;
fill-opacity: 1;
stroke: orange;
stroke-width: 4px;
}
circle.find {
fill: green;
fill-opacity: 1;
stroke: red;
stroke-width: 5px;
}
rect {
fill: none;
stroke: none;
shape-rendering: crispEdges;
}
rect.visited {
stroke: #888;
stroke-width: 1px;
}
circle.radius {
fill: none;
}
</style>`
height = 500
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
