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 37 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 > *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 GeoLib::QuadTree::Quadrant

strong

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

Definition at line 40 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 53 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().

◆ ~QuadTree()

template<typename POINT >

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

inline

destructor

Definition at line 85 of file QuadTree.h.

     {
         for (auto& 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

Returns

Definition at line 494 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 99 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) {
             for (auto& child : _children)
             {
                 if (child->addPoint(pnt))
                 {
                     return true;
                 }
             }
             return false;
         }
  
         // 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 163 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 337 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 304 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 334 of file QuadTree.h.

334 { 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 417 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 302 of file QuadTree.h.

302 { 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 266 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 >::isLeaf(), GeoLib::QuadTree< POINT >::NE, GeoLib::QuadTree< POINT >::NW, GeoLib::QuadTree< POINT >::SE, and GeoLib::QuadTree< POINT >::SW.

Referenced by 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 243 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 314 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 349 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 258 of file QuadTree.h.

258 { return _pnts; }

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

◆ getSouthNeighbor()

template<typename POINT >

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

inlineprivate

Definition at line 383 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 260 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 451 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 344 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 342 of file QuadTree.h.

342 { 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 > * node )

inlinestaticprivate

Definition at line 544 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 507 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 >::_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 632 of file QuadTree.h.

Referenced by GeoLib::QuadTree< POINT >::~QuadTree(), GeoLib::QuadTree< POINT >::addPoint(), 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 642 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 624 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 644 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 637 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 648 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 643 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 641 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

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

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

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