Public
Edited
Oct 24, 2023
3 forks
47 stars
Insert cell
Insert cell
Insert cell
Insert cell
// 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;
}
Insert cell
Insert cell
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;
}
Insert cell
quadtree = d3
.quadtree()
.extent([[-1, -1], [width + 1, height + 1]])
.addAll(data)
Insert cell
Insert cell
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);
}
}
Insert cell
// 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;
}
Insert cell
data = {
const randomx = d3.randomUniform(0, width),
randomy = d3.randomUniform(0, height);
return Array.from({ length: 2500 }, () => [randomx(), randomy()]);
}
Insert cell
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>`
Insert cell
height = 500
Insert cell

One platform to build and deploy the best data apps

Experiment and prototype by building visualizations in live JavaScript notebooks. Collaborate with your team and decide which concepts to build out.
Use Observable Framework to build data apps locally. Use data loaders to build in any language or library, including Python, SQL, and R.
Seamlessly deploy to Observable. Test before you ship, use automatic deploy-on-commit, and ensure your projects are always up-to-date.
Learn more