NuKDBox< T, D > Class Template Reference

Helper for NuKDTree. More...

List of all members.

Public Member Functions

 NuKDBox (unsigned int d=0)
 ~NuKDBox ()
void Build (NuKDPtWithPayload< T, D > *const i0, NuKDPtWithPayload< T, D > *const i1)
 Construct this box and the ones below it.
unsigned int NChildren () const
 Number of children contrained in this box.
void FindNearestPts (const NuKDPt< D > &p, unsigned int N, set< NuKDPtWithPayload< T, D >, NuKDDistOrd< T, D > > &ret, const NuKDPt< D > &lo, const NuKDPt< D > &hi, list< NuKDTaskRecord< T, D > > &todo) const

Protected Attributes

NuKDPtWithPayload< T, D > fPt
 Each box owns exactly one point.
NuKDBoxfSubs0
 Subtree, all points are smaller than fPt along fDir. Maybe null.
NuKDBoxfSubs1
 Subtree, all points are larger than fPt along fDir. Maybe null.
unsigned int fDir
 The dimension in which the bifurcation is to be taken.
unsigned int fNChild
 Number of children of this node, including fPt.

Detailed Description

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

Helper for NuKDTree.

The internal tree structure is composed of these boxes

Definition at line 69 of file NuKDTree.cxx.


Constructor & Destructor Documentation

template<class T, unsigned int D>
NuKDBox< T, D >::NuKDBox ( unsigned int  d = 0  )  [inline]
Parameters:
d The dimension along which the box is divided

Definition at line 73 of file NuKDTree.cxx.

Referenced by NuKDBox< T, D >::Build().

00073 : fSubs0(0), fSubs1(0), fDir(d) {}

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

Definition at line 125 of file NuKDTree.cxx.

References NuKDBox< T, D >::fSubs0, and NuKDBox< T, D >::fSubs1.

00126 {
00127   if(fSubs0) delete fSubs0;
00128   if(fSubs1) delete fSubs1;
00129 }


Member Function Documentation

template<class T , unsigned int D>
void NuKDBox< T, D >::Build ( NuKDPtWithPayload< T, D > *const   i0,
NuKDPtWithPayload< T, D > *const   i1 
) [inline]

Construct this box and the ones below it.

Split the input events in two equal samples along dimension fDir. Hold onto the median point ourself and construct two sub-boxes, oriented along the next dimension in sequence, holding the low points and high points respectively.

Parameters:
i0 The first point belonging to this box
i1 The last point belonging to this box + 1

Definition at line 148 of file NuKDTree.cxx.

References NuKDBox< T, D >::Build(), NuKDBox< T, D >::fDir, NuKDBox< T, D >::fNChild, NuKDBox< T, D >::fPt, NuKDBox< T, D >::fSubs0, NuKDBox< T, D >::fSubs1, and NuKDBox< T, D >::NuKDBox().

Referenced by NuKDBox< T, D >::Build().

00150 {
00151   assert(i1 > i0);
00152 
00153   fNChild = i1-i0;
00154 
00155   // Sort all the points based on the sort direction of this cell
00156   NuKDCompAlongDir<T, D> op(fDir);
00157   sort(i0, i1, op);
00158 
00159   // Find the median one, that's the one we'll own
00160   NuKDPtWithPayload<T, D>* const medit = i0+fNChild/2;
00161 
00162   // If there are any smaller than the median
00163   if(medit > i0){
00164     // Then we need a box for them, split in the next direction
00165     fSubs0 = new NuKDBox((fDir+1)%D);
00166     fSubs0->Build(i0, medit);
00167   }
00168   else
00169     fSubs0 = 0;
00170 
00171   // We keep the median point for ourself
00172   fPt = *medit;
00173 
00174   // Similarly for points larger than the median
00175   if(i1-1 > medit){
00176     fSubs1 = new NuKDBox((fDir+1)%D);
00177     fSubs1->Build(medit+1, i1);
00178   }
00179   else
00180     fSubs1 = 0;
00181 }

template<class T , unsigned int D>
void NuKDBox< T, D >::FindNearestPts ( const NuKDPt< D > &  p,
unsigned int  N,
set< NuKDPtWithPayload< T, D >, NuKDDistOrd< T, D > > &  ret,
const NuKDPt< D > &  lo,
const NuKDPt< D > &  hi,
list< NuKDTaskRecord< T, D > > &  todo 
) const [inline]

Add our child point to the list of best matches if it beats any of the candidates so far. Add our children to todo. Unless we can prove nothing in this box can beat any of our candidate points, in which case the rest of the tree below us won't be searched.

Parameters:
p The point we're finding neighbours for
N The number of neighbours we're trying to find
ret The set of candidate nearest points so far
lo All points in the box are guaranteed to be larger than this
hi All points in the box are guaranteed to be smaller than this
todo If our child boxes need to be searched they will be added to this list

Definition at line 185 of file NuKDTree.cxx.

References NuKDBox< T, D >::fDir, NuKDBox< T, D >::fPt, NuKDBox< T, D >::fSubs0, NuKDBox< T, D >::fSubs1, and SQR.

00191 {
00192   // You learn something new every day... Well, actually I didn't because
00193   // I don't quite understand what typename is needed for. Something to do
00194   // with (un)qualified types and possible instantiation-time ambiguities
00195   typename set<NuKDPtWithPayload<T, D> >::iterator worst = ret.begin();
00196 
00197   // A set is sorted, so this is the squared distance to the worst point so far
00198   float maxdist = DBL_MAX;
00199   if(!ret.empty()){
00200     maxdist = 0;
00201     for(unsigned int d = 0; d < D; ++d)
00202       maxdist += SQR(worst->pt[d]-p[d]);
00203   }
00204 
00205   // Have we found enough points yet?
00206   const bool enough = ret.size() == N;
00207 
00208   if(enough){
00209     // The closest that any of our points can possibly be
00210     // ie the distance to the nearest edge or corner (0 inside)
00211     float minpos = 0;
00212     for(unsigned int d = 0; d < D; ++d){
00213       const float lodist = lo[d]-p[d];
00214       if(lodist > 0){
00215         minpos += SQR(lodist);
00216         if(minpos > maxdist) return;
00217       }
00218       else{
00219         const float hidist = p[d]-hi[d];
00220         if(hidist > 0){
00221           minpos += SQR(hidist);
00222           if(minpos > maxdist) return;
00223         }
00224       }
00225     }
00226   }
00227 
00228   // If the list isn't full yet add our point
00229   if(!enough){
00230     ret.insert(fPt);
00231   }
00232   // Or if our point is better then replace the worst point
00233   else{
00234     float ptDist = 0;
00235     bool better = true;
00236     for(unsigned int d = 0; d < D; ++d){
00237       ptDist += SQR(fPt.pt[d]-p[d]);
00238       if(ptDist > maxdist){
00239         better = false;
00240         break;
00241       }
00242     }
00243     if(better){
00244       ret.erase(worst);
00245       ret.insert(fPt);
00246     }
00247   }
00248 
00249   // We need to ask our children if they can beat anything in the list, so add
00250   // them to the todo list.
00251   if(fSubs0){
00252     NuKDPt<D> pt = hi;
00253     pt[fDir] = fPt.pt[fDir];
00254     todo.push_back(NuKDTaskRecord<T, D>(fSubs0, lo, pt));
00255   }
00256   if(fSubs1){
00257     NuKDPt<D> pt = lo;
00258     pt[fDir] = fPt.pt[fDir];
00259     todo.push_back(NuKDTaskRecord<T, D>(fSubs1, pt, hi));
00260   }
00261 }

template<class T, unsigned int D>
unsigned int NuKDBox< T, D >::NChildren (  )  const [inline]

Number of children contrained in this box.

including fPt and both child boxes

Definition at line 89 of file NuKDTree.cxx.

References NuKDBox< T, D >::fNChild.

00089 {return fNChild;}


Member Data Documentation

template<class T, unsigned int D>
unsigned int NuKDBox< T, D >::fDir [protected]

The dimension in which the bifurcation is to be taken.

Definition at line 118 of file NuKDTree.cxx.

Referenced by NuKDBox< T, D >::Build(), and NuKDBox< T, D >::FindNearestPts().

template<class T, unsigned int D>
unsigned int NuKDBox< T, D >::fNChild [protected]

Number of children of this node, including fPt.

Definition at line 120 of file NuKDTree.cxx.

Referenced by NuKDBox< T, D >::Build(), and NuKDBox< T, D >::NChildren().

template<class T, unsigned int D>
NuKDPtWithPayload<T, D> NuKDBox< T, D >::fPt [protected]

Each box owns exactly one point.

This is where the bifurcation line goes

Definition at line 112 of file NuKDTree.cxx.

Referenced by NuKDBox< T, D >::Build(), and NuKDBox< T, D >::FindNearestPts().

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

Subtree, all points are smaller than fPt along fDir. Maybe null.

Definition at line 114 of file NuKDTree.cxx.

Referenced by NuKDBox< T, D >::Build(), NuKDBox< T, D >::FindNearestPts(), and NuKDBox< T, D >::~NuKDBox().

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

Subtree, all points are larger than fPt along fDir. Maybe null.

Definition at line 116 of file NuKDTree.cxx.

Referenced by NuKDBox< T, D >::Build(), NuKDBox< T, D >::FindNearestPts(), and NuKDBox< T, D >::~NuKDBox().


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

Generated on 24 Jul 2018 for loon by  doxygen 1.6.1