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
97
98
99
100
101
102
|
#include <memory>
#include "QuadTreeCollisionChecker.h"
#include "Museum.h"
using namespace std;
QuadTreeCollisionChecker::QuadTreeCollisionChecker(Museum & museum) : CollisionChecker(museum) {
this->boundary = {
.x = 0.0,
.y = 0.0,
.width = static_cast<float>(museum.canvas.data.columns),
.height = static_cast<float>(museum.canvas.data.rows),
};
this->artists = museum.people.get_artists();
for (auto & _ : this->artists) this->artists_size++;
if (this->artists_size > this->capacity)
this->subdivide();
}
QuadTreeCollisionChecker::QuadTreeCollisionChecker(const QuadTreeCollisionChecker * parent, const Rectangle & boundary) : CollisionChecker(parent->museum) {
this->boundary = boundary;
this->artists = parent->artists;
this->artists_size = parent->artists_size;
this->cull();
if (this->artists_size > this->capacity)
this->subdivide();
}
void QuadTreeCollisionChecker::subdivide() {
float half_width = this->boundary.width / 2;
float half_height = this->boundary.height / 2;
// squares smaller than artists will subdivide infinitely
if (half_width <= 0.5) return;
if (half_height <= 0.5) return;
this->subtree[0] = unique_ptr<QuadTreeCollisionChecker>(new QuadTreeCollisionChecker(this, {
.x = this->boundary.x,
.y = this->boundary.y,
.width = half_width,
.height = half_height,
}));
this->subtree[1] = unique_ptr<QuadTreeCollisionChecker>(new QuadTreeCollisionChecker(this, {
.x = this->boundary.x + half_width,
.y = this->boundary.y,
.width = half_width,
.height = half_height,
}));
this->subtree[2] = unique_ptr<QuadTreeCollisionChecker>(new QuadTreeCollisionChecker(this, {
.x = this->boundary.x,
.y = this->boundary.y + half_height,
.width = half_width,
.height = half_height,
}));
this->subtree[3] = unique_ptr<QuadTreeCollisionChecker>(new QuadTreeCollisionChecker(this, {
.x = this->boundary.x + half_width,
.y = this->boundary.y + half_height,
.width = half_width,
.height = half_height,
}));
// now all artists are stored in subtrees, so they no longer have to be
// stored in this quad
this->artists.clear();
this->artists_size = 0;
}
void QuadTreeCollisionChecker::cull() {
// remove artists that are *completely* outside the boundary
this->artists_size -= this->artists.remove_if([this](const Artist * artist) -> bool {
if (artist->data.x + 0.5 < this->boundary.x) return true;
if (artist->data.y + 0.5 < this->boundary.y) return true;
if (artist->data.x > this->boundary.x + this->boundary.width) return true;
if (artist->data.y > this->boundary.y + this->boundary.height) return true;
return false;
});
}
void QuadTreeCollisionChecker::check() {
if (this->artists_size > 0) {
auto begin = this->artists.begin();
auto end = this->artists.end();
for (auto it1 = begin; it1 != end; ++it1) {
auto it2 = it1;
++it2;
for (; it2 != end; ++it2) {
this->compare(**it1, **it2);
}
}
}
for (size_t i = 0; i < 4; i++) {
if (this->subtree[i] == nullptr) continue;
this->subtree[i]->check();
}
}
|