add basic QTNode

1 files changed, 33 insertions, 3 deletions

diff --git a/modules/Geometry.js b/modules/Geometry.js
index c34f4d2..f32dc0e 100644
--- a/modules/Geometry.js
+++ b/modules/Geometry.js
@@ -55,12 +55,42 @@ class QTNode {
 
 	insert(point) {
 		if (this.aabb.contains(point)) {
-			this.type = QTNode.Leaf;
-			this.point = point;
-			return true;
+			if (this.type == QTNode.Empty) {
+				this.type = QTNode.Leaf;
+				this.point = point;
+				return true;
+			}
+			else if (this.type == QTNode.Leaf) {
+				this.type = QTNode.Branch;
+				this.subdivide();
+				let result = this.insert(this.point);
+				if (!result) return false;
+				this.point = undefined;
+				return this.insert(point);
+			}
+			else {
+				// Branch
+				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!!
+			}
 		}
 		return false;
 	}
+
+	subdivide() {
+		const x = this.aabb.x; const y = this.aabb.y;
+		const w = this.aabb.width/2; const h = this.aabb.height/2;
+
+		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),
+		];
+	}
 }
 
 export { AABB, QTNode };