I've been working on a recursive quadtree in C++. How can I improve my code? My primary goals are improving the performance/speed, as well as practice.

QuadTree.h

#pragma once

#include <vector>
#include <algorithm>
#include <functional>

struct AABB 
 double left, top, right, bottom;

 AABB() 
 AABB(const double &l, const double &t, const double &r, const double &b);
 bool within(const AABB&) const;
 bool intersects(const AABB&) const;
;

struct Object 
 friend class QuadTree;
public:
 AABB _bound;

 Object() ;
 Object(const AABB&, void *data = nullptr);
 void setData(void *data);
 void *getData() const;
private:
 void *_data = nullptr;
 QuadTree *_qt = nullptr;
;

class QuadTree 
public:
 QuadTree(const AABB&, const unsigned &capacity, const unsigned &maxLevel, 
 const unsigned &level = 0, QuadTree *parent = nullptr);

 bool insert(Object*);
 bool remove(Object*);
 void update(Object*);
 bool contains(Object*) const;
 void search(const AABB&, const std::function<void(Object*)> &callback) const;
 void query(const AABB&, std::vector<Object*> &returnObjects) const;
 bool any(const AABB&, const std::function<bool(Object*)> &condition = nullptr) const;
 unsigned getTotalChildren() const;
 unsigned getTotalObjects() const;
 void clear();

 QuadTree() 
 ~QuadTree();
private:
 AABB _bound;
 QuadTree* _parent;
 QuadTree* _children[4];
 bool _isLeaf = true;
 double _centerX;
 double _centerY;
 unsigned _level;
 unsigned _maxLevel;
 unsigned _capacity;
 std::vector<Object*> _objects;

 void subdivide();
 void discardEmptyBuckets(QuadTree *node);
 QuadTree *getChild(const AABB&) const;
;

QuadTree.cpp

#include "QuadTree.h"

//** AABB **//
AABB::AABB(const double &l, const double &t, const double &r, const double &b) :
 left(l),
 top(t),
 right(r),
 bottom(b) 

bool AABB::within(const AABB &bound) const 
 return left > bound.left && bottom > bound.bottom
 && right < bound.right && top < bound.top;

bool AABB::intersects(const AABB &bound) const 
 if (bound.right <= left) return false;
 if (bound.left >= right) return false;
 if (bound.top <= bottom) return false;
 if (bound.bottom >= top) return false;
 return true; // intersection


//** Object **//
Object::Object(const AABB &bound, void *data):
 _bound(bound), 
 _data(data) 
;
void Object::setData(void *data) 
 _data = data;

void *Object::getData() const 
 return _data;


//** QuadTree **//
QuadTree::QuadTree(const AABB &bound, const unsigned &capacity, const unsigned &maxLevel, 
 const unsigned &level, QuadTree *parent):
 _capacity(capacity),
 _maxLevel(maxLevel),
 _level(level), 
 _parent(parent),
 _centerX((bound.left + bound.right) * 0.5f),
 _centerY((bound.bottom + bound.top) * 0.5f),
 _bound(bound) 


// Inserts an object into this quadtree
bool QuadTree::insert(Object *obj) 
 // Item already exists
 if (obj->_qt != nullptr)
 return false;

 // insert object at the lowest level
 if (!_isLeaf) 
 if (QuadTree *child = getChild(obj->_bound))
 return child->insert(obj);
 
 _objects.push_back(obj);
 obj->_qt = this; // used for quick search by quadtree

 // Subdivide if required
 if (_isLeaf && _level < _maxLevel && _objects.size() >= _capacity) 
 subdivide();

 // Re-insert objects into new quadrant
 for (unsigned i = 0; i < _objects.size();) 
 Object *object = _objects[i];
 if (QuadTree *child = getChild(object->_bound)) 
 _objects.erase(_objects.begin() + i);
 object->_qt = nullptr;
 child->insert(object);
 
 else ++i;
 
 
 return true;


// Removes an object from this quadtree
bool QuadTree::remove(Object *obj) 
 if (obj->_qt == nullptr)
 return false;
 if (obj->_qt != this)
 return obj->_qt->remove(obj);

 _objects.erase(std::find(_objects.begin(), _objects.end(), obj));
 obj->_qt = nullptr;
 discardEmptyBuckets(this);
 return true;


// Removes and re-inserts object into quadtree (for objects that move)
void QuadTree::update(Object *obj) 

// Checks if object exists in this quadtree
bool QuadTree::contains(Object *obj) const 
 if (obj->_qt == nullptr)
 return false;
 if (obj->_qt != this)
 return obj->_qt->contains(obj);

 return std::find(_objects.begin(), _objects.end(), obj) != _objects.end();


// Searches quadtree for objects within the provided boundary and returns them in callback
void QuadTree::search(const AABB &bound, const std::function<void(Object*)> &callback) const 
 // Search children first
 if (!_isLeaf) 
 if (QuadTree *child = getChild(bound)) 
 child->search(bound, callback);
 else 
 for (auto&& node : _children) 
 if (node->_bound.intersects(bound))
 node->search(bound, callback);
 
 
 
 // Now search objects
 for (auto&& obj : _objects) 
 if (obj->_bound.intersects(bound))
 callback(obj);
 


// Searches quadtree for objects within the provided boundary and adds them to provided vector
void QuadTree::query(const AABB &bound, std::vector<Object*> &returnObjects) const 
 search(bound, [&returnObjects](Object *obj) 
 returnObjects.push_back(obj);
 );


// Checks if any object exists in the specified bounds (with optional filter)
bool QuadTree::any(const AABB &bound, const std::function<bool(Object*)> &condition) const 
 bool found = false;
 search(bound, [&condition, &found](Object *obj) );
 return found;


// Returns total children count for this quadtree
unsigned QuadTree::getTotalChildren() const 
 unsigned count = 0;
 if (!_isLeaf) 
 for (auto&& child : _children)
 count += child->getTotalChildren();
 
 return (_isLeaf? 0 : 4) + count;


// Returns total object count for this quadtree
unsigned QuadTree::getTotalObjects() const 
 unsigned count = 0;
 if (!_isLeaf) 
 for (auto&& node : _children)
 count += node->getTotalObjects();
 
 return _objects.size() + count;


// Removes all objects and children from this quadtree
void QuadTree::clear() 
 if (!_objects.empty()) 
 for (auto&& obj : _objects)
 remove(obj);
 _objects.clear();
 
 if (!_isLeaf) 
 delete _children[0];
 delete _children[1];
 delete _children[2];
 delete _children[3];
 _isLeaf = true;
 


// Subdivides into four quadrants
void QuadTree::subdivide() 
 // Bottom right
 _children[0] = new QuadTree(
 _centerX, _centerY, _bound.right, _bound.bottom ,
 _capacity, _maxLevel, _level + 1, this
 );
 // Bottom left
 _children[1] = new QuadTree(
 _bound.left, _centerY, _centerX, _bound.bottom ,
 _capacity, _maxLevel, _level + 1, this
 );
 // Top left
 _children[2] = new QuadTree(
 _bound.left, _bound.top, _centerX, _centerY ,
 _capacity, _maxLevel, _level + 1, this
 );
 // Top right
 _children[3] = new QuadTree(
 _centerX, _bound.top, _bound.right, _centerY ,
 _capacity, _maxLevel, _level + 1, this
 );
 _isLeaf = false;


// Discards buckets if all children are leaves and contain no objects
void QuadTree::discardEmptyBuckets(QuadTree *node) 
 if (!node->_objects.empty())
 return;
 if (!node->_isLeaf) 
 for (auto &&child : node->_children) 
 if (!child->_isLeaf 
 node->clear();
 
 if (node->_parent != nullptr)
 discardEmptyBuckets(node->_parent);


// Returns child/quadrant that the provided boundary is in
QuadTree *QuadTree::getChild(const AABB &bound) const 
 bool bottom = bound.bottom > _centerY;
 bool left = bound.left < _centerX;
 bool top = !bottom && bound.top < _centerY;
 if (left && bound.right < _centerX) 
 if (top) return _children[1]; // top left
 if (bottom) return _children[2]; // bottom left
 
 else if (!left) 
 if (top) return _children[0]; // top right
 if (bottom) return _children[3]; // bottom right
 
 return nullptr;


QuadTree::~QuadTree() 
 clear();

I've done some profiling in VS2017 and I have found that the insert method takes the longest (i'm guessing due to the recursion), followed by AABB::intersects, then search. I have no clue on what I can do to make those methods faster. I'm curious to see what you guys have to say about it :)

AABB() 
Object() ;
QuadTree() 

What does this do, compared with not mentioning it at all? I notice you add an empty default constructor to all your classes. Look up “the rule of five”. In the case of AABB, you can remove the other constructor and then aggregate initialization takes hold, which is the same thing you wanted. Getting rid of it means I don’t have to wonder why you are passing double by const ref instead of value.

And you have a stray ; .

Writing identifiers with a leading underscore is a bad idea, and is generally dissuaded as a style. Note that it is legal for member names if (and only if) the next character is not a capital letter or another underscore.

The Object default constructor simply allows the default data initializers to apply, so it is not necessary (and can be worse) to write it explicitly. You can use =default if you need to mention it, but leaving it off completely is best.

OTOH, you did not define a copy constructor etc. What happens when an instance is copied? The pointer members get shallow copied, which generally is not right.

Raw pointers? what is the ownership/relationship/lifetime of these data members?

A void* data member? Don’t do that. There are safe ways to do type erasure in C++, or templates to customize the payload type, std::any, etc.

QuadTree(const AABB&, const unsigned &capacity, const unsigned &maxLevel, 
 const unsigned &level = 0, QuadTree *parent = nullptr);

Why would you pass an unsigned as a const ref?

void search(const AABB&, const std::function<void(Object*)> &callback) const;

How do you use this? Normally a search takes a predicate but you have it labeled callback, and the first parameter is unnamed. I think it would be clearer to call it enumerate (If I understand what it does) and name the searched-for rectangle to be clear that’s what it is for.

void query(const AABB&, std::vector<Object*> &returnObjects) const;

Don’t use “out” parameters. Return values (⧺F.20).

std::vector<Object*> query (const AABB&) const;

You might get faster code if you declared within, intersects and whatever else you can as noexcept.

It’s odd that within and intersects are written in totally different styles when they work in the identical manner.

speed of insert

Look at branch prediction. If an if statement will go one way or the other at random (as when traversing a tree) the predictor will never get it right and you have a huge latency.

_children[0] = new QuadTree(

⧺C.149 — no naked new or delete.

I also think that allocating nodes as part of insert is why it is slow! That is inherently a slow operation. You might time the subdivide function separately and compare that to the insert time, and see what percentage it accounts for.

Quadtrees are very useful, so this is a good exercise to implement your own. I think you've done a reasonable job here, but I see some things that could be improved.

Naming

Always name all of your parameters in your header. It makes it so much easier for another programmer that's trying to call the methods in a class if the parameters have useful, descriptive names. For example, in the Object constructor, what is the AABB parameter? Is it the bounds of the object? Is it the bounds of the quad in a QuadTree in which the object is found? Please clarify!

Speaking of the Object class, the name Object is meaningless. Every single thing in your program (other than PODT) are objects, yet they can't all be inserted into a QuadTree. Usually quad trees are used for things like collision-detection or finding the distance to neighbors. I would rename the Object class to Collidable or something along those lines.

What is the difference between contains(), search() and query()? Just looking at the names, they all sound like the same thing. You should give them more distinct names that clarify what they actually do. Looking at the code, it seems that contains() does a shallow search of the object's QuadTree for the existence of the object. (Isn't that a tautology? Shouldn't you never be allowed to have an object's _qt be a QuadTree to which it does not belong?) search() calls a callback for every object in a bounding box. So maybe a better name would be performTaskOnObjectsInRegion() or something like that. And query() appears to collect all objects within a bounding box, so I'd call it collectObjectsInRegion() or something along those lines.

Default Constructors

All 3 of your classes have default constructors that do nothing and leave their member variables in an undefined state. Why? It would be better to disallow creating these objects in an unusable state. Instead of an axis-aligned bounding box that contains random (possibly nonsensical) values for its bounds, simply disallow creating one without bounds by using:

AABB() = delete;

This removes the default constructor and solves the problem of an invalid object being created. Likewise, if you do the same for Object, then you never need for its _bound to be invalid. You can then also remove the setData() method as its data will always be set in the constructor. (I'd also remove the default nullptr value as there's no use in having an Object with no data.) Likewise with QuadTree. Doing this eliminates a huge class of bugs that crop up from badly initialized instances of objects.

Performance

I ran a profile of inserting 100,000 objects into a QuadTree. The slowest part (84% of runtime in my experiment) is the call to vector::erase(). The reason is that this causes the rest of the elements in the vector to be moved back 1 spot. It ends up being a bunch of calls to memmove(). It might be worth trying other containers instead of std::vector. One that has O(1) removal would fix this problem. Or, you could swap the object that you're currently working on with the last object in the vector and then erase only the last object. Doing this removed insert() from even showing up in my traces. (I didn't do much verification of the resulting QuadTree because there are no tests here, and no examples of how to use it, so make sure you do a lot of tests before going with that method.) It looked like this:

 // Re-insert objects into new quadrant
 for (unsigned i = 0; i < _objects.size();) 
 Object *object = _objects[i];
 if (QuadTree *child = getChild(object->_bound)) 
 std::swap(*(_objects.begin() + i), *(_objects.end() - 1));
 _objects.erase(_objects.end() - 1);
 object->_qt = nullptr;
 child->insert(object);
 
 else ++i;
 

Some things I haven't seen in the previous reviews, or I just plain missed ...

Quadtree

With moving object the quadtree might not be your best choice, at best an object will move from one child into the next but at worst you could have to delete a whole bunch as the path that the item is on might become empty and you have to remove all the children. Having multiple objects per node also forces you to keep a dynamic data structure in the node, that is not ideal. An alternative solution is the AABB Tree, (http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/) has a good description. As this tree only has one object per leaf at max and has a max number of nodes you can preallocate the memory and you can use a linear store for all the nodes. Additionally it is possible to change the object AABBs and update the structure with new bounding boxes. If updating the tree usually you'll check for an amount of change that will trigger a rebuild.

Depending on the number of objects, you might just be quicker doing a pairwise AABB test, did you do the timing ?

Allocations

Each insertion and removal incurs a good number of deallocations and allocations, if you want to stick with the quad-tree you can save on allocations by preserving children that you have already allocated and only allocating when needed.

update()

Your update calls remove() and insert() which updates the array twice, that is not optimal. If you're doing collision detection, in most cases you'll probably have a bunch of updates to do at the same time. If you can utilize this you might be able to improve your performance.

Do you really need it ?

• 
  _maxLevel and _level are never read in the code, do you really need it ?


• 
  contains() are you sure you ever need to test if a specific object is in the tree ? Meaning are you ever in a state where there are objects that might be in the tree ? If you can get rid of that function, you can get rid of the tracking std::vector<> the maintainance of which cost a lot of time.

_children

_children could be a std::array rather than a c-array;

Formatting

I'm not a fan of use of braces like this

if (!_isLeaf) 
 if (QuadTree *child = getChild(obj->_bound))
 return child->insert(obj);

What made you put the first pair of brace in ? Just because it looks complicated ? A rule of thumb I use is, "you can skip the braces if it fits in one line, e.g.

if (obj->_qt != nullptr) return false;

Naming

contains, query, search, any do very similar things, contains, getObjectsInBound, search could be labeled as forEachObjectInBound (similar to std::for_each with bounds), and any is findEachObjectInBoundIf (similar to std::find_if with bounds)

Consider std::algorithm

Your trio of query, search and any could be replaced by always using the following search()

void QuadTree::query(const AABB &bound, std::vector<Object*> &returnObjects) const 
 if (!_isLeaf) 
 if (QuadTree *child = getChild(bound)) 
 child->search(bound, returnObjects);
 else 
 for (auto&& node : _children) 
 if (node->_bound.intersects(bound))
 node->search(bound, returnObjects);
 
 
 
 // Now search objects
 for (auto&& obj : _objects) 
 if (obj->_bound.intersects(bound))
 returnObjects.push_back(obj);
 

And then use std::foreach or std::find_if on it. Although if you use any() a lot you would want to implement it in a way it exits as sound as the condition is satisfied, your implementation finds all objects no matter if the condition is true early.