summaryrefslogtreecommitdiff
path: root/src/Geometry/Geometry.js
diff options
context:
space:
mode:
authorsanine <sanine.not@pm.me>2022-06-05 13:20:17 -0500
committersanine <sanine.not@pm.me>2022-06-05 13:20:17 -0500
commitb9d4c658d3561106a452d8014c4d021fe175b759 (patch)
tree59d8a7e58a6368880ff35687cb8464cb48a11fa7 /src/Geometry/Geometry.js
parent483468407d05f55e407e61879794898fc72bd4c9 (diff)
add QTNode.remove()
Diffstat (limited to 'src/Geometry/Geometry.js')
-rw-r--r--src/Geometry/Geometry.js35
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 --