OGS
GeoLib::QuadTree< POINT > Class Template Reference

## Detailed Description

template<typename 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)

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

void getMaxDepth (std::size_t &max_depth) const

std::size_t getDepth () const

## Private Member Functions

bool isLeaf () const

QuadTree< POINT > * getNorthNeighbor () const

QuadTree< POINT > * getSouthNeighbor () const

QuadTree< POINT > * getEastNeighbor () const

QuadTree< POINT > * getWestNeighbor () const

void splitNode ()

## Static Private Member Functions

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

## Private Attributes

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

template<typename POINT >
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

template<typename POINT >
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.

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
const std::size_t _max_points_per_leaf
std::size_t _depth

template<typename POINT >
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

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.

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

template<typename POINT >
inline

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.

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)
125 }
126
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 {
137 }
138 }
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

## ◆ 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 {
165 getLeafs(leaf_list);
166
167 while (!leaf_list.empty())
168 {
170 leaf_list.pop_front();
171
172 if (node->isLeaf())
173 {
174 if (needToRefine(node))
175 {
176 node->splitNode();
181
182 // check if north neighbor has to be refined
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
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
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
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)
void getLeafs(std::list< QuadTree< POINT > * > &leaf_list)

## ◆ getChild() [1/2]

template<typename POINT >
inlineprivate

Definition at line 339 of file QuadTree.h.

340 {
342 }

## ◆ getChild() [2/2]

template<typename POINT >
inline

Definition at line 305 of file QuadTree.h.

306 {
308 }

## ◆ 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; }

## ◆ getEastNeighbor()

template<typename POINT >
inlineprivate

Definition at line 419 of file QuadTree.h.

420 {
421 if (this->_father == nullptr)
422 { // root of QuadTree
423 return nullptr;
424 }
425
427 {
429 }
431 {
433 }
434
436 if (east_neighbor == nullptr)
437 {
438 return nullptr;
439 }
440 if (east_neighbor->isLeaf())
441 {
442 return east_neighbor;
443 }
444
446 {
448 }
449
451 }

## ◆ getFather()

template<typename POINT >
inline

Definition at line 303 of file QuadTree.h.

303{ return _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
279 ur);
280 }
281 else
282 { // NORTH
284 ur);
285 }
286 }
287 else // EAST
288 {
289 if (pnt[1] <= 0.5 * (_ur[1] + _ll[1]))
290 { // SOUTH
292 ur);
293 }
294 else
295 { // NORTH
297 ur);
298 }
299 }
300 }
301 }
bool isLeaf() const
void getLeaf(const POINT &pnt, POINT &ll, POINT &ur)

## ◆ getLeafs()

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

Parameters
 leaf_list list 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 }

## ◆ 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 }

## ◆ getNorthNeighbor()

template<typename POINT >
inlineprivate

Definition at line 351 of file QuadTree.h.

352 {
353 if (this->_father == nullptr)
354 { // root of QuadTree
355 return nullptr;
356 }
357
359 {
361 }
363 {
365 }
366
368 if (north_neighbor == nullptr)
369 {
370 return nullptr;
371 }
372 if (north_neighbor->isLeaf())
373 {
374 return north_neighbor;
375 }
376
378 {
380 }
381
383 }

## ◆ 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; }

## ◆ getSouthNeighbor()

template<typename POINT >
inlineprivate

Definition at line 385 of file QuadTree.h.

386 {
387 if (this->_father == nullptr)
388 { // root of QuadTree
389 return nullptr;
390 }
391
393 {
395 }
397 {
399 }
400
402 if (south_neighbor == nullptr)
403 {
404 return nullptr;
405 }
406 if (south_neighbor->isLeaf())
407 {
408 return south_neighbor;
409 }
410
412 {
414 }
415
417 }

## ◆ 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 }

## ◆ getWestNeighbor()

template<typename POINT >
inlineprivate

Definition at line 453 of file QuadTree.h.

454 {
455 if (this->_father == nullptr)
456 { // root of QuadTree
457 return nullptr;
458 }
459
461 {
463 }
465 {
467 }
468
470 if (west_neighbor == nullptr)
471 {
472 return nullptr;
473 }
474 if (west_neighbor->isLeaf())
475 {
476 return west_neighbor;
477 }
478
480 {
482 }
483
485 }

## ◆ isChild()

template<typename POINT >
inlineprivate

Definition at line 346 of file QuadTree.h.

347 {
349 }

## ◆ isLeaf()

template<typename POINT >
 bool GeoLib::QuadTree< POINT >::isLeaf ( ) const
inlineprivate

Definition at line 344 of file QuadTree.h.

344{ return _is_leaf; }

## ◆ 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 {
553 if (north_neighbor != nullptr)
554 {
555 if (north_neighbor->getDepth() == node->getDepth())
556 {
557 if (!north_neighbor->isLeaf())
558 {
560 {
561 return true;
562 }
564 {
565 return true;
566 }
567 }
568 }
569 }
570
572 if (west_neighbor != nullptr)
573 {
574 if (west_neighbor->getDepth() == node->getDepth())
575 {
576 if (!west_neighbor->isLeaf())
577 {
579 {
580 return true;
581 }
583 {
584 return true;
585 }
586 }
587 }
588 }
589
591 if (south_neighbor != nullptr)
592 {
593 if (south_neighbor->getDepth() == node->getDepth())
594 {
595 if (!south_neighbor->isLeaf())
596 {
598 {
599 return true;
600 }
602 {
603 return true;
604 }
605 }
606 }
607 }
608
610 if (east_neighbor != nullptr)
611 {
612 if (east_neighbor->getDepth() == node->getDepth())
613 {
614 if (!east_neighbor->isLeaf())
615 {
617 {
618 return true;
619 }
621 {
622 return true;
623 }
624 }
625 }
626 }
627 return false;
628 }

## ◆ 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 {
541 {
542 nfound = false;
543 }
544 }
545 }
546 _pnts.clear();
547 _is_leaf = false;
548 }

## ◆ _children

template<typename POINT >
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};

## ◆ _depth

template<typename POINT >
 std::size_t GeoLib::QuadTree< POINT >::_depth = 0
private

Definition at line 648 of file QuadTree.h.

## ◆ _father

template<typename POINT >
private

## ◆ _is_leaf

template<typename POINT >
 bool GeoLib::QuadTree< POINT >::_is_leaf = true
private

Definition at line 650 of file QuadTree.h.

## ◆ _ll

template<typename POINT >
private

lower left point of the square

Definition at line 643 of file QuadTree.h.

## ◆ _max_points_per_leaf

template<typename POINT >
private

maximum number of points per leaf

Definition at line 654 of file QuadTree.h.

## ◆ _pnts

template<typename POINT >
private

Definition at line 649 of file QuadTree.h.

## ◆ _ur

template<typename POINT >