summaryrefslogtreecommitdiff
path: root/src/Geometry
diff options
context:
space:
mode:
Diffstat (limited to 'src/Geometry')
-rw-r--r--src/Geometry/Geometry.js233
-rw-r--r--src/Geometry/Geometry.test.js259
2 files changed, 492 insertions, 0 deletions
diff --git a/src/Geometry/Geometry.js b/src/Geometry/Geometry.js
new file mode 100644
index 0000000..43f277f
--- /dev/null
+++ b/src/Geometry/Geometry.js
@@ -0,0 +1,233 @@
+'use strict';
+
+function dist(a, b) {
+ return Math.sqrt((a.x - b.x)**2 + (a.y - b.y)**2);
+}
+
+/* AABB - axis-aligned bounding box */
+class AABB {
+ /* create a new AABB */
+ constructor(x, y, width, height) {
+ this.x = x; this.y = y;
+ this.width = width; this.height = height;
+ }
+
+ /* check if a point is inside the box
+ *
+ * a "point" is any object with an x- and y-coordinate.
+ * any other data in the object is ignored.
+ *
+ * returns true if the point is inside, and false otherwise.
+ */
+ contains(point) {
+ if (point.x >= this.x && point.y >= this.y
+ && point.x < this.x + this.width
+ && point.y < this.y + this.height)
+ return true;
+ return false;
+ }
+
+ /* check if two AABBs overlap */
+ intersects(aabb) {
+ const overlap = (ax, arange, bx, brange) => {
+ const range = ax < bx ? arange : brange;
+ if (Math.abs(bx - ax) < range)
+ return true;
+ return false;
+ };
+
+ if (overlap(this.x, this.width, aabb.x, aabb.width) &&
+ overlap(this.y, this.height, aabb.y, aabb.height))
+ return true;
+ return false;
+ }
+}
+
+
+/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ *
+ * QUADTREE
+ *
+ * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ */
+
+/* lil enum class for QTNode types */
+class QTNodeType {
+ constructor(name) { this.name = name; }
+ toString() { return `QTNode.${this.name}`; }
+}
+
+
+/* nodes in a quadtree
+ *
+ * they can be either "Empty" (no point),
+ * "Leaf" (they contain a point and no sub-nodes),
+ * or "Branch" (they contain no point and have sub-nodes).
+ * There are no QTNodes with children and point data.
+ */
+class QTNode {
+ static Empty = new QTNodeType('Empty');
+ static Leaf = new QTNodeType('Leaf');
+ static Branch = new QTNodeType('Branch');
+
+ constructor(x, y, width, height) {
+ this.aabb = new AABB(x, y, width, height);
+ /* all QTNodes start empty */
+ this.type = QTNode.Empty;
+ }
+
+ /* insert a point into the tree, starting with this node
+ *
+ * as above, points are just objects with 'x' and 'y' values.
+ * other data in the point is not examined and is incorporated into the
+ * tree.
+ *
+ * this function returns false if the point was not contained in the bounding box,
+ * and true otherwise. inserting a point may cause the node's type to change
+ * (e.g. a Leaf node would become a Branch node and its point data would be
+ * moved lower in the tree).
+ */
+ insert(point) {
+ if (this.aabb.contains(point)) {
+ if (this.type == QTNode.Empty) {
+ /* empty nodes are easy -- just switch to Leaf and add the point */
+ this.type = QTNode.Leaf;
+ this.point = point;
+ return true;
+ }
+ else if (this.type == QTNode.Leaf) {
+ /* Leaf must become a Branch */
+ this.type = QTNode.Branch;
+ this.subdivide();
+
+ /* move current point into a child */
+ let result = this.insert(this.point);
+ if (!result) return false;
+ this.point = undefined;
+
+ /* add new point */
+ return this.insert(point);
+ }
+ else {
+ /* This is a Branch, and we should insert into a child node */
+ /* just try them all until we find one where the point can go */
+ if (this.subnode[0].insert(point)) return true;
+ if (this.subnode[1].insert(point)) return true;
+ if (this.subnode[2].insert(point)) return true;
+ if (this.subnode[3].insert(point)) return true;
+ return false; // something strange has happened!!
+ }
+ }
+ /* point not in this node, return false */
+ return false;
+ }
+
+ /* subdivide the node into four child nodes
+ *
+ * under normal circumstances, the user should not call this function --
+ * it's just meant to be used during insertion.
+ */
+ subdivide() {
+ /* some useful constants */
+ const x = this.aabb.x; const y = this.aabb.y;
+ const w = this.aabb.width/2; const h = this.aabb.height/2;
+
+ /* generate sub-nodes */
+ this.subnode = [
+ new QTNode(x, y, w, h),
+ new QTNode(x+w, y, w, h),
+ new QTNode(x, y+h, w, h),
+ new QTNode(x+w, y+h, w, h),
+ ];
+ }
+
+ /* query the tree for all points contained within a region recursively
+ *
+ * returns an array containing any points in the tree beneath this node
+ * that are inside the supplied AABB.
+ */
+ getPointsInRegion(aabb) {
+ if (this.type == QTNode.Empty) return [];
+ if (!this.aabb.intersects(aabb)) return [];
+ if (this.type == QTNode.Leaf) return [this.point];
+
+ /* Branch - recusively query children */
+ return [
+ ...this.subnode[0].getPointsInRegion(aabb),
+ ...this.subnode[1].getPointsInRegion(aabb),
+ ...this.subnode[2].getPointsInRegion(aabb),
+ ...this.subnode[3].getPointsInRegion(aabb),
+ ];
+ }
+}
+
+
+/* full-blown quadtree! */
+class QuadTree {
+ /* create a new quadtree */
+ constructor(width, height) {
+ this.root = new QTNode(0, 0, width, height);
+ }
+
+ /* insert a point into the tree */
+ insert(point) {
+ return this.root.insert(point);
+ }
+
+ /* get the closest tree point to the given point */
+ closest(point) {
+ /* the algorithm goes like this:
+ * 1. find the smallest node containing the point
+ * 2. the closest point is within a box at most 4x the
+ * size of that lowest node, so query all points within
+ * such a region.
+ * 3. brute-force within the list of points.
+ */
+
+ /* recursively find the node containing a point */
+ const getLeaf = (point, node) => {
+ /* is point in bounding box? */
+ if (!node.aabb.contains(point)) return null;
+ /* is this a Leaf or Empty node? */
+ if (node.type == QTNode.Empty ||
+ node.type == QTNode.Leaf) return node;
+
+ /* this is a branch node, so recurse */
+ for (let subnode of node.subnode) {
+ const leaf = getLeaf(point, subnode);
+ if (leaf !== null) return leaf;
+ }
+
+ /* should never get here */
+ return null;
+ }
+
+ /* find the node, starting at the tree root */
+ const leaf = getLeaf(point, this.root);
+ if (leaf === null) return leaf;
+
+ /* construct the 4x AABB, centered on the query point */
+ const dim = 2*Math.max(leaf.aabb.width, leaf.aabb.height);
+ const region = new AABB(point.x - dim, point.y - dim, 2*dim, 2*dim);
+
+ /* get all points */
+ const points = this.root.getPointsInRegion(region);
+
+ /* brute force search within the small list */
+ let closest = null;
+ let min_dist = 100 * this.root.aabb.width * this.root.aabb.height;
+ const dist = (a, b) => (a.x - b.x)**2 + (a.y - b.y)**2;
+ for (let pt of points) {
+ const d = dist(point, pt);
+ if (d < min_dist) {
+ closest = pt;
+ min_dist = d;
+ }
+ }
+
+ /* done! */
+ return closest;
+ }
+}
+
+export { dist, AABB, QTNode, QuadTree };
diff --git a/src/Geometry/Geometry.test.js b/src/Geometry/Geometry.test.js
new file mode 100644
index 0000000..0b81438
--- /dev/null
+++ b/src/Geometry/Geometry.test.js
@@ -0,0 +1,259 @@
+import { test, assert } from '../test-assert.js';
+import { AABB, QTNode, QuadTree } from './Geometry.js';
+
+const RUN_BENCHMARKS = false;
+
+
+test('AABB correctly contains/excludes points', () => {
+ const box = new AABB(0, 0, 1, 1);
+
+ // interior
+ assert.ok(box.contains({ x: 0.5, y: 0.5 }));
+
+ // upper left
+ assert.ok(!box.contains({ x: -1, y: -1 }));
+
+ // above
+ assert.ok(!box.contains({ x: 0.5, y: -1}));
+
+ // upper right
+ assert.ok(!box.contains({ x: 2, y: -1 }));
+
+ // left
+ assert.ok(!box.contains({ x: -1, y: 0.5 }));
+
+ // right
+ assert.ok(!box.contains({ x: 2, y: 0.5}));
+
+ // lower left
+ assert.ok(!box.contains({ x: -1, y: 2 }));
+
+ // below
+ assert.ok(!box.contains({ x: 0.5, y: 2}));
+
+ // lower right
+ assert.ok(!box.contains({ x: 2, y: 2 }));
+});
+
+
+test('AABB correctly intersects other AABBs', () => {
+ const box = new AABB(1, 1, 4, 4);
+
+ // interior
+ assert.ok(box.intersects(new AABB(2, 2, 2, 2,)));
+
+ // upper left
+ assert.ok(box.intersects(new AABB(0, 0, 4, 4)));
+ assert.ok(!box.intersects(new AABB(0, 0, 0.5, 0.5)));
+
+ // above
+ assert.ok(box.intersects(new AABB(2, 0, 2, 2)));
+ assert.ok(!box.intersects(new AABB(2, 0, 2, 0.5)));
+
+ // upper right
+ assert.ok(box.intersects(new AABB(2, 0, 4, 2)));
+ assert.ok(!box.intersects(new AABB(6, 0, 4, 2)));
+
+ // left
+ assert.ok(box.intersects(new AABB(0, 2, 2, 2)));
+ assert.ok(!box.intersects(new AABB(0, 2, 0.5, 2)));
+
+ // right
+ assert.ok(box.intersects(new AABB(4, 2, 2, 2)));
+ assert.ok(!box.intersects(new AABB(6, 2, 2, 2)));
+
+ // lower left
+ assert.ok(box.intersects(new AABB(0, 4, 4, 4)));
+ assert.ok(!box.intersects(new AABB(0, 6, 0.5, 0.5)));
+
+ // below
+ assert.ok(box.intersects(new AABB(2, 4, 2, 2)));
+ assert.ok(!box.intersects(new AABB(2, 6, 2, 0.5)));
+
+ // lower right
+ assert.ok(box.intersects(new AABB(2, 4, 4, 2)));
+ assert.ok(!box.intersects(new AABB(6, 6, 4, 2)));
+});
+
+
+test('AABB correctly handles points at the edges', () => {
+ const box = new AABB(0, 0, 1, 1);
+
+ assert.ok(box.contains({ x: 0, y: 0 }));
+ assert.ok(box.contains({ x: 0.5, y: 0 }));
+ assert.ok(box.contains({ x: 0, y: 0.5 }));
+
+ // bad corners
+ assert.ok(!box.contains({ x: 1, y: 0 }));
+ assert.ok(!box.contains({ x: 0, y: 1 }));
+ assert.ok(!box.contains({ x: 1, y: 1 }));
+
+ // bad edges
+ assert.ok(!box.contains({ x: 1, y: 0.5 }));
+ assert.ok(!box.contains({ x: 0.5, y: 1 }));
+});
+
+
+test('QTNode correctly inserts points', () => {
+ const node = new QTNode(0, 0, 1, 1);
+ assert.equal(node.type.toString(), 'QTNode.Empty');
+
+ let result = node.insert({ x: -1, y: -1 }); // out of range, should not insert
+ assert.ok(!result);
+ assert.equal(node.type.toString(), 'QTNode.Empty');
+
+ result = node.insert({ x: 0.5, y: 0.5 }); // in range
+ assert.ok(result);
+ assert.equal(node.type.toString(), 'QTNode.Leaf');
+ assert.deepEqual(node.point, { x: 0.5, y: 0.5 });
+});
+
+
+test('QTNode correctly subdivides', () => {
+ const node = new QTNode(0, 0, 2, 2);
+ assert.ok(!node.subnode);
+ node.subdivide();
+ assert.equal(node.subnode.length, 4);
+
+ assert.deepEqual(node.subnode[0], new QTNode(0, 0, 1, 1));
+ assert.deepEqual(node.subnode[1], new QTNode(1, 0, 1, 1));
+ assert.deepEqual(node.subnode[2], new QTNode(0, 1, 1, 1));
+ assert.deepEqual(node.subnode[3], new QTNode(1, 1, 1, 1));
+});
+
+
+test('QTNode correctly inserts multiple points', () => {
+ const node = new QTNode(0, 0, 2, 2);
+
+ const p0 = { x: 1, y: 1 };
+ const p1 = { x: 0.5, y: 0.5 };
+ const oob = { x: 10, y: 15 };
+
+ assert.ok(node.insert(p0));
+ assert.ok(node.insert(p1));
+ assert.ok(!node.insert(oob));
+
+ assert.equal(node.type.toString(), 'QTNode.Branch');
+
+ assert.equal(node.subnode[0].type.toString(), 'QTNode.Leaf');
+ assert.deepEqual(node.subnode[0].point, p1);
+
+ assert.equal(node.subnode[1].type.toString(), 'QTNode.Empty');
+ assert.equal(node.subnode[2].type.toString(), 'QTNode.Empty');
+
+ assert.equal(node.subnode[3].type.toString(), 'QTNode.Leaf');
+assert.deepEqual(node.subnode[3].point, p0);
+});
+
+
+const randomPoint = () => ({ x: Math.random(), y: Math.random() });
+
+
+test('QTNode correctly returns points in region', () => {
+ const node = new QTNode(0, 0, 1, 1);
+ let points = [];
+ for (let i=0; i<100; i++) {
+ const pt = randomPoint();
+ node.insert(pt);
+ points.push(pt);
+ }
+
+ const pointsInRegion = aabb => {
+ let pts = [];
+ for (let pt of points) {
+ if (aabb.contains(pt)) pts.push(pt);
+ }
+ return pts;
+ };
+
+ const region = new AABB(0.25, 0.25, 0.5, 0.5);
+ let bf_points = pointsInRegion(region);
+ let qt_points = node.getPointsInRegion(region);
+ const compare = (a, b) => {
+ if (a.x == b.x)
+ return b.y - a.y;
+ return b.x - a.x;
+ };
+ bf_points.sort(compare);
+ qt_points.sort(compare);
+ assert.deepEqual(bf_points, qt_points);});
+
+
+test('QuadTree correctly finds closest point for 10,000 random points', () => {
+ const tree = new QuadTree(1, 1);
+
+ let points = [];
+ for (let i=0; i<10000; i++) {
+ const pt = randomPoint();
+ tree.insert(pt);
+ points.push(pt);
+ }
+
+ const distance = (a, b) => Math.sqrt((a.x - b.x)**2 + (a.y - b.y)**2);
+ const bf_closest = a => {
+ let closest = null;
+ let min_dist = 1000;
+ for (let b of points) {
+ let d = distance(a, b);
+ if (d < min_dist) {
+ min_dist = d;
+ closest = b;
+ }
+ }
+ return closest;
+ }
+
+ for (let i=0; i<10000; i++) {
+ const pt = randomPoint();
+ assert.deepEqual(bf_closest(pt), tree.closest(pt));
+ }
+});
+
+
+function benchmark(desc, f, iterations) {
+ process.stdout.write(`${desc}: `);
+ const start = process.uptime();
+ for (let i=0; i<iterations; i++) f();
+ const elapsed = process.uptime() - start;
+ console.log(`${elapsed} seconds`);
+}
+
+const closest_benchmark = () => {
+ const n_points = 1e5;
+ const iterations = 1e4;
+ console.log(`> benchmark get closest of ${n_points} random points ${iterations} times`);
+
+ const tree = new QuadTree(1, 1);
+ let points = [];
+ for (let i=0; i<n_points; i++) {
+ const pt = randomPoint();
+ tree.insert(pt);
+ points.push(pt);
+ }
+
+ const distance = (a, b) => Math.sqrt((a.x - b.x)**2 + (a.y - b.y)**2);
+ const bf_closest = a => {
+ let closest = null;
+ let min_dist = 1000;
+ for (let b of points) {
+ let d = distance(a, b);
+ if (d < min_dist) {
+ min_dist = d;
+ closest = b;
+ }
+ }
+ return closest;
+ }
+
+ benchmark('\tbrute force', () => {
+ const pt = randomPoint();
+ bf_closest(pt);
+ }, iterations);
+
+ benchmark('\tquadtree', () => {
+ const pt = randomPoint();
+ tree.closest(pt);
+ }, iterations);
+}
+if (RUN_BENCHMARKS)
+ closest_benchmark();
generated by cgit v1.2.1 (git 2.18.0) at 2024-11-15 05:52:01 +0000