2
\$\begingroup\$

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); }
};
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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
}
\$\endgroup\$
1
  • \$\begingroup\$ Thanks for the suggestion, useful and got me to search up the visitor pattern! \$\endgroup\$
    – Xoanon
    Jan 8, 2017 at 12:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.