MFEM v4.7.0
Finite element discretization library
Loading...
Searching...
No Matches
kdtree.hpp
Go to the documentation of this file.
1// Copyright (c) 2010-2024, Lawrence Livermore National Security, LLC. Produced
2// at the Lawrence Livermore National Laboratory. All Rights reserved. See files
3// LICENSE and NOTICE for details. LLNL-CODE-806117.
4//
5// This file is part of the MFEM library. For more information and source code
6// availability visit https://mfem.org.
7//
8// MFEM is free software; you can redistribute it and/or modify it under the
9// terms of the BSD-3 license. We welcome feedback and contributions, see file
10// CONTRIBUTING.md for details
11
12#ifndef MFEM_KDTREE_HPP
13#define MFEM_KDTREE_HPP
14
15#include "../config/config.hpp"
16
17#include <vector>
18#include <algorithm>
19#include <fstream>
20#include <iostream>
21#include <cmath>
22#include <cstdint>
23#include <tuple>
24
25namespace mfem
26{
27
28namespace KDTreeNorms
29{
30
31/// Evaluates l1 norm of a vector.
32template <typename Tfloat, int ndim>
33struct Norm_l1
34{
35 Tfloat operator()(const Tfloat* xx) const
36 {
37 Tfloat tm=abs(xx[0]);
38 for (int i=1; i<ndim; i++)
39 {
40 tm=tm+abs(xx[i]);
41 }
42 return tm;
43 }
44};
45
46/// Evaluates l2 norm of a vector.
47template<typename Tfloat,int ndim>
48struct Norm_l2
49{
50 Tfloat operator()(const Tfloat* xx) const
51 {
52 Tfloat tm;
53 tm=xx[0]*xx[0];
54 for (int i=1; i<ndim; i++)
55 {
56 tm=tm+xx[i]*xx[i];
57 }
58 return sqrt(tm);
59 }
60};
61
62/// Finds the max absolute value of a vector.
63template<typename Tfloat,int ndim>
64struct Norm_li
65{
66 Tfloat operator()(const Tfloat* xx) const
67 {
68 Tfloat tm;
69 if (xx[0]<Tfloat(0.0)) { tm=-xx[0];}
70 else { tm=xx[0];}
71 for (int i=1; i<ndim; i++)
72 {
73 if (xx[i]<Tfloat(0.0))
74 {
75 if (tm<(-xx[i])) {tm=-xx[i];}
76 }
77 else
78 {
79 if (tm<xx[i]) {tm=xx[i];}
80 }
81 }
82 return tm;
83 }
84};
85
86}
87
88/// @brief Abstract base class for KDTree. Can be used when the dimension of the
89/// space is known dynamically.
90template <typename Tindex, typename Tfloat>
92{
93public:
94 /// Adds a point to the tree. See KDTree::AddPoint().
95 virtual void AddPoint(const Tfloat *xx, Tindex ii) = 0;
96 /// @brief Sorts the tree. Should be performed after adding points and before
97 /// performing queries. See KDTree::Sort().
98 virtual void Sort() = 0;
99 /// Returns the index of the closest point to @a xx.
100 virtual Tindex FindClosestPoint(const Tfloat *xx) const = 0;
101 /// Virtual destructor.
102 virtual ~KDTreeBase() { }
103};
104
105/// Template class for build KDTree with template parameters Tindex
106/// specifying the type utilized for indexing the points, Tfloat
107/// specifying a float type for representing the coordinates of the
108/// points, integer parameter ndim specifying the dimensionality of the
109/// space and template function Tnorm for evaluating the distance
110/// between two points. The KDTree class implements the standard k-d
111/// tree data structure that can be used to transfer a ParGridFunction
112/// defined on one MPI communicator to a ParGridFunction/GridFunction
113/// defined on different MPI communicator. This can be useful when
114/// comparing a solution computed on m ranks against a solution
115/// computed with n or 1 rank(s).
116template <typename Tindex, typename Tfloat, size_t ndim=3,
117 typename Tnorm=KDTreeNorms::Norm_l2<Tfloat,ndim> >
118class KDTree : public KDTreeBase<Tindex, Tfloat>
119{
120public:
121
122 /// Structure defining a geometric point in the ndim-dimensional space. The
123 /// coordinate type (Tfloat) can be any floating or integer type. It can be
124 /// even a character if necessary. For such types users should redefine the
125 /// norms.
126 struct PointND
127 {
128 /// Default constructor: fill with zeros
129 PointND() { std::fill(xx,xx+ndim,Tfloat(0.0)); }
130 /// Copy coordinates from pointer/array @a xx_
131 PointND(const Tfloat *xx_) { std::copy(xx_,xx_+ndim,xx); }
132 /// Coordinates of the point
133 Tfloat xx[ndim];
134 };
135
136 /// Structure defining a node in the KDTree.
137 struct NodeND
138 {
139 /// Defines a point in the ndim-dimensional space
141 /// Defines the attached index
142 Tindex ind = 0;
143 /// Default constructor: fill with zeros
144 NodeND() = default;
145 /// Create from given point and index
146 NodeND(PointND pt_, Tindex ind_ = 0) : pt(pt_), ind(ind_) { }
147 };
148
149 /// Default constructor
150 KDTree() = default;
151
152 /// Returns the spatial dimension of the points
153 int SpaceDimension() const
154 {
155 return ndim;
156 }
157
158 /// Data iterator
159 typedef typename std::vector<NodeND>::iterator iterator;
160
161 /// Returns iterator to beginning of the point cloud
163 {
164 return data.begin();
165 }
166
167 /// Returns iterator to the end of the point cloud
169 {
170 return data.end();
171 }
172
173 /// Returns the size of the point cloud
174 size_t size() const
175 {
176 return data.size();
177 }
178
179 /// Clears the point cloud
180 void clear()
181 {
182 data.clear();
183 }
184
185 /// Builds the KDTree. If the point cloud is modified the tree
186 /// needs to be rebuild by a new call to Sort().
187 void Sort() override
188 {
189 SortInPlace(data.begin(),data.end(),0);
190 }
191
192 /// Adds a new node to the point cloud
193 void AddPoint(const PointND &pt, Tindex ii)
194 {
195 data.emplace_back(pt, ii);
196 }
197
198 /// Adds a new node by coordinates and an associated index
199 void AddPoint(const Tfloat *xx,Tindex ii) override
200 {
201 data.emplace_back(xx, ii);
202 }
203
204 /// Finds the nearest neighbour index
205 Tindex FindClosestPoint(const PointND &pt) const
206 {
207 PointS best_candidate;
208 best_candidate.sp=pt;
209 //initialize the best candidate
210 best_candidate.pos =0;
211 best_candidate.dist=Dist(data[0].pt, best_candidate.sp);
212 best_candidate.level=0;
213 PSearch(data.begin(), data.end(), 0, best_candidate);
214 return data[best_candidate.pos].ind;
215 }
216
217 Tindex FindClosestPoint(const Tfloat *xx) const override
218 {
219 return FindClosestPoint(PointND(xx));
220 }
221
222 /// Finds the nearest neighbour index and return the clossest point in clp
223 Tindex FindClosestPoint(const PointND &pt, const PointND &clp) const
224 {
225 PointS best_candidate;
226 best_candidate.sp=pt;
227 //initialize the best candidate
228 best_candidate.pos =0;
229 best_candidate.dist=Dist(data[0].pt, best_candidate.sp);
230 best_candidate.level=0;
231 PSearch(data.begin(), data.end(), 0, best_candidate);
232
233 clp=data[best_candidate.pos].pt;
234 return data[best_candidate.pos].ind;
235 }
236
237 /// Returns the closest point and the distance to the input point pt.
238 void FindClosestPoint(const PointND &pt, Tindex &ind, Tfloat &dist) const
239 {
240 PointND clp;
241 FindClosestPoint(pt,ind,dist,clp);
242 }
243
244 /// Returns the closest point and the distance to the input point pt.
245 void FindClosestPoint(const PointND &pt, Tindex &ind, Tfloat &dist,
246 PointND &clp) const
247 {
248 PointS best_candidate;
249 best_candidate.sp=pt;
250 //initialize the best candidate
251 best_candidate.pos =0;
252 best_candidate.dist=Dist(data[0].pt, best_candidate.sp);
253 best_candidate.level=0;
254 PSearch(data.begin(), data.end(), 0, best_candidate);
255
256 ind=data[best_candidate.pos].ind;
257 dist=best_candidate.dist;
258 clp=data[best_candidate.pos].pt;
259 }
260
261
262 /// Brute force search - please, use it only for debuging purposes
263 void FindClosestPointSlow(const PointND &pt, Tindex &ind, Tfloat &dist) const
264 {
265 PointS best_candidate;
266 best_candidate.sp=pt;
267 //initialize the best candidate
268 best_candidate.pos =0;
269 best_candidate.dist=Dist(data[0].pt, best_candidate.sp);
270 Tfloat dd;
271 for (auto iti=data.begin()+1; iti!=data.end(); iti++)
272 {
273 dd=Dist(iti->pt, best_candidate.sp);
274 if (dd<best_candidate.dist)
275 {
276 best_candidate.pos=iti-data.begin();
277 best_candidate.dist=dd;
278 }
279 }
280
281 ind=data[best_candidate.pos].ind;
282 dist=best_candidate.dist;
283 }
284
285 /// Finds all points within a distance R from point pt. The indices are
286 /// returned in the vector res and the correponding distances in vector dist.
287 void FindNeighborPoints(const PointND &pt,Tfloat R, std::vector<Tindex> & res,
288 std::vector<Tfloat> & dist)
289 {
290 FindNeighborPoints(pt,R,data.begin(),data.end(),0,res,dist);
291 }
292
293 /// Finds all points within a distance R from point pt. The indices are
294 /// returned in the vector res and the correponding distances in vector dist.
295 void FindNeighborPoints(const PointND &pt,Tfloat R, std::vector<Tindex> & res)
296 {
297 FindNeighborPoints(pt,R,data.begin(),data.end(),0,res);
298 }
299
300 /// Brute force search - please, use it only for debuging purposes
301 void FindNeighborPointsSlow(const PointND &pt,Tfloat R,
302 std::vector<Tindex> &res,
303 std::vector<Tfloat> &dist)
304 {
305 Tfloat dd;
306 for (auto iti=data.begin(); iti!=data.end(); iti++)
307 {
308 dd=Dist(iti->pt, pt);
309 if (dd<R)
310 {
311 res.push_back(iti->ind);
312 dist.push_back(dd);
313 }
314 }
315 }
316
317 /// Brute force search - please, use it only for debuging purposes
318 void FindNeighborPointsSlow(const PointND &pt,Tfloat R,
319 std::vector<Tindex> &res)
320 {
321 Tfloat dd;
322 for (auto iti=data.begin(); iti!=data.end(); iti++)
323 {
324 dd=Dist(iti->pt, pt);
325 if (dd<R)
326 {
327 res.push_back(iti->ind);
328 }
329 }
330 }
331
332private:
333
334 /// Functor utilized in the coordinate comparison
335 /// for building the KDTree
336 struct CompN
337 {
338 /// Current coordinate index
339 std::uint8_t dim;
340
341 /// Constructor for the comparison
342 CompN(std::uint8_t dd):dim(dd) {}
343
344 /// Compares two points p1 and p2
345 bool operator() (const PointND& p1, const PointND& p2)
346 {
347 return p1.xx[dim]<p2.xx[dim];
348 }
349
350 /// Compares two nodes n1 and n2
351 bool operator() (const NodeND& n1, const NodeND& n2)
352 {
353 return n1.pt.xx[dim]<n2.pt.xx[dim];
354 }
355 };
356
357 mutable PointND tp; ///< Point for storing tmp data
358 Tnorm fnorm;
359
360 /// Computes the distance between two nodes
361 Tfloat Dist(const PointND &pt1, const PointND &pt2) const
362 {
363 for (size_t i=0; i<ndim; i++)
364 {
365 tp.xx[i]=pt1.xx[i]-pt2.xx[i];
366 }
367 return fnorm(tp.xx);
368 }
369
370 /// The point cloud is stored in a vector.
371 std::vector<NodeND> data;
372
373 /// Finds the median for a sequence of nodes starting with itb
374 /// and ending with ite. The current coordinate index is set by cdim.
375 Tfloat FindMedian(typename std::vector<NodeND>::iterator itb,
376 typename std::vector<NodeND>::iterator ite,
377 std::uint8_t cdim)
378 {
379 size_t siz=ite-itb;
380 std::nth_element(itb, itb+siz/2, ite, CompN(cdim));
381 return itb->pt.xx[cdim];
382 }
383
384 /// Sorts the point cloud
385 void SortInPlace(typename std::vector<NodeND>::iterator itb,
386 typename std::vector<NodeND>::iterator ite,
387 size_t level)
388 {
389 std::uint8_t cdim=(std::uint8_t)(level%ndim);
390 size_t siz=ite-itb;
391 if (siz>2)
392 {
393 std::nth_element(itb, itb+siz/2, ite, CompN(cdim));
394 level=level+1;
395 SortInPlace(itb, itb+siz/2, level);
396 SortInPlace(itb+siz/2+1,ite, level);
397 }
398 }
399
400 /// Structure utilized for nearest neighbor search (NNS)
401 struct PointS
402 {
403 Tfloat dist;
404 size_t pos;
405 size_t level;
406 PointND sp;
407 };
408
409 /// Finds the closest point to bc.sp in the point cloud
410 /// bounded between [itb,ite).
411 void PSearch(typename std::vector<NodeND>::const_iterator itb,
412 typename std::vector<NodeND>::const_iterator ite,
413 size_t level, PointS& bc) const
414 {
415 std::uint8_t dim=(std::uint8_t) (level%ndim);
416 size_t siz=ite-itb;
417 typename std::vector<NodeND>::const_iterator mtb=itb+siz/2;
418 if (siz>2)
419 {
420 // median is at itb+siz/2
421 level=level+1;
422 if ((bc.sp.xx[dim]-bc.dist)>mtb->pt.xx[dim]) // look on the right only
423 {
424 PSearch(itb+siz/2+1, ite, level, bc);
425 }
426 else if ((bc.sp.xx[dim]+bc.dist)<mtb->pt.xx[dim]) // look on the left only
427 {
428 PSearch(itb,itb+siz/2, level, bc);
429 }
430 else // check all
431 {
432 if (bc.sp.xx[dim]<mtb->pt.xx[dim])
433 {
434 // start with the left portion
435 PSearch(itb,itb+siz/2, level, bc);
436 // and continue to the right
437 if (!((bc.sp.xx[dim]+bc.dist)<mtb->pt.xx[dim]))
438 {
439 PSearch(itb+siz/2+1, ite, level, bc);
440 {
441 // check central one
442 Tfloat dd=Dist(mtb->pt, bc.sp);
443 if (dd<bc.dist)
444 {
445 bc.dist=dd; bc.pos=mtb-data.begin(); bc.level=level;
446 }
447 } // end central point check
448 }
449 }
450 else
451 {
452 // start with the right portion
453 PSearch(itb+siz/2+1, ite, level, bc);
454 // and continue with left
455 if (!((bc.sp.xx[dim]-bc.dist)>mtb->pt.xx[dim]))
456 {
457 PSearch(itb, itb+siz/2, level, bc);
458 {
459 // check central one
460 Tfloat dd=Dist(mtb->pt, bc.sp);
461 if (dd<bc.dist)
462 {
463 bc.dist=dd; bc.pos=mtb-data.begin(); bc.level=level;
464 }
465 } // end central point check
466 }
467 }
468 }
469 }
470 else
471 {
472 // check the nodes
473 Tfloat dd;
474 for (auto it=itb; it!=ite; it++)
475 {
476 dd=Dist(it->pt, bc.sp);
477 if (dd<bc.dist) // update bc
478 {
479 bc.pos=it-data.begin();
480 bc.dist=dd;
481 bc.level=level;
482 }
483 }
484 }
485 }
486
487 /// Returns distances and indices of the n closest points to a point pt.
488 void NNS(PointND& pt,const int& npoints,
489 typename std::vector<NodeND>::iterator itb,
490 typename std::vector<NodeND>::iterator ite,
491 size_t level,
492 std::vector< std::tuple<Tfloat,Tindex> > & res) const
493 {
494 std::uint8_t dim=(std::uint8_t) (level%ndim);
495 size_t siz=ite-itb;
496 typename std::vector<NodeND>::iterator mtb=itb+siz/2;
497 if (siz>2)
498 {
499 // median is at itb+siz/2
500 level=level+1;
501 Tfloat R=std::get<0>(res[npoints-1]);
502 // check central one
503 Tfloat dd=Dist(mtb->pt, pt);
504 if (dd<R)
505 {
506 res[npoints-1]=std::make_tuple(dd,mtb->ind);
507 std::nth_element(res.begin(), res.end()-1, res.end());
508 R=std::get<0>(res[npoints-1]);
509 }
510 if ((pt.xx[dim]-R)>mtb->pt.xx[dim]) // look to the right only
511 {
512 NNS(pt, npoints, itb+siz/2+1, ite, level, res);
513 }
514 else if ((pt.xx[dim]+R)<mtb->pt.xx[dim]) // look to the left only
515 {
516 NNS(pt, npoints, itb, itb+siz/2, level, res);
517 }
518 else // check all
519 {
520 NNS(pt,npoints, itb+siz/2+1, ite, level, res); // right
521 NNS(pt,npoints, itb, itb+siz/2, level, res); // left
522 }
523 }
524 else
525 {
526 Tfloat dd;
527 for (auto it=itb; it!=ite; it++)
528 {
529 dd=Dist(it->pt, pt);
530 if (dd< std::get<0>(res[npoints-1])) // update the list
531 {
532 res[npoints-1]=std::make_tuple(dd,it->ind);
533 std::nth_element(res.begin(), res.end()-1, res.end());
534 }
535 }
536 }
537 }
538
539 /// Finds the set of indices of points within a distance R of a point pt.
540 void FindNeighborPoints(PointND& pt, Tfloat R,
541 typename std::vector<NodeND>::iterator itb,
542 typename std::vector<NodeND>::iterator ite,
543 size_t level,
544 std::vector<Tindex> & res) const
545 {
546 std::uint8_t dim=(std::uint8_t) (level%ndim);
547 size_t siz=ite-itb;
548 typename std::vector<NodeND>::iterator mtb=itb+siz/2;
549 if (siz>2)
550 {
551 // median is at itb+siz/2
552 level=level+1;
553 if ((pt.xx[dim]-R)>mtb->pt.xx[dim]) // look to the right only
554 {
555 FindNeighborPoints(pt, R, itb+siz/2+1, ite, level, res);
556 }
557 else if ((pt.xx[dim]+R)<mtb->pt.xx[dim]) // look to the left only
558 {
559 FindNeighborPoints(pt,R, itb, itb+siz/2, level, res);
560 }
561 else //check all
562 {
563 FindNeighborPoints(pt,R, itb+siz/2+1, ite, level, res); // right
564 FindNeighborPoints(pt,R, itb, itb+siz/2, level, res); // left
565
566 // check central one
567 Tfloat dd=Dist(mtb->pt, pt);
568 if (dd<R)
569 {
570 res.push_back(mtb->ind);
571 }
572 }
573 }
574 else
575 {
576 Tfloat dd;
577 for (auto it=itb; it!=ite; it++)
578 {
579 dd=Dist(it->pt, pt);
580 if (dd<R) // update bc
581 {
582 res.push_back(it->ind);
583 }
584 }
585 }
586 }
587
588 /// Finds the set of indices of points within a distance R of a point pt.
589 void FindNeighborPoints(PointND& pt, Tfloat R,
590 typename std::vector<NodeND>::iterator itb,
591 typename std::vector<NodeND>::iterator ite,
592 size_t level,
593 std::vector<Tindex> & res, std::vector<Tfloat> & dist) const
594 {
595 std::uint8_t dim=(std::uint8_t) (level%ndim);
596 size_t siz=ite-itb;
597 typename std::vector<NodeND>::iterator mtb=itb+siz/2;
598 if (siz>2)
599 {
600 // median is at itb+siz/2
601 level=level+1;
602 if ((pt.xx[dim]-R)>mtb->pt.xx[dim]) // look to the right only
603 {
604 FindNeighborPoints(pt, R, itb+siz/2+1, ite, level, res, dist);
605 }
606 else if ((pt.xx[dim]+R)<mtb->pt.xx[dim]) // look to the left only
607 {
608 FindNeighborPoints(pt,R, itb, itb+siz/2, level, res, dist);
609 }
610 else // check all
611 {
612 FindNeighborPoints(pt,R, itb+siz/2+1, ite, level, res, dist); // right
613 FindNeighborPoints(pt,R, itb, itb+siz/2, level, res, dist); // left
614
615 // check central one
616 Tfloat dd=Dist(mtb->pt, pt);
617 if (dd<R)
618 {
619 res.push_back(mtb->ind);
620 dist.push_back(dd);
621 }
622 }
623 }
624 else
625 {
626 Tfloat dd;
627 for (auto it=itb; it!=ite; it++)
628 {
629 dd=Dist(it->pt, pt);
630 if (dd<R) // update bc
631 {
632 res.push_back(it->ind);
633 dist.push_back(dd);
634 }
635 }
636 }
637 }
638};
639
640/// Defines KDTree in 3D
642
643/// Defines KDTree in 2D
645
646/// Defines KDTree in 1D
648
649} // namespace mfem
650
651#endif // MFEM_KDTREE_HPP
Abstract base class for KDTree. Can be used when the dimension of the space is known dynamically.
Definition kdtree.hpp:92
virtual ~KDTreeBase()
Virtual destructor.
Definition kdtree.hpp:102
virtual void AddPoint(const Tfloat *xx, Tindex ii)=0
Adds a point to the tree. See KDTree::AddPoint().
virtual void Sort()=0
Sorts the tree. Should be performed after adding points and before performing queries....
virtual Tindex FindClosestPoint(const Tfloat *xx) const =0
Returns the index of the closest point to xx.
void FindClosestPointSlow(const PointND &pt, Tindex &ind, Tfloat &dist) const
Brute force search - please, use it only for debuging purposes.
Definition kdtree.hpp:263
Tindex FindClosestPoint(const PointND &pt, const PointND &clp) const
Finds the nearest neighbour index and return the clossest point in clp.
Definition kdtree.hpp:223
std::vector< NodeND >::iterator iterator
Data iterator.
Definition kdtree.hpp:159
void FindNeighborPoints(const PointND &pt, Tfloat R, std::vector< Tindex > &res, std::vector< Tfloat > &dist)
Definition kdtree.hpp:287
size_t size() const
Returns the size of the point cloud.
Definition kdtree.hpp:174
void Sort() override
Definition kdtree.hpp:187
void FindClosestPoint(const PointND &pt, Tindex &ind, Tfloat &dist, PointND &clp) const
Returns the closest point and the distance to the input point pt.
Definition kdtree.hpp:245
void FindNeighborPointsSlow(const PointND &pt, Tfloat R, std::vector< Tindex > &res)
Brute force search - please, use it only for debuging purposes.
Definition kdtree.hpp:318
Tindex FindClosestPoint(const PointND &pt) const
Finds the nearest neighbour index.
Definition kdtree.hpp:205
void FindNeighborPoints(const PointND &pt, Tfloat R, std::vector< Tindex > &res)
Definition kdtree.hpp:295
void AddPoint(const PointND &pt, Tindex ii)
Adds a new node to the point cloud.
Definition kdtree.hpp:193
KDTree()=default
Default constructor.
iterator end()
Returns iterator to the end of the point cloud.
Definition kdtree.hpp:168
void AddPoint(const Tfloat *xx, Tindex ii) override
Adds a new node by coordinates and an associated index.
Definition kdtree.hpp:199
iterator begin()
Returns iterator to beginning of the point cloud.
Definition kdtree.hpp:162
void clear()
Clears the point cloud.
Definition kdtree.hpp:180
void FindNeighborPointsSlow(const PointND &pt, Tfloat R, std::vector< Tindex > &res, std::vector< Tfloat > &dist)
Brute force search - please, use it only for debuging purposes.
Definition kdtree.hpp:301
int SpaceDimension() const
Returns the spatial dimension of the points.
Definition kdtree.hpp:153
void FindClosestPoint(const PointND &pt, Tindex &ind, Tfloat &dist) const
Returns the closest point and the distance to the input point pt.
Definition kdtree.hpp:238
Tindex FindClosestPoint(const Tfloat *xx) const override
Returns the index of the closest point to xx.
Definition kdtree.hpp:217
int dim
Definition ex24.cpp:53
KDTree< int, real_t, 1 > KDTree1D
Defines KDTree in 1D.
Definition kdtree.hpp:647
KDTree< int, real_t, 3 > KDTree3D
Defines KDTree in 3D.
Definition kdtree.hpp:641
KDTree< int, real_t, 2 > KDTree2D
Defines KDTree in 2D.
Definition kdtree.hpp:644
Evaluates l1 norm of a vector.
Definition kdtree.hpp:34
Tfloat operator()(const Tfloat *xx) const
Definition kdtree.hpp:35
Evaluates l2 norm of a vector.
Definition kdtree.hpp:49
Tfloat operator()(const Tfloat *xx) const
Definition kdtree.hpp:50
Finds the max absolute value of a vector.
Definition kdtree.hpp:65
Tfloat operator()(const Tfloat *xx) const
Definition kdtree.hpp:66
Structure defining a node in the KDTree.
Definition kdtree.hpp:138
NodeND()=default
Default constructor: fill with zeros.
Tindex ind
Defines the attached index.
Definition kdtree.hpp:142
PointND pt
Defines a point in the ndim-dimensional space.
Definition kdtree.hpp:140
NodeND(PointND pt_, Tindex ind_=0)
Create from given point and index.
Definition kdtree.hpp:146
PointND()
Default constructor: fill with zeros.
Definition kdtree.hpp:129
Tfloat xx[ndim]
Coordinates of the point.
Definition kdtree.hpp:133
PointND(const Tfloat *xx_)
Copy coordinates from pointer/array xx_.
Definition kdtree.hpp:131