From 2c9567e42d2e96de3479f95125f0fff04ff52c2d Mon Sep 17 00:00:00 2001
From: sanine <sanine.not@pm.me>
Date: Wed, 25 May 2022 14:17:04 -0500
Subject: begin refactor to use quadtree

---
 modules/Geometry.js | 66 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 66 insertions(+)
 create mode 100644 modules/Geometry.js

(limited to 'modules/Geometry.js')

diff --git a/modules/Geometry.js b/modules/Geometry.js
new file mode 100644
index 0000000..c34f4d2
--- /dev/null
+++ b/modules/Geometry.js
@@ -0,0 +1,66 @@
+'use strict';
+
+class AABB {
+	constructor(x, y, width, height) {
+		this.x = x; this.y = y;
+		this.width = width; this.height = height;
+	}
+
+	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;
+	}
+
+	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
+ *
+ * ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+ */
+
+class QTNodeType {
+	constructor(name) { this.name = name; }
+	toString() { return `QTNode.${this.name}`; }
+}
+
+
+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);
+		this.type = QTNode.Empty;
+	}
+
+	insert(point) {
+		if (this.aabb.contains(point)) {
+			this.type = QTNode.Leaf;
+			this.point = point;
+			return true;
+		}
+		return false;
+	}
+}
+
+export { AABB, QTNode };
-- 
cgit v1.2.1