C++ Quadtree SDL2

Question

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); }
};

Answer 1

When grabbing the items most code will simply iterate over them and then discard the vector.

You can avoid the allocation and copying cost by using a visitor pattern.

template<class UnaryFunction>
void visit(const T &item, UnaryFunction& visit){
        if (!intersects(bounds, item.getBounds())) return; //item isn't in bounds, don't perform population

    if (isLeaf())
        for (auto &item: items) f(item); //leaf node, iterate over items
    else
        for (auto &child : children) child->visit(item, visit); //visit children
}