loon: NuKDBox< T, D > Class Template Reference

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.

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 }


Public Member Functions
	NuKDBox (unsigned int d=0)
	d The dimension along which the box is divided
	~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.
NuKDBox *	fSubs0
	Subtree, all points are smaller than fPt along fDir. Maybe null.
NuKDBox *	fSubs1
	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.

NuKDBox< T, D > Class Template Reference

Public Member Functions

Protected Attributes

Detailed Description

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

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation