4
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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);
}
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – brandonp Oct 12 '16 at 9:11
1
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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