NuVPTree< T, distance > Class Template Reference

#include <NuVPTree.h>

List of all members.

Classes

struct  DistanceComparator
struct  HeapItem
struct  Node

Public Member Functions

 NuVPTree ()
 ~NuVPTree ()
void create (const std::vector< T > &items)
void search (const T &target, int k, std::vector< T > *results, std::vector< double > *distances)

Private Member Functions

NodebuildFromPoints (int lower, int upper)
void search (Node *node, const T &target, int k, std::priority_queue< HeapItem > &heap)

Private Attributes

std::vector< T > _items
double _tau
struct NuVPTree::Node_root

Detailed Description

template<typename T, double(*)(const T &, const T &) distance>
class NuVPTree< T, distance >

Definition at line 16 of file NuVPTree.h.


Constructor & Destructor Documentation

template<typename T, double(*)(const T &, const T &) distance>
NuVPTree< T, distance >::NuVPTree (  )  [inline]

Definition at line 19 of file NuVPTree.h.

00019 : _root(0) {}

template<typename T, double(*)(const T &, const T &) distance>
NuVPTree< T, distance >::~NuVPTree (  )  [inline]

Definition at line 21 of file NuVPTree.h.

00021               {
00022     delete _root;
00023   }


Member Function Documentation

template<typename T, double(*)(const T &, const T &) distance>
Node* NuVPTree< T, distance >::buildFromPoints ( int  lower,
int  upper 
) [inline, private]

Definition at line 90 of file NuVPTree.h.

Referenced by NuVPTree< Point, NukNN::EuclideanDistance >::buildFromPoints(), and NuVPTree< Point, NukNN::EuclideanDistance >::create().

00091   {
00092     if ( upper == lower ) {
00093       return NULL;
00094     }
00095 
00096     Node* node = new Node();
00097     node->index = lower;
00098 
00099     if ( upper - lower > 1 ) {
00100 
00101       // choose an arbitrary point and move it to the start
00102       int i = (int)((double)rand() / RAND_MAX * (upper - lower - 1) ) + lower;
00103       std::swap( _items[lower], _items[i] );
00104 
00105       int median = ( upper + lower ) / 2;
00106 
00107       // partitian around the median distance
00108       std::nth_element(
00109                        _items.begin() + lower + 1,
00110                        _items.begin() + median,
00111                        _items.begin() + upper,
00112                        DistanceComparator( _items[lower] ));
00113 
00114       // what was the median?
00115       node->threshold = distance( _items[lower], _items[median] );
00116 
00117       node->index = lower;
00118       node->left = buildFromPoints( lower + 1, median );
00119       node->right = buildFromPoints( median, upper );
00120     }
00121 
00122     return node;
00123   }

template<typename T, double(*)(const T &, const T &) distance>
void NuVPTree< T, distance >::create ( const std::vector< T > &  items  )  [inline]

Definition at line 25 of file NuVPTree.h.

Referenced by NukNN::Initialize().

00025                                            {
00026     delete _root;
00027     _items = items;
00028     _root = buildFromPoints(0, items.size());
00029   }

template<typename T, double(*)(const T &, const T &) distance>
void NuVPTree< T, distance >::search ( Node node,
const T &  target,
int  k,
std::priority_queue< HeapItem > &  heap 
) [inline, private]

Definition at line 125 of file NuVPTree.h.

00127   {
00128     if ( node == NULL ) return;
00129 
00130     double dist = distance( _items[node->index], target );
00131     //printf("dist=%g tau=%gn", dist, _tau );
00132 
00133     if ( dist < _tau ) {
00134       if ( heap.size() == (unsigned int)k ) heap.pop();
00135       heap.push( HeapItem(node->index, dist) );
00136       if ( heap.size() == (unsigned int)k ) _tau = heap.top().dist;
00137     }
00138 
00139     if ( node->left == NULL && node->right == NULL ) {
00140       return;
00141     }
00142 
00143     if ( dist < node->threshold ) {
00144       //if ( dist - _tau <= node->threshold ) {
00145       search( node->left, target, k, heap );
00146       //}
00147 
00148       if ( dist + _tau >= node->threshold ) {
00149         search( node->right, target, k, heap );
00150       }
00151 
00152     } else {
00153       //if ( dist + _tau >= node->threshold ) {
00154       search( node->right, target, k, heap );
00155       //}
00156 
00157       if ( dist - _tau <= node->threshold ) {
00158         search( node->left, target, k, heap );
00159       }
00160     }
00161   }

template<typename T, double(*)(const T &, const T &) distance>
void NuVPTree< T, distance >::search ( const T &  target,
int  k,
std::vector< T > *  results,
std::vector< double > *  distances 
) [inline]

Definition at line 31 of file NuVPTree.h.

Referenced by NukNN::GetShwEnergy(), and NuVPTree< Point, NukNN::EuclideanDistance >::search().

00033   {
00034     std::priority_queue<HeapItem> heap;
00035 
00036     _tau = std::numeric_limits<double>::max();
00037     search( _root, target, k, heap );
00038 
00039     results->clear(); distances->clear();
00040 
00041     while( !heap.empty() ) {
00042       results->push_back( _items[heap.top().index] );
00043       distances->push_back( heap.top().dist );
00044       heap.pop();
00045     }
00046 
00047     std::reverse( results->begin(), results->end() );
00048     std::reverse( distances->begin(), distances->end() );
00049   }


Member Data Documentation

template<typename T, double(*)(const T &, const T &) distance>
std::vector<T> NuVPTree< T, distance >::_items [private]
template<typename T, double(*)(const T &, const T &) distance>
struct NuVPTree::Node* NuVPTree< T, distance >::_root [private]
template<typename T, double(*)(const T &, const T &) distance>
double NuVPTree< T, distance >::_tau [private]

Definition at line 53 of file NuVPTree.h.

Referenced by NuVPTree< Point, NukNN::EuclideanDistance >::search().


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

Generated on 22 Nov 2017 for loon by  doxygen 1.6.1