1 files changed, 80 insertions, 0 deletions
diff --git a/QuadTree.cpp b/QuadTree.cpp
index 54cb0af..3850e2c 100644
--- a/QuadTree.cpp
+++ b/QuadTree.cpp
@@ -1,3 +1,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;
+	});
+}