improve comments in Geometry.js

1 files changed, 76 insertions, 1 deletions

diff --git a/modules/Geometry.js b/modules/Geometry.js
index 48e682a..628512b 100644
--- a/modules/Geometry.js
+++ b/modules/Geometry.js
@@ -1,11 +1,20 @@
 'use strict';
 
+/* 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
@@ -14,6 +23,7 @@ class AABB {
 		return false;
 	}
 
+	/* check if two AABBs overlap */
 	intersects(aabb) {
 		const overlap = (ax, arange, bx, brange) => {
 			const range = ax < bx ? arange : brange;
@@ -37,12 +47,20 @@ class AABB {
  * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  */
 
+/* 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');
@@ -50,26 +68,45 @@ class QTNode {
 
 	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 {
-				// Branch
+				/* 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;
@@ -77,13 +114,21 @@ class QTNode {
 				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),
@@ -92,11 +137,17 @@ class QTNode {
 		];
 	}
 
+	/* 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),
@@ -107,36 +158,58 @@ class QTNode {
 }
 
 
+/* 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;
@@ -147,6 +220,8 @@ class QuadTree {
 				min_dist = d;
 			}
 		}
+
+		/* done! */
 		return closest;
 	}
 }