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
|
#include <memory>
#include "QuadTree.h"
#include "Museum.h"
using namespace std;
QuadTree::QuadTree(Museum & 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();
}
QuadTree::QuadTree(const QuadTree * parent, const Rectangle & boundary) {
this->boundary = boundary;
this->artists = parent->artists;
this->artists_size = parent->artists_size;
this->cull();
if (this->artists_size > this->capacity)
this->subdivide();
}
void QuadTree::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<QuadTree>(new QuadTree(this, {
.x = this->boundary.x,
.y = this->boundary.y,
.width = half_width,
.height = half_height,
}));
this->subtree[1] = unique_ptr<QuadTree>(new QuadTree(this, {
.x = this->boundary.x + half_width,
.y = this->boundary.y,
.width = half_width,
.height = half_height,
}));
this->subtree[2] = unique_ptr<QuadTree>(new QuadTree(this, {
.x = this->boundary.x,
.y = this->boundary.y + half_height,
.width = half_width,
.height = half_height,
}));
this->subtree[3] = unique_ptr<QuadTree>(new QuadTree(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();
}
void QuadTree::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;
});
}
|