QuadTree C++ Implementation

Question

I recently created a QuadTree implementation in C++. It varies slightly from most implementations.

Instead of storing elements it only organizes elements. This allows programmers to insert elements into the QuadTree and maintain access of those elements outside the QuadTree.

Nodes will only subdivide if an element is inserted and that element has a different position than other elements in that node. This allows multiple elements of the same position to exist within the QuadTree.

I am hoping to get some feedback on code. I haven't had many people criticize my code before, so I am really looking for ways that I could improve it.

Anyways, I've also put my code up on GitHub: https://github.com/bnpfeife/quadtree

---

quadtree.hpp:

#pragma once
#include <vector>
namespace bnp {
// When storing elements in the QuadTree, users may want to use unique/custom
// objects. To aid the QuadTree with interpreting different types of data,
// implement the qt_point_adapter on your objects.
class qt_point_adapter {
public:
 virtual float get_x() const = 0; // Retrieves x position
 virtual float get_y() const = 0; // Retrieves y position
 // Determines if point equals another
 virtual bool equals(const qt_point_adapter & point) const;
};
// This is used as the QuadTree's internal point structure. This prevents the
// QuadTree from explicitly using new/delete on points. If one wishes to use
// their own point objects, create an adapter function or use
// qt_point_adapter where applicable.
class qt_point : public qt_point_adapter {
private:
 float mX; // Stores x position
 float mY; // Stores y position
public:
 void set_x(const float& x); // Assigns x position
 void set_y(const float& y); // Assigns y position
 float get_x() const; // Retrieves x position
 float get_y() const; // Retrieves y position
 // Constructor for initializing POD members
 qt_point();
 // Constructor for assigning POD members
 qt_point(const float& x, const float& y);
};
// This is used as the QuadTree's internal boundary structure.
class qt_box {
private:
 float mX0; // Stores x0 position
 float mY0; // Stores y0 position
 float mX1; // Stores x1 position
 float mY1; // Stores y1 position
public:
 void set_x0(const float& x0); // Assigns x0 position
 void set_y0(const float& y0); // Assigns y0 position
 void set_x1(const float& x1); // Assigns x1 position
 void set_y1(const float& y1); // Assigns y1 position
 virtual float get_x0() const; // Retrieves x0 position
 virtual float get_y0() const; // Retrieves y0 position
 virtual float get_x1() const; // Retrieves x1 position
 virtual float get_y1() const; // Retrieves y1 position
 // Determines if qt_point or qt_box intersects
 bool intersects(const qt_point_adapter& point) const;
 bool intersects(const qt_box& box) const;
 // Constructor for initializing POD members
 qt_box();
 // Constructor for assigning POD members
 qt_box(const float& x0, const float& y0,
 const float& x1, const float& x2);
};
class quadtree {
private:
 quadtree* mNodeNW; // Stores north west node
 quadtree* mNodeNE; // Stores north east node
 quadtree* mNodeSW; // Stores south west node
 quadtree* mNodeSE; // Stores south east node
 qt_box mBounds; // Stores quadrant boundaries
 // Elements stored in the QuadTree are not owned by the QuadTree. This
 // allows the user access to the elements outside the QuadTree and have
 // them spatially organized within.
 std::vector<qt_point_adapter*> mElements;
 // Subdivides the QuadTree. This private because certain conditions must be
 // met before the tree can subdivide. In this implementation the QuadTree
 // subdivides when a new point is inserted, but does not match the point
 // location in the current node.
 void subdivide();
 // Joins the QuadTree. This does the opposite operation of subdivide. This
 // is private because certain conditions must be met before the QuadTree can
 // join. The QuadTree nodes must have no elements and must be joined.
 void join();
public:
 // Constructs an empty QuadTree. All QuadTrees must have specified
 // boundaries. All child QuadTrees are unaware that they are children and
 // have a parent tree. This is to maintain autonomy of the trees.
 quadtree(const qt_box& bounds);
 // QuadTree needs an explicit destructor. This is so that it can delete
 // it's children.
 ~quadtree();
 // QuadTree needs an explicit copy constructor and operator. C++'s default
 // copy will incorrectly link the subtrees to the new QuadTree. This
 // overrides this behavior.
 quadtree(const quadtree& qt);
 quadtree& operator=(const quadtree& qt);
 bool insert(qt_point_adapter* point); // Inserts point into tree
 bool remove(qt_point_adapter* point); // Removes point from tree
 // Retrieves elements from a defined region. If a node intersects the
 // defined region, elements are not automatically returned. Those elements
 // must also intersect the defined region.
 std::vector<qt_point_adapter*> query(const qt_box& bounds) const;
 std::vector<qt_point_adapter*> query(const qt_point& point) const;
 // Retrieves elements from a defined region and removes those elements from
 // the QuadTree. If a node intersects the defined region, elements are not
 // automatically returned. Those elements must also
 // intersect the defined region.
 std::vector<qt_point_adapter*> pull(const qt_box& bounds);
 std::vector<qt_point_adapter*> pull(const qt_point& point);
 // Clears the QuadTree and all of its children.
 void clear();
};
} // namespace bnp

quadtree.cc

#include "quadtree.hpp"
namespace bnp {
// Determines if point equals another
bool qt_point_adapter::equals(const qt_point_adapter & point) const {
 // Determines if point equals another
 return !(get_x() != point.get_x() || get_y() != point.get_y());
}
// Initializes POD members
qt_point::qt_point() : mX(0.0f), mY(0.0f) {}
// Initializes POD members
qt_point::qt_point(const float& x, const float& y) : mX(x), mY(y) {}
void qt_point::set_x(const float& x) { mX = x; } // Assigns x position
void qt_point::set_y(const float& y) { mY = y; } // Assigns y position
float qt_point::get_x() const { return mX; } // Retrieves x position
float qt_point::get_y() const { return mY; } // Retrieves y position
qt_box::qt_box() :
 // Initializes the POD members
 mX0(0.0f), mY0(0.0f),
 mX1(0.0f), mY1(0.0f) {}
qt_box::qt_box(
 const float& x0, const float& y0,
 const float& x1, const float& y1) :
 // Initializes the POD members
 mX0(x0), mY0(y0), mX1(x1), mY1(y1) {}
void qt_box::set_x0(const float& x0) { mX0 = x0; } // Assigns x0 position
void qt_box::set_y0(const float& y0) { mY0 = y0; } // Assigns y0 position
void qt_box::set_x1(const float& x1) { mX1 = x1; } // Assigns x1 position
void qt_box::set_y1(const float& y1) { mY1 = y1; } // Assigns y1 position
float qt_box::get_x0() const { return mX0; } // Retrieves x0 position
float qt_box::get_y0() const { return mY0; } // Retrieves y0 position
float qt_box::get_x1() const { return mX1; } // Retrieves x1 position
float qt_box::get_y1() const { return mY1; } // Retrieves y1 position
bool qt_box::intersects(const qt_point_adapter& point) const {
 // Determines if the point intersects the box
 return !((point.get_x() < get_x0()) || (point.get_y() < get_y0()) ||
 (point.get_x() > get_x1()) || (point.get_y() > get_y1()));
}
bool qt_box::intersects(const qt_box& box) const {
 // Determines if the boxes intersect one another
 return !((get_x0() > box.get_x1()) || (get_y0() > box.get_y1()) ||
 (get_x1() < box.get_x0()) || (get_y1() < box.get_y0()));
}
// Initializes the QuadTree bounds
quadtree::quadtree(const qt_box& bounds) :
 mNodeNW(nullptr), mNodeNE(nullptr),
 mNodeSW(nullptr), mNodeSE(nullptr),
 mBounds(bounds) {}
// Releases the QuadTree
quadtree::~quadtree() {
 if (mNodeNW != nullptr) {
 // Destructs the nodes
 delete mNodeNW;
 delete mNodeNE;
 delete mNodeSW;
 delete mNodeSE;
 }
}
void quadtree::subdivide() {
 if (mNodeNW == nullptr) {
 // Retrieves "upper" bounds
 float x0 = mBounds.get_x0();
 float y0 = mBounds.get_y0();
 // Retrieves "lower" bounds
 float x2 = mBounds.get_x1();
 float y2 = mBounds.get_y1();
 // Calculates the midpoints
 float x1 = (x0 + x2) / 2.0f;
 float y1 = (y0 + y2) / 2.0f;
 // Constructs the new nodes
 mNodeNW = new quadtree(qt_box(x0, y0, x1, y1));
 mNodeNE = new quadtree(qt_box(x1, y0, x2, y1));
 mNodeSW = new quadtree(qt_box(x0, y1, x1, y2));
 mNodeSE = new quadtree(qt_box(x1, y1, x2, y2));
 while (!mElements.empty()) {
 // Moves our elements into the new nodes
 if (mNodeNW->insert(mElements.back()));
 else if (mNodeNE->insert(mElements.back()));
 else if (mNodeSW->insert(mElements.back()));
 else if (mNodeSE->insert(mElements.back()));
 // Removes elements from our storage
 mElements.pop_back();
 }
 }
}
void quadtree::join() {
 if (mNodeNW != nullptr) {
 // Determines if our nodes are empty
 if ((mNodeNW->mElements.empty()) &&
 (mNodeNE->mElements.empty()) &&
 (mNodeSW->mElements.empty()) &&
 (mNodeSE->mElements.empty()) &&
 // Determines if our nodes are not branches
 (mNodeNW->mNodeNW == nullptr) &&
 (mNodeNE->mNodeNW == nullptr) &&
 (mNodeSW->mNodeNW == nullptr) &&
 (mNodeSE->mNodeNW == nullptr)) {
 // Destructs the nodes
 delete mNodeNW;
 delete mNodeNE;
 delete mNodeSW;
 delete mNodeSE;
 mNodeNW = nullptr;
 mNodeNE = nullptr;
 mNodeSW = nullptr;
 mNodeSE = nullptr;
 }
 }
}
bool quadtree::insert(qt_point_adapter* point) {
 if (mBounds.intersects(*point)) {
 // Determines if QuadTree is subdivided
 if (mNodeNW != nullptr) {
 // Inserts element in the nodes
 if (mNodeNW->insert(point));
 else if (mNodeNE->insert(point));
 else if (mNodeSW->insert(point));
 else if (mNodeSE->insert(point));
 } else {
 // Inserts element into our storage
 mElements.push_back(point);
 // Determines if the QuadTree needs to subdivide
 if (!mElements.front()->equals(*point)) { subdivide(); }
 }
 return true;
 }
 return false;
}
bool quadtree::remove(qt_point_adapter* point) {
 if (mBounds.intersects(*point)) {
 // Determines if the QuadTree is subdivided
 if (mNodeNW != nullptr) {
 // Removes elements from the nodes
 if (mNodeNW->remove(point) ||
 mNodeNE->remove(point) ||
 mNodeSW->remove(point) ||
 mNodeSE->remove(point)) {
 // Joins the QuadTree
 join();
 return true;
 }
 }
 // Iterates through the QuadTree
 for (auto i = mElements.begin(); i != mElements.end(); i++)
 // Removes the element from the QuadTree
 if (*i == point) { mElements.erase(i); return true; }
 }
 return false;
}
std::vector<qt_point_adapter*> quadtree::query(const qt_point & point) const {
 std::vector<qt_point_adapter*> points;
 if (mBounds.intersects(*(qt_point_adapter*)&point)) {
 // Determines if the QuadTree is subdivided
 if (mNodeNW != nullptr) {
 // Retrieves elements from the nodes
 std::vector<qt_point_adapter*> NW = mNodeNW->query(point);
 std::vector<qt_point_adapter*> NE = mNodeNE->query(point);
 std::vector<qt_point_adapter*> SW = mNodeSW->query(point);
 std::vector<qt_point_adapter*> SE = mNodeSE->query(point);
 // Copies elements from the nodes
 points.reserve(NW.size() + NE.size() + SW.size() + SE.size());
 points.insert(points.end(), NW.begin(), NW.end());
 points.insert(points.end(), NE.begin(), NE.end());
 points.insert(points.end(), SW.begin(), SW.end());
 points.insert(points.end(), SE.begin(), SE.end());
 }
 if (!mElements.empty())
 // Copies elements from the QuadTree
 if (mElements.back()->equals(*(qt_point_adapter*)&point))
 { points = mElements; }
 }
 return points;
}
std::vector<qt_point_adapter*> quadtree::query(const qt_box & bounds) const {
 std::vector<qt_point_adapter*> points;
 if (mBounds.intersects(bounds)) {
 // Determines if the QuadTree is subdivided
 if (mNodeNW != nullptr) {
 // Retrieves elements from the nodes
 std::vector<qt_point_adapter*> NW = mNodeNW->query(bounds);
 std::vector<qt_point_adapter*> NE = mNodeNE->query(bounds);
 std::vector<qt_point_adapter*> SW = mNodeSW->query(bounds);
 std::vector<qt_point_adapter*> SE = mNodeSE->query(bounds);
 // Copies elements from the nodes
 points.reserve(NW.size() + NE.size() + SW.size() + SE.size());
 points.insert(points.end(), NW.begin(), NW.end());
 points.insert(points.end(), NE.begin(), NE.end());
 points.insert(points.end(), SW.begin(), SW.end());
 points.insert(points.end(), SE.begin(), SE.end());
 }
 if (!mElements.empty())
 // Copies elements from the QuadTree
 if (bounds.intersects(*mElements.back()))
 { points = mElements; }
 }
 return points;
}
std::vector<qt_point_adapter*> quadtree::pull(const qt_point & point) {
 std::vector<qt_point_adapter*> points;
 if (mBounds.intersects(*(qt_point_adapter*)&point)) {
 // Determines if the QuadTree is subdivided
 if (mNodeNW != nullptr) {
 // Retrieves elements from the nodes
 std::vector<qt_point_adapter*> NW = mNodeNW->pull(point);
 std::vector<qt_point_adapter*> NE = mNodeNE->pull(point);
 std::vector<qt_point_adapter*> SW = mNodeSW->pull(point);
 std::vector<qt_point_adapter*> SE = mNodeSE->pull(point);
 // Copies elements from the nodes
 points.reserve(NW.size() + NE.size() + SW.size() + SE.size());
 points.insert(points.end(), NW.begin(), NW.end());
 points.insert(points.end(), NE.begin(), NE.end());
 points.insert(points.end(), SW.begin(), SW.end());
 points.insert(points.end(), SE.begin(), SE.end());
 // Collapses the QuadTree
 join();
 }
 if (!mElements.empty())
 // Copies elements from the QuadTree
 if (mElements.back()->equals(*(qt_point_adapter*)&point)) {
 points = mElements;
 mElements.clear();
 }
 }
 return points;
}
std::vector<qt_point_adapter*> quadtree::pull(const qt_box & bounds) {
 std::vector<qt_point_adapter*> points;
 if (mBounds.intersects(bounds)) {
 // Determines if the QuadTree is subdivided
 if (mNodeNW != nullptr) {
 // Retrieves elements from the nodes
 std::vector<qt_point_adapter*> NW = mNodeNW->pull(bounds);
 std::vector<qt_point_adapter*> NE = mNodeNE->pull(bounds);
 std::vector<qt_point_adapter*> SW = mNodeSW->pull(bounds);
 std::vector<qt_point_adapter*> SE = mNodeSE->pull(bounds);
 // Copies elements from the nodes
 points.reserve(NW.size() + NE.size() + SW.size() + SE.size());
 points.insert(points.end(), NW.begin(), NW.end());
 points.insert(points.end(), NE.begin(), NE.end());
 points.insert(points.end(), SW.begin(), SW.end());
 points.insert(points.end(), SE.begin(), SE.end());
 // Collapses the QuadTree
 join();
 }
 if (!mElements.empty())
 // Copies elements from the QuadTree
 if (bounds.intersects(*mElements.back())) {
 points = mElements;
 mElements.clear();
 }
 }
 return points;
}
// Clears the QuadTree
void quadtree::clear() {
 if (mNodeNW != nullptr) {
 // Destructs the nodes
 delete mNodeNW;
 delete mNodeNE;
 delete mNodeSW;
 delete mNodeSE;
 mNodeNW = nullptr;
 mNodeNE = nullptr;
 mNodeSW = nullptr;
 mNodeSE = nullptr;
 }
}
quadtree & quadtree::operator=(const quadtree& qt) {
 // Copies the QuadTree boundaries
 mBounds = qt.mBounds;
 // Determines if subdivided
 if (qt.mNodeNW != nullptr) {
 // Subdivide the QuadTree
 subdivide();
 // Copies the nodes
 *mNodeNW = *qt.mNodeNW;
 *mNodeNE = *qt.mNodeNE;
 *mNodeSW = *qt.mNodeSW;
 *mNodeSE = *qt.mNodeSE;
 }
 // Copies the elements
 if (!qt.mElements.empty()) {
 mElements = qt.mElements;
 }
 // Returns the QuadTree
 return *this;
}
quadtree::quadtree(const quadtree& qt) {
 // Copies the QuadTree boundaries
 mBounds = qt.mBounds;
 // Determines if subdivided
 if (qt.mNodeNW != nullptr) {
 // Subdivide the QuadTree
 subdivide();
 // Copies the nodes
 *mNodeNW = *qt.mNodeNW;
 *mNodeNE = *qt.mNodeNE;
 *mNodeSW = *qt.mNodeSW;
 *mNodeSE = *qt.mNodeSE;
 }
 // Copies the elements
 if (!qt.mElements.empty()) {
 mElements = qt.mElements;
 }
}
} // namespace: bnp

Answer 1

A minor comment about your equals method:

// Determines if point equals another
bool qt_point_adapter::equals(const qt_point_adapter & point) const {
 // Determines if point equals another
 return !(get_x() != point.get_x() || get_y() != point.get_y());
}

It is somewhat confusing that you check equality by double negation. Just check for equality and remove the pointless comment while you're at it:

bool qt_point_adapter::equals(const qt_point_adapter & point) const {
 return (get_x() == point.get_x() && get_y() == point.get_y());
}

Also you might want to define those directly as operators:

// Determines if point equals another
bool operator==(const qt_point_adapter &point1, 
 const qt_point_adapter &point2) const {
 return (point1.get_x() == point2.get_x() && point1.get_y() == point2.get_y());
}
bool operator!=(const qt_point_adapter &point1, 
 const qt_point_adapter &point2) const {
 return !(point1 == point2);
}

• brandonp: Thanks for the advice. I definitely see how using the double negative can be confusing. It would definitely give me some pause if I had to look at this code several days/weeks/months from now. I am also going to change "equals()" to "==" and "!=" functions. It makes more sense and is more c++ idiomatic.

Answer 2

1) You've the same code in the assignment operator and in the copy constructor. You should simply call the assignment operator (or create a new function for copying the data, but that would be an overkill), like this:

quadtree::quadtree(const quadtree& qt) {
 this->operator=(qt);
}

2) Most of the time returning a vector from a function is not a good idea. If the compiler cannot optimize the return value, it would mean (at least one) additional copy of the vector. In this case it's not a big deal since the vector is small, but you shouldn't use returning by value anyway (just for the built-in "value" types, like int, char, etc.).

A solution for this is to pass the vector as a reference to the function:

// instead of
std::vector<qt_point_adapter*> quadtree::pull(const qt_box & bounds)
// use
void quadtree::pull(const qt_box & bounds, std::vector<qt_point_adapter*>& result)

3) This is a minor thing, but can make your life easier: typedef. If you have to use the same type multiple times (like the std::vector<qt_point_adapter*>), you can create a typedef for it.

Consider the following example:

class A
{
public:
 typedef std::vector<B*> BVec;
 void foo(BVec& result);
private:
 BVec vec;
};

From outside of the class, you can access the BVec by typing A::BVec

4) For virtual function overrides you can use the override keyword. This way the compiler tell you if you try to override a function which is actually not an override. Example:

class Base
{
public:
 virtual void foo() = 0;
};
class Derived : public Base
{
public:
 void foo() override { } // Ok
 void foo(int i) override { } // Error
};