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

42 {
43 NE = 0,
44 NW,
45 SW,
46 SE
47 };

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
lllower left point of the square
urupper right point of the square
max_points_per_leafmaximum number of points per leaf

Definition at line 55 of file QuadTree.h.

56 : _father(nullptr),
57 _ll(std::move(ll)),
58 _ur(std::move(ur)),
59 _max_points_per_leaf(max_points_per_leaf)
60 {
61 assert(_max_points_per_leaf > 0);
62
63 if ((_ur[0] - _ll[0]) > (_ur[1] - _ll[1]))
64 {
65 _ur[1] = _ll[1] + _ur[0] - _ll[0];
66 }
67 else
68 {
69 _ur[0] = _ll[0] + _ur[1] - _ll[1];
70 }
71
72 DBUG(
73 "QuadTree(): lower left: ({:f},{:f},{:f}), upper right: "
74 "({:f},{:f},{:f}), depth: {:d}",
75 _ll[0],
76 _ll[1],
77 _ll[2],
78 _ur[0],
79 _ur[1],
80 _ur[2],
81 _depth);
82 }
void DBUG(fmt::format_string< Args... > fmt, Args &&... args)
Definition Logging.h:30
QuadTree< POINT > * _father
Definition QuadTree.h:630
const std::size_t _max_points_per_leaf
Definition QuadTree.h:654
std::size_t _depth
Definition QuadTree.h:648

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

88 {
89 for (auto const& child : _children)
90 {
91 delete child;
92 }
93 }
std::array< QuadTree< POINT > *, 4 > _children
Definition QuadTree.h:638

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
lllower left point
urupper right point
fatherfather in the tree
depthdepth of the node
max_points_per_leafmaximum number of points per leaf

Definition at line 495 of file QuadTree.h.

500 : _father(father),
501 _ll(std::move(ll)),
502 _ur(std::move(ur)),
503 _depth(depth),
504 _max_points_per_leaf(max_points_per_leaf)
505 {
506 }

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
pntthe point
Returns
If the point can be inserted the method returns true, else false.

Definition at line 101 of file QuadTree.h.

102 {
103 if ((*pnt)[0] < _ll[0])
104 {
105 return false;
106 }
107 if ((*pnt)[0] >= _ur[0])
108 {
109 return false;
110 }
111 if ((*pnt)[1] < _ll[1])
112 {
113 return false;
114 }
115 if ((*pnt)[1] >= _ur[1])
116 {
117 return false;
118 }
119
120 if (!_is_leaf)
121 {
122 return std::any_of(begin(_children), end(_children),
123 [&pnt](auto* child)
124 { return child->addPoint(pnt); });
125 }
126
127 // check if point is already in quadtree
128 bool pnt_in_quadtree(false);
129 for (std::size_t k(0); k < _pnts.size() && !pnt_in_quadtree; k++)
130 {
131 const double v0((*(_pnts[k]))[0] - (*pnt)[0]);
132 const double v1((*(_pnts[k]))[1] - (*pnt)[1]);
133 const double sqr_dist(v0 * v0 + v1 * v1);
134 if (sqr_dist < std::numeric_limits<double>::epsilon())
135 {
136 pnt_in_quadtree = true;
137 }
138 }
139 if (!pnt_in_quadtree)
140 {
141 _pnts.push_back(pnt);
142 }
143 else
144 {
145 return false;
146 }
147
148 if (_pnts.size() > _max_points_per_leaf)
149 {
150 splitNode();
151 }
152 return true;
153 }
std::vector< POINT const * > _pnts
Definition QuadTree.h:649

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.

163 {
164 std::list<QuadTree<POINT>*> leaf_list;
165 getLeafs(leaf_list);
166
167 while (!leaf_list.empty())
168 {
169 QuadTree<POINT>* node(leaf_list.front());
170 leaf_list.pop_front();
171
172 if (node->isLeaf())
173 {
174 if (needToRefine(node))
175 {
176 node->splitNode();
177 leaf_list.push_back(node->getChild(Quadrant::NE));
178 leaf_list.push_back(node->getChild(Quadrant::NW));
179 leaf_list.push_back(node->getChild(Quadrant::SW));
180 leaf_list.push_back(node->getChild(Quadrant::SE));
181
182 // check if north neighbor has to be refined
183 QuadTree<POINT>* north_neighbor(node->getNorthNeighbor());
184 if (north_neighbor != nullptr)
185 {
186 if (north_neighbor->getDepth() < node->getDepth())
187 {
188 if (north_neighbor->isLeaf())
189 {
190 leaf_list.push_back(north_neighbor);
191 }
192 }
193 }
194
195 // check if west neighbor has to be refined
196 QuadTree<POINT>* west_neighbor(node->getWestNeighbor());
197 if (west_neighbor != nullptr)
198 {
199 if (west_neighbor->getDepth() < node->getDepth())
200 {
201 if (west_neighbor->isLeaf())
202 {
203 leaf_list.push_back(west_neighbor);
204 }
205 }
206 }
207
208 // check if south neighbor has to be refined
209 QuadTree<POINT>* south_neighbor(node->getSouthNeighbor());
210 if (south_neighbor != nullptr)
211 {
212 if (south_neighbor->getDepth() < node->getDepth())
213 {
214 if (south_neighbor->isLeaf())
215 {
216 leaf_list.push_back(south_neighbor);
217 }
218 }
219 }
220
221 // check if east neighbor has to be refined
222 QuadTree<POINT>* east_neighbor(node->getEastNeighbor());
223 if (east_neighbor != nullptr)
224 {
225 if (east_neighbor->getDepth() < node->getDepth())
226 {
227 if (east_neighbor->isLeaf())
228 {
229 leaf_list.push_back(east_neighbor);
230 }
231 }
232 }
233 }
234 }
235 }
236 }
static bool needToRefine(QuadTree< POINT > const *const node)
Definition QuadTree.h:550
void getLeafs(std::list< QuadTree< POINT > * > &leaf_list)
Definition QuadTree.h:242

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

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.

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

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

◆ getChild() [2/2]

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

420 {
421 if (this->_father == nullptr)
422 { // root of QuadTree
423 return nullptr;
424 }
425
426 if (this->_father->isChild(this, Quadrant::NW))
427 {
428 return this->_father->getChild(Quadrant::NE);
429 }
430 if (this->_father->isChild(this, Quadrant::SW))
431 {
432 return this->_father->getChild(Quadrant::SE);
433 }
434
435 QuadTree<POINT>* east_neighbor(this->_father->getEastNeighbor());
436 if (east_neighbor == nullptr)
437 {
438 return nullptr;
439 }
440 if (east_neighbor->isLeaf())
441 {
442 return east_neighbor;
443 }
444
445 if (this->_father->isChild(this, Quadrant::SE))
446 {
447 return east_neighbor->getChild(Quadrant::SW);
448 }
449
450 return east_neighbor->getChild(Quadrant::NW);
451 }

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.

266 {
267 if (this->isLeaf())
268 {
269 ll = _ll;
270 ur = _ur;
271 }
272 else
273 {
274 if (pnt[0] <= 0.5 * (_ur[0] + _ll[0])) // WEST
275 {
276 if (pnt[1] <= 0.5 * (_ur[1] + _ll[1]))
277 { // SOUTH
278 _children[static_cast<int>(Quadrant::SW)]->getLeaf(pnt, ll,
279 ur);
280 }
281 else
282 { // NORTH
283 _children[static_cast<int>(Quadrant::NW)]->getLeaf(pnt, ll,
284 ur);
285 }
286 }
287 else // EAST
288 {
289 if (pnt[1] <= 0.5 * (_ur[1] + _ll[1]))
290 { // SOUTH
291 _children[static_cast<int>(Quadrant::SE)]->getLeaf(pnt, ll,
292 ur);
293 }
294 else
295 { // NORTH
296 _children[static_cast<int>(Quadrant::NE)]->getLeaf(pnt, ll,
297 ur);
298 }
299 }
300 }
301 }
bool isLeaf() const
Definition QuadTree.h:344
void getLeaf(const POINT &pnt, POINT &ll, POINT &ur)
Definition QuadTree.h:265

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_listlist of leafs

Definition at line 242 of file QuadTree.h.

243 {
244 if (_is_leaf)
245 {
246 leaf_list.push_back(this);
247 }
248 else
249 {
250 for (auto& child : _children)
251 {
252 child->getLeafs(leaf_list);
253 }
254 }
255 }

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.

317 {
318 if (max_depth < _depth)
319 {
320 max_depth = _depth;
321 }
322
323 for (auto& child : _children)
324 {
325 if (child)
326 {
327 child->getMaxDepth(max_depth);
328 }
329 }
330 }

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.

352 {
353 if (this->_father == nullptr)
354 { // root of QuadTree
355 return nullptr;
356 }
357
358 if (this->_father->isChild(this, Quadrant::SW))
359 {
360 return this->_father->getChild(Quadrant::NW);
361 }
362 if (this->_father->isChild(this, Quadrant::SE))
363 {
364 return this->_father->getChild(Quadrant::NE);
365 }
366
367 QuadTree<POINT>* north_neighbor(this->_father->getNorthNeighbor());
368 if (north_neighbor == nullptr)
369 {
370 return nullptr;
371 }
372 if (north_neighbor->isLeaf())
373 {
374 return north_neighbor;
375 }
376
377 if (this->_father->isChild(this, Quadrant::NW))
378 {
379 return north_neighbor->getChild(Quadrant::SW);
380 }
381
382 return north_neighbor->getChild(Quadrant::SE);
383 }

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.

386 {
387 if (this->_father == nullptr)
388 { // root of QuadTree
389 return nullptr;
390 }
391
392 if (this->_father->isChild(this, Quadrant::NW))
393 {
394 return this->_father->getChild(Quadrant::SW);
395 }
396 if (this->_father->isChild(this, Quadrant::NE))
397 {
398 return this->_father->getChild(Quadrant::SE);
399 }
400
401 QuadTree<POINT>* south_neighbor(this->_father->getSouthNeighbor());
402 if (south_neighbor == nullptr)
403 {
404 return nullptr;
405 }
406 if (south_neighbor->isLeaf())
407 {
408 return south_neighbor;
409 }
410
411 if (this->_father->isChild(this, Quadrant::SW))
412 {
413 return south_neighbor->getChild(Quadrant::NW);
414 }
415
416 return south_neighbor->getChild(Quadrant::NE);
417 }

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.

260 {
261 ll = _ll;
262 ur = _ur;
263 }

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.

454 {
455 if (this->_father == nullptr)
456 { // root of QuadTree
457 return nullptr;
458 }
459
460 if (this->_father->isChild(this, Quadrant::NE))
461 {
462 return this->_father->getChild(Quadrant::NW);
463 }
464 if (this->_father->isChild(this, Quadrant::SE))
465 {
466 return this->_father->getChild(Quadrant::SW);
467 }
468
469 QuadTree<POINT>* west_neighbor(this->_father->getWestNeighbor());
470 if (west_neighbor == nullptr)
471 {
472 return nullptr;
473 }
474 if (west_neighbor->isLeaf())
475 {
476 return west_neighbor;
477 }
478
479 if (this->_father->isChild(this, Quadrant::SW))
480 {
481 return west_neighbor->getChild(Quadrant::SE);
482 }
483
484 return west_neighbor->getChild(Quadrant::NE);
485 }

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.

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

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

◆ isLeaf()

◆ needToRefine()

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

Definition at line 550 of file QuadTree.h.

551 {
552 QuadTree<POINT>* north_neighbor(node->getNorthNeighbor());
553 if (north_neighbor != nullptr)
554 {
555 if (north_neighbor->getDepth() == node->getDepth())
556 {
557 if (!north_neighbor->isLeaf())
558 {
559 if (!(north_neighbor->getChild(Quadrant::SW))->isLeaf())
560 {
561 return true;
562 }
563 if (!(north_neighbor->getChild(Quadrant::SE))->isLeaf())
564 {
565 return true;
566 }
567 }
568 }
569 }
570
571 QuadTree<POINT>* west_neighbor(node->getWestNeighbor());
572 if (west_neighbor != nullptr)
573 {
574 if (west_neighbor->getDepth() == node->getDepth())
575 {
576 if (!west_neighbor->isLeaf())
577 {
578 if (!(west_neighbor->getChild(Quadrant::SE))->isLeaf())
579 {
580 return true;
581 }
582 if (!(west_neighbor->getChild(Quadrant::NE))->isLeaf())
583 {
584 return true;
585 }
586 }
587 }
588 }
589
590 QuadTree<POINT>* south_neighbor(node->getSouthNeighbor());
591 if (south_neighbor != nullptr)
592 {
593 if (south_neighbor->getDepth() == node->getDepth())
594 {
595 if (!south_neighbor->isLeaf())
596 {
597 if (!(south_neighbor->getChild(Quadrant::NE))->isLeaf())
598 {
599 return true;
600 }
601 if (!(south_neighbor->getChild(Quadrant::NW))->isLeaf())
602 {
603 return true;
604 }
605 }
606 }
607 }
608
609 QuadTree<POINT>* east_neighbor(node->getEastNeighbor());
610 if (east_neighbor != nullptr)
611 {
612 if (east_neighbor->getDepth() == node->getDepth())
613 {
614 if (!east_neighbor->isLeaf())
615 {
616 if (!(east_neighbor->getChild(Quadrant::NW))->isLeaf())
617 {
618 return true;
619 }
620 if (!(east_neighbor->getChild(Quadrant::SW))->isLeaf())
621 {
622 return true;
623 }
624 }
625 }
626 }
627 return false;
628 }

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.

509 {
510 // create children
511 POINT mid_point(_ll);
512 mid_point[0] += (_ur[0] - _ll[0]) / 2.0;
513 mid_point[1] += (_ur[1] - _ll[1]) / 2.0;
514 assert(_children[0] == nullptr);
515 _children[0] = new QuadTree<POINT>(mid_point, _ur, this, _depth + 1,
516 _max_points_per_leaf); // north east
517 POINT h_ll(mid_point), h_ur(mid_point);
518 h_ll[0] = _ll[0];
519 h_ur[1] = _ur[1];
520 assert(_children[1] == nullptr);
521 _children[1] = new QuadTree<POINT>(h_ll, h_ur, this, _depth + 1,
522 _max_points_per_leaf); // north west
523 assert(_children[2] == nullptr);
524 _children[2] = new QuadTree<POINT>(_ll, mid_point, this, _depth + 1,
525 _max_points_per_leaf); // south west
526 h_ll = _ll;
527 h_ll[0] = mid_point[0];
528 h_ur = _ur;
529 h_ur[1] = mid_point[1];
530 assert(_children[3] == nullptr);
531 _children[3] = new QuadTree<POINT>(h_ll, h_ur, this, _depth + 1,
532 _max_points_per_leaf); // south east
533
534 // distribute points to sub quadtrees
535 for (std::size_t j(0); j < _pnts.size(); j++)
536 {
537 bool nfound(true);
538 for (std::size_t k(0); k < 4 && nfound; k++)
539 {
540 if (_children[k]->addPoint(_pnts[j]))
541 {
542 nfound = false;
543 }
544 }
545 }
546 _pnts.clear();
547 _is_leaf = false;
548 }
bool addPoint(POINT const *pnt)
Definition QuadTree.h:101

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

◆ _father

◆ _is_leaf

◆ _ll

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

◆ _ur


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