1 files changed, 0 insertions, 233 deletions
diff --git a/src/modules/Geometry.js b/src/modules/Geometry.js
deleted file mode 100644
index 43f277f..0000000
--- a/src/modules/Geometry.js
+++ /dev/null
@@ -1,233 +0,0 @@
-'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 };