-
Notifications
You must be signed in to change notification settings - Fork 0
/
quadtree.js
96 lines (89 loc) · 3.13 KB
/
quadtree.js
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
import { drawRect } from "./utils.js"
class Rectangle{
constructor(x,y,width,height){
this.x = x
this.y = y
this.width = width
this.height = height
}
contains(object) {
return (object.pos.x >= this.x - this.width &&
object.pos.x <= this.x + this.width &&
object.pos.y >= this.y - this.height &&
object.pos.y <= this.y + this.height);
}
intersect(region) {
return !(region.x - region.width > this.x + this.width ||
region.x + region.width < this.x - this.width ||
region.y - region.height > this.y + this.height ||
region.y + region.height < this.y - this.height);
}
draw(){
drawRect(this.x,this.y, this.width, this.height);
}
}
// let globalcheck = 0;
class QuadTree{
constructor(x,y,width,height){
this.objects = [];
this.boundary = new Rectangle(x,y,width,height)
this.capacity = 1;
this.isDivided = false;
// this.check = 0;
}
insert(object) {
if(!this.boundary.contains(object))
return false;
if(this.objects.length < this.capacity){
this.objects.push(object);
return true;
}else{
if(!this.isDivided){
this.isDivided = true;
this.northwest = new QuadTree(this.boundary.x,this.boundary.y,this.boundary.width/2,this.boundary.height/2)
this.northeast = new QuadTree(this.boundary.x+this.boundary.width/2,this.boundary.y,this.boundary.width/2,this.boundary.height/2)
this.southwest = new QuadTree(this.boundary.x,this.boundary.y+this.boundary.height/2,this.boundary.width/2,this.boundary.height/2)
this.southeast = new QuadTree(this.boundary.x+this.boundary.width/2,this.boundary.y+this.boundary.height/2,this.boundary.width/2,this.boundary.height/2)
}
if(this.northwest.insert(object))
return true;
if(this.northeast.insert(object))
return true;
if(this.southwest.insert(object))
return true;
if(this.southeast.insert(object))
return true;
}
}
query(region, found){
if(!found){
// globalcheck = 0;
found = [];
}
if(!this.boundary.intersect(region))
return;
for(let p of this.objects){
// globalcheck++;
if(region.contains(p))
found.push(p)
}
if(this.isDivided){
this.northwest.query(region, found)
this.northeast.query(region, found)
this.southwest.query(region, found)
this.southeast.query(region, found)
}
// this.check = globalcheck;
return found;
}
show(){
this.boundary.draw();
if(this.isDivided){
this.northwest.show()
this.northeast.show()
this.southwest.show()
this.southeast.show()
}
}
}
export { QuadTree, Rectangle }