I've written a simple Quad-tree in C++ for an SDL2 application I'm working on. It's quite simplistic, and seems to be doing its job. Its only designed to work with a collection of unmovable physical entities. I plan to expand upon it, but I'd just like to make sure I'm going in the right direction so far.
One thing I am aware of is it's perfectly possible for getCanidates() to populate a vector with multiple copies of a pointer to a potentially colliding item. Thus far this hasn't seemed to be an issue in the code that uses it. If it turns out to be so, I'll change the vector to a set.
Critique on code and functionality would be much appreciated! I've only recently started writing C++, and am using Bjarne Stroustrup's "The C++ Programming Language 4th Edition" as reference.
#pragma once
#include <vector>
#include <sdl.h>
#include "Camera.h" //just an abstraction for SDL2 rendering operations
#include <memory>
template<typename T>
class QuadTree
{
private:
static const int maxItems = 8; //maximum number of Items a node can hold until splitting
static const int maxDepth = 7; //maximum depth of the quadTree
//bounding box intersection
static bool intersects(const SDL_Rect &r1, const SDL_Rect &r2) { return !(r1.x + r1.w < r2.x || r1.x > r2.x + r2.w || r1.y > r2.y + r2.h || r1.y + r1.w < r2.y); }
//Node constituting tree structure
struct Node
{
const SDL_Rect bounds; //physical bounds of node
const int depth; //depth
std::unique_ptr<Node> children[4]; //child nodes
std::vector<const T*> items; //collection of retItems
Node(SDL_Rect &_bounds, int pLevel) : bounds(_bounds), depth(++pLevel) {}
bool isLeaf() { return children[0] == nullptr; }
void split()
{
//create a child for each quadrant
SDL_Point hSize = SDL_Point{ bounds.w / 2, bounds.h / 2 };
children[0].reset(new Node(SDL_Rect{ bounds.x, bounds.y, hSize.x, hSize.y }, depth));
children[1].reset(new Node(SDL_Rect{ bounds.x + hSize.x, bounds.y, hSize.x, hSize.y }, depth));
children[2].reset(new Node(SDL_Rect{ bounds.x, bounds.y + hSize.y, hSize.x, hSize.y }, depth));
children[3].reset(new Node(SDL_Rect{ bounds.x + hSize.x, bounds.y + hSize.y, hSize.x, hSize.y }, depth));
//insert items into children
for (auto item : items)
for (int i = 0; i < 4; i++)
children[i]->insert(*item);
//clear item collection
items.clear();
}
void draw(Camera &cam)
{
if (isLeaf())
cam.drawRectangle(bounds); //leaf node, draw boundinng box
else
for (auto &child : children) child->draw(cam); //draw children
}
void populate(const T &item, std::vector<const T*> &retItems)
{
if (!intersects(bounds, item.getBounds())) return; //item isn't in bounds, don't perform population
if (isLeaf())
retItems.insert(retItems.end(), items.begin(), items.end()); //leaf node, populate return collection
else
for (auto &child : children) child->populate(item, retItems); //attempt to populate from children
}
void insert(const T &item)
{
if (!intersects(bounds, item.getBounds())) return; //item isn't in bounds, don't perform insertion
if (isLeaf() && items.size() == maxItems && depth < maxDepth)
split(); //criteria met for split, perform operation
if (isLeaf())
items.push_back(&item); //leaf node, directly add to item collection
else
for (auto &child : children) child->insert(item); //attempt to insert into children
}
};
Node root;
public:
QuadTree(SDL_Rect quadRect) : root(quadRect, 0) {}
void insert(const T &item) { root.insert(item); }
void getCanidates(const T &item, std::vector<const T*> &items) { root.populate(item, items); }
void draw(Camera &cam) { root.draw(cam); }
};