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