GeoLib::OctTree< POINT, MAX_POINTS > Class Template Reference

Detailed Description

template<typename POINT, std::size_t MAX_POINTS>
class GeoLib::OctTree< POINT, MAX_POINTS >

Template Parameters

POINT	point data type the OctTree will use
MAX_POINTS	maximum number of pointers of POINT in a leaf

Definition at line 27 of file OctTree.h.

#include <OctTree.h>

Public Member Functions
virtual	~OctTree ()
bool	addPoint (POINT *pnt, POINT *&ret_pnt)
template<typename T >
void	getPointsInRange (T const &min, T const &max, std::vector< POINT * > &pnts) const
Eigen::Vector3d const &	getLowerLeftCornerPoint () const
Eigen::Vector3d const &	getUpperRightCornerPoint () const
OctTree< POINT, MAX_POINTS > const *	getChild (std::size_t i) const
std::vector< POINT * > const &	getPointVector () const

Static Public Member Functions
static OctTree< POINT, MAX_POINTS > *	createOctTree (Eigen::Vector3d ll, Eigen::Vector3d ur, double eps=std::numeric_limits< double >::epsilon())

Private Types
enum class	Quadrant : std::int8_t {   NEL = 0 , NWL , SWL , SEL ,   NEU , NWU , SWU , SEU }

Private Member Functions
	OctTree (Eigen::Vector3d const &ll, Eigen::Vector3d const &ur, double eps)
bool	addPoint_ (POINT *pnt, POINT *&ret_pnt)
bool	addPointToChild (POINT *pnt)
void	splitNode (POINT *pnt)
bool	isOutside (POINT *pnt) const
template<typename T >
void	getPointsInRange_ (T const &min, T const &max, std::vector< POINT * > &pnts) const

Private Attributes
std::array< OctTree< POINT, MAX_POINTS > *, 8 >	_children
Eigen::Vector3d const	_ll
	lower left front face point of the cube
Eigen::Vector3d const	_ur
	upper right back face point of the cube
std::vector< POINT * >	_pnts
	vector of pointers to POINT objects
bool	_is_leaf
	flag if this OctTree is a leaf
double const	_eps
	threshold for point uniqueness

Member Enumeration Documentation

Quadrant

template<typename POINT , std::size_t MAX_POINTS>

enum class GeoLib::OctTree::Quadrant : std::int8_t

strongprivate

Enumerator
NEL	north east lower
NWL	north west lower
SWL	south west lower
SEL	south east lower
NEU	south west upper
NWU	south west upper
SWU	south west upper
SEU	south east upper

Definition at line 93 of file OctTree.h.

    {
        NEL = 0,  
        NWL,      
        SWL,      
        SEL,      
        NEU,      
        NWU,      
        SWU,      
        SEU       
    };

Constructor & Destructor Documentation

~OctTree()

template<typename POINT , std::size_t MAX_POINTS>

GeoLib::OctTree< POINT, MAX_POINTS >::~OctTree ( )

virtual

Destroys the children of this node.

Attention

Does not destroy the pointers to the managed objects.

Definition at line 68 of file OctTree-impl.h.

{
    for (auto c : _children)
    {
        delete c;
    }
}

OctTree()

template<typename POINT , std::size_t MAX_POINTS>

GeoLib::OctTree< POINT, MAX_POINTS >::OctTree ( Eigen::Vector3d const & ll, Eigen::Vector3d const & ur, double eps )

private

private constructor

Parameters

ll	lower left point
ur	upper right point
eps	the euclidean distance as a threshold to make objects unique

Definition at line 196 of file OctTree-impl.h.

    : _ll(ll), _ur(ur), _is_leaf(true), _eps(eps)
{
    _children.fill(nullptr);
}

References GeoLib::OctTree< POINT, MAX_POINTS >::_children.

Member Function Documentation

addPoint()

template<typename POINT , std::size_t MAX_POINTS>

bool GeoLib::OctTree< POINT, MAX_POINTS >::addPoint	(	POINT *	pnt,
		POINT *&	ret_pnt )

This method adds the given point to the OctTree. If necessary, new OctTree nodes will be inserted deploying a split of the corresponding OctTree node.

Parameters

pnt	the pointer to a point that should be inserted
ret_pnt	the pointer to a point in the OctTree. Three cases can occur: (1) ret_pnt is nullptr: the given point (pnt) is outside of the OctTree domain (2) ret_pnt is equal to pnt: the point is added to the OctTree (3) In case ret_pnt is neither equal to pnt nor equal to nullptr, another item within the eps distance is already in the OctTree and the pointer to this object is returned.

Returns

If the point can be inserted the method returns true, else false.

Definition at line 77 of file OctTree-impl.h.

{
    // first do a range query using a small box around the point pnt
    std::vector<POINT*> query_pnts;
    Eigen::Vector3d const min = pnt->asEigenVector3d().array() - _eps;
    Eigen::Vector3d const max = {
        std::abs(((*pnt)[0] + _eps) - (*pnt)[0]) > 0.0
            ? (*pnt)[0] + _eps
            : std::nextafter((*pnt)[0],
                             std::numeric_limits<double>::infinity()),
        std::abs(((*pnt)[1] + _eps) - (*pnt)[1]) > 0.0
            ? (*pnt)[1] + _eps
            : std::nextafter((*pnt)[1],
                             std::numeric_limits<double>::infinity()),
        std::abs(((*pnt)[2] + _eps) - (*pnt)[2]) > 0.0
            ? (*pnt)[2] + _eps
            : std::nextafter((*pnt)[2],
                             std::numeric_limits<double>::infinity())};
    getPointsInRange(min, max, query_pnts);
    auto const it =
        std::find_if(query_pnts.begin(), query_pnts.end(),
                     [pnt, this](auto const* p)
                     {
                         return (p->asEigenVector3d() - pnt->asEigenVector3d())
                                    .squaredNorm() < _eps * _eps;
                     });
    if (it != query_pnts.end())
    {
        ret_pnt = *it;
        return false;
    }
 
    // the point pnt is not yet in the OctTree
    if (isOutside(pnt))
    {
        ret_pnt = nullptr;
        return false;
    }
 
    // at this place it holds true that the point is within [_ll, _ur]
    if (!_is_leaf)
    {
        for (auto c : _children)
        {
            if (c->addPoint_(pnt, ret_pnt))
            {
                return true;
            }
            if (ret_pnt != nullptr)
            {
                return false;
            }
        }
    }
 
    ret_pnt = pnt;
 
    if (_pnts.size() < MAX_POINTS)
    {
        _pnts.push_back(pnt);
    }
    else
    {  // i.e. _pnts.size () == MAX_POINTS
        splitNode(pnt);
        _pnts.clear();
    }
    return true;
}

Referenced by makeNodesUnique(), and resetNodesInRegularElements().

addPoint_()

template<typename POINT , std::size_t MAX_POINTS>

bool GeoLib::OctTree< POINT, MAX_POINTS >::addPoint_ ( POINT * pnt, POINT *& ret_pnt )

private

This method tries to add the given point to the OctTree. If necessary for adding the point, new nodes will be inserted into the OctTree.

Parameters

pnt,ret_pnt

see documentation of addPoint()

Returns

If the point can be inserted the method returns true, else false.

Definition at line 204 of file OctTree-impl.h.

{
    if (isOutside(pnt))
    {
        ret_pnt = nullptr;
        return false;
    }
 
    // at this place it holds true that the point is within [_ll, _ur]
    if (!_is_leaf)
    {
        for (auto c : _children)
        {
            if (c->addPoint_(pnt, ret_pnt))
            {
                return true;
            }
            if (ret_pnt != nullptr)
            {
                return false;
            }
        }
    }
 
    ret_pnt = pnt;
    if (_pnts.size() < MAX_POINTS)
    {
        _pnts.push_back(pnt);
    }
    else
    {  // i.e. _pnts.size () == MAX_POINTS
        splitNode(pnt);
        _pnts.clear();
    }
    return true;
}

addPointToChild()

template<typename POINT , std::size_t MAX_POINTS>

bool GeoLib::OctTree< POINT, MAX_POINTS >::addPointToChild ( POINT * pnt )

private

This method adds the given point to the OctTree. If necessary, the OctTree will be extended.

Parameters

pnt

the point

Returns

If the point can be inserted the method returns true, else false.

Definition at line 242 of file OctTree-impl.h.

{
    if (isOutside(pnt))
    {
        return false;
    }
 
    if (_pnts.size() < MAX_POINTS)
    {
        _pnts.push_back(pnt);
    }
    else
    {  // i.e. _pnts.size () == MAX_POINTS
        splitNode(pnt);
        _pnts.clear();
    }
    return true;
}

createOctTree()

template<typename POINT , std::size_t MAX_POINTS>

OctTree< POINT, MAX_POINTS > * GeoLib::OctTree< POINT, MAX_POINTS >::createOctTree ( Eigen::Vector3d ll, Eigen::Vector3d ur, double eps = std::numeric_limits<double>::epsilon() )

static

Create an OctTree object. The arguments ll and ur are used to compute a cube domain the OctTree will living in.

Attention

This cubic domain can not be resized during the life time of the OctTree.

Parameters

ll	lower left front point, used for computation of cubic domain
ur	upper right back point, used for computation of cubic domain
eps	the euclidean distance as a threshold to make objects unique [default std::numeric_limits<double>::epsilon()] Adding a new item to an already "filled" OctTree node results in a split of the OctTree node. The smaller this number is the more leaves the OctTree will have, i.e. it needs more memory and more time to walk through the OctTree, but the search inside a leaf is fast. In contrast a big value results into a smaller number of OctTree leaves, the memory requirements for the OctTree may be lower but the search inside a OctTree leaf may be more expensive. The value should be chosen application dependent. [default 8]

Definition at line 16 of file OctTree-impl.h.

{
    // compute an axis aligned cube around the points ll and ur
    const double dx(ur[0] - ll[0]);
    const double dy(ur[1] - ll[1]);
    const double dz(ur[2] - ll[2]);
    if (dx >= dy && dx >= dz)
    {
        ll[1] -= (dx - dy) / 2.0;
        ur[1] += (dx - dy) / 2.0;
        ll[2] -= (dx - dz) / 2.0;
        ur[2] += (dx - dz) / 2.0;
    }
    else
    {
        if (dy >= dx && dy >= dz)
        {
            ll[0] -= (dy - dx) / 2.0;
            ur[0] += (dy - dx) / 2.0;
            ll[2] -= (dy - dz) / 2.0;
            ur[2] += (dy - dz) / 2.0;
        }
        else
        {
            ll[0] -= (dz - dx) / 2.0;
            ur[0] += (dz - dx) / 2.0;
            ll[1] -= (dz - dy) / 2.0;
            ur[1] += (dz - dy) / 2.0;
        }
    }
    if (eps == 0.0)
    {
        eps = std::numeric_limits<double>::epsilon();
    }
    for (std::size_t k(0); k < 3; ++k)
    {
        if (ur[k] - ll[k] > 0.0)
        {
            ur[k] += (ur[k] - ll[k]) * 1e-6;
        }
        else
        {
            ur[k] += eps;
        }
    }
    Eigen::Vector3d lower_left{ll[0], ll[1], ll[2]};
    Eigen::Vector3d upper_right{ur[0], ur[1], ur[2]};
    return new OctTree<POINT, MAX_POINTS>(lower_left, upper_right, eps);
}

Referenced by main(), and MeshToolsLib::partitionNodesByCoordinateMatch().

getChild()

template<typename POINT , std::size_t MAX_POINTS>

OctTree< POINT, MAX_POINTS > const * GeoLib::OctTree< POINT, MAX_POINTS >::getChild ( std::size_t i ) const

inline

Definition at line 79 of file OctTree.h.

    {
        return _children[i];
    }

References GeoLib::OctTree< POINT, MAX_POINTS >::_children.

getLowerLeftCornerPoint()

template<typename POINT , std::size_t MAX_POINTS>

Eigen::Vector3d const & GeoLib::OctTree< POINT, MAX_POINTS >::getLowerLeftCornerPoint ( ) const

inline

Definition at line 77 of file OctTree.h.

{ return _ll; }

References GeoLib::OctTree< POINT, MAX_POINTS >::_ll.

getPointsInRange()

template<typename POINT , std::size_t MAX_POINTS>

template<typename T >

void GeoLib::OctTree< POINT, MAX_POINTS >::getPointsInRange	(	T const &	min,
		T const &	max,
		std::vector< POINT * > &	pnts ) const

range query - returns all points inside the range [min[0], max[0]) x [min[1], max[1]) x [min[2], max[2])

Definition at line 148 of file OctTree-impl.h.

{
    if (max[0] == min[0] || max[1] == min[1] || max[2] == min[2])
    {
        ERR("The search range [{}, {}) x [{}, {}) x [{}, {}) is empty.", min[0],
            max[0], min[1], max[1], min[2], max[2]);
        return;
    }
 
    return getPointsInRange_(min, max, pnts);
}

References ERR().

Referenced by getExistingNodeFromOctTree().

getPointsInRange_()

template<typename POINT , std::size_t MAX_POINTS>

template<typename T >

void GeoLib::OctTree< POINT, MAX_POINTS >::getPointsInRange_ ( T const & min, T const & max, std::vector< POINT * > & pnts ) const

private

range query - returns all points inside the range [min[0], max[0]) x [min[1], max[1]) x [min[2], max[2])

Definition at line 163 of file OctTree-impl.h.

{
    if (_ur[0] < min[0] || _ur[1] < min[1] || _ur[2] < min[2])
    {
        return;
    }
 
    if (max[0] < _ll[0] || max[1] < _ll[1] || max[2] < _ll[2])
    {
        return;
    }
 
    if (_is_leaf)
    {
        std::copy_if(_pnts.begin(), _pnts.end(), std::back_inserter(pnts),
                     [&min, &max](auto const* p)
                     {
                         return (min[0] <= (*p)[0] && (*p)[0] < max[0] &&
                                 min[1] <= (*p)[1] && (*p)[1] < max[1] &&
                                 min[2] <= (*p)[2] && (*p)[2] < max[2]);
                     });
    }
    else
    {
        for (std::size_t k(0); k < 8; k++)
        {
            _children[k]->getPointsInRange_(min, max, pnts);
        }
    }
}

getPointVector()

template<typename POINT , std::size_t MAX_POINTS>

std::vector< POINT * > const & GeoLib::OctTree< POINT, MAX_POINTS >::getPointVector ( ) const

inline

Definition at line 83 of file OctTree.h.

{ return _pnts; }

References GeoLib::OctTree< POINT, MAX_POINTS >::_pnts.

getUpperRightCornerPoint()

template<typename POINT , std::size_t MAX_POINTS>

Eigen::Vector3d const & GeoLib::OctTree< POINT, MAX_POINTS >::getUpperRightCornerPoint ( ) const

inline

Definition at line 78 of file OctTree.h.

{ return _ur; }

References GeoLib::OctTree< POINT, MAX_POINTS >::_ur.

isOutside()

template<typename POINT , std::size_t MAX_POINTS>

bool GeoLib::OctTree< POINT, MAX_POINTS >::isOutside ( POINT * pnt ) const

private

checks if the given point pnt is outside of the OctTree node.

Parameters

pnt	the point that check is performed on

Returns

true if the point is outside of the OctTree node.

Definition at line 344 of file OctTree-impl.h.

{
    if ((*pnt)[0] < _ll[0] || (*pnt)[1] < _ll[1] || (*pnt)[2] < _ll[2])
    {
        return true;
    }
    if ((*pnt)[0] >= _ur[0] || (*pnt)[1] >= _ur[1] || (*pnt)[2] >= _ur[2])
    {
        return true;
    }
    return false;
}

splitNode()

template<typename POINT , std::size_t MAX_POINTS>

void GeoLib::OctTree< POINT, MAX_POINTS >::splitNode ( POINT * pnt )

private

Creates the child nodes of this leaf and distribute the points stored in _pnts to the children.

Parameters

pnt	the pointer to the points that is responsible for the split

Definition at line 262 of file OctTree-impl.h.

{
    const double x_mid((_ur[0] + _ll[0]) / 2.0);
    const double y_mid((_ur[1] + _ll[1]) / 2.0);
    const double z_mid((_ur[2] + _ll[2]) / 2.0);
    Eigen::Vector3d p0{x_mid, y_mid, _ll[2]};
    Eigen::Vector3d p1{_ur[0], _ur[1], z_mid};
 
    // create child NEL
    _children[static_cast<std::int8_t>(Quadrant::NEL)] =
        new OctTree<POINT, MAX_POINTS>(p0, p1, _eps);
 
    // create child NWL
    p0[0] = _ll[0];
    p1[0] = x_mid;
    _children[static_cast<std::int8_t>(Quadrant::NWL)] =
        new OctTree<POINT, MAX_POINTS>(p0, p1, _eps);
 
    // create child SWL
    p0[1] = _ll[1];
    p1[1] = y_mid;
    _children[static_cast<std::int8_t>(Quadrant::SWL)] =
        new OctTree<POINT, MAX_POINTS>(_ll, p1, _eps);
 
    // create child NEU
    _children[static_cast<std::int8_t>(Quadrant::NEU)] =
        new OctTree<POINT, MAX_POINTS>(p1, _ur, _eps);
 
    // create child SEL
    p0[0] = x_mid;
    p1[0] = _ur[0];
    _children[static_cast<std::int8_t>(Quadrant::SEL)] =
        new OctTree<POINT, MAX_POINTS>(p0, p1, _eps);
 
    // create child NWU
    p0[0] = _ll[0];
    p0[1] = y_mid;
    p0[2] = z_mid;
    p1[0] = x_mid;
    p1[1] = _ur[1];
    p1[2] = _ur[2];
    _children[static_cast<std::int8_t>(Quadrant::NWU)] =
        new OctTree<POINT, MAX_POINTS>(p0, p1, _eps);
 
    // create child SWU
    p0[1] = _ll[1];
    p1[1] = y_mid;
    _children[static_cast<std::int8_t>(Quadrant::SWU)] =
        new OctTree<POINT, MAX_POINTS>(p0, p1, _eps);
 
    // create child SEU
    p0[0] = x_mid;
    p1[0] = _ur[0];
    p1[1] = y_mid;
    p1[2] = _ur[2];
    _children[static_cast<std::int8_t>(Quadrant::SEU)] =
        new OctTree<POINT, MAX_POINTS>(p0, p1, _eps);
 
    // add the passed point pnt to the children at first
    for (std::size_t k(0); k < 8; k++)
    {
        if (_children[k]->addPointToChild(pnt))
        {
            break;
        }
    }
 
    // distribute points to sub quadtrees
    const std::size_t n_pnts(_pnts.size());
    for (std::size_t j(0); j < n_pnts; j++)
    {
        if (std::any_of(begin(_children), end(_children),
                        [&](auto* child)
                        { return child->addPointToChild(_pnts[j]); }))
        {
            continue;
        }
    }
    _is_leaf = false;
}

Member Data Documentation

_children

template<typename POINT , std::size_t MAX_POINTS>

std::array<OctTree<POINT, MAX_POINTS>*, 8> GeoLib::OctTree< POINT, MAX_POINTS >::_children

private

children are sorted: _children[0] is north east lower child _children[1] is north west lower child _children[2] is south west lower child _children[3] is south east lower child _children[4] is north east upper child _children[5] is north west upper child _children[6] is south west upper child _children[7] is south east upper child

Definition at line 145 of file OctTree.h.

Referenced by GeoLib::OctTree< POINT, MAX_POINTS >::OctTree(), and GeoLib::OctTree< POINT, MAX_POINTS >::getChild().

_eps

template<typename POINT , std::size_t MAX_POINTS>

double const GeoLib::OctTree< POINT, MAX_POINTS >::_eps

private

threshold for point uniqueness

Definition at line 155 of file OctTree.h.

_is_leaf

template<typename POINT , std::size_t MAX_POINTS>

bool GeoLib::OctTree< POINT, MAX_POINTS >::_is_leaf

private

flag if this OctTree is a leaf

Definition at line 153 of file OctTree.h.

_ll

template<typename POINT , std::size_t MAX_POINTS>

Eigen::Vector3d const GeoLib::OctTree< POINT, MAX_POINTS >::_ll

private

lower left front face point of the cube

Definition at line 147 of file OctTree.h.

Referenced by GeoLib::OctTree< POINT, MAX_POINTS >::getLowerLeftCornerPoint().

_pnts

template<typename POINT , std::size_t MAX_POINTS>

std::vector<POINT*> GeoLib::OctTree< POINT, MAX_POINTS >::_pnts

private

vector of pointers to POINT objects

Definition at line 151 of file OctTree.h.

Referenced by GeoLib::OctTree< POINT, MAX_POINTS >::getPointVector().

_ur

template<typename POINT , std::size_t MAX_POINTS>

Eigen::Vector3d const GeoLib::OctTree< POINT, MAX_POINTS >::_ur

private

upper right back face point of the cube

Definition at line 149 of file OctTree.h.

Referenced by GeoLib::OctTree< POINT, MAX_POINTS >::getUpperRightCornerPoint().

---

The documentation for this class was generated from the following files:

• GeoLib/OctTree.h
• GeoLib/OctTree-impl.h