diff options
Diffstat (limited to 'src/Geometry/Geometry.js')
| -rw-r--r-- | src/Geometry/Geometry.js | 35 |
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 -- |