diff options
Diffstat (limited to 'modules/Geometry.js')
| -rw-r--r-- | modules/Geometry.js | 36 |
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 }; |