GeoLib::QuadTree< POINT > Class Template Reference

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 27 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 30 of file QuadTree.h.

    {
        NE = 0,  
        NW,      
        SW,      
        SE       
    };

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 44 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 76 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 484 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 90 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 151 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 328 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 294 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 325 of file QuadTree.h.

{ return _depth; }

References _depth.

Referenced by balance(), and needToRefine().

getEastNeighbor()

template<typename POINT>

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

inlineprivate

Definition at line 408 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 292 of file QuadTree.h.

{ 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 254 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 231 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 305 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 340 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 246 of file QuadTree.h.

{ return _pnts; }

References _pnts.

getSouthNeighbor()

template<typename POINT>

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

inlineprivate

Definition at line 374 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 248 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 442 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 335 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 333 of file QuadTree.h.

{ 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 539 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 497 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 627 of file QuadTree.h.

                                              {nullptr, nullptr, nullptr,
                                                 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 637 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 619 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 639 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 632 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 643 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 638 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 636 of file QuadTree.h.

Referenced by QuadTree(), QuadTree(), addPoint(), getLeaf(), getSquarePoints(), and splitNode().

---

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

• GMSHAdaptiveMeshDensity.h
• QuadTree.h