53 QuadTree(POINT ll, POINT ur, std::size_t max_points_per_leaf)
71 "QuadTree(): lower left: ({:f},{:f},{:f}), upper right: "
72 "({:f},{:f},{:f}), depth: {:d}",
101 if ((*pnt)[0] <
_ll[0])
105 if ((*pnt)[0] >=
_ur[0])
109 if ((*pnt)[1] <
_ll[1])
113 if ((*pnt)[1] >=
_ur[1])
121 if (child->addPoint(pnt))
130 bool pnt_in_quadtree (
false);
131 for (std::size_t k(0); k <
_pnts.size() && !pnt_in_quadtree; k++) {
132 const double v0((*(
_pnts[k]))[0] - (*pnt)[0]);
133 const double v1((*(
_pnts[k]))[1] - (*pnt)[1]);
134 const double sqr_dist (v0*v0 + v1*v1);
135 if (sqr_dist < std::numeric_limits<double>::epsilon())
137 pnt_in_quadtree =
true;
140 if (!pnt_in_quadtree)
142 _pnts.push_back (pnt);
165 std::list<QuadTree<POINT>*> leaf_list;
168 while (!leaf_list.empty())
171 leaf_list.pop_front ();
185 if (north_neighbor !=
nullptr)
189 if (north_neighbor->
isLeaf())
191 leaf_list.push_back(north_neighbor);
198 if (west_neighbor !=
nullptr)
202 if (west_neighbor->
isLeaf())
204 leaf_list.push_back(west_neighbor);
211 if (south_neighbor !=
nullptr)
215 if (south_neighbor->
isLeaf())
217 leaf_list.push_back(south_neighbor);
224 if (east_neighbor !=
nullptr)
228 if (east_neighbor->
isLeaf())
230 leaf_list.push_back(east_neighbor);
247 leaf_list.push_back (
this);
253 child->getLeafs(leaf_list);
266 void getLeaf (
const POINT& pnt, POINT& ll, POINT& ur)
275 if (pnt[0] <= 0.5 * (
_ur[0] +
_ll[0]))
277 if (pnt[1] <= 0.5 * (
_ur[1] +
_ll[1]))
289 if (pnt[1] <= 0.5 * (
_ur[1] +
_ll[1]))
325 child->getMaxDepth(max_depth);
339 return _children[
static_cast<int>(quadrant)];
346 return _children[
static_cast<int>(quadrant)] == tree;
366 if (north_neighbor ==
nullptr)
370 if (north_neighbor->
isLeaf())
372 return north_neighbor;
400 if (south_neighbor ==
nullptr)
404 if (south_neighbor->
isLeaf())
406 return south_neighbor;
434 if (east_neighbor ==
nullptr)
438 if (east_neighbor->
isLeaf())
440 return east_neighbor;
468 if (west_neighbor ==
nullptr)
472 if (west_neighbor->
isLeaf())
474 return west_neighbor;
498 std::size_t max_points_per_leaf)
511 mid_point[0] += (
_ur[0] -
_ll[0]) / 2.0;
512 mid_point[1] += (
_ur[1] -
_ll[1]) / 2.0;
515 POINT h_ll(mid_point), h_ur(mid_point);
523 h_ll[0] = mid_point[0];
525 h_ur[1] = mid_point[1];
530 for (std::size_t j(0); j <
_pnts.size(); j++) {
532 for (std::size_t k(0); k < 4 && nfound; k++)
547 if (north_neighbor !=
nullptr)
551 if (!north_neighbor->
isLeaf ())
566 if (west_neighbor !=
nullptr)
570 if (!west_neighbor->
isLeaf ())
585 if (south_neighbor !=
nullptr)
589 if (!south_neighbor->
isLeaf())
604 if (east_neighbor !=
nullptr)
608 if (!east_neighbor->
isLeaf ())
632 std::array<QuadTree<POINT>*, 4>
_children = {
nullptr,
nullptr,
nullptr,
void DBUG(char const *fmt, Args const &... args)
QuadTree< POINT > * _father
QuadTree< POINT > * getChild(Quadrant quadrant)
bool isChild(QuadTree< POINT > const *const tree, Quadrant quadrant) const
QuadTree< POINT > * getWestNeighbor() const
std::array< QuadTree< POINT > *, 4 > _children
QuadTree< POINT > * getEastNeighbor() const
std::size_t getDepth() const
void getMaxDepth(std::size_t &max_depth) const
const std::vector< POINT const * > & getPoints() const
void getLeafs(std::list< QuadTree< POINT > * > &leaf_list)
QuadTree< POINT > * getNorthNeighbor() const
static bool needToRefine(QuadTree< POINT > *node)
const std::size_t _max_points_per_leaf
std::vector< POINT const * > _pnts
void getLeaf(const POINT &pnt, POINT &ll, POINT &ur)
bool addPoint(POINT const *pnt)
QuadTree< POINT > const * getFather() const
QuadTree< POINT > * getSouthNeighbor() const
QuadTree< POINT > const * getChild(Quadrant quadrant) const
void getSquarePoints(POINT &ll, POINT &ur) const
QuadTree(POINT ll, POINT ur, QuadTree *father, std::size_t depth, std::size_t max_points_per_leaf)
QuadTree(POINT ll, POINT ur, std::size_t max_points_per_leaf)