QuadTree.h

Go to the documentation of this file.

#pragma once

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

#include <deque>


#include <concurrent_vector.h>
#include <mutex>
#include <tbb/spin_mutex.h>

struct FloatPoint
{
    FloatPoint(const float v[3]) { vec[0] = v[0]; vec[1] = v[1]; vec[2] = v[2]; }
    FloatPoint(float x, float y, float z) { vec[0] = x; vec[1] = y; vec[2] = z; }    
    float vec[3];
    float x() const { return vec[0]; }
    float y() const { return vec[1]; }
    float z() const { return vec[2]; }
};

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 LX_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 LX_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;
};


class PointStorageMT
{
public:
    using container = concurrency::concurrent_vector<ColorPoint>;
    using iterator = typename container::iterator;
    using const_iterator = typename container::const_iterator;

    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 addPoint(const ColorPoint& p) { mData.push_back(p); };        

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

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


private:

    container mData;


};

class LX_GEOM_EXPORT QuadTreeMT
{
public:
    QuadTreeMT(Geom::Rect boundary, size_t capacity, int myDeep = 1);
    QuadTreeMT* findQuadTree(const FloatPoint& cp);
    QuadTreeMT* findQuadTree(const Geom::Pnt &p);
    virtual ~QuadTreeMT();

    bool insert(const FloatPoint& fp, const uint32_t color );

    const Geom::Rect& getBoundary() const;
    std::vector<FloatPoint> getPoints() const;
    std::vector<uint32_t>   getColors() const;
    const bool hasPoints() const;
    const size_t getPointCount() const;
    std::vector<QuadTreeMT*> getChildren() const;

    const size_t getPointCountRecursive() const;
    std::vector<QuadTreeMT*> getChildrenRecursive() const;
    void removePointsRecursive();
        
    void setBBox( Geom::Bnd_Box b ) { _bbox = b; }
    Geom::Bnd_Box getBBox(  ) { return _bbox; }
    void setDeep(int deep);
    int getDeep();


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

private:
    
    void getDeep(int& deep);
    void split();
    QuadTreeMT();

    // 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;
    Geom::Bnd_Box _bbox;

    // Points in this quad tree node
    concurrency::concurrent_vector<FloatPoint> _points;
    concurrency::concurrent_vector<uint32_t>   _colors;
    
    std::mutex m_mutex;
};




}  // namespace Geom