queso-0.57.1
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Pages
ANNkd_tree Class Reference

#include <ANN.h>

Inheritance diagram for ANNkd_tree:
ANNpointSet ANNbd_tree

Public Member Functions

 ANNkd_tree (int n=0, int dd=0, int bs=1)
 
 ANNkd_tree (ANNpointArray pa, int n, int dd, int bs=1, ANNsplitRule split=ANN_KD_SUGGEST)
 
 ANNkd_tree (std::istream &in)
 
 ~ANNkd_tree ()
 
void annkSearch (ANNpoint q, int k, ANNidxArray nn_idx, ANNdistArray dd, double eps=0.0)
 
void annkPriSearch (ANNpoint q, int k, ANNidxArray nn_idx, ANNdistArray dd, double eps=0.0)
 
int annkFRSearch (ANNpoint q, ANNdist sqRad, int k, ANNidxArray nn_idx=NULL, ANNdistArray dd=NULL, double eps=0.0)
 
int theDim ()
 
int nPoints ()
 
ANNpointArray thePoints ()
 
virtual void Print (ANNbool with_pts, std::ostream &out)
 
virtual void Dump (ANNbool with_pts, std::ostream &out)
 
virtual void getStats (ANNkdStats &st)
 
- Public Member Functions inherited from ANNpointSet
virtual ~ANNpointSet ()
 

Protected Member Functions

void SkeletonTree (int n, int dd, int bs, ANNpointArray pa=NULL, ANNidxArray pi=NULL)
 

Protected Attributes

int dim
 
int n_pts
 
int bkt_size
 
ANNpointArray pts
 
ANNidxArray pidx
 
ANNkd_ptr root
 
ANNpoint bnd_box_lo
 
ANNpoint bnd_box_hi
 

Detailed Description

Definition at line 705 of file ANN.h.

Constructor & Destructor Documentation

ANNkd_tree::ANNkd_tree ( int  n = 0,
int  dd = 0,
int  bs = 1 
)

Definition at line 273 of file kd_tree.cpp.

References SkeletonTree().

277 { SkeletonTree(n, dd, bs); } // construct skeleton tree
void SkeletonTree(int n, int dd, int bs, ANNpointArray pa=NULL, ANNidxArray pi=NULL)
Definition: kd_tree.cpp:244
ANNkd_tree::ANNkd_tree ( ANNpointArray  pa,
int  n,
int  dd,
int  bs = 1,
ANNsplitRule  split = ANN_KD_SUGGEST 
)

Definition at line 368 of file kd_tree.cpp.

References ANN_KD_FAIR, ANN_KD_MIDPT, ANN_KD_SL_FAIR, ANN_KD_SL_MIDPT, ANN_KD_STD, ANN_KD_SUGGEST, ANNabort, annCopyPt(), annEnclRect(), annError(), bnd_box_hi, bnd_box_lo, fair_split(), ANNorthRect::hi, kd_split(), ANNorthRect::lo, midpt_split(), pidx, pts, rkd_tree(), root, SkeletonTree(), sl_fair_split(), and sl_midpt_split().

374 {
375  SkeletonTree(n, dd, bs); // set up the basic stuff
376  pts = pa; // where the points are
377  if (n == 0) return; // no points--no sweat
378 
379  ANNorthRect bnd_box(dd); // bounding box for points
380  annEnclRect(pa, pidx, n, dd, bnd_box);// construct bounding rectangle
381  // copy to tree structure
382  bnd_box_lo = annCopyPt(dd, bnd_box.lo);
383  bnd_box_hi = annCopyPt(dd, bnd_box.hi);
384 
385  switch (split) { // build by rule
386  case ANN_KD_STD: // standard kd-splitting rule
387  root = rkd_tree(pa, pidx, n, dd, bs, bnd_box, kd_split);
388  break;
389  case ANN_KD_MIDPT: // midpoint split
390  root = rkd_tree(pa, pidx, n, dd, bs, bnd_box, midpt_split);
391  break;
392  case ANN_KD_FAIR: // fair split
393  root = rkd_tree(pa, pidx, n, dd, bs, bnd_box, fair_split);
394  break;
395  case ANN_KD_SUGGEST: // best (in our opinion)
396  case ANN_KD_SL_MIDPT: // sliding midpoint split
397  root = rkd_tree(pa, pidx, n, dd, bs, bnd_box, sl_midpt_split);
398  break;
399  case ANN_KD_SL_FAIR: // sliding fair split
400  root = rkd_tree(pa, pidx, n, dd, bs, bnd_box, sl_fair_split);
401  break;
402  default:
403  annError("Illegal splitting method", ANNabort);
404  }
405 }
void SkeletonTree(int n, int dd, int bs, ANNpointArray pa=NULL, ANNidxArray pi=NULL)
Definition: kd_tree.cpp:244
ANNidxArray pidx
Definition: ANN.h:711
void annEnclRect(ANNpointArray pa, ANNidxArray pidx, int n, int dim, ANNorthRect &bnds)
Definition: kd_util.cpp:73
void sl_midpt_split(ANNpointArray pa, ANNidxArray pidx, const ANNorthRect &bnds, int n, int dim, int &cut_dim, ANNcoord &cut_val, int &n_lo)
Definition: kd_split.cpp:146
void sl_fair_split(ANNpointArray pa, ANNidxArray pidx, const ANNorthRect &bnds, int n, int dim, int &cut_dim, ANNcoord &cut_val, int &n_lo)
Definition: kd_split.cpp:346
ANNkd_ptr rkd_tree(ANNpointArray pa, ANNidxArray pidx, int n, int dim, int bsp, ANNorthRect &bnd_box, ANNkd_splitter splitter)
Definition: kd_tree.cpp:314
void kd_split(ANNpointArray pa, ANNidxArray pidx, const ANNorthRect &bnds, int n, int dim, int &cut_dim, ANNcoord &cut_val, int &n_lo)
Definition: kd_split.cpp:44
ANNpoint bnd_box_lo
Definition: ANN.h:713
ANNkd_ptr root
Definition: ANN.h:712
Definition: ANNx.h:48
ANNpoint bnd_box_hi
Definition: ANN.h:714
void fair_split(ANNpointArray pa, ANNidxArray pidx, const ANNorthRect &bnds, int n, int dim, int &cut_dim, ANNcoord &cut_val, int &n_lo)
Definition: kd_split.cpp:243
ANNsplitRule split
Definition: ann_test.cpp:491
DLL_API ANNpoint annCopyPt(int dim, ANNpoint source)
Definition: ANN.cpp:140
void annError(const char *msg, ANNerr level)
Definition: ANN.cpp:169
void midpt_split(ANNpointArray pa, ANNidxArray pidx, const ANNorthRect &bnds, int n, int dim, int &cut_dim, ANNcoord &cut_val, int &n_lo)
Definition: kd_split.cpp:76
ANNpointArray pts
Definition: ANN.h:710
ANNkd_tree::ANNkd_tree ( std::istream &  in)
ANNkd_tree::~ANNkd_tree ( )

Definition at line 209 of file kd_tree.cpp.

References annDeallocPt(), bnd_box_hi, bnd_box_lo, pidx, and root.

210 {
211  if (root != NULL) delete root;
212  if (pidx != NULL) delete [] pidx;
213  if (bnd_box_lo != NULL) annDeallocPt(bnd_box_lo);
214  if (bnd_box_hi != NULL) annDeallocPt(bnd_box_hi);
215 }
ANNidxArray pidx
Definition: ANN.h:711
DLL_API void annDeallocPt(ANNpoint &p)
Definition: ANN.cpp:127
ANNpoint bnd_box_lo
Definition: ANN.h:713
ANNkd_ptr root
Definition: ANN.h:712
ANNpoint bnd_box_hi
Definition: ANN.h:714

Member Function Documentation

int ANNkd_tree::annkFRSearch ( ANNpoint  q,
ANNdist  sqRad,
int  k,
ANNidxArray  nn_idx = NULL,
ANNdistArray  dd = NULL,
double  eps = 0.0 
)
virtual

Implements ANNpointSet.

Definition at line 58 of file kd_fix_rad_search.cpp.

References annBoxDistance(), ANNkdFRDim, ANNkdFRMaxErr, ANNkdFRPointMK, ANNkdFRPts, ANNkdFRPtsInRange, ANNkdFRPtsVisited, ANNkdFRQ, ANNkdFRSqRad, bnd_box_hi, bnd_box_lo, dim, pts, and root.

Referenced by QUESO::computeMI_ANN(), and main().

65 {
66  ANNkdFRDim = dim; // copy arguments to static equivs
67  ANNkdFRQ = q;
68  ANNkdFRSqRad = sqRad;
69  ANNkdFRPts = pts;
70  ANNkdFRPtsVisited = 0; // initialize count of points visited
71  ANNkdFRPtsInRange = 0; // ...and points in the range
72 
73  ANNkdFRMaxErr = ANN_POW(1.0 + eps);
74  ANN_FLOP(2) // increment floating op count
75 
76  ANNkdFRPointMK = new ANNmin_k(k); // create set for closest k points
77  // search starting at the root
78  root->ann_FR_search(annBoxDistance(q, bnd_box_lo, bnd_box_hi, dim));
79 
80  for (int i = 0; i < k; i++) { // extract the k-th closest points
81  if (dd != NULL)
82  dd[i] = ANNkdFRPointMK->ith_smallest_key(i);
83  if (nn_idx != NULL)
84  nn_idx[i] = ANNkdFRPointMK->ith_smallest_info(i);
85  }
86 
87  delete ANNkdFRPointMK; // deallocate closest point set
88  return ANNkdFRPtsInRange; // return final point count
89 }
ANNmin_k * ANNkdFRPointMK
ANNpoint ANNkdFRQ
ANNpoint bnd_box_lo
Definition: ANN.h:713
ANNpointArray ANNkdFRPts
double ANNkdFRMaxErr
ANNkd_ptr root
Definition: ANN.h:712
int dim
Definition: ANN.h:707
int ANNkdFRDim
ANNpoint bnd_box_hi
Definition: ANN.h:714
int ANNkdFRPtsVisited
ANNdist annBoxDistance(const ANNpoint q, const ANNpoint lo, const ANNpoint hi, int dim)
Definition: kd_util.cpp:124
ANNdist ANNkdFRSqRad
int ANNkdFRPtsInRange
DistArray< T >::DistArray(const Map &inputMap, const int inputRowSize) for(int i=0;i< m_Map.NumGlobalElements();++i)
Definition: DistArray.C:53
ANNpointArray pts
Definition: ANN.h:710
void ANNkd_tree::annkPriSearch ( ANNpoint  q,
int  k,
ANNidxArray  nn_idx,
ANNdistArray  dd,
double  eps = 0.0 
)

Definition at line 87 of file kd_pr_search.cpp.

References annBoxDistance(), ANNmaxPtsVisited, ANNprBoxPQ, ANNprDim, ANNprMaxErr, ANNprPointMK, ANNprPts, ANNprQ, ANNptsVisited, bnd_box_hi, bnd_box_lo, dim, n_pts, pts, and root.

Referenced by main().

93 {
94  // max tolerable squared error
95  ANNprMaxErr = ANN_POW(1.0 + eps);
96  ANN_FLOP(2) // increment floating ops
97 
98  ANNprDim = dim; // copy arguments to static equivs
99  ANNprQ = q;
100  ANNprPts = pts;
101  ANNptsVisited = 0; // initialize count of points visited
102 
103  ANNprPointMK = new ANNmin_k(k); // create set for closest k points
104 
105  // distance to root box
106  ANNdist box_dist = annBoxDistance(q,
107  bnd_box_lo, bnd_box_hi, dim);
108 
109  ANNprBoxPQ = new ANNpr_queue(n_pts);// create priority queue for boxes
110  ANNprBoxPQ->insert(box_dist, root); // insert root in priority queue
111 
112  while (ANNprBoxPQ->non_empty() &&
114  ANNkd_ptr np; // next box from prior queue
115 
116  // extract closest box from queue
117  ANNprBoxPQ->extr_min(box_dist, (void *&) np);
118 
119  ANN_FLOP(2) // increment floating ops
120  if (box_dist*ANNprMaxErr >= ANNprPointMK->max_key())
121  break;
122 
123  np->ann_pri_search(box_dist); // search this subtree.
124  }
125 
126  for (int i = 0; i < k; i++) { // extract the k-th closest points
127  dd[i] = ANNprPointMK->ith_smallest_key(i);
128  nn_idx[i] = ANNprPointMK->ith_smallest_info(i);
129  }
130 
131  delete ANNprPointMK; // deallocate closest point set
132  delete ANNprBoxPQ; // deallocate priority queue
133 }
ANNmin_k * ANNprPointMK
ANNpr_queue * ANNprBoxPQ
double ANNdist
Definition: ANN.h:159
double ANNprMaxErr
int ANNprDim
ANNpoint bnd_box_lo
Definition: ANN.h:713
ANNpoint ANNprQ
int ANNptsVisited
Definition: ANN.cpp:191
ANNkd_ptr root
Definition: ANN.h:712
int dim
Definition: ANN.h:707
int n_pts
Definition: ANN.h:708
ANNpoint bnd_box_hi
Definition: ANN.h:714
int ANNmaxPtsVisited
Definition: ANN.cpp:190
ANNkd_node * ANNkd_ptr
Definition: ANN.h:702
McOptionsValues::McOptionsValues(#ifdef QUESO_USES_SEQUENCE_STATISTICAL_OPTIONS const SsOptionsValues *alternativePSsOptionsValues, const SsOptionsValues *alternativeQSsOptionsValues#endif if)(m_alternativeQSsOptionsValues=*alternativeQSsOptionsValues)
ANNdist annBoxDistance(const ANNpoint q, const ANNpoint lo, const ANNpoint hi, int dim)
Definition: kd_util.cpp:124
ANNpointArray ANNprPts
DistArray< T >::DistArray(const Map &inputMap, const int inputRowSize) for(int i=0;i< m_Map.NumGlobalElements();++i)
Definition: DistArray.C:53
ANNpointArray pts
Definition: ANN.h:710
void ANNkd_tree::annkSearch ( ANNpoint  q,
int  k,
ANNidxArray  nn_idx,
ANNdistArray  dd,
double  eps = 0.0 
)
virtual

Implements ANNpointSet.

Definition at line 89 of file kd_search.cpp.

References ANNabort, annBoxDistance(), annError(), ANNkdDim, ANNkdMaxErr, ANNkdPointMK, ANNkdPts, ANNkdQ, ANNptsVisited, bnd_box_hi, bnd_box_lo, dim, n_pts, pts, and root.

Referenced by QUESO::distANN_XY(), and main().

95 {
96 
97  ANNkdDim = dim; // copy arguments to static equivs
98  ANNkdQ = q;
99  ANNkdPts = pts;
100  ANNptsVisited = 0; // initialize count of points visited
101 
102  if (k > n_pts) { // too many near neighbors?
103  annError("Requesting more near neighbors than data points", ANNabort);
104  }
105 
106  ANNkdMaxErr = ANN_POW(1.0 + eps);
107  ANN_FLOP(2) // increment floating op count
108 
109  ANNkdPointMK = new ANNmin_k(k); // create set for closest k points
110  // search starting at the root
111  root->ann_search(annBoxDistance(q, bnd_box_lo, bnd_box_hi, dim));
112 
113  for (int i = 0; i < k; i++) { // extract the k-th closest points
114  dd[i] = ANNkdPointMK->ith_smallest_key(i);
115  nn_idx[i] = ANNkdPointMK->ith_smallest_info(i);
116  }
117  delete ANNkdPointMK; // deallocate closest point set
118 }
int ANNkdDim
Definition: kd_search.cpp:79
ANNpoint ANNkdQ
Definition: kd_search.cpp:80
ANNpointArray ANNkdPts
Definition: kd_search.cpp:82
ANNpoint bnd_box_lo
Definition: ANN.h:713
int ANNptsVisited
Definition: ANN.cpp:191
double ANNkdMaxErr
Definition: kd_search.cpp:81
ANNkd_ptr root
Definition: ANN.h:712
int dim
Definition: ANN.h:707
Definition: ANNx.h:48
int n_pts
Definition: ANN.h:708
ANNpoint bnd_box_hi
Definition: ANN.h:714
ANNdist annBoxDistance(const ANNpoint q, const ANNpoint lo, const ANNpoint hi, int dim)
Definition: kd_util.cpp:124
void annError(const char *msg, ANNerr level)
Definition: ANN.cpp:169
DistArray< T >::DistArray(const Map &inputMap, const int inputRowSize) for(int i=0;i< m_Map.NumGlobalElements();++i)
Definition: DistArray.C:53
ANNmin_k * ANNkdPointMK
Definition: kd_search.cpp:83
ANNpointArray pts
Definition: ANN.h:710
void ANNkd_tree::Dump ( ANNbool  with_pts,
std::ostream &  out 
)
virtual

Definition at line 102 of file kd_dump.cpp.

References ANNcoordPrec, annPrintPt(), and dim.

Referenced by main().

105 {
106  out << "#ANN " << ANNversion << "\n";
107  out.precision(ANNcoordPrec); // use full precision in dumping
108  if (with_pts) { // print point coordinates
109  out << "points " << dim << " " << n_pts << "\n";
110  for (int i = 0; i < n_pts; i++) {
111  out << i << " ";
112  annPrintPt(pts[i], dim, out);
113  out << "\n";
114  }
115  }
116  out << "tree " // print tree elements
117  << dim << " "
118  << n_pts << " "
119  << bkt_size << "\n";
120 
121  annPrintPt(bnd_box_lo, dim, out); // print lower bound
122  out << "\n";
123  annPrintPt(bnd_box_hi, dim, out); // print upper bound
124  out << "\n";
125 
126  if (root == NULL) // empty tree?
127  out << "null\n";
128  else {
129  root->dump(out); // invoke printing at root
130  }
131  out.precision(0); // restore default precision
132 }
void annPrintPt(ANNpoint pt, int dim, std::ostream &out)
Definition: ANN.cpp:70
ANNpoint bnd_box_lo
Definition: ANN.h:713
int bkt_size
Definition: ANN.h:709
const int ANNcoordPrec
Definition: ANN.h:220
ANNkd_ptr root
Definition: ANN.h:712
int dim
Definition: ANN.h:707
int n_pts
Definition: ANN.h:708
ANNpoint bnd_box_hi
Definition: ANN.h:714
ANNpointArray pts
Definition: ANN.h:710
void ANNkd_tree::getStats ( ANNkdStats st)
virtual

Definition at line 191 of file kd_tree.cpp.

References ANNkdStats::avg_ar, bkt_size, bnd_box_hi, bnd_box_lo, ANNkdStats::n_lf, ANNkdStats::reset(), root, and ANNkdStats::sum_ar.

Referenced by treeStats().

193 {
194  st.reset(dim, n_pts, bkt_size); // reset stats
195  // create bounding box
197  if (root != NULL) { // if nonempty tree
198  root->getStats(dim, st, bnd_box); // get statistics
199  st.avg_ar = st.sum_ar / st.n_lf; // average leaf asp ratio
200  }
201 }
float sum_ar
Definition: ANNperf.h:55
ANNpoint bnd_box_lo
Definition: ANN.h:713
int bkt_size
Definition: ANN.h:709
ANNkd_ptr root
Definition: ANN.h:712
int dim
Definition: ANN.h:707
int n_pts
Definition: ANN.h:708
ANNpoint bnd_box_hi
Definition: ANN.h:714
void reset(int d=0, int n=0, int bs=0)
Definition: ANNperf.h:59
float avg_ar
Definition: ANNperf.h:56
int n_lf
Definition: ANNperf.h:50
int ANNkd_tree::nPoints ( )
inlinevirtual

Implements ANNpointSet.

Definition at line 766 of file ANN.h.

Referenced by main().

767  { return n_pts; }
int n_pts
Definition: ANN.h:708
void ANNkd_tree::Print ( ANNbool  with_pts,
std::ostream &  out 
)
virtual

Definition at line 104 of file kd_tree.cpp.

References annPrintPt(), dim, n_pts, pts, and root.

Referenced by main().

107 {
108  out << "ANN Version " << ANNversion << "\n";
109  if (with_pts) { // print point coordinates
110  out << " Points:\n";
111  for (int i = 0; i < n_pts; i++) {
112  out << "\t" << i << ": ";
113  annPrintPt(pts[i], dim, out);
114  out << "\n";
115  }
116  }
117  if (root == NULL) // empty tree?
118  out << " Null tree.\n";
119  else {
120  root->print(0, out); // invoke printing at root
121  }
122 }
void annPrintPt(ANNpoint pt, int dim, std::ostream &out)
Definition: ANN.cpp:70
ANNkd_ptr root
Definition: ANN.h:712
int dim
Definition: ANN.h:707
int n_pts
Definition: ANN.h:708
ANNpointArray pts
Definition: ANN.h:710
void ANNkd_tree::SkeletonTree ( int  n,
int  dd,
int  bs,
ANNpointArray  pa = NULL,
ANNidxArray  pi = NULL 
)
protected

Definition at line 244 of file kd_tree.cpp.

References bkt_size, bnd_box_hi, bnd_box_lo, IDX_TRIVIAL, KD_TRIVIAL, pidx, pts, and root.

Referenced by ANNkd_tree().

250 {
251  dim = dd; // initialize basic elements
252  n_pts = n;
253  bkt_size = bs;
254  pts = pa; // initialize points array
255 
256  root = NULL; // no associated tree yet
257 
258  if (pi == NULL) { // point indices provided?
259  pidx = new ANNidx[n]; // no, allocate space for point indices
260  for (int i = 0; i < n; i++) {
261  pidx[i] = i; // initially identity
262  }
263  }
264  else {
265  pidx = pi; // yes, use them
266  }
267 
268  bnd_box_lo = bnd_box_hi = NULL; // bounding box is nonexistent
269  if (KD_TRIVIAL == NULL) // no trivial leaf node yet?
270  KD_TRIVIAL = new ANNkd_leaf(0, IDX_TRIVIAL); // allocate it
271 }
ANNidxArray pidx
Definition: ANN.h:711
int ANNidx
Definition: ANN.h:175
static int IDX_TRIVIAL[]
Definition: kd_tree.cpp:49
ANNpoint bnd_box_lo
Definition: ANN.h:713
int bkt_size
Definition: ANN.h:709
ANNkd_leaf * KD_TRIVIAL
Definition: kd_tree.cpp:50
ANNkd_ptr root
Definition: ANN.h:712
int dim
Definition: ANN.h:707
int n_pts
Definition: ANN.h:708
ANNpoint bnd_box_hi
Definition: ANN.h:714
ANNpointArray pts
Definition: ANN.h:710
int ANNkd_tree::theDim ( )
inlinevirtual

Implements ANNpointSet.

Definition at line 763 of file ANN.h.

References dim.

Referenced by main().

764  { return dim; }
int dim
Definition: ANN.h:707
ANNpointArray ANNkd_tree::thePoints ( )
inlinevirtual

Implements ANNpointSet.

Definition at line 769 of file ANN.h.

Referenced by main().

770  { return pts; }
ANNpointArray pts
Definition: ANN.h:710

Member Data Documentation

int ANNkd_tree::bkt_size
protected

Definition at line 709 of file ANN.h.

Referenced by getStats(), and SkeletonTree().

ANNpoint ANNkd_tree::bnd_box_hi
protected
ANNpoint ANNkd_tree::bnd_box_lo
protected
int ANNkd_tree::dim
protected

Definition at line 707 of file ANN.h.

Referenced by annkFRSearch(), annkPriSearch(), annkSearch(), and Print().

int ANNkd_tree::n_pts
protected

Definition at line 708 of file ANN.h.

Referenced by annkPriSearch(), annkSearch(), and Print().

ANNidxArray ANNkd_tree::pidx
protected

Definition at line 711 of file ANN.h.

Referenced by ANNbd_tree::ANNbd_tree(), ANNkd_tree(), SkeletonTree(), and ~ANNkd_tree().

ANNpointArray ANNkd_tree::pts
protected
ANNkd_ptr ANNkd_tree::root
protected

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

Generated on Tue Jun 5 2018 19:48:57 for queso-0.57.1 by  doxygen 1.8.5