Quad Tree
Showcases quad tree. Use CTRL+Click to add a rect, ALT+Click to remove all intersecting.
Code
ts
import {
arcAtDegrees,
BatchEntry,
buildRectPoints,
buildSquarePoints,
CanvasApp,
Circle,
Color,
LineBatcher,
LineLike,
LineObject,
linePath,
QuadTree,
Rect,
TimeSampler,
vec,
Vec2,
WGLDriver,
WGLLineBatchRenderer,
} from '../../src';
const TEMP_VEC = Vec2.zero();
const BACKGROUND_COLOR = Color.fromHexString('#ffffffff');
const RECT_COLOR = Color.fromHexString('#43b427ff');
const RECT_COLOR_INTERSECTED = Color.fromHexString('#ff2478ff');
const QUAD_COLOR = Color.fromHexString('#f78c28ff');
interface Entity {
line: LineObject;
entry?: BatchEntry<LineLike>;
}
export class QuadTreeApp extends CanvasApp<WGLDriver> {
private readonly lineRenderer = new WGLLineBatchRenderer(this.driver);
private readonly lineBatcher = new LineBatcher(this.changeTracker);
private readonly globalLineBatcher = new LineBatcher(this.changeTracker);
private quadTreeEntries = new Map<Rect, Entity>();
private quadEntities: Entity[] = [];
private quadTree: QuadTree<Rect>;
private cursor!: Entity;
private viewportMouse = vec();
private sceneMouse = new Circle(0, 0, 24);
private intersectionTime = new TimeSampler('intersections');
private readonly bounds = new Rect(-300, -150, 600, 300);
constructor(canvas: HTMLCanvasElement, driver: WGLDriver) {
super(canvas, driver);
this.quadTree = new QuadTree<Rect>(this.bounds.clone(), 4, 4);
canvas.addEventListener('mousemove', e => {
this.updateMouse(e.offsetX, e.offsetY);
});
canvas.addEventListener('click', e => {
if (e.ctrlKey && !e.altKey) {
const pos = this.driver.projections.projectDOMPointToScene(
new Vec2(e.offsetX, e.offsetY),
this.camera,
);
this.addRect(pos.x, pos.y);
}
const del = !e.ctrlKey && e.altKey;
const delSpatial = e.ctrlKey && e.altKey;
if (del || delSpatial) {
this.updateMouse(e.offsetX, e.offsetY);
const intersections = this.intersections(this.sceneMouse);
for (const intersection of intersections.values) {
if (del) this.quadTree.delete(intersection, true);
else if (delSpatial)
this.quadTree.deleteSpatial(intersection, true);
const entity = this.quadTreeEntries.get(intersection);
if (entity) {
this.quadTreeEntries.delete(intersection);
this.lineBatcher.delete(entity.entry!);
}
}
}
});
}
override async initialize() {
await super.initialize();
this.lineBatcher.setMaximums(64_000);
this.globalLineBatcher.setMaximums(64_000);
this.cursor = {
line: new LineObject({
points: linePath(arcAtDegrees(0, 0, 24)).build(),
style: { color: Color.BLACK, thickness: 1 },
}),
};
this.cursor.entry = this.globalLineBatcher.add(this.cursor.line);
}
protected override tick(elapsed: number): void {
super.tick(elapsed);
this.quadEntities.forEach(o => this.lineBatcher.delete(o.entry!));
this.quadEntities.length = 0;
for (const quad of this.quadTree.quads()) {
const pos = TEMP_VEC.copyFrom(quad.bounds);
const entity = {
line: new LineObject({
points: buildRectPoints(
pos.x,
pos.y,
quad.bounds.width,
quad.bounds.height,
),
closed: true,
style: {
color: QUAD_COLOR,
thickness: 2,
},
}),
} as Entity;
this.quadEntities.push(entity);
entity.entry = this.lineBatcher.add(entity.line);
this.transforms.change(entity.line);
}
this.quadTreeEntries.forEach(e => {
e.line.style.color = RECT_COLOR;
this.lineBatcher.change(e.entry!);
});
this.intersectionTime.start();
const intersects = this.intersections(this.sceneMouse);
this.intersectionTime.finish();
intersects.values.forEach(r => {
const entity = this.quadTreeEntries.get(r)!;
entity.line.style.color = RECT_COLOR_INTERSECTED;
this.lineBatcher.change(entity.entry!);
});
this.cursor.line.transform.position.copyFrom(this.viewportMouse);
this.transforms.change(this.cursor.line);
this.globalLineBatcher.change(this.cursor.entry!);
}
override render(): void {
super.render();
this.driver.useRenderTarget('canvas');
this.driver.clear(BACKGROUND_COLOR);
this.lineRenderer.render(this.lineBatcher.finalize(), this.camera);
this.lineRenderer.render(this.globalLineBatcher.finalize());
}
private updateMouse(x: number, y: number) {
const point = this.driver.projections.projectDOMPointToViewport(
vec(x, y),
);
this.viewportMouse.copyFrom(point);
this.driver.projections.projectViewportPointToScene(point, this.camera);
this.sceneMouse.copyCenterFrom(point);
}
private intersections(circle: Circle) {
return this.quadTree.filter(
e => circle.intersectsRect(e),
q => circle.intersectsRect(q),
);
}
addRects(count: number): void {
for (let i = 0; i < count; i++) {
const x =
Math.random() * this.quadTree.bounds.width +
this.quadTree.bounds.x;
const y =
Math.random() * this.quadTree.bounds.height +
this.quadTree.bounds.y;
this.addRect(x, y);
}
}
addRect(x: number, y: number) {
const d = Math.random() * 12 + 4;
const pos = new Vec2(Math.floor(x - d), Math.floor(y - d));
const rect = Rect.fromPoint(pos, 2 * d, 2 * d);
this.quadTree.add(rect);
const entity = {
line: new LineObject({
points: buildSquarePoints(0, 0, 2 * d),
closed: true,
position: pos,
style: { thickness: 2, color: RECT_COLOR },
}),
} as Entity;
this.quadTreeEntries.set(rect, entity);
this.transforms.change(entity.line);
entity.entry = this.lineBatcher.add(entity.line);
}
}