diff options
Diffstat (limited to 'modules/Geometry.js')
| -rw-r--r-- | modules/Geometry.js | 229 |
1 files changed, 0 insertions, 229 deletions
diff --git a/modules/Geometry.js b/modules/Geometry.js deleted file mode 100644 index 628512b..0000000 --- a/modules/Geometry.js +++ /dev/null @@ -1,229 +0,0 @@ -'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 - && 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 { AABB, QTNode, QuadTree }; |