#include <NuKDTree.h>
Public Member Functions | |
| NuKDTree () | |
| ~NuKDTree () | |
| void | AddPt (T payload, const NuKDPt< D > &p) |
| Add your points one by one here. Then call Commit. | |
| void | Commit () |
| After all points are added but before you do anything else, call this. | |
| bool | Committed () const |
| Has Commit been called yet? | |
| std::vector< NuKDPtWithPayload< T, D > > | FindNearestPts (NuKDPt< D > p, unsigned int N) const |
| Find the N points closest to p. | |
Protected Member Functions | |
| void | FillSDs () |
| Called at Commit time. | |
Protected Attributes | |
| bool | fCommitted |
| Has Commit been called yet. | |
| NuKDBox< T, D > * | fBox |
| All the real work is done by the toplevel NuKDBox. | |
| std::vector< NuKDPtWithPayload< T, D > > | fPts |
| We stage the points from AddPt here before Commit is called. | |
| double | fSDs [D] |
| Standard deviations of the variables, from FillSDs. | |
http://en.wikipedia.org/wiki/Kd-tree is a reasonable overview.
Stores data of type T at D dimensional coordinates, and can rapidly find N nearest neighbours to any point.
First, add all your points with AddPt, then call Commit to prepare the tree. Now you can call FindNearestPts
The metric used to determine nearest points is a D dimensional Euclidean metric. Each dimension is normalized by the standard deviation of the input data along that dimension.
Definition at line 72 of file NuKDTree.h.
|
|||||||||
|
Definition at line 264 of file NuKDTree.cxx. References NuKDTree< T, D >::fBox. 00264 : fCommitted(false) 00265 { 00266 fBox = new NuKDBox<T, D>; 00267 }
|
|
|||||||||
|
Definition at line 270 of file NuKDTree.cxx. 00271 {
00272 delete fBox;
00273 }
|
|
||||||||||||||||
|
Add your points one by one here. Then call Commit.
Definition at line 277 of file NuKDTree.cxx. References NuKDTree< T, D >::fCommitted, and NuKDTree< T, D >::fPts. Referenced by NuReco::InitializeShowerEnergykNN(). 00278 {
00279 assert(!fCommitted && "You can't add any new points after you've committed");
00280 fPts.push_back(NuKDPtWithPayload<T, D>(pt, payload));
00281 }
|
|
|||||||||
|
After all points are added but before you do anything else, call this.
Definition at line 300 of file NuKDTree.cxx. References NuKDTree< T, D >::fBox, NuKDTree< T, D >::fCommitted, NuKDTree< T, D >::FillSDs(), NuKDTree< T, D >::fPts, and NuKDTree< T, D >::fSDs. Referenced by NuReco::InitializeShowerEnergykNN(). 00301 {
00302 if(fCommitted) return;
00303
00304 FillSDs();
00305
00306 // Divide every point through by its standard deviation
00307 const unsigned int N = fPts.size();
00308 for(unsigned int n = 0; n < N; ++n){
00309 for(unsigned int d = 0; d < D; ++d){
00310 fPts[n].pt[d] /= fSDs[d];
00311 }
00312 }
00313
00314 // Trigger the building of the whole tree
00315 fBox->Build(&fPts[0], &fPts[0]+fPts.size());
00316 // Check that it worked
00317 assert(fBox->NChildren() == fPts.size());
00318 fPts.clear();
00319 fCommitted = true;
00320 }
|
|
|||||||||
|
Has Commit been called yet?
Definition at line 86 of file NuKDTree.h. Referenced by NuReco::GetShowerEnergykNN(). 00086 {return fCommitted;}
|
|
|||||||||
|
Called at Commit time.
Definition at line 284 of file NuKDTree.cxx. References NuKDTree< T, D >::fPts, and NuKDTree< T, D >::fSDs. Referenced by NuKDTree< T, D >::Commit(). 00285 {
00286 for(unsigned int d = 0; d < D; ++d){
00287 const int N = fPts.size();
00288 double a = 0;
00289 double b = 0;
00290 for(int n = 0; n < N; ++n){
00291 const double p = fPts[n].pt[d];
00292 a += p*p;
00293 b += p;
00294 }
00295 fSDs[d] = sqrt(N*a-b*b)/N;
00296 }
00297 }
|
|
||||||||||||||||
|
Find the N points closest to p.
Definition at line 325 of file NuKDTree.cxx. References NuKDTaskRecord< T, D >::box, NuKDTree< T, D >::fBox, NuKDTree< T, D >::fCommitted, NuKDTree< T, D >::fSDs, NuKDTaskRecord< T, D >::hi, and NuKDTaskRecord< T, D >::lo. Referenced by NuReco::GetShowerEnergykNN(). 00326 {
00327 assert(fCommitted && "Need to commit the points before you can do anything");
00328
00329 // Convert the passed-in point to normalized space
00330 for(unsigned int d = 0; d < D; ++d) p[d] /= fSDs[d];
00331
00332 // Don't ask for impossibly large number of children
00333 assert(N <= fBox->NChildren());
00334
00335 // To start with the box is infinite
00336 NuKDPt<D> lo;
00337 NuKDPt<D> hi;
00338 for(unsigned int d = 0; d < D; ++d){
00339 lo[d] = -DBL_MAX;
00340 hi[d] = +DBL_MAX;
00341 }
00342 NuKDDistOrd<T, D> op(p);
00343 // This is the set the search accumulates results in
00344 set<NuKDPtWithPayload<T, D>, NuKDDistOrd<T, D> > retset(op);
00345
00346 // We need to start with the toplevel box and see what happens
00347 // Doing it this way, instead of recursively in FindNearestPts makes the
00348 // search breadth-first instead of depth-first, which is important to get
00349 // the correct performance characteristics.
00350 list<NuKDTaskRecord<T, D> > todo;
00351 todo.push_back(NuKDTaskRecord<T, D>(fBox, lo, hi));
00352 while(!todo.empty()){
00353 const NuKDTaskRecord<T, D> tr = *todo.begin();
00354 todo.pop_front();
00355
00356 tr.box->FindNearestPts(p, N, retset, tr.lo, tr.hi, todo);
00357 }
00358
00359 // Convert retset to a vector, since that's what we're supposed to return
00360 vector<NuKDPtWithPayload<T, D> > ret(retset.begin(), retset.end());
00361 // The points are returned in furthest-first order. We need them to be
00362 // closest-first so reverse them.
00363 reverse(ret.begin(), ret.end());
00364
00365 // Correct off the effect of SD normalization
00366 const unsigned int R = ret.size();
00367 for(unsigned int n = 0; n < R; ++n){
00368 for(unsigned int d = 0; d < D; ++d)
00369 ret[n].pt[d] *= fSDs[d];
00370 }
00371
00372 return ret;
00373 }
|
|
|||||
|
All the real work is done by the toplevel NuKDBox.
Definition at line 99 of file NuKDTree.h. Referenced by NuKDTree< T, D >::Commit(), NuKDTree< T, D >::FindNearestPts(), and NuKDTree< T, D >::NuKDTree(). |
|
|||||
|
Has Commit been called yet.
Definition at line 97 of file NuKDTree.h. Referenced by NuKDTree< T, D >::AddPt(), NuKDTree< T, D >::Commit(), and NuKDTree< T, D >::FindNearestPts(). |
|
|||||
|
We stage the points from AddPt here before Commit is called.
Definition at line 101 of file NuKDTree.h. Referenced by NuKDTree< T, D >::AddPt(), NuKDTree< T, D >::Commit(), and NuKDTree< T, D >::FillSDs(). |
|
|||||
|
Standard deviations of the variables, from FillSDs.
Definition at line 104 of file NuKDTree.h. Referenced by NuKDTree< T, D >::Commit(), NuKDTree< T, D >::FillSDs(), and NuKDTree< T, D >::FindNearestPts(). |
1.3.9.1