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

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 181 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 189 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 227 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().

◆ 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.

77{ 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 (_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);
        }
    }
}

Referenced by getExistingNodeFromOctTree().

◆ 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.

83{ 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.

78{ 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 329 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 247 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 139 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 149 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 147 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 141 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 145 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 143 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

Detailed Description

Public Member Functions

Static Public Member Functions

Private Types

Private Member Functions

Private Attributes

Member Enumeration Documentation

◆ Quadrant

Constructor & Destructor Documentation

◆ ~OctTree()

◆ OctTree()

Member Function Documentation

◆ addPoint()

◆ addPoint_()

◆ addPointToChild()

◆ createOctTree()

◆ getChild()

◆ getLowerLeftCornerPoint()

◆ getPointsInRange()

◆ getPointVector()

◆ getUpperRightCornerPoint()

◆ isOutside()

◆ splitNode()

Member Data Documentation

◆ _children

◆ _eps

◆ _is_leaf

◆ _ll

◆ _pnts

◆ _ur