1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
|
'use strict';
class AABB {
constructor(x, y, width, height) {
this.x = x; this.y = y;
this.width = width; this.height = height;
}
contains(point) {
if (point.x >= this.x && point.y >= this.y
&& point.x < this.x + this.width
&& point.y < this.y + this.height)
return true;
return false;
}
intersects(aabb) {
const overlap = (ax, arange, bx, brange) => {
const range = ax < bx ? arange : brange;
if (Math.abs(bx - ax) < range)
return true;
return false;
};
if (overlap(this.x, this.width, aabb.x, aabb.width) &&
overlap(this.y, this.height, aabb.y, aabb.height))
return true;
return false;
}
}
/* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* QUADTREE
*
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*/
class QTNodeType {
constructor(name) { this.name = name; }
toString() { return `QTNode.${this.name}`; }
}
class QTNode {
static Empty = new QTNodeType('Empty');
static Leaf = new QTNodeType('Leaf');
static Branch = new QTNodeType('Branch');
constructor(x, y, width, height) {
this.aabb = new AABB(x, y, width, height);
this.type = QTNode.Empty;
}
insert(point) {
if (this.aabb.contains(point)) {
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 };
|
