diff options
Diffstat (limited to 'modules')
| -rw-r--r-- | modules/Geometry.js | 77 |
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; } } |