QuadTree.h

Go to the documentation of this file.

#pragma once

#include <Base/Color.h>
#include <Geom/Pnt.h>
#include <Geom/Precision.h>
#include <Geom/Rect.h>
#include <Geom/geom_defines.h>

#include <deque>


namespace Geom
{
class QuadTree;

class QuadTreeIterator
{
    QuadTreeIterator(QuadTree* q) : _start(q), _current(q){};

    bool operator==(const QuadTreeIterator& b) const { return (b._current == _current); }

    QuadTreeIterator& operator++() { return *this; }


    QuadTree* _current;
    const QuadTree* _start;
};

class GEOM_EXPORT ColorPoint
{
public:
    ColorPoint(){};
    ColorPoint(const Geom::Pnt& p, const Base::MColor& c) : p(p), c(c){};
    Geom::Pnt p;
    Base::MColor c;
};


class PointStorage
{
public:
    using container = std::deque<ColorPoint>;
    using iterator = typename container::iterator;
    using const_iterator = typename container::const_iterator;

    void addPoint(const ColorPoint& p) { mData.emplace_back(p); };
    iterator begin() { return mData.begin(); }
    iterator end() { return mData.end(); }
    const_iterator begin() const { return mData.begin(); }
    const_iterator end() const { return mData.end(); }
    const_iterator cbegin() const { return mData.cbegin(); }
    const_iterator cend() const { return mData.cend(); }

    void clear() { mData.clear(); };
    bool empty() const  { return mData.empty(); };

    const container& getData() const { return mData; }


private:

    container mData;


};

class GEOM_EXPORT QuadTree
{
public:
    QuadTree(Geom::Rect boundary, size_t capacity, int myDeep = 1);
    virtual ~QuadTree();

    bool insert(const Geom::ColorPoint& cp);

    const Geom::Rect& getBoundary() const;
    const std::deque<Geom::ColorPoint>& getPoints() const;
    const bool hasPoints() const;
    const size_t getPointCount() const;
    std::vector<QuadTree*> getChildren() const;

    void getPointsRecursive(std::deque<Geom::ColorPoint>& points);
    const size_t getPointCountRecursive() const;
    std::vector<QuadTree*> getChildrenRecursive() const;
    void removePointsRecursive();

    void setAutoSplit(bool on);
    void split();
    void setDeep(int deep);
    int getDeep();


    // Children
    QuadTree* northWest;
    QuadTree* northEast;
    QuadTree* southWest;
    QuadTree* southEast;

    QuadTreeIterator begin();
    QuadTreeIterator end();


private:
    void getDeep(int& deep);

    QuadTree();

    // Arbitrary constant to indicate how many elements can be stored in this quad tree node capacity
    size_t _capacity;

    int m_myDeep;
    int m_maxDeep;

    // Axis-aligned bounding box stored as a center with half-dimensions
    // to represent the boundaries of this quad tree
    Geom::Rect _boundary;

    // Points in this quad tree node
    PointStorage _points;

    size_t _pointCount;

    bool _autoSplit;
};



}  // namespace Geom