octree.hpp

Go to the documentation of this file.

/*
*
*      AggregPacking : Generator of random aggregate packings in concrete     
*                                                                             
*                           version 0.1 (2014-08-22)                          
* 
*                      Copyright (C)  2014  Jan Stransky                      
* 
*          Czech Technical University, Faculty of Civil Engineering,          
*      Department of Structural Mechanics, 166 29 Prague, Czech Republic      
* 
* AggregPacking is free software: you can redistribute it and/or modify it
* under the terms of the GNU Lesser General Public License as published by the
* Free Software Foundation, either version 3 of the License, or (at your
* option) any later version.
* 
* AggregPacking is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
* for more details.
* 
* You should have received a copy of the GNU Lesser General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef OCTREE_HPP
#define OCTREE_HPP

#ifdef AGGREGPACKING_BOOST_PYTHON
#include <boost/python.hpp>
#endif

#include <vector>
#include <iterator>
using std::vector;

namespace octree {


template<class T> class OctreeNode;

/**********************************************************************
* OCTREE ITERATOR
**********************************************************************/
// TODO reduce code duplication
template<class T>
class OctreeIterator : public std::iterator<std::input_iterator_tag, OctreeNode<T>> {
    protected:
        OctreeNode<T>* ptr;

    public:
        OctreeIterator(OctreeNode<T>* ptr) : ptr(ptr) {}

        OctreeIterator(const OctreeIterator& it) : ptr(it.ptr) {}

        OctreeIterator& operator++();

        OctreeIterator operator++(int) {OctreeIterator tmp(*this); operator++(); return tmp; }

        bool operator==(const OctreeIterator& rhs) { return ptr == rhs.ptr; }

        bool operator!=(const OctreeIterator& rhs) { return ptr != rhs.ptr; }

        OctreeNode<T>& operator*() { return *(this->ptr); }

        OctreeNode<T>* operator->() { return this->ptr; }
};

template<class T>
class OctreeConstIterator : public std::iterator<std::input_iterator_tag, OctreeNode<T>> {
    protected:
        OctreeNode<T>* ptr;

    public:
        OctreeConstIterator(OctreeNode<T>* ptr) : ptr(ptr) {}

        OctreeConstIterator(const OctreeConstIterator& it) : ptr(it.ptr) {}

        OctreeConstIterator& operator++();

        OctreeConstIterator operator++(int) {OctreeConstIterator tmp(*this); operator++(); return tmp; }

        bool operator==(const OctreeConstIterator& rhs) { return ptr == rhs.ptr; }

        bool operator!=(const OctreeConstIterator& rhs) { return ptr != rhs.ptr; }

        const OctreeNode<T>& operator*() const { return *(this->ptr); }

        const OctreeNode<T>* operator->() const { return this->ptr; }
};






/**********************************************************************
* OCTREE
**********************************************************************/
template <class T>
class Octree {
    private:
        int depth;

        OctreeNode<T>* root;

    public:
        Octree() : depth(0), root() {}


        Octree(double x, double y, double z, double size, int depth);


        Octree(double x, double y, double z, double size) : Octree(x,y,z,size,0) {};

        ~Octree();

        int getDepth() { return depth; }

        double getSize() { return root->getSize(); }


        void build(double x, double y, double z, double size);

        OctreeNode<T>* getRoot() { return root; }

        const OctreeNode<T>* getRoot() const { return root; }

        void addData(const T& data);

        int getNumberOfNodes();

        typedef OctreeIterator<T> iterator; // for boost python

        OctreeIterator<T> begin() { return OctreeIterator<T>(root); }

        OctreeIterator<T> end() { return OctreeIterator<T>(nullptr); }

        OctreeConstIterator<T> begin() const { return OctreeConstIterator<T>(root); }

        OctreeConstIterator<T> end() const { return OctreeConstIterator<T>(nullptr); }


        void getPotentialNeighbors(vector<T>& answer, double x, double y, double z, double size) const;


        void getPotentialNeighbors(vector<T>& answer, const T& o) const { getPotentialNeighbors(answer,get_x(o), get_y(o), get_z(o), get_size(o)); }


        void getPotentialNeighbors(vector<T>& answer, const T& o, int scale) const { getPotentialNeighbors(answer,get_x(o), get_y(o), get_z(o), get_size(o)*scale); }

#ifdef AGGREGPACKING_BOOST_PYTHON
        vector<T>* py_getPotentialNeighbors(double x, double y, double z, double size) const;

        vector<T>* py_getPotentialNeighbors(const T& o) const { return py_getPotentialNeighbors(get_x(o), get_y(o), get_z(o), get_size(o)); }

        vector<T>* py_getPotentialNeighbors(const T& o,int scale) const { return py_getPotentialNeighbors(get_x(o), get_y(o), get_z(o), get_size(o)*scale); }
#endif
};




/**********************************************************************
* OCTREE
**********************************************************************/
template <class T>
class OctreeNode {
    private:
        double x;

        double y;

        double z;

        OctreeNode** children;

        vector<T> data;

        OctreeNode* parent;

        int level;

        double size;
        
        int number;
        

        OctreeNode(double x, double y, double z, OctreeNode& parent, int number);


        OctreeNode(double x, double y, double z, double size);


        void divide(int depth);

    public:
        ~OctreeNode();

        bool operator==(const OctreeNode& other) { return &other == this; }

        bool operator!=(const OctreeNode& other) { return &other != this; }

        double getX() { return x; }

        double getY() { return y; }

        double getZ() { return z; }

        double getSize() { return size; }

        int getLevel() { return level; }

        int getNumber() { return number; }

        const vector<T>& getData() const { return data; }

        vector<T>& getData() { return data; }

        const OctreeNode** getChildren() const { return children; }

        vector<OctreeNode*>* py_getChildren();

        OctreeNode* getParent() { return parent; }

        const OctreeNode* getParent() const { return parent; }

        bool isRoot() const { return parent == nullptr; }

        bool isLeaf() const { return children == nullptr; }

        void addData(const T& data);

        void addData(const T& data, double x, double y, double z, double size);


        bool containsEntireBox(double x, double y, double z, double size) const;

        bool containsEntireBox(const T& o) const { return containsEntireBox(X_Y_Z_FROM_T(o)); }


        int getChildrenIntersectingBox(double x, double y, double z, double size) const;

        int getChildrenIntersectingBox(const T& o) const { return getChildrenIntersectingBox(get_x(o), get_y(o), get_z(o), get_size(o)); }

#ifdef AGGREGPACKING_BOOST_PYTHON
        vector<OctreeNode*>* py_getChildrenIntersectingBox(double x, double y, double z, double size) const;

        vector<OctreeNode*>* py_getChildrenIntersectingBox(const T& o) const { return py_getChildrenIntersectingBox(get_x(o), get_y(o), get_z(o), get_size(o)); }
#endif

        OctreeNode* getRoot();

        const OctreeNode* getRoot() const;


        OctreeNode* next() const;


        void getPotentialNeighbors(vector<T>& answer, double x, double y, double z, double size) const;


        void getPotentialNeighbors(vector<T>& answer, const T& o) const { getPotentialNeighbors(answer,get_x(o), get_y(o), get_z(o), get_size(o)); }

#ifdef AGGREGPACKING_BOOST_PYTHON
        vector<T>* py_getPotentialNeighbors(double x, double y, double z, double size) const;

        vector<T>* py_getPotentialNeighbors(const T& o) const { return py_getPotentialNeighbors(get_x(o), get_y(o), get_z(o), get_size(o)); }
#endif


        static inline bool bitFlag2bool(int flag, int index) { return (bool)(flag & (1 << index) ); }

        // Auxiliary function // TODO
        //static inline bool quickIntersectionCheck(const T& o, double x, double y, double z, double size);

    friend void Octree<T>::build(double x, double y, double z, double size);
};

#include "octree.tcc"


} // namespace
#endif