add QTNode.remove()

1 files changed, 35 insertions, 0 deletions

diff --git a/src/Geometry/Geometry.js b/src/Geometry/Geometry.js
index 43f277f..6c296ad 100644
--- a/src/Geometry/Geometry.js
+++ b/src/Geometry/Geometry.js
@@ -122,6 +122,41 @@ class QTNode {
 		return false;
 	}
 
+	/* remove a node from the tree */
+	remove(point) {
+		if (this.aabb.contains(point)) {
+			switch(this.type) {
+				case QTNode.Empty:
+					break;
+
+				case QTNode.Leaf:
+					if (this.point.x === point.x && this.point.y === point.y) {
+						this.point = undefined;
+						this.type = QTNode.Empty;
+					}
+					break;
+
+				case QTNode.Branch:
+					for (let subnode of this.subnode) subnode.remove(point);
+					let numBranches = 0;
+					let numLeaves = 0;
+					for (let subnode of this.subnode) {
+						if (subnode.type === QTNode.Leaf) numLeaves += 1;
+						if (subnode.type === QTNode.Branch) numBranches += 1;
+					}
+					if (numBranches == 0 && numLeaves == 1) {
+						/* contract to leaf node */
+						this.type = QTNode.Empty; // start as Empty so insertion works correctly
+						for (let subnode of this.subnode) {
+							if (subnode.type == QTNode.Leaf) this.insert(subnode.point);
+						}
+						this.subnode = undefined;
+					}
+					break;
+			}
+		}
+	}
+
 	/* subdivide the node into four child nodes
 	 *
 	 * under normal circumstances, the user should not call this function --