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;
}
}
}
}