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 _depth, _father, _ll, _max_points_per_leaf, _ur, DBUG(), and GeoLib::POINT.

Referenced by QuadTree(), balance(), getChild(), getChild(), getEastNeighbor(), getFather(), getLeafs(), getNorthNeighbor(), getSouthNeighbor(), getWestNeighbor(), isChild(), needToRefine(), and 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 _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)
    {
    }

References QuadTree(), _depth, _father, _ll, _max_points_per_leaf, _ur, and GeoLib::POINT.

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 _children, _is_leaf, _ll, _max_points_per_leaf, _pnts, _ur, GeoLib::POINT, and splitNode().

Referenced by 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);
                            }
                        }
                    }
                }
            }
        }
    }

References QuadTree(), getChild(), getDepth(), getEastNeighbor(), getLeafs(), getNorthNeighbor(), getSouthNeighbor(), getWestNeighbor(), isLeaf(), NE, needToRefine(), NW, SE, splitNode(), and SW.

◆ 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 QuadTree(), and _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 QuadTree(), and _children.

Referenced by balance(), getEastNeighbor(), getNorthNeighbor(), getSouthNeighbor(), getWestNeighbor(), and 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 _depth.

Referenced by balance(), and 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 QuadTree(), _father, getChild(), isLeaf(), NE, NW, SE, and SW.

Referenced by balance(), and 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 QuadTree(), and _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 _children, _ll, _ur, getLeaf(), isLeaf(), NE, NW, GeoLib::POINT, SE, and SW.

Referenced by getLeaf().

◆ 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 QuadTree(), _children, and _is_leaf.

Referenced by balance().

◆ 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 _children, and _depth.

◆ 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 QuadTree(), _father, getChild(), isLeaf(), NE, NW, SE, and SW.

Referenced by balance(), and 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 _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 QuadTree(), _father, getChild(), isLeaf(), NE, NW, SE, and SW.

Referenced by balance(), and 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 _ll, _ur, and GeoLib::POINT.

◆ 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 QuadTree(), _father, getChild(), isLeaf(), NE, NW, SE, and SW.

Referenced by balance(), and 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 QuadTree(), and _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 _is_leaf.

Referenced by balance(), getEastNeighbor(), getLeaf(), getNorthNeighbor(), getSouthNeighbor(), getWestNeighbor(), and needToRefine().

◆ needToRefine()

template<typename POINT>

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 QuadTree(), getChild(), getDepth(), getEastNeighbor(), getNorthNeighbor(), getSouthNeighbor(), getWestNeighbor(), isLeaf(), NE, NW, SE, and SW.

Referenced by 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 QuadTree(), _children, _depth, _is_leaf, _ll, _max_points_per_leaf, _pnts, _ur, addPoint(), and GeoLib::POINT.

Referenced by addPoint(), and 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 ~QuadTree(), addPoint(), getChild(), getChild(), getLeaf(), getLeafs(), getMaxDepth(), isChild(), and splitNode().

◆ _depth

template<typename POINT>

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

private

Definition at line 648 of file QuadTree.h.

Referenced by QuadTree(), QuadTree(), getDepth(), getMaxDepth(), and splitNode().

◆ _father

template<typename POINT>

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

private

Definition at line 630 of file QuadTree.h.

Referenced by QuadTree(), QuadTree(), getEastNeighbor(), getFather(), getNorthNeighbor(), getSouthNeighbor(), and getWestNeighbor().

◆ _is_leaf

template<typename POINT>

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

private

Definition at line 650 of file QuadTree.h.

Referenced by addPoint(), getLeafs(), isLeaf(), and 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 QuadTree(), QuadTree(), addPoint(), getLeaf(), getSquarePoints(), and 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 QuadTree(), QuadTree(), addPoint(), and splitNode().

◆ _pnts

template<typename POINT>

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

private

Definition at line 649 of file QuadTree.h.

Referenced by addPoint(), getPoints(), and 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 QuadTree(), QuadTree(), addPoint(), getLeaf(), getSquarePoints(), and 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