QuadTree C++实现

Question

我最近在QuadTree中创建了一个C++实现。它与大多数实现略有不同。

它不是存储元素，而是只组织元素。这允许程序员将元素插入到QuadTree中，并维护对QuadTree之外的这些元素的访问。

节点只有在插入元素时才会细分，并且该元素的位置与该节点中的其他元素不同。这允许在QuadTree中存在相同位置的多个元素。

我希望得到一些关于代码的反馈。我以前没有很多人批评过我的代码，所以我真的在寻找可以改进它的方法。

无论如何，我还把我的代码放在了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

关于您的equals方法的一个次要评论：

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

通过双重否定检查等式有点令人困惑。只需检查是否相等，并删除无意义的评论时，你在它：

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

此外，您可能希望直接将这些定义为运算符：

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

Answer 2

1)赋值操作符和复制构造函数中有相同的代码。您应该简单地调用赋值操作符(或者创建一个用于复制数据的新函数，但这将是过度的)，如下所示：

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

2)大多数情况下，从函数返回向量不是一个好主意。如果编译器无法优化返回值，则意味着(至少一个)向量的附加副本。在这种情况下，这并不是什么大问题，因为向量很小，但无论如何也不应该使用返回值(仅用于内置的" value“类型，如int、char等)。

解决这一问题的方法是将向量作为函数的引用传递：

// 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)这是一件小事，但可以使你的生活变得更轻松。如果您必须多次使用相同的类型(如std::vector<qt_point_adapter*>)，则可以为其创建一个ty胡枝子。

请考虑以下示例：

class A
{
public:
    typedef std::vector<B*> BVec;

    void foo(BVec& result);

private:
    BVec vec;
};

从类的外部，您可以通过键入BVec来访问A::BVec。

4)对于虚拟函数重写，可以使用override关键字。这样，编译器就会告诉您，如果您试图重写一个实际上不是覆盖的函数。示例：

class Base
{
public:
    virtual void foo() = 0;
};

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