// Geometry.ts
interface Point {
x: number;
y: number;
}
/**
* Box Representation, provides:
* left, right, top bottom
* width, height
* half width, half height
* center
*/
class Bounds {
w: number;
h: number;
hw: number;
hh: number;
c: Point;
constructor(
public l: number,
public r: number,
public t: number,
public b: number
) {
this.w = r - l;
this.h = t - b;
this.hw = this.w * 0.5;
this.hh = this.h * 0.5;
this.c = { x: this.l + this.w, y: this.b + this.h };
}
contains(p: Point) {
return p.x >= this.l && p.x < this.r && p.y < this.t && p.y >= this.b;
}
intersects(c: Bounds) {
return !(this.l > c.r || this.r < c.l || this.b > c.t || this.t < c.b);
}
}
//Quadtree.ts
class QuadTree {
points: Point[] = [];
children: QuadTree[] = [];
isLeafNode: boolean = true;
constructor(public bounds: Bounds, public maxPoints = 1) {}
addPoint(p: Point) {
// If the point isn't a member of our set
if (!this.bounds.contains(p)) return false;
// Are we a leaf node? If not, pass the point along
if (!this.isLeafNode) {
this.children.map(qt => qt.addPoint(p));
return true;
}
// Point is a member of our set
this.points.push(p);
// Do we have too many points?
if (this.points.length > this.maxPoints) {
// Split node and distribute points to children
this.split();
return true;
}
}
/**
* Splits quadtree node into 4 and disperses current points
*/
private split() {
const { l, r, t, b, hw, hh } = this.bounds;
const halfX = l + hw;
const halfY = b + hh;
// Create four sub cells
const ul = new QuadTree(new Bounds(l, r - hw, t, b + hh));
const ur = new QuadTree(new Bounds(l + hw, r, t, b + hh));
const bl = new QuadTree(new Bounds(l, r - hw, t - hh, b));
const br = new QuadTree(new Bounds(l + hw, r, t - hh, b));
// Distribute our points to the children
this.points.map(p => {
if (p.x > halfX) {
p.y > halfY ? ur.points.push(p) : br.points.push(p);
} else {
p.y > halfY ? ul.points.push(p) : bl.points.push(p);
}
});
// Store child nodes
this.children = [ul, ur, bl, br];
// Delete points
this.points = [];
// Turn into a normal node
this.isLeafNode = false;
}
getPoints(b: Bounds): Point[] {
// If we arn't a leaf node, recurse through tree concatenating any
// points we find then returning. Trimming nodes not in the region
if (!this.isLeafNode) {
const init: Point[] = [];
return this.children
.filter(c => c.bounds.intersects(b))
.reduce((points, node) => {
return points.concat(node.getPoints(b));
}, init);
} else {
return this.points.filter(p => b.contains(p));
}
}
}
// TEST BULLSHIT
// VVVVVVV
function test() {
let s = new Bounds(0, 200, 200, 0);
let c = new Bounds(39, 40, 80, 79);
const pointArray: Point[] = [];
const qt = new QuadTree(s, 1);
function randPoint(b: Bounds) {
return {
x: Math.random() * b.w + b.l,
y: Math.random() * b.h + b.b
};
}
for (let i = 0; i < 300000; i++) {
const newPoint = randPoint(s);
qt.addPoint(newPoint);
pointArray.push(newPoint);
}
const quadResults: number[] = [];
const arrayResults: number[] = [];
function runTest() {
const x = Math.random() * s.w + s.l;
const y = Math.random() * s.h + s.b;
const c = new Bounds(x - 1, x, y, y - 1);
quadResults.push(calcQuadAccess(qt, c));
arrayResults.push(calcArrayAccess(pointArray, c));
}
for (let i = 0; i < 500; i++) {
runTest();
}
console.log('quad', average(quadResults));
console.log('array', average(arrayResults));
}
function average(a: number[]): number {
const s = a.reduce((a, b) => a + b, 0);
return s / a.length;
}
function timeDiff(start: Date, end: Date): number {
return (
end.getSeconds() * 1000 +
end.getMilliseconds() -
start.getSeconds() * 1000 -
start.getMilliseconds()
);
}
function calcQuadAccess(qt: QuadTree, b: Bounds) {
const start = new Date();
const cBounds = qt.getPoints(b);
const end = new Date();
return timeDiff(start, end);
}
function calcArrayAccess(pointArray: Point[], b: Bounds) {
const startLinear = new Date();
const cPoints = [];
for (let i = 0; i < pointArray.length; i++) {
if (b.contains(pointArray[i])) cPoints.push(pointArray[i]);
}
const endLinear = new Date();
return timeDiff(startLinear, endLinear);
}
// 300,000 points, grabs a small random region 1000 times
// Averages access times for point set.
test();
