OGS
GeoLib::OctTree< POINT, MAX_POINTS > Class Template Reference

Detailed Description

template<typename POINT, std::size_t MAX_POINTS>
class GeoLib::OctTree< POINT, MAX_POINTS >
Template Parameters
POINTpoint data type the OctTree will use
MAX_POINTSmaximum number of pointers of POINT in a leaf

Definition at line 27 of file OctTree.h.

#include <OctTree.h>

Public Member Functions

virtual ~OctTree ()
 
bool addPoint (POINT *pnt, POINT *&ret_pnt)
 
template<typename T >
void getPointsInRange (T const &min, T const &max, std::vector< POINT * > &pnts) const
 
Eigen::Vector3d const & getLowerLeftCornerPoint () const
 
Eigen::Vector3d const & getUpperRightCornerPoint () const
 
OctTree< POINT, MAX_POINTS > const * getChild (std::size_t i) const
 
std::vector< POINT * > const & getPointVector () const
 

Static Public Member Functions

static OctTree< POINT, MAX_POINTS > * createOctTree (Eigen::Vector3d ll, Eigen::Vector3d ur, double eps=std::numeric_limits< double >::epsilon())
 

Private Types

enum class  Quadrant : std::int8_t {
  NEL = 0 , NWL , SWL , SEL ,
  NEU , NWU , SWU , SEU
}
 

Private Member Functions

 OctTree (Eigen::Vector3d const &ll, Eigen::Vector3d const &ur, double eps)
 
bool addPoint_ (POINT *pnt, POINT *&ret_pnt)
 
bool addPointToChild (POINT *pnt)
 
void splitNode (POINT *pnt)
 
bool isOutside (POINT *pnt) const
 

Private Attributes

std::array< OctTree< POINT, MAX_POINTS > *, 8 > _children
 
Eigen::Vector3d const _ll
 lower left front face point of the cube More...
 
Eigen::Vector3d const _ur
 upper right back face point of the cube More...
 
std::vector< POINT * > _pnts
 vector of pointers to POINT objects More...
 
bool _is_leaf
 flag if this OctTree is a leaf More...
 
double const _eps
 threshold for point uniqueness More...
 

Member Enumeration Documentation

◆ Quadrant

template<typename POINT , std::size_t MAX_POINTS>
enum class GeoLib::OctTree::Quadrant : std::int8_t
strongprivate
Enumerator
NEL 

north east lower

NWL 

north west lower

SWL 

south west lower

SEL 

south east lower

NEU 

south west upper

NWU 

south west upper

SWU 

south west upper

SEU 

south east upper

Definition at line 93 of file OctTree.h.

94 {
95 NEL = 0,
96 NWL,
97 SWL,
98 SEL,
99 NEU,
100 NWU,
101 SWU,
102 SEU
103 };

Constructor & Destructor Documentation

◆ ~OctTree()

template<typename POINT , std::size_t MAX_POINTS>
GeoLib::OctTree< POINT, MAX_POINTS >::~OctTree
virtual

Destroys the children of this node.

Attention
Does not destroy the pointers to the managed objects.

Definition at line 68 of file OctTree-impl.h.

69{
70 for (auto c : _children)
71 {
72 delete c;
73 }
74}
std::array< OctTree< POINT, MAX_POINTS > *, 8 > _children
Definition: OctTree.h:139

References MaterialPropertyLib::c.

◆ OctTree()

template<typename POINT , std::size_t MAX_POINTS>
GeoLib::OctTree< POINT, MAX_POINTS >::OctTree ( Eigen::Vector3d const &  ll,
Eigen::Vector3d const &  ur,
double  eps 
)
private

private constructor

Parameters
lllower left point
urupper right point
epsthe euclidean distance as a threshold to make objects unique

Definition at line 169 of file OctTree-impl.h.

171 : _ll(ll), _ur(ur), _is_leaf(true), _eps(eps)
172{
173 _children.fill(nullptr);
174}
Eigen::Vector3d const _ur
upper right back face point of the cube
Definition: OctTree.h:143
bool _is_leaf
flag if this OctTree is a leaf
Definition: OctTree.h:147
double const _eps
threshold for point uniqueness
Definition: OctTree.h:149
Eigen::Vector3d const _ll
lower left front face point of the cube
Definition: OctTree.h:141

References GeoLib::OctTree< POINT, MAX_POINTS >::_children.

Member Function Documentation

◆ addPoint()

template<typename POINT , std::size_t MAX_POINTS>
bool GeoLib::OctTree< POINT, MAX_POINTS >::addPoint ( POINT *  pnt,
POINT *&  ret_pnt 
)

This method adds the given point to the OctTree. If necessary, new OctTree nodes will be inserted deploying a split of the corresponding OctTree node.

Parameters
pntthe pointer to a point that should be inserted
ret_pntthe pointer to a point in the OctTree. Three cases can occur: (1) ret_pnt is nullptr: the given point (pnt) is outside of the OctTree domain (2) ret_pnt is equal to pnt: the point is added to the OctTree (3) In case ret_pnt is neither equal to pnt nor equal to nullptr, another item within the eps distance is already in the OctTree and the pointer to this object is returned.
Returns
If the point can be inserted the method returns true, else false.

Definition at line 77 of file OctTree-impl.h.

78{
79 // first do a range query using a epsilon box around the point pnt
80 std::vector<POINT*> query_pnts;
81 Eigen::Vector3d const min = pnt->asEigenVector3d().array() - _eps;
82 Eigen::Vector3d const max = pnt->asEigenVector3d().array() + _eps;
83 getPointsInRange(min, max, query_pnts);
84 auto const it =
85 std::find_if(query_pnts.begin(), query_pnts.end(),
86 [pnt, this](auto const* p)
87 {
88 return (p->asEigenVector3d() - pnt->asEigenVector3d())
89 .squaredNorm() < _eps * _eps;
90 });
91 if (it != query_pnts.end())
92 {
93 ret_pnt = *it;
94 return false;
95 }
96
97 // the point pnt is not yet in the OctTree
98 if (isOutside(pnt))
99 {
100 ret_pnt = nullptr;
101 return false;
102 }
103
104 // at this place it holds true that the point is within [_ll, _ur]
105 if (!_is_leaf)
106 {
107 for (auto c : _children)
108 {
109 if (c->addPoint_(pnt, ret_pnt))
110 {
111 return true;
112 }
113 if (ret_pnt != nullptr)
114 {
115 return false;
116 }
117 }
118 }
119
120 ret_pnt = pnt;
121
122 if (_pnts.size() < MAX_POINTS)
123 {
124 _pnts.push_back(pnt);
125 }
126 else
127 { // i.e. _pnts.size () == MAX_POINTS
128 splitNode(pnt);
129 _pnts.clear();
130 }
131 return true;
132}
void splitNode(POINT *pnt)
Definition: OctTree-impl.h:235
void getPointsInRange(T const &min, T const &max, std::vector< POINT * > &pnts) const
Definition: OctTree-impl.h:136
std::vector< POINT * > _pnts
vector of pointers to POINT objects
Definition: OctTree.h:145
bool isOutside(POINT *pnt) const
Definition: OctTree-impl.h:318

References MaterialPropertyLib::c.

◆ addPoint_()

template<typename POINT , std::size_t MAX_POINTS>
bool GeoLib::OctTree< POINT, MAX_POINTS >::addPoint_ ( POINT *  pnt,
POINT *&  ret_pnt 
)
private

This method tries to add the given point to the OctTree. If necessary for adding the point, new nodes will be inserted into the OctTree.

Parameters
pnt,ret_pntsee documentation of addPoint()
Returns
If the point can be inserted the method returns true, else false.

Definition at line 177 of file OctTree-impl.h.

178{
179 if (isOutside(pnt))
180 {
181 ret_pnt = nullptr;
182 return false;
183 }
184
185 // at this place it holds true that the point is within [_ll, _ur]
186 if (!_is_leaf)
187 {
188 for (auto c : _children)
189 {
190 if (c->addPoint_(pnt, ret_pnt))
191 {
192 return true;
193 }
194 if (ret_pnt != nullptr)
195 {
196 return false;
197 }
198 }
199 }
200
201 ret_pnt = pnt;
202 if (_pnts.size() < MAX_POINTS)
203 {
204 _pnts.push_back(pnt);
205 }
206 else
207 { // i.e. _pnts.size () == MAX_POINTS
208 splitNode(pnt);
209 _pnts.clear();
210 }
211 return true;
212}

References MaterialPropertyLib::c.

◆ addPointToChild()

template<typename POINT , std::size_t MAX_POINTS>
bool GeoLib::OctTree< POINT, MAX_POINTS >::addPointToChild ( POINT *  pnt)
private

This method adds the given point to the OctTree. If necessary, the OctTree will be extended.

Parameters
pntthe point
Returns
If the point can be inserted the method returns true, else false.

Definition at line 215 of file OctTree-impl.h.

216{
217 if (isOutside(pnt))
218 {
219 return false;
220 }
221
222 if (_pnts.size() < MAX_POINTS)
223 {
224 _pnts.push_back(pnt);
225 }
226 else
227 { // i.e. _pnts.size () == MAX_POINTS
228 splitNode(pnt);
229 _pnts.clear();
230 }
231 return true;
232}

◆ createOctTree()

template<typename POINT , std::size_t MAX_POINTS>
OctTree< POINT, MAX_POINTS > * GeoLib::OctTree< POINT, MAX_POINTS >::createOctTree ( Eigen::Vector3d  ll,
Eigen::Vector3d  ur,
double  eps = std::numeric_limits<double>::epsilon() 
)
static

Create an OctTree object. The arguments ll and ur are used to compute a cube domain the OctTree will living in.

Attention
This cubic domain can not be resized during the life time of the OctTree.
Parameters
lllower left front point, used for computation of cubic domain
urupper right back point, used for computation of cubic domain
epsthe euclidean distance as a threshold to make objects unique [default std::numeric_limits<double>::epsilon()] Adding a new item to an already "filled" OctTree node results in a split of the OctTree node. The smaller this number is the more leaves the OctTree will have, i.e. it needs more memory and more time to walk through the OctTree, but the search inside a leaf is fast. In contrast a big value results into a smaller number of OctTree leaves, the memory requirements for the OctTree may be lower but the search inside a OctTree leaf may be more expensive. The value should be chosen application dependent. [default 8]

Definition at line 16 of file OctTree-impl.h.

18{
19 // compute an axis aligned cube around the points ll and ur
20 const double dx(ur[0] - ll[0]);
21 const double dy(ur[1] - ll[1]);
22 const double dz(ur[2] - ll[2]);
23 if (dx >= dy && dx >= dz)
24 {
25 ll[1] -= (dx - dy) / 2.0;
26 ur[1] += (dx - dy) / 2.0;
27 ll[2] -= (dx - dz) / 2.0;
28 ur[2] += (dx - dz) / 2.0;
29 }
30 else
31 {
32 if (dy >= dx && dy >= dz)
33 {
34 ll[0] -= (dy - dx) / 2.0;
35 ur[0] += (dy - dx) / 2.0;
36 ll[2] -= (dy - dz) / 2.0;
37 ur[2] += (dy - dz) / 2.0;
38 }
39 else
40 {
41 ll[0] -= (dz - dx) / 2.0;
42 ur[0] += (dz - dx) / 2.0;
43 ll[1] -= (dz - dy) / 2.0;
44 ur[1] += (dz - dy) / 2.0;
45 }
46 }
47 if (eps == 0.0)
48 {
49 eps = std::numeric_limits<double>::epsilon();
50 }
51 for (std::size_t k(0); k < 3; ++k)
52 {
53 if (ur[k] - ll[k] > 0.0)
54 {
55 ur[k] += (ur[k] - ll[k]) * 1e-6;
56 }
57 else
58 {
59 ur[k] += eps;
60 }
61 }
62 Eigen::Vector3d lower_left{ll[0], ll[1], ll[2]};
63 Eigen::Vector3d upper_right{ur[0], ur[1], ur[2]};
64 return new OctTree<POINT, MAX_POINTS>(lower_left, upper_right, eps);
65}

◆ getChild()

template<typename POINT , std::size_t MAX_POINTS>
OctTree< POINT, MAX_POINTS > const * GeoLib::OctTree< POINT, MAX_POINTS >::getChild ( std::size_t  i) const
inline

Definition at line 79 of file OctTree.h.

80 {
81 return _children[i];
82 }

References GeoLib::OctTree< POINT, MAX_POINTS >::_children.

◆ getLowerLeftCornerPoint()

template<typename POINT , std::size_t MAX_POINTS>
Eigen::Vector3d const & GeoLib::OctTree< POINT, MAX_POINTS >::getLowerLeftCornerPoint ( ) const
inline

Definition at line 77 of file OctTree.h.

77{ return _ll; }

References GeoLib::OctTree< POINT, MAX_POINTS >::_ll.

◆ getPointsInRange()

template<typename POINT , std::size_t MAX_POINTS>
template<typename T >
void GeoLib::OctTree< POINT, MAX_POINTS >::getPointsInRange ( T const &  min,
T const &  max,
std::vector< POINT * > &  pnts 
) const

range query - returns all points inside the range [min[0], max[0]) x [min[1], max[1]) x [min[2], max[2])

Definition at line 136 of file OctTree-impl.h.

138{
139 if (_ur[0] < min[0] || _ur[1] < min[1] || _ur[2] < min[2])
140 {
141 return;
142 }
143
144 if (max[0] < _ll[0] || max[1] < _ll[1] || max[2] < _ll[2])
145 {
146 return;
147 }
148
149 if (_is_leaf)
150 {
151 std::copy_if(_pnts.begin(), _pnts.end(), std::back_inserter(pnts),
152 [&min, &max](auto const* p)
153 {
154 return (min[0] <= (*p)[0] && (*p)[0] < max[0] &&
155 min[1] <= (*p)[1] && (*p)[1] < max[1] &&
156 min[2] <= (*p)[2] && (*p)[2] < max[2]);
157 });
158 }
159 else
160 {
161 for (std::size_t k(0); k < 8; k++)
162 {
163 _children[k]->getPointsInRange(min, max, pnts);
164 }
165 }
166}

◆ getPointVector()

template<typename POINT , std::size_t MAX_POINTS>
std::vector< POINT * > const & GeoLib::OctTree< POINT, MAX_POINTS >::getPointVector ( ) const
inline

Definition at line 83 of file OctTree.h.

83{ return _pnts; }

References GeoLib::OctTree< POINT, MAX_POINTS >::_pnts.

◆ getUpperRightCornerPoint()

template<typename POINT , std::size_t MAX_POINTS>
Eigen::Vector3d const & GeoLib::OctTree< POINT, MAX_POINTS >::getUpperRightCornerPoint ( ) const
inline

Definition at line 78 of file OctTree.h.

78{ return _ur; }

References GeoLib::OctTree< POINT, MAX_POINTS >::_ur.

◆ isOutside()

template<typename POINT , std::size_t MAX_POINTS>
bool GeoLib::OctTree< POINT, MAX_POINTS >::isOutside ( POINT *  pnt) const
private

checks if the given point pnt is outside of the OctTree node.

Parameters
pntthe point that check is performed on
Returns
true if the point is outside of the OctTree node.

Definition at line 318 of file OctTree-impl.h.

319{
320 if ((*pnt)[0] < _ll[0] || (*pnt)[1] < _ll[1] || (*pnt)[2] < _ll[2])
321 {
322 return true;
323 }
324 if ((*pnt)[0] >= _ur[0] || (*pnt)[1] >= _ur[1] || (*pnt)[2] >= _ur[2])
325 {
326 return true;
327 }
328 return false;
329}

◆ splitNode()

template<typename POINT , std::size_t MAX_POINTS>
void GeoLib::OctTree< POINT, MAX_POINTS >::splitNode ( POINT *  pnt)
private

Creates the child nodes of this leaf and distribute the points stored in _pnts to the children.

Parameters
pntthe pointer to the points that is responsible for the split

Definition at line 235 of file OctTree-impl.h.

236{
237 const double x_mid((_ur[0] + _ll[0]) / 2.0);
238 const double y_mid((_ur[1] + _ll[1]) / 2.0);
239 const double z_mid((_ur[2] + _ll[2]) / 2.0);
240 Eigen::Vector3d p0{x_mid, y_mid, _ll[2]};
241 Eigen::Vector3d p1{_ur[0], _ur[1], z_mid};
242
243 // create child NEL
244 _children[static_cast<std::int8_t>(Quadrant::NEL)] =
245 new OctTree<POINT, MAX_POINTS>(p0, p1, _eps);
246
247 // create child NWL
248 p0[0] = _ll[0];
249 p1[0] = x_mid;
250 _children[static_cast<std::int8_t>(Quadrant::NWL)] =
251 new OctTree<POINT, MAX_POINTS>(p0, p1, _eps);
252
253 // create child SWL
254 p0[1] = _ll[1];
255 p1[1] = y_mid;
256 _children[static_cast<std::int8_t>(Quadrant::SWL)] =
257 new OctTree<POINT, MAX_POINTS>(_ll, p1, _eps);
258
259 // create child NEU
260 _children[static_cast<std::int8_t>(Quadrant::NEU)] =
261 new OctTree<POINT, MAX_POINTS>(p1, _ur, _eps);
262
263 // create child SEL
264 p0[0] = x_mid;
265 p1[0] = _ur[0];
266 _children[static_cast<std::int8_t>(Quadrant::SEL)] =
267 new OctTree<POINT, MAX_POINTS>(p0, p1, _eps);
268
269 // create child NWU
270 p0[0] = _ll[0];
271 p0[1] = y_mid;
272 p0[2] = z_mid;
273 p1[0] = x_mid;
274 p1[1] = _ur[1];
275 p1[2] = _ur[2];
276 _children[static_cast<std::int8_t>(Quadrant::NWU)] =
277 new OctTree<POINT, MAX_POINTS>(p0, p1, _eps);
278
279 // create child SWU
280 p0[1] = _ll[1];
281 p1[1] = y_mid;
282 _children[static_cast<std::int8_t>(Quadrant::SWU)] =
283 new OctTree<POINT, MAX_POINTS>(p0, p1, _eps);
284
285 // create child SEU
286 p0[0] = x_mid;
287 p1[0] = _ur[0];
288 p1[1] = y_mid;
289 p1[2] = _ur[2];
290 _children[static_cast<std::int8_t>(Quadrant::SEU)] =
291 new OctTree<POINT, MAX_POINTS>(p0, p1, _eps);
292
293 // add the passed point pnt to the children at first
294 for (std::size_t k(0); k < 8; k++)
295 {
296 if (_children[k]->addPointToChild(pnt))
297 {
298 break;
299 }
300 }
301
302 // distribute points to sub quadtrees
303 const std::size_t n_pnts(_pnts.size());
304 for (std::size_t j(0); j < n_pnts; j++)
305 {
306 for (auto c : _children)
307 {
308 if (c->addPointToChild(_pnts[j]))
309 {
310 break;
311 }
312 }
313 }
314 _is_leaf = false;
315}
bool addPointToChild(POINT *pnt)
Definition: OctTree-impl.h:215
@ NEU
south west upper
@ NEL
north east lower
@ SWU
south west upper
@ SEU
south east upper
@ NWL
north west lower
@ SWL
south west lower
@ NWU
south west upper
@ SEL
south east lower

References MaterialPropertyLib::c.

Member Data Documentation

◆ _children

template<typename POINT , std::size_t MAX_POINTS>
std::array<OctTree<POINT, MAX_POINTS>*, 8> GeoLib::OctTree< POINT, MAX_POINTS >::_children
private

children are sorted: _children[0] is north east lower child _children[1] is north west lower child _children[2] is south west lower child _children[3] is south east lower child _children[4] is north east upper child _children[5] is north west upper child _children[6] is south west upper child _children[7] is south east upper child

Definition at line 139 of file OctTree.h.

Referenced by GeoLib::OctTree< POINT, MAX_POINTS >::OctTree(), and GeoLib::OctTree< POINT, MAX_POINTS >::getChild().

◆ _eps

template<typename POINT , std::size_t MAX_POINTS>
double const GeoLib::OctTree< POINT, MAX_POINTS >::_eps
private

threshold for point uniqueness

Definition at line 149 of file OctTree.h.

◆ _is_leaf

template<typename POINT , std::size_t MAX_POINTS>
bool GeoLib::OctTree< POINT, MAX_POINTS >::_is_leaf
private

flag if this OctTree is a leaf

Definition at line 147 of file OctTree.h.

◆ _ll

template<typename POINT , std::size_t MAX_POINTS>
Eigen::Vector3d const GeoLib::OctTree< POINT, MAX_POINTS >::_ll
private

lower left front face point of the cube

Definition at line 141 of file OctTree.h.

Referenced by GeoLib::OctTree< POINT, MAX_POINTS >::getLowerLeftCornerPoint().

◆ _pnts

template<typename POINT , std::size_t MAX_POINTS>
std::vector<POINT*> GeoLib::OctTree< POINT, MAX_POINTS >::_pnts
private

vector of pointers to POINT objects

Definition at line 145 of file OctTree.h.

Referenced by GeoLib::OctTree< POINT, MAX_POINTS >::getPointVector().

◆ _ur

template<typename POINT , std::size_t MAX_POINTS>
Eigen::Vector3d const GeoLib::OctTree< POINT, MAX_POINTS >::_ur
private

upper right back face point of the cube

Definition at line 143 of file OctTree.h.

Referenced by GeoLib::OctTree< POINT, MAX_POINTS >::getUpperRightCornerPoint().


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