Detailed Description

template<typename POINT>
class GeoLib::QuadTree< POINT >

A quadtree is a rooted tree in which every internal node has four children. Every node corresponds to a square. (see Computational Geometry - Algorithms and Applications [Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars] - Chapter 14)

One can instantiate the class template with a point type and a value for the maximal number of points per node. The point-type have to provide the access to its coordinates via operator[] and for debugging purposes operator<<)

Definition at line 38 of file QuadTree.h.

#include <QuadTree.h>

Public Types
enum class	Quadrant { NE = 0 , NW , SW , SE }

Public Member Functions
	QuadTree (POINT ll, POINT ur, std::size_t max_points_per_leaf)

	~QuadTree ()

bool	addPoint (POINT const *pnt)

void	balance ()

void	getLeafs (std::list< QuadTree< POINT > * > &leaf_list)

const std::vector< POINT const * > &	getPoints () const

void	getSquarePoints (POINT &ll, POINT &ur) const

void	getLeaf (const POINT &pnt, POINT &ll, POINT &ur)

QuadTree< POINT > const *	getFather () const

QuadTree< POINT > const *	getChild (Quadrant quadrant) const

void	getMaxDepth (std::size_t &max_depth) const

std::size_t	getDepth () const

Private Member Functions
QuadTree< POINT > *	getChild (Quadrant quadrant)

bool	isLeaf () const

bool	isChild (QuadTree< POINT > const *const tree, Quadrant quadrant) const

QuadTree< POINT > *	getNorthNeighbor () const

QuadTree< POINT > *	getSouthNeighbor () const

QuadTree< POINT > *	getEastNeighbor () const

QuadTree< POINT > *	getWestNeighbor () const

	QuadTree (POINT ll, POINT ur, QuadTree *father, std::size_t depth, std::size_t max_points_per_leaf)

void	splitNode ()

Static Private Member Functions
static bool	needToRefine (QuadTree< POINT > const *const node)

Private Attributes
QuadTree< POINT > *	_father

std::array< QuadTree< POINT > *, 4 >	_children

POINT	_ll

POINT	_ur

std::size_t	_depth = 0

std::vector< POINT const * >	_pnts

bool	_is_leaf = true

const std::size_t	_max_points_per_leaf

Member Enumeration Documentation

◆ Quadrant

template<typename POINT >

enum class GeoLib::QuadTree::Quadrant

strong

Enumerator
NE	north east
NW	north west
SW	south west
SE	south east

Definition at line 41 of file QuadTree.h.

Constructor & Destructor Documentation

◆ QuadTree() [1/2]

template<typename POINT >

GeoLib::QuadTree< POINT >::QuadTree	(	POINT	ll,
		POINT	ur,
		std::size_t	max_points_per_leaf )

inline

This is the constructor for class QuadTree. It takes two points (lower left and the upper right points).

Parameters

ll	lower left point of the square
ur	upper right point of the square
max_points_per_leaf	maximum number of points per leaf

Definition at line 55 of file QuadTree.h.

        : _father(nullptr),
          _ll(std::move(ll)),
          _ur(std::move(ur)),
          _max_points_per_leaf(max_points_per_leaf)
    {
        assert(_max_points_per_leaf > 0);
 
        if ((_ur[0] - _ll[0]) > (_ur[1] - _ll[1]))
        {
            _ur[1] = _ll[1] + _ur[0] - _ll[0];
        }
        else
        {
            _ur[0] = _ll[0] + _ur[1] - _ll[1];
        }
 
        DBUG(
            "QuadTree(): lower left: ({:f},{:f},{:f}), upper right: "
            "({:f},{:f},{:f}), depth: {:d}",
            _ll[0],
            _ll[1],
            _ll[2],
            _ur[0],
            _ur[1],
            _ur[2],
            _depth);
    }

References GeoLib::QuadTree< POINT >::_depth, GeoLib::QuadTree< POINT >::_ll, GeoLib::QuadTree< POINT >::_max_points_per_leaf, GeoLib::QuadTree< POINT >::_ur, and DBUG().

Referenced by GeoLib::QuadTree< POINT >::splitNode().

◆ ~QuadTree()

template<typename POINT >

GeoLib::QuadTree< POINT >::~QuadTree ( )

inline

destructor

Definition at line 87 of file QuadTree.h.

    {
        for (auto const& child : _children)
        {
            delete child;
        }
    }

References GeoLib::QuadTree< POINT >::_children.

◆ QuadTree() [2/2]

template<typename POINT >

GeoLib::QuadTree< POINT >::QuadTree	(	POINT	ll,
		POINT	ur,
		QuadTree< POINT > *	father,
		std::size_t	depth,
		std::size_t	max_points_per_leaf )

inlineprivate

private constructor

Parameters

ll	lower left point
ur	upper right point
father	father in the tree
depth	depth of the node
max_points_per_leaf	maximum number of points per leaf

Definition at line 495 of file QuadTree.h.

        : _father(father),
          _ll(std::move(ll)),
          _ur(std::move(ur)),
          _depth(depth),
          _max_points_per_leaf(max_points_per_leaf)
    {
    }

Member Function Documentation

◆ addPoint()

template<typename POINT >

bool GeoLib::QuadTree< POINT >::addPoint ( POINT const * pnt )

inline

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

Parameters

pnt the point

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

Definition at line 101 of file QuadTree.h.

    {
        if ((*pnt)[0] < _ll[0])
        {
            return false;
        }
        if ((*pnt)[0] >= _ur[0])
        {
            return false;
        }
        if ((*pnt)[1] < _ll[1])
        {
            return false;
        }
        if ((*pnt)[1] >= _ur[1])
        {
            return false;
        }
 
        if (!_is_leaf)
        {
            return std::any_of(begin(_children), end(_children),
                               [&pnt](auto* child)
                               { return child->addPoint(pnt); });
        }
 
        // check if point is already in quadtree
        bool pnt_in_quadtree(false);
        for (std::size_t k(0); k < _pnts.size() && !pnt_in_quadtree; k++)
        {
            const double v0((*(_pnts[k]))[0] - (*pnt)[0]);
            const double v1((*(_pnts[k]))[1] - (*pnt)[1]);
            const double sqr_dist(v0 * v0 + v1 * v1);
            if (sqr_dist < std::numeric_limits<double>::epsilon())
            {
                pnt_in_quadtree = true;
            }
        }
        if (!pnt_in_quadtree)
        {
            _pnts.push_back(pnt);
        }
        else
        {
            return false;
        }
 
        if (_pnts.size() > _max_points_per_leaf)
        {
            splitNode();
        }
        return true;
    }

References GeoLib::QuadTree< POINT >::_children, GeoLib::QuadTree< POINT >::_is_leaf, GeoLib::QuadTree< POINT >::_ll, GeoLib::QuadTree< POINT >::_max_points_per_leaf, GeoLib::QuadTree< POINT >::_pnts, GeoLib::QuadTree< POINT >::_ur, and GeoLib::QuadTree< POINT >::splitNode().

Referenced by FileIO::GMSH::GMSHAdaptiveMeshDensity::addPoints(), and GeoLib::QuadTree< POINT >::splitNode().

◆ balance()

template<typename POINT >

void GeoLib::QuadTree< POINT >::balance ( )

inline

This method balances the quadtree, i.e., it will be inserted nodes such that the depth between neighbored leafs is at most one. If you want to create a mesh (for instance with GMSH) you can use this method to improve the mesh quality. The balance method should be used after inserting all points.

Definition at line 162 of file QuadTree.h.

    {
        std::list<QuadTree<POINT>*> leaf_list;
        getLeafs(leaf_list);
 
        while (!leaf_list.empty())
        {
            QuadTree<POINT>* node(leaf_list.front());
            leaf_list.pop_front();
 
            if (node->isLeaf())
            {
                if (needToRefine(node))
                {
                    node->splitNode();
                    leaf_list.push_back(node->getChild(Quadrant::NE));
                    leaf_list.push_back(node->getChild(Quadrant::NW));
                    leaf_list.push_back(node->getChild(Quadrant::SW));
                    leaf_list.push_back(node->getChild(Quadrant::SE));
 
                    // check if north neighbor has to be refined
                    QuadTree<POINT>* north_neighbor(node->getNorthNeighbor());
                    if (north_neighbor != nullptr)
                    {
                        if (north_neighbor->getDepth() < node->getDepth())
                        {
                            if (north_neighbor->isLeaf())
                            {
                                leaf_list.push_back(north_neighbor);
                            }
                        }
                    }
 
                    // check if west neighbor has to be refined
                    QuadTree<POINT>* west_neighbor(node->getWestNeighbor());
                    if (west_neighbor != nullptr)
                    {
                        if (west_neighbor->getDepth() < node->getDepth())
                        {
                            if (west_neighbor->isLeaf())
                            {
                                leaf_list.push_back(west_neighbor);
                            }
                        }
                    }
 
                    // check if south neighbor has to be refined
                    QuadTree<POINT>* south_neighbor(node->getSouthNeighbor());
                    if (south_neighbor != nullptr)
                    {
                        if (south_neighbor->getDepth() < node->getDepth())
                        {
                            if (south_neighbor->isLeaf())
                            {
                                leaf_list.push_back(south_neighbor);
                            }
                        }
                    }
 
                    // check if east neighbor has to be refined
                    QuadTree<POINT>* east_neighbor(node->getEastNeighbor());
                    if (east_neighbor != nullptr)
                    {
                        if (east_neighbor->getDepth() < node->getDepth())
                        {
                            if (east_neighbor->isLeaf())
                            {
                                leaf_list.push_back(east_neighbor);
                            }
                        }
                    }
                }
            }
        }
    }

Referenced by FileIO::GMSH::GMSHAdaptiveMeshDensity::addPoints().

◆ getChild() [1/2]

template<typename POINT >

QuadTree< POINT > * GeoLib::QuadTree< POINT >::getChild ( Quadrant quadrant )

inlineprivate

Definition at line 339 of file QuadTree.h.

    {
        return _children[static_cast<int>(quadrant)];
    }

References GeoLib::QuadTree< POINT >::_children.

◆ getChild() [2/2]

template<typename POINT >

QuadTree< POINT > const * GeoLib::QuadTree< POINT >::getChild ( Quadrant quadrant ) const

inline

Definition at line 305 of file QuadTree.h.

    {
        return _children[quadrant];
    }

References GeoLib::QuadTree< POINT >::_children.

Referenced by GeoLib::QuadTree< POINT >::balance(), GeoLib::QuadTree< POINT >::getEastNeighbor(), GeoLib::QuadTree< POINT >::getNorthNeighbor(), GeoLib::QuadTree< POINT >::getSouthNeighbor(), GeoLib::QuadTree< POINT >::getWestNeighbor(), and GeoLib::QuadTree< POINT >::needToRefine().

◆ getDepth()

template<typename POINT >

std::size_t GeoLib::QuadTree< POINT >::getDepth ( ) const

inline

Method returns the depth of the current QuadTree node.

Returns: the depth of the current QuadTree node

Definition at line 336 of file QuadTree.h.

336{ return _depth; }

References GeoLib::QuadTree< POINT >::_depth.

Referenced by GeoLib::QuadTree< POINT >::balance(), and GeoLib::QuadTree< POINT >::needToRefine().

◆ getEastNeighbor()

template<typename POINT >

QuadTree< POINT > * GeoLib::QuadTree< POINT >::getEastNeighbor ( ) const

inlineprivate

Definition at line 419 of file QuadTree.h.

    {
        if (this->_father == nullptr)
        {  // root of QuadTree
            return nullptr;
        }
 
        if (this->_father->isChild(this, Quadrant::NW))
        {
            return this->_father->getChild(Quadrant::NE);
        }
        if (this->_father->isChild(this, Quadrant::SW))
        {
            return this->_father->getChild(Quadrant::SE);
        }
 
        QuadTree<POINT>* east_neighbor(this->_father->getEastNeighbor());
        if (east_neighbor == nullptr)
        {
            return nullptr;
        }
        if (east_neighbor->isLeaf())
        {
            return east_neighbor;
        }
 
        if (this->_father->isChild(this, Quadrant::SE))
        {
            return east_neighbor->getChild(Quadrant::SW);
        }
 
        return east_neighbor->getChild(Quadrant::NW);
    }

References GeoLib::QuadTree< POINT >::_father, GeoLib::QuadTree< POINT >::getChild(), GeoLib::QuadTree< POINT >::isLeaf(), GeoLib::QuadTree< POINT >::NE, GeoLib::QuadTree< POINT >::NW, GeoLib::QuadTree< POINT >::SE, and GeoLib::QuadTree< POINT >::SW.

Referenced by GeoLib::QuadTree< POINT >::balance(), and GeoLib::QuadTree< POINT >::needToRefine().

◆ getFather()

template<typename POINT >

QuadTree< POINT > const * GeoLib::QuadTree< POINT >::getFather ( ) const

inline

Definition at line 303 of file QuadTree.h.

303{ return _father; }

References GeoLib::QuadTree< POINT >::_father.

◆ getLeaf()

template<typename POINT >

void GeoLib::QuadTree< POINT >::getLeaf	(	const POINT &	pnt,
		POINT &	ll,
		POINT &	ur )

inline

Definition at line 265 of file QuadTree.h.

    {
        if (this->isLeaf())
        {
            ll = _ll;
            ur = _ur;
        }
        else
        {
            if (pnt[0] <= 0.5 * (_ur[0] + _ll[0]))  // WEST
            {
                if (pnt[1] <= 0.5 * (_ur[1] + _ll[1]))
                {  // SOUTH
                    _children[static_cast<int>(Quadrant::SW)]->getLeaf(pnt, ll,
                                                                       ur);
                }
                else
                {  // NORTH
                    _children[static_cast<int>(Quadrant::NW)]->getLeaf(pnt, ll,
                                                                       ur);
                }
            }
            else  // EAST
            {
                if (pnt[1] <= 0.5 * (_ur[1] + _ll[1]))
                {  // SOUTH
                    _children[static_cast<int>(Quadrant::SE)]->getLeaf(pnt, ll,
                                                                       ur);
                }
                else
                {  // NORTH
                    _children[static_cast<int>(Quadrant::NE)]->getLeaf(pnt, ll,
                                                                       ur);
                }
            }
        }
    }

References GeoLib::QuadTree< POINT >::_children, GeoLib::QuadTree< POINT >::_ll, GeoLib::QuadTree< POINT >::_ur, GeoLib::QuadTree< POINT >::getLeaf(), GeoLib::QuadTree< POINT >::isLeaf(), GeoLib::QuadTree< POINT >::NE, GeoLib::QuadTree< POINT >::NW, GeoLib::QuadTree< POINT >::SE, and GeoLib::QuadTree< POINT >::SW.

Referenced by GeoLib::QuadTree< POINT >::getLeaf(), FileIO::GMSH::GMSHAdaptiveMeshDensity::getMeshDensityAtPoint(), and FileIO::GMSH::GMSHAdaptiveMeshDensity::getMeshDensityAtStation().

◆ getLeafs()

template<typename POINT >

void GeoLib::QuadTree< POINT >::getLeafs ( std::list< QuadTree< POINT > * > & leaf_list )

inline

add all leafs of the quadtree to the list

Parameters

leaf_list list of leafs

Definition at line 242 of file QuadTree.h.

    {
        if (_is_leaf)
        {
            leaf_list.push_back(this);
        }
        else
        {
            for (auto& child : _children)
            {
                child->getLeafs(leaf_list);
            }
        }
    }

References GeoLib::QuadTree< POINT >::_children, and GeoLib::QuadTree< POINT >::_is_leaf.

Referenced by GeoLib::QuadTree< POINT >::balance(), FileIO::GMSH::GMSHAdaptiveMeshDensity::getQuadTreeGeometry(), and FileIO::GMSH::GMSHAdaptiveMeshDensity::getSteinerPoints().

◆ getMaxDepth()

template<typename POINT >

void GeoLib::QuadTree< POINT >::getMaxDepth ( std::size_t & max_depth ) const

inline

Method calculates the maximum depth of the QuadTree instance. It is used within the method GMSHAdaptiveMeshDensity::getSteinerPoints().

Parameters

max_depth (input/output) at the entry max_depth contains the maximum depth up to now

Definition at line 316 of file QuadTree.h.

    {
        if (max_depth < _depth)
        {
            max_depth = _depth;
        }
 
        for (auto& child : _children)
        {
            if (child)
            {
                child->getMaxDepth(max_depth);
            }
        }
    }

References GeoLib::QuadTree< POINT >::_children, and GeoLib::QuadTree< POINT >::_depth.

Referenced by FileIO::GMSH::GMSHAdaptiveMeshDensity::getSteinerPoints().

◆ getNorthNeighbor()

template<typename POINT >

QuadTree< POINT > * GeoLib::QuadTree< POINT >::getNorthNeighbor ( ) const

inlineprivate

Definition at line 351 of file QuadTree.h.

    {
        if (this->_father == nullptr)
        {  // root of QuadTree
            return nullptr;
        }
 
        if (this->_father->isChild(this, Quadrant::SW))
        {
            return this->_father->getChild(Quadrant::NW);
        }
        if (this->_father->isChild(this, Quadrant::SE))
        {
            return this->_father->getChild(Quadrant::NE);
        }
 
        QuadTree<POINT>* north_neighbor(this->_father->getNorthNeighbor());
        if (north_neighbor == nullptr)
        {
            return nullptr;
        }
        if (north_neighbor->isLeaf())
        {
            return north_neighbor;
        }
 
        if (this->_father->isChild(this, Quadrant::NW))
        {
            return north_neighbor->getChild(Quadrant::SW);
        }
 
        return north_neighbor->getChild(Quadrant::SE);
    }

References GeoLib::QuadTree< POINT >::_father, GeoLib::QuadTree< POINT >::getChild(), GeoLib::QuadTree< POINT >::isLeaf(), GeoLib::QuadTree< POINT >::NE, GeoLib::QuadTree< POINT >::NW, GeoLib::QuadTree< POINT >::SE, and GeoLib::QuadTree< POINT >::SW.

Referenced by GeoLib::QuadTree< POINT >::balance(), and GeoLib::QuadTree< POINT >::needToRefine().

◆ getPoints()

template<typename POINT >

const std::vector< POINT const * > & GeoLib::QuadTree< POINT >::getPoints ( ) const

inline

Definition at line 257 of file QuadTree.h.

257{ return _pnts; }

References GeoLib::QuadTree< POINT >::_pnts.

◆ getSouthNeighbor()

template<typename POINT >

QuadTree< POINT > * GeoLib::QuadTree< POINT >::getSouthNeighbor ( ) const

inlineprivate

Definition at line 385 of file QuadTree.h.

    {
        if (this->_father == nullptr)
        {  // root of QuadTree
            return nullptr;
        }
 
        if (this->_father->isChild(this, Quadrant::NW))
        {
            return this->_father->getChild(Quadrant::SW);
        }
        if (this->_father->isChild(this, Quadrant::NE))
        {
            return this->_father->getChild(Quadrant::SE);
        }
 
        QuadTree<POINT>* south_neighbor(this->_father->getSouthNeighbor());
        if (south_neighbor == nullptr)
        {
            return nullptr;
        }
        if (south_neighbor->isLeaf())
        {
            return south_neighbor;
        }
 
        if (this->_father->isChild(this, Quadrant::SW))
        {
            return south_neighbor->getChild(Quadrant::NW);
        }
 
        return south_neighbor->getChild(Quadrant::NE);
    }

References GeoLib::QuadTree< POINT >::_father, GeoLib::QuadTree< POINT >::getChild(), GeoLib::QuadTree< POINT >::isLeaf(), GeoLib::QuadTree< POINT >::NE, GeoLib::QuadTree< POINT >::NW, GeoLib::QuadTree< POINT >::SE, and GeoLib::QuadTree< POINT >::SW.

Referenced by GeoLib::QuadTree< POINT >::balance(), and GeoLib::QuadTree< POINT >::needToRefine().

◆ getSquarePoints()

template<typename POINT >

void GeoLib::QuadTree< POINT >::getSquarePoints	(	POINT &	ll,
		POINT &	ur ) const

inline

Definition at line 259 of file QuadTree.h.

    {
        ll = _ll;
        ur = _ur;
    }

References GeoLib::QuadTree< POINT >::_ll, and GeoLib::QuadTree< POINT >::_ur.

◆ getWestNeighbor()

template<typename POINT >

QuadTree< POINT > * GeoLib::QuadTree< POINT >::getWestNeighbor ( ) const

inlineprivate

Definition at line 453 of file QuadTree.h.

    {
        if (this->_father == nullptr)
        {  // root of QuadTree
            return nullptr;
        }
 
        if (this->_father->isChild(this, Quadrant::NE))
        {
            return this->_father->getChild(Quadrant::NW);
        }
        if (this->_father->isChild(this, Quadrant::SE))
        {
            return this->_father->getChild(Quadrant::SW);
        }
 
        QuadTree<POINT>* west_neighbor(this->_father->getWestNeighbor());
        if (west_neighbor == nullptr)
        {
            return nullptr;
        }
        if (west_neighbor->isLeaf())
        {
            return west_neighbor;
        }
 
        if (this->_father->isChild(this, Quadrant::SW))
        {
            return west_neighbor->getChild(Quadrant::SE);
        }
 
        return west_neighbor->getChild(Quadrant::NE);
    }

References GeoLib::QuadTree< POINT >::_father, GeoLib::QuadTree< POINT >::getChild(), GeoLib::QuadTree< POINT >::isLeaf(), GeoLib::QuadTree< POINT >::NE, GeoLib::QuadTree< POINT >::NW, GeoLib::QuadTree< POINT >::SE, and GeoLib::QuadTree< POINT >::SW.

Referenced by GeoLib::QuadTree< POINT >::balance(), and GeoLib::QuadTree< POINT >::needToRefine().

◆ isChild()

template<typename POINT >

bool GeoLib::QuadTree< POINT >::isChild	(	QuadTree< POINT > const *const	tree,
		Quadrant	quadrant ) const

inlineprivate

Definition at line 346 of file QuadTree.h.

    {
        return _children[static_cast<int>(quadrant)] == tree;
    }

References GeoLib::QuadTree< POINT >::_children.

◆ isLeaf()

template<typename POINT >

bool GeoLib::QuadTree< POINT >::isLeaf ( ) const

inlineprivate

Definition at line 344 of file QuadTree.h.

344{ return _is_leaf; }

References GeoLib::QuadTree< POINT >::_is_leaf.

Referenced by GeoLib::QuadTree< POINT >::balance(), GeoLib::QuadTree< POINT >::getEastNeighbor(), GeoLib::QuadTree< POINT >::getLeaf(), GeoLib::QuadTree< POINT >::getNorthNeighbor(), GeoLib::QuadTree< POINT >::getSouthNeighbor(), GeoLib::QuadTree< POINT >::getWestNeighbor(), and GeoLib::QuadTree< POINT >::needToRefine().

◆ needToRefine()

template<typename POINT >

static bool GeoLib::QuadTree< POINT >::needToRefine ( QuadTree< POINT > const *const node )

inlinestaticprivate

Definition at line 550 of file QuadTree.h.

    {
        QuadTree<POINT>* north_neighbor(node->getNorthNeighbor());
        if (north_neighbor != nullptr)
        {
            if (north_neighbor->getDepth() == node->getDepth())
            {
                if (!north_neighbor->isLeaf())
                {
                    if (!(north_neighbor->getChild(Quadrant::SW))->isLeaf())
                    {
                        return true;
                    }
                    if (!(north_neighbor->getChild(Quadrant::SE))->isLeaf())
                    {
                        return true;
                    }
                }
            }
        }
 
        QuadTree<POINT>* west_neighbor(node->getWestNeighbor());
        if (west_neighbor != nullptr)
        {
            if (west_neighbor->getDepth() == node->getDepth())
            {
                if (!west_neighbor->isLeaf())
                {
                    if (!(west_neighbor->getChild(Quadrant::SE))->isLeaf())
                    {
                        return true;
                    }
                    if (!(west_neighbor->getChild(Quadrant::NE))->isLeaf())
                    {
                        return true;
                    }
                }
            }
        }
 
        QuadTree<POINT>* south_neighbor(node->getSouthNeighbor());
        if (south_neighbor != nullptr)
        {
            if (south_neighbor->getDepth() == node->getDepth())
            {
                if (!south_neighbor->isLeaf())
                {
                    if (!(south_neighbor->getChild(Quadrant::NE))->isLeaf())
                    {
                        return true;
                    }
                    if (!(south_neighbor->getChild(Quadrant::NW))->isLeaf())
                    {
                        return true;
                    }
                }
            }
        }
 
        QuadTree<POINT>* east_neighbor(node->getEastNeighbor());
        if (east_neighbor != nullptr)
        {
            if (east_neighbor->getDepth() == node->getDepth())
            {
                if (!east_neighbor->isLeaf())
                {
                    if (!(east_neighbor->getChild(Quadrant::NW))->isLeaf())
                    {
                        return true;
                    }
                    if (!(east_neighbor->getChild(Quadrant::SW))->isLeaf())
                    {
                        return true;
                    }
                }
            }
        }
        return false;
    }

References GeoLib::QuadTree< POINT >::getChild(), GeoLib::QuadTree< POINT >::getDepth(), GeoLib::QuadTree< POINT >::getEastNeighbor(), GeoLib::QuadTree< POINT >::getNorthNeighbor(), GeoLib::QuadTree< POINT >::getSouthNeighbor(), GeoLib::QuadTree< POINT >::getWestNeighbor(), GeoLib::QuadTree< POINT >::isLeaf(), GeoLib::QuadTree< POINT >::NE, GeoLib::QuadTree< POINT >::NW, GeoLib::QuadTree< POINT >::SE, and GeoLib::QuadTree< POINT >::SW.

Referenced by GeoLib::QuadTree< POINT >::balance().

◆ splitNode()

template<typename POINT >

void GeoLib::QuadTree< POINT >::splitNode ( )

inlineprivate

Definition at line 508 of file QuadTree.h.

    {
        // create children
        POINT mid_point(_ll);
        mid_point[0] += (_ur[0] - _ll[0]) / 2.0;
        mid_point[1] += (_ur[1] - _ll[1]) / 2.0;
        assert(_children[0] == nullptr);
        _children[0] = new QuadTree<POINT>(mid_point, _ur, this, _depth + 1,
                                           _max_points_per_leaf);  // north east
        POINT h_ll(mid_point), h_ur(mid_point);
        h_ll[0] = _ll[0];
        h_ur[1] = _ur[1];
        assert(_children[1] == nullptr);
        _children[1] = new QuadTree<POINT>(h_ll, h_ur, this, _depth + 1,
                                           _max_points_per_leaf);  // north west
        assert(_children[2] == nullptr);
        _children[2] = new QuadTree<POINT>(_ll, mid_point, this, _depth + 1,
                                           _max_points_per_leaf);  // south west
        h_ll = _ll;
        h_ll[0] = mid_point[0];
        h_ur = _ur;
        h_ur[1] = mid_point[1];
        assert(_children[3] == nullptr);
        _children[3] = new QuadTree<POINT>(h_ll, h_ur, this, _depth + 1,
                                           _max_points_per_leaf);  // south east
 
        // distribute points to sub quadtrees
        for (std::size_t j(0); j < _pnts.size(); j++)
        {
            bool nfound(true);
            for (std::size_t k(0); k < 4 && nfound; k++)
            {
                if (_children[k]->addPoint(_pnts[j]))
                {
                    nfound = false;
                }
            }
        }
        _pnts.clear();
        _is_leaf = false;
    }

References GeoLib::QuadTree< POINT >::QuadTree(), GeoLib::QuadTree< POINT >::_children, GeoLib::QuadTree< POINT >::_depth, GeoLib::QuadTree< POINT >::_is_leaf, GeoLib::QuadTree< POINT >::_ll, GeoLib::QuadTree< POINT >::_max_points_per_leaf, GeoLib::QuadTree< POINT >::_pnts, GeoLib::QuadTree< POINT >::_ur, GeoLib::QuadTree< POINT >::addPoint(), and GeoLib::POINT.

Referenced by GeoLib::QuadTree< POINT >::addPoint(), and GeoLib::QuadTree< POINT >::balance().

Member Data Documentation

◆ _children

template<typename POINT >

std::array<QuadTree<POINT>*, 4> GeoLib::QuadTree< POINT >::_children

private

Initial value:

= {nullptr, nullptr, nullptr,

nullptr}

children are sorted: _children[0] is north east child _children[1] is north west child _children[2] is south west child _children[3] is south east child

Definition at line 638 of file QuadTree.h.

638 {nullptr, nullptr, nullptr,

639 nullptr};

Referenced by GeoLib::QuadTree< POINT >::~QuadTree(), GeoLib::QuadTree< POINT >::addPoint(), GeoLib::QuadTree< POINT >::getChild(), GeoLib::QuadTree< POINT >::getChild(), GeoLib::QuadTree< POINT >::getLeaf(), GeoLib::QuadTree< POINT >::getLeafs(), GeoLib::QuadTree< POINT >::getMaxDepth(), GeoLib::QuadTree< POINT >::isChild(), and GeoLib::QuadTree< POINT >::splitNode().

◆ _depth

template<typename POINT >

std::size_t GeoLib::QuadTree< POINT >::_depth = 0

private

Definition at line 648 of file QuadTree.h.

Referenced by GeoLib::QuadTree< POINT >::QuadTree(), GeoLib::QuadTree< POINT >::getDepth(), GeoLib::QuadTree< POINT >::getMaxDepth(), and GeoLib::QuadTree< POINT >::splitNode().

◆ _father

template<typename POINT >

QuadTree<POINT>* GeoLib::QuadTree< POINT >::_father

private

Definition at line 630 of file QuadTree.h.

Referenced by GeoLib::QuadTree< POINT >::getEastNeighbor(), GeoLib::QuadTree< POINT >::getFather(), GeoLib::QuadTree< POINT >::getNorthNeighbor(), GeoLib::QuadTree< POINT >::getSouthNeighbor(), and GeoLib::QuadTree< POINT >::getWestNeighbor().

◆ _is_leaf

template<typename POINT >

bool GeoLib::QuadTree< POINT >::_is_leaf = true

private

Definition at line 650 of file QuadTree.h.

Referenced by GeoLib::QuadTree< POINT >::addPoint(), GeoLib::QuadTree< POINT >::getLeafs(), GeoLib::QuadTree< POINT >::isLeaf(), and GeoLib::QuadTree< POINT >::splitNode().

◆ _ll

template<typename POINT >

POINT GeoLib::QuadTree< POINT >::_ll

private

lower left point of the square

Definition at line 643 of file QuadTree.h.

Referenced by GeoLib::QuadTree< POINT >::QuadTree(), GeoLib::QuadTree< POINT >::addPoint(), GeoLib::QuadTree< POINT >::getLeaf(), GeoLib::QuadTree< POINT >::getSquarePoints(), and GeoLib::QuadTree< POINT >::splitNode().

◆ _max_points_per_leaf

template<typename POINT >

const std::size_t GeoLib::QuadTree< POINT >::_max_points_per_leaf

private

maximum number of points per leaf

Definition at line 654 of file QuadTree.h.

Referenced by GeoLib::QuadTree< POINT >::QuadTree(), GeoLib::QuadTree< POINT >::addPoint(), and GeoLib::QuadTree< POINT >::splitNode().

◆ _pnts

template<typename POINT >

std::vector<POINT const*> GeoLib::QuadTree< POINT >::_pnts

private

Definition at line 649 of file QuadTree.h.

Referenced by GeoLib::QuadTree< POINT >::addPoint(), GeoLib::QuadTree< POINT >::getPoints(), and GeoLib::QuadTree< POINT >::splitNode().

◆ _ur

template<typename POINT >

POINT GeoLib::QuadTree< POINT >::_ur

private

upper right point of the square

Definition at line 647 of file QuadTree.h.

Referenced by GeoLib::QuadTree< POINT >::QuadTree(), GeoLib::QuadTree< POINT >::addPoint(), GeoLib::QuadTree< POINT >::getLeaf(), GeoLib::QuadTree< POINT >::getSquarePoints(), and GeoLib::QuadTree< POINT >::splitNode().

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

Applications/FileIO/Gmsh/GMSHAdaptiveMeshDensity.h
GeoLib/QuadTree.h

Detailed Description

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Private Attributes

Member Enumeration Documentation

◆ Quadrant

Constructor & Destructor Documentation

◆ QuadTree() [1/2]

◆ ~QuadTree()

◆ QuadTree() [2/2]

Member Function Documentation

◆ addPoint()

◆ balance()

◆ getChild() [1/2]

◆ getChild() [2/2]

◆ getDepth()

◆ getEastNeighbor()

◆ getFather()

◆ getLeaf()

◆ getLeafs()

◆ getMaxDepth()

◆ getNorthNeighbor()

◆ getPoints()

◆ getSouthNeighbor()

◆ getSquarePoints()

◆ getWestNeighbor()

◆ isChild()

◆ isLeaf()

◆ needToRefine()

◆ splitNode()

Member Data Documentation

◆ _children

◆ _depth

◆ _father

◆ _is_leaf

◆ _ll

◆ _max_points_per_leaf

◆ _pnts

◆ _ur