summaryrefslogtreecommitdiff
path: root/src/Geometry/Geometry.js
blob: 43f277fd3e1bd81558fb744f5c15747acb242562 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
'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 };