From ebf18fa330e5513d9f118b41bf63692aa9093462 Mon Sep 17 00:00:00 2001 From: sanine Date: Wed, 25 May 2022 14:48:59 -0500 Subject: add basic QTNode --- modules/Geometry.js | 36 +++++++++++++++++++++++++++++++++--- 1 file changed, 33 insertions(+), 3 deletions(-) (limited to 'modules/Geometry.js') 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 }; -- cgit v1.2.1