NuKDTree< T, D > Class Template Reference

A kd-tree - for calculating kNN shower energy. More...

#include <NuKDTree.h>

List of all members.

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.

Detailed Description

template<class T, unsigned int D>
class NuKDTree< T, D >

A kd-tree - for calculating kNN shower energy.

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.


Constructor & Destructor Documentation

template<class T , unsigned int D>
NuKDTree< T, D >::NuKDTree (  )  [inline]

Definition at line 264 of file NuKDTree.cxx.

References NuKDTree< T, D >::fBox.

00264                                                            : fCommitted(false)
00265 {
00266   fBox = new NuKDBox<T, D>;
00267 }

template<class T , unsigned int D>
NuKDTree< T, D >::~NuKDTree (  )  [inline]

Definition at line 270 of file NuKDTree.cxx.

References NuKDTree< T, D >::fBox.

00271 {
00272   delete fBox;
00273 }


Member Function Documentation

template<class T , unsigned int D>
void NuKDTree< T, D >::AddPt ( payload,
const NuKDPt< D > &  p 
) [inline]

Add your points one by one here. Then call Commit.

Parameters:
payload The value stored
p The coordinates to store the payload at

Definition at line 277 of file NuKDTree.cxx.

References NuKDTree< T, D >::fCommitted, and NuKDTree< T, D >::fPts.

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 }

template<class T , unsigned int D>
void NuKDTree< T, D >::Commit (  )  [inline]

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, NuKDTree< T, D >::fSDs, and n.

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 }

template<class T, unsigned int D>
bool NuKDTree< T, D >::Committed (  )  const [inline]

Has Commit been called yet?

Definition at line 86 of file NuKDTree.h.

References NuKDTree< T, D >::fCommitted.

Referenced by NuReco::GetShowerEnergykNN().

00086 {return fCommitted;}

template<class T , unsigned int D>
void NuKDTree< T, D >::FillSDs (  )  [inline, protected]

Called at Commit time.

Definition at line 284 of file NuKDTree.cxx.

References MuELoss::a, NuKDTree< T, D >::fPts, NuKDTree< T, D >::fSDs, and n.

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 }

template<class T , unsigned int D>
vector< NuKDPtWithPayload< T, D > > NuKDTree< T, D >::FindNearestPts ( NuKDPt< D >  p,
unsigned int  N 
) const [inline]

Find the N points closest to p.

Parameters:
p Point we're looking for points close to
N number of points to find
Returns:
List of the N points closest to p, nearest first

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, NuKDTaskRecord< T, D >::lo, n, and MuELoss::R.

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 }


Member Data Documentation

template<class T, unsigned int D>
NuKDBox<T, D>* NuKDTree< T, D >::fBox [protected]

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(), NuKDTree< T, D >::NuKDTree(), and NuKDTree< T, D >::~NuKDTree().

template<class T, unsigned int D>
bool NuKDTree< T, D >::fCommitted [protected]
template<class T, unsigned int D>
std::vector<NuKDPtWithPayload<T, D> > NuKDTree< T, D >::fPts [protected]

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().

template<class T, unsigned int D>
double NuKDTree< T, D >::fSDs[D] [protected]

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().


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

Generated on 22 Nov 2017 for loon by  doxygen 1.6.1