Public
Edited
Aug 2, 2024
2 stars
Insert cell
Insert cell
{
let qtree = new Quadtree({ x0: 0, x1: width, y0: 0, y1: height });
for (let point of points) qtree.insert(point);

let svg = d3.create("svg").attr("viewBox", [0, 0, width, height]);
let x = d3.scaleLinear().domain([qtree.x0, qtree.x1]).range([0, width]);
let y = d3.scaleLinear().domain([qtree.y1, qtree.y0]).range([height, 0]);

svg
.selectAll(".node")
.data(points)
.enter()
.append("circle")
.attr("cx", (d) => x(d[0]))
.attr("cy", (d) => y(d[1]))
.attr("r", 2)
.attr("stroke", "orange")
.attr("fill", "orange");

svg
.selectAll(".boundary")
.data(Array.from(qtree.visit()))
.join("rect")
.attr("x", (d) => x(d.x0))
.attr("y", (d) => y(d.y0))
.attr("width", (d) => x(d.x1 - d.x0))
.attr("height", (d) => y(d.y1 - d.y0))
.attr("fill", "none")
.attr("stroke", "black");

return svg.node();
}
Insert cell
class Quadtree {
constructor(region, opts = {}) {
this.x0 = region.x0;
this.x1 = region.x1;
this.y0 = region.y0;
this.y1 = region.y1;
this.capacity = opts.capacity ?? 4;

this.nodes = [];
}
contains([x, y]) {
return x > this.x0 && x < this.x1 && y > this.y0 && y < this.y1;
}
insert(node) {
if (!this.contains(node)) {
return false;
}
if (this.nodes.length < this.capacity) {
this.nodes.push(node);
return true;
}
if (!this.subtrees) {
this.subdivide();
}
return (
this.subtrees.ne.insert(node) ||
this.subtrees.nw.insert(node) ||
this.subtrees.se.insert(node) ||
this.subtrees.sw.insert(node)
);
}
subdivide() {
let { x0, x1, y0, y1, capacity } = this;
let xMid = x0 + (x1 - x0) / 2;
let yMid = y0 + (y1 - y0) / 2;
this.subtrees = {
ne: new Quadtree({ x0, x1: xMid, y0, y1: yMid }, { capacity }),
nw: new Quadtree({ x0: xMid, x1, y0, y1: yMid }, { capacity }),
se: new Quadtree({ x0, x1: xMid, y0: yMid, y1 }, { capacity }),
sw: new Quadtree({ x0: xMid, x1, y0: yMid, y1 }, { capacity })
};
}
*visit() {
yield this;
for (let tree of Object.values(this.subtrees ?? {})) {
for (let child of tree.visit()) {
yield child;
}
}
}
}
Insert cell
points = d3.ticks(0, width, 2000).map((x) => {
let amplitude = 200;
let frequency = 40;
let y = height / 2 + amplitude * Math.sin(x / frequency);
return [x, y];
})
Insert cell
height = width
Insert cell
import("d3@7")
Insert cell

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.
Learn more