NearestNeighborsGNAT.h
1 /*********************************************************************
2 * Software License Agreement (BSD License)
3 *
4 * Copyright (c) 2011, Rice University
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 *
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above
14 * copyright notice, this list of conditions and the following
15 * disclaimer in the documentation and/or other materials provided
16 * with the distribution.
17 * * Neither the name of the Rice University nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32 * POSSIBILITY OF SUCH DAMAGE.
33 *********************************************************************/
34 
35 /* Author: Mark Moll, Bryant Gipson */
36 
37 #ifndef OMPL_DATASTRUCTURES_NEAREST_NEIGHBORS_GNAT_
38 #define OMPL_DATASTRUCTURES_NEAREST_NEIGHBORS_GNAT_
39 
40 #include "ompl/datastructures/NearestNeighbors.h"
41 #include "ompl/datastructures/GreedyKCenters.h"
42 #ifdef GNAT_SAMPLER
43 #include "ompl/datastructures/PDF.h"
44 #endif
45 #include "ompl/util/Exception.h"
46 #include <boost/unordered_set.hpp>
47 #include <queue>
48 #include <algorithm>
49 
50 namespace ompl
51 {
52 
69  template<typename _T>
71  {
72  protected:
74  // internally, we use a priority queue for nearest neighbors, paired
75  // with their distance to the query point
76  typedef std::pair<const _T*,double> DataDist;
77  struct DataDistCompare
78  {
79  bool operator()(const DataDist& d0, const DataDist& d1)
80  {
81  return d0.second < d1.second;
82  }
83  };
84  typedef std::priority_queue<DataDist, std::vector<DataDist>, DataDistCompare> NearQueue;
85 
86  // another internal data structure is a priority queue of nodes to
87  // check next for possible nearest neighbors
88  class Node;
89  typedef std::pair<Node*,double> NodeDist;
90  struct NodeDistCompare
91  {
92  bool operator()(const NodeDist& n0, const NodeDist& n1) const
93  {
94  return (n0.second - n0.first->maxRadius_) > (n1.second - n1.first->maxRadius_);
95  }
96  };
97  typedef std::priority_queue<NodeDist, std::vector<NodeDist>, NodeDistCompare> NodeQueue;
99 
100  public:
101  NearestNeighborsGNAT(unsigned int degree = 4, unsigned int minDegree = 2,
102  unsigned int maxDegree = 6, unsigned int maxNumPtsPerLeaf = 50,
103  unsigned int removedCacheSize = 50, bool rebalancing = false
104 #ifdef GNAT_SAMPLER
105  , double estimatedDimension = 6.0
106 #endif
107  )
108  : NearestNeighbors<_T>(), tree_(NULL), degree_(degree),
109  minDegree_(std::min(degree,minDegree)), maxDegree_(std::max(maxDegree,degree)),
110  maxNumPtsPerLeaf_(maxNumPtsPerLeaf), size_(0),
111  rebuildSize_(rebalancing ? maxNumPtsPerLeaf*degree : std::numeric_limits<std::size_t>::max()),
112  removedCacheSize_(removedCacheSize)
113 #ifdef GNAT_SAMPLER
114  , estimatedDimension_(estimatedDimension)
115 #endif
116  {
117  }
118 
119  virtual ~NearestNeighborsGNAT()
120  {
121  if (tree_)
122  delete tree_;
123  }
125  virtual void setDistanceFunction(const typename NearestNeighbors<_T>::DistanceFunction &distFun)
126  {
128  pivotSelector_.setDistanceFunction(distFun);
129  if (tree_)
131  }
132 
133  virtual void clear()
134  {
135  if (tree_)
136  {
137  delete tree_;
138  tree_ = NULL;
139  }
140  size_ = 0;
141  removed_.clear();
142  if (rebuildSize_ != std::numeric_limits<std::size_t>::max())
144  }
145 
146  virtual bool reportsSortedResults() const
147  {
148  return true;
149  }
150 
151  virtual void add(const _T &data)
152  {
153  if (tree_)
154  {
155  if (isRemoved(data))
157  tree_->add(*this, data);
158  }
159  else
160  {
161  tree_ = new Node(degree_, maxNumPtsPerLeaf_, data);
162  size_ = 1;
163  }
164  }
165  virtual void add(const std::vector<_T> &data)
166  {
167  if (tree_)
169  else if (data.size()>0)
170  {
171  tree_ = new Node(degree_, maxNumPtsPerLeaf_, data[0]);
172 #ifdef GNAT_SAMPLER
173  tree_->subtreeSize_= data.size();
174 #endif
175  for (unsigned int i=1; i<data.size(); ++i)
176  tree_->data_.push_back(data[i]);
177  if (tree_->needToSplit(*this))
178  tree_->split(*this);
179  }
180  size_ += data.size();
181  }
184  {
185  std::vector<_T> lst;
186  list(lst);
187  clear();
188  add(lst);
189  }
195  virtual bool remove(const _T &data)
196  {
197  if (!size_) return false;
198  NearQueue nbhQueue;
199  // find data in tree
200  bool isPivot = nearestKInternal(data, 1, nbhQueue);
201  if (*nbhQueue.top().first != data)
202  return false;
203  removed_.insert(nbhQueue.top().first);
204  size_--;
205  // if we removed a pivot or if the capacity of removed elements
206  // has been reached, we rebuild the entire GNAT
207  if (isPivot || removed_.size()>=removedCacheSize_)
209  return true;
210  }
211 
212  virtual _T nearest(const _T &data) const
213  {
214  if (size_)
215  {
216  std::vector<_T> nbh;
217  nearestK(data, 1, nbh);
218  if (!nbh.empty()) return nbh[0];
219  }
220  throw Exception("No elements found in nearest neighbors data structure");
221  }
222 
224  virtual void nearestK(const _T &data, std::size_t k, std::vector<_T> &nbh) const
225  {
226  nbh.clear();
227  if (k == 0) return;
228  if (size_)
229  {
230  NearQueue nbhQueue;
231  nearestKInternal(data, k, nbhQueue);
232  postprocessNearest(nbhQueue, nbh);
233  }
234  }
235 
237  virtual void nearestR(const _T &data, double radius, std::vector<_T> &nbh) const
238  {
239  nbh.clear();
240  if (size_)
241  {
242  NearQueue nbhQueue;
243  nearestRInternal(data, radius, nbhQueue);
244  postprocessNearest(nbhQueue, nbh);
245  }
246  }
247 
248  virtual std::size_t size() const
249  {
250  return size_;
251  }
252 
253 #ifdef GNAT_SAMPLER
254  const _T& sample(RNG &rng) const
256  {
257  if (!size())
258  throw Exception("Cannot sample from an empty tree");
259  else
260  return tree_->sample(*this, rng);
261  }
262 #endif
263 
264  virtual void list(std::vector<_T> &data) const
265  {
266  data.clear();
267  data.reserve(size());
268  if (tree_)
269  tree_->list(*this, data);
270  }
271 
273  friend std::ostream& operator<<(std::ostream& out, const NearestNeighborsGNAT<_T>& gnat)
274  {
275  if (gnat.tree_)
276  {
277  out << *gnat.tree_;
278  if (!gnat.removed_.empty())
279  {
280  out << "Elements marked for removal:\n";
281  for (typename boost::unordered_set<const _T*>::const_iterator it = gnat.removed_.begin();
282  it != gnat.removed_.end(); it++)
283  out << **it << '\t';
284  out << std::endl;
285  }
286  }
287  return out;
288  }
289 
290  // for debugging purposes
291  void integrityCheck()
292  {
293  std::vector<_T> lst;
294  boost::unordered_set<const _T*> tmp;
295  // get all elements, including those marked for removal
296  removed_.swap(tmp);
297  list(lst);
298  // check if every element marked for removal is also in the tree
299  for (typename boost::unordered_set<const _T*>::iterator it=tmp.begin(); it!=tmp.end(); it++)
300  {
301  unsigned int i;
302  for (i=0; i<lst.size(); ++i)
303  if (lst[i]==**it)
304  break;
305  if (i == lst.size())
306  {
307  // an element marked for removal is not actually in the tree
308  std::cout << "***** FAIL!! ******\n" << *this << '\n';
309  for (unsigned int j=0; j<lst.size(); ++j) std::cout<<lst[j]<<'\t';
310  std::cout<<std::endl;
311  }
312  assert(i != lst.size());
313  }
314  // restore
315  removed_.swap(tmp);
316  // get elements in the tree with elements marked for removal purged from the list
317  list(lst);
318  if (lst.size() != size_)
319  std::cout << "#########################################\n" << *this << std::endl;
320  assert(lst.size() == size_);
321  }
322  protected:
324 
326  bool isRemoved(const _T& data) const
327  {
328  return !removed_.empty() && removed_.find(&data) != removed_.end();
329  }
330 
335  bool nearestKInternal(const _T &data, std::size_t k, NearQueue& nbhQueue) const
336  {
337  bool isPivot;
338  double dist;
339  NodeDist nodeDist;
340  NodeQueue nodeQueue;
341 
342  isPivot = tree_->insertNeighborK(nbhQueue, k, tree_->pivot_, data,
344  tree_->nearestK(*this, data, k, nbhQueue, nodeQueue, isPivot);
345  while (nodeQueue.size() > 0)
346  {
347  dist = nbhQueue.top().second; // note the difference with nearestRInternal
348  nodeDist = nodeQueue.top();
349  nodeQueue.pop();
350  if (nbhQueue.size() == k &&
351  (nodeDist.second > nodeDist.first->maxRadius_ + dist ||
352  nodeDist.second < nodeDist.first->minRadius_ - dist))
353  break;
354  nodeDist.first->nearestK(*this, data, k, nbhQueue, nodeQueue, isPivot);
355  }
356  return isPivot;
357  }
359  void nearestRInternal(const _T &data, double radius, NearQueue& nbhQueue) const
360  {
361  double dist = radius; // note the difference with nearestKInternal
362  NodeQueue nodeQueue;
363  NodeDist nodeDist;
364 
365  tree_->insertNeighborR(nbhQueue, radius, tree_->pivot_,
367  tree_->nearestR(*this, data, radius, nbhQueue, nodeQueue);
368  while (nodeQueue.size() > 0)
369  {
370  nodeDist = nodeQueue.top();
371  nodeQueue.pop();
372  if (nodeDist.second > nodeDist.first->maxRadius_ + dist ||
373  nodeDist.second < nodeDist.first->minRadius_ - dist)
374  break;
375  nodeDist.first->nearestR(*this, data, radius, nbhQueue, nodeQueue);
376  }
377  }
380  void postprocessNearest(NearQueue& nbhQueue, std::vector<_T> &nbh) const
381  {
382  typename std::vector<_T>::reverse_iterator it;
383  nbh.resize(nbhQueue.size());
384  for (it=nbh.rbegin(); it!=nbh.rend(); it++, nbhQueue.pop())
385  *it = *nbhQueue.top().first;
386  }
387 
389  class Node
390  {
391  public:
394  Node(int degree, int capacity, const _T& pivot)
395  : degree_(degree), pivot_(pivot),
396  minRadius_(std::numeric_limits<double>::infinity()),
397  maxRadius_(-minRadius_), minRange_(degree, minRadius_),
398  maxRange_(degree, maxRadius_)
399 #ifdef GNAT_SAMPLER
400  , subtreeSize_(1), activity_(0)
401 #endif
402  {
403  // The "+1" is needed because we add an element before we check whether to split
404  data_.reserve(capacity+1);
405  }
406 
407  ~Node()
408  {
409  for (unsigned int i=0; i<children_.size(); ++i)
410  delete children_[i];
411  }
412 
415  void updateRadius(double dist)
416  {
417  if (minRadius_ > dist)
418  minRadius_ = dist;
419 #ifndef GNAT_SAMPLER
420  if (maxRadius_ < dist)
421  maxRadius_ = dist;
422 #else
423  if (maxRadius_ < dist)
424  {
425  maxRadius_ = dist;
426  activity_ = 0;
427  }
428  else
429  activity_ = std::max(-32, activity_ - 1);
430 #endif
431  }
435  void updateRange(unsigned int i, double dist)
436  {
437  if (minRange_[i] > dist)
438  minRange_[i] = dist;
439  if (maxRange_[i] < dist)
440  maxRange_[i] = dist;
441  }
443  void add(GNAT& gnat, const _T& data)
444  {
445 #ifdef GNAT_SAMPLER
446  subtreeSize_++;
447 #endif
448  if (children_.size()==0)
449  {
450  data_.push_back(data);
451  gnat.size_++;
452  if (needToSplit(gnat))
453  {
454  if (gnat.removed_.size() > 0)
455  gnat.rebuildDataStructure();
456  else if (gnat.size_ >= gnat.rebuildSize_)
457  {
458  gnat.rebuildSize_ <<= 1;
459  gnat.rebuildDataStructure();
460  }
461  else
462  split(gnat);
463  }
464  }
465  else
466  {
467  std::vector<double> dist(children_.size());
468  double minDist = dist[0] = gnat.distFun_(data, children_[0]->pivot_);
469  int minInd = 0;
470 
471  for (unsigned int i=1; i<children_.size(); ++i)
472  if ((dist[i] = gnat.distFun_(data, children_[i]->pivot_)) < minDist)
473  {
474  minDist = dist[i];
475  minInd = i;
476  }
477  for (unsigned int i=0; i<children_.size(); ++i)
478  children_[i]->updateRange(minInd, dist[i]);
479  children_[minInd]->updateRadius(minDist);
480  children_[minInd]->add(gnat, data);
481  }
482  }
484  bool needToSplit(const GNAT& gnat) const
485  {
486  unsigned int sz = data_.size();
487  return sz > gnat.maxNumPtsPerLeaf_ && sz > degree_;
488  }
492  void split(GNAT& gnat)
493  {
494  std::vector<std::vector<double> > dists;
495  std::vector<unsigned int> pivots;
496 
497  children_.reserve(degree_);
498  gnat.pivotSelector_.kcenters(data_, degree_, pivots, dists);
499  for(unsigned int i=0; i<pivots.size(); i++)
500  children_.push_back(new Node(degree_, gnat.maxNumPtsPerLeaf_, data_[pivots[i]]));
501  degree_ = pivots.size(); // in case fewer than degree_ pivots were found
502  for (unsigned int j=0; j<data_.size(); ++j)
503  {
504  unsigned int k = 0;
505  for (unsigned int i=1; i<degree_; ++i)
506  if (dists[j][i] < dists[j][k])
507  k = i;
508  Node *child = children_[k];
509  if (j != pivots[k])
510  {
511  child->data_.push_back(data_[j]);
512  child->updateRadius(dists[j][k]);
513  }
514  for (unsigned int i=0; i<degree_; ++i)
515  children_[i]->updateRange(k, dists[j][i]);
516  }
517 
518  for (unsigned int i=0; i<degree_; ++i)
519  {
520  // make sure degree lies between minDegree_ and maxDegree_
521  children_[i]->degree_ = std::min(std::max(
522  degree_ * (unsigned int)(children_[i]->data_.size() / data_.size()),
523  gnat.minDegree_), gnat.maxDegree_);
524  // singleton
525  if (children_[i]->minRadius_ >= std::numeric_limits<double>::infinity())
526  children_[i]->minRadius_ = children_[i]->maxRadius_ = 0.;
527 #ifdef GNAT_SAMPLER
528  // set subtree size
529  children_[i]->subtreeSize_ = children_[i]->data_.size() + 1;
530 #endif
531  }
532  // this does more than clear(); it also sets capacity to 0 and frees the memory
533  std::vector<_T> tmp;
534  data_.swap(tmp);
535  // check if new leaves need to be split
536  for (unsigned int i=0; i<degree_; ++i)
537  if (children_[i]->needToSplit(gnat))
538  children_[i]->split(gnat);
539  }
540 
542  bool insertNeighborK(NearQueue& nbh, std::size_t k, const _T& data, const _T& key, double dist) const
543  {
544  if (nbh.size() < k)
545  {
546  nbh.push(std::make_pair(&data, dist));
547  return true;
548  }
549  else if (dist < nbh.top().second ||
550  (dist < std::numeric_limits<double>::epsilon() && data==key))
551  {
552  nbh.pop();
553  nbh.push(std::make_pair(&data, dist));
554  return true;
555  }
556  return false;
557  }
558 
564  void nearestK(const GNAT& gnat, const _T &data, std::size_t k,
565  NearQueue& nbh, NodeQueue& nodeQueue, bool &isPivot) const
566  {
567  for (unsigned int i=0; i<data_.size(); ++i)
568  if (!gnat.isRemoved(data_[i]))
569  {
570  if (insertNeighborK(nbh, k, data_[i], data, gnat.distFun_(data, data_[i])))
571  isPivot = false;
572  }
573  if (children_.size() > 0)
574  {
575  double dist;
576  Node *child;
577  std::vector<double> distToPivot(children_.size());
578  std::vector<int> permutation(children_.size());
579 
580  for (unsigned int i=0; i<permutation.size(); ++i)
581  permutation[i] = i;
582  std::random_shuffle(permutation.begin(), permutation.end());
583 
584  for (unsigned int i=0; i<children_.size(); ++i)
585  if (permutation[i] >= 0)
586  {
587  child = children_[permutation[i]];
588  distToPivot[permutation[i]] = gnat.distFun_(data, child->pivot_);
589  if (insertNeighborK(nbh, k, child->pivot_, data, distToPivot[permutation[i]]))
590  isPivot = true;
591  if (nbh.size()==k)
592  {
593  dist = nbh.top().second; // note difference with nearestR
594  for (unsigned int j=0; j<children_.size(); ++j)
595  if (permutation[j] >=0 && i != j &&
596  (distToPivot[permutation[i]] - dist > child->maxRange_[permutation[j]] ||
597  distToPivot[permutation[i]] + dist < child->minRange_[permutation[j]]))
598  permutation[j] = -1;
599  }
600  }
601 
602  dist = nbh.top().second;
603  for (unsigned int i=0; i<children_.size(); ++i)
604  if (permutation[i] >= 0)
605  {
606  child = children_[permutation[i]];
607  if (nbh.size()<k ||
608  (distToPivot[permutation[i]] - dist <= child->maxRadius_ &&
609  distToPivot[permutation[i]] + dist >= child->minRadius_))
610  nodeQueue.push(std::make_pair(child, distToPivot[permutation[i]]));
611  }
612  }
613  }
615  void insertNeighborR(NearQueue& nbh, double r, const _T& data, double dist) const
616  {
617  if (dist <= r)
618  nbh.push(std::make_pair(&data, dist));
619  }
623  void nearestR(const GNAT& gnat, const _T &data, double r, NearQueue& nbh, NodeQueue& nodeQueue) const
624  {
625  double dist = r; //note difference with nearestK
626 
627  for (unsigned int i=0; i<data_.size(); ++i)
628  if (!gnat.isRemoved(data_[i]))
629  insertNeighborR(nbh, r, data_[i], gnat.distFun_(data, data_[i]));
630  if (children_.size() > 0)
631  {
632  Node *child;
633  std::vector<double> distToPivot(children_.size());
634  std::vector<int> permutation(children_.size());
635 
636  for (unsigned int i=0; i<permutation.size(); ++i)
637  permutation[i] = i;
638  std::random_shuffle(permutation.begin(), permutation.end());
639 
640  for (unsigned int i=0; i<children_.size(); ++i)
641  if (permutation[i] >= 0)
642  {
643  child = children_[permutation[i]];
644  distToPivot[i] = gnat.distFun_(data, child->pivot_);
645  insertNeighborR(nbh, r, child->pivot_, distToPivot[i]);
646  for (unsigned int j=0; j<children_.size(); ++j)
647  if (permutation[j] >=0 && i != j &&
648  (distToPivot[i] - dist > child->maxRange_[permutation[j]] ||
649  distToPivot[i] + dist < child->minRange_[permutation[j]]))
650  permutation[j] = -1;
651  }
652 
653  for (unsigned int i=0; i<children_.size(); ++i)
654  if (permutation[i] >= 0)
655  {
656  child = children_[permutation[i]];
657  if (distToPivot[i] - dist <= child->maxRadius_ &&
658  distToPivot[i] + dist >= child->minRadius_)
659  nodeQueue.push(std::make_pair(child, distToPivot[i]));
660  }
661  }
662  }
663 
664 #ifdef GNAT_SAMPLER
665  double getSamplingWeight(const GNAT& gnat) const
666  {
667  double minR = std::numeric_limits<double>::max();
668  for(size_t i = 0; i<minRange_.size(); i++)
669  if(minRange_[i] < minR && minRange_[i] > 0.0)
670  minR = minRange_[i];
671  minR = std::max(minR, maxRadius_);
672  return std::pow(minR, gnat.estimatedDimension_) / (double) subtreeSize_;
673  }
674  const _T& sample(const GNAT& gnat, RNG &rng) const
675  {
676  if (children_.size() != 0)
677  {
678  if (rng.uniform01() < 1./(double) subtreeSize_)
679  return pivot_;
680  PDF<const Node*> distribution;
681  for(unsigned int i = 0; i < children_.size(); ++i)
682  distribution.add(children_[i], children_[i]->getSamplingWeight(gnat));
683  return distribution.sample(rng.uniform01())->sample(gnat, rng);
684  }
685  else
686  {
687  unsigned int i = rng.uniformInt(0, data_.size());
688  return (i==data_.size()) ? pivot_ : data_[i];
689  }
690  }
691 #endif
692 
693  void list(const GNAT& gnat, std::vector<_T> &data) const
694  {
695  if (!gnat.isRemoved(pivot_))
696  data.push_back(pivot_);
697  for (unsigned int i=0; i<data_.size(); ++i)
698  if(!gnat.isRemoved(data_[i]))
699  data.push_back(data_[i]);
700  for (unsigned int i=0; i<children_.size(); ++i)
701  children_[i]->list(gnat, data);
702  }
703 
704  friend std::ostream& operator<<(std::ostream& out, const Node &node)
705  {
706  out << "\ndegree:\t" << node.degree_;
707  out << "\nminRadius:\t" << node.minRadius_;
708  out << "\nmaxRadius:\t" << node.maxRadius_;
709  out << "\nminRange:\t";
710  for (unsigned int i=0; i<node.minRange_.size(); ++i)
711  out << node.minRange_[i] << '\t';
712  out << "\nmaxRange: ";
713  for (unsigned int i=0; i<node.maxRange_.size(); ++i)
714  out << node.maxRange_[i] << '\t';
715  out << "\npivot:\t" << node.pivot_;
716  out << "\ndata: ";
717  for (unsigned int i=0; i<node.data_.size(); ++i)
718  out << node.data_[i] << '\t';
719  out << "\nthis:\t" << &node;
720 #ifdef GNAT_SAMPLER
721  out << "\nsubtree size:\t" << node.subtreeSize_;
722  out << "\nactivity:\t" << node.activity_;
723 #endif
724  out << "\nchildren:\n";
725  for (unsigned int i=0; i<node.children_.size(); ++i)
726  out << node.children_[i] << '\t';
727  out << '\n';
728  for (unsigned int i=0; i<node.children_.size(); ++i)
729  out << *node.children_[i] << '\n';
730  return out;
731  }
732 
734  unsigned int degree_;
736  const _T pivot_;
738  double minRadius_;
740  double maxRadius_;
743  std::vector<double> minRange_;
746  std::vector<double> maxRange_;
749  std::vector<_T> data_;
752  std::vector<Node*> children_;
753 #ifdef GNAT_SAMPLER
754  unsigned int subtreeSize_;
760  int activity_;
761 #endif
762  };
763 
767  unsigned int degree_;
772  unsigned int minDegree_;
777  unsigned int maxDegree_;
780  unsigned int maxNumPtsPerLeaf_;
782  std::size_t size_;
785  std::size_t rebuildSize_;
789  std::size_t removedCacheSize_;
793  boost::unordered_set<const _T*> removed_;
794 #ifdef GNAT_SAMPLER
795  double estimatedDimension_;
797 #endif
798  };
799 
800 }
801 
802 #endif
std::vector< double > maxRange_
The i-th element in maxRange_ is the maximum distance between the pivot and any data_ element in the ...
std::vector< _T > data_
The data elements stored in this node (in addition to the pivot element). An internal node has no ele...
virtual std::size_t size() const
Get the number of elements in the datastructure.
virtual void nearestR(const _T &data, double radius, std::vector< _T > &nbh) const
Return the nearest neighbors within distance radius in sorted order.
std::size_t size_
Number of elements stored in the tree.
unsigned int maxNumPtsPerLeaf_
Maximum number of elements allowed to be stored in a Node before it needs to be split into several no...
void updateRadius(double dist)
Update minRadius_ and maxRadius_, given that an element was added with distance dist to the pivot...
An instance of this class can be used to greedily select a given number of representatives from a set...
boost::function< double(const _T &, const _T &)> DistanceFunction
The definition of a distance function.
void add(GNAT &gnat, const _T &data)
Add an element to the tree rooted at this node.
const _T pivot_
Data element stored in this Node.
bool nearestKInternal(const _T &data, std::size_t k, NearQueue &nbhQueue) const
Return in nbhQueue the k nearest neighbors of data. For k=1, return true if the nearest neighbor is a...
virtual void setDistanceFunction(const typename NearestNeighbors< _T >::DistanceFunction &distFun)
Set the distance function to use.
void insertNeighborR(NearQueue &nbh, double r, const _T &data, double dist) const
Insert data in nbh if it is a near neighbor.
STL namespace.
double minRadius_
Minimum distance between the pivot element and the elements stored in data_.
Geometric Near-neighbor Access Tree (GNAT), a data structure for nearest neighbor search...
void rebuildDataStructure()
Rebuild the internal data structure.
void nearestK(const GNAT &gnat, const _T &data, std::size_t k, NearQueue &nbh, NodeQueue &nodeQueue, bool &isPivot) const
Compute the k nearest neighbors of data in the tree. For k=1, isPivot is true if the nearest neighbor...
unsigned int maxDegree_
After splitting a Node, each child Node has degree equal to the default degree times the fraction of ...
void split(GNAT &gnat)
The split operation finds pivot elements for the child nodes and moves each data element of this node...
A container that supports probabilistic sampling over weighted data.
Definition: PDF.h:48
double uniform01()
Generate a random real between 0 and 1.
Definition: RandomNumbers.h:62
unsigned int minDegree_
After splitting a Node, each child Node has degree equal to the default degree times the fraction of ...
Main namespace. Contains everything in this library.
Definition: Cost.h:42
Random number generation. An instance of this class cannot be used by multiple threads at once (membe...
Definition: RandomNumbers.h:54
void nearestR(const GNAT &gnat, const _T &data, double r, NearQueue &nbh, NodeQueue &nodeQueue) const
Return all elements that are within distance r in nbh. The nodeQueue, which contains other Nodes that...
virtual _T nearest(const _T &data) const
Get the nearest neighbor of a point.
virtual void setDistanceFunction(const DistanceFunction &distFun)
Set the distance function to use.
virtual void nearestK(const _T &data, std::size_t k, std::vector< _T > &nbh) const
Return the k nearest neighbors in sorted order.
virtual void list(std::vector< _T > &data) const
Get all the elements in the datastructure.
void nearestRInternal(const _T &data, double radius, NearQueue &nbhQueue) const
Return in nbhQueue the elements that are within distance radius of data.
virtual void add(const _T &data)
Add an element to the datastructure.
void updateRange(unsigned int i, double dist)
Update minRange_[i] and maxRange_[i], given that an element was added to the i-th child of the parent...
GreedyKCenters< _T > pivotSelector_
The data structure used to split data into subtrees.
virtual bool reportsSortedResults() const
Return true if the solutions reported by this data structure are sorted, when calling nearestK / near...
DistanceFunction distFun_
The used distance function.
std::size_t rebuildSize_
If size_ exceeds rebuildSize_, the tree will be rebuilt (and automatically rebalanced), and rebuildSize_ will be doubled.
friend std::ostream & operator<<(std::ostream &out, const NearestNeighborsGNAT< _T > &gnat)
Print a GNAT structure (mostly useful for debugging purposes).
Abstract representation of a container that can perform nearest neighbors queries.
The exception type for ompl.
Definition: Exception.h:47
virtual void add(const _T &data)=0
Add an element to the datastructure.
Element * add(const _T &d, const double w)
Adds a piece of data with a given weight to the PDF. Returns a corresponding Element, which can be used to subsequently update or remove the data from the PDF.
Definition: PDF.h:97
std::vector< double > minRange_
The i-th element in minRange_ is the minimum distance between the pivot and any data_ element in the ...
unsigned int degree_
Number of child nodes.
boost::unordered_set< const _T * > removed_
Cache of removed elements.
bool isRemoved(const _T &data) const
Return true iff data has been marked for removal.
bool insertNeighborK(NearQueue &nbh, std::size_t k, const _T &data, const _T &key, double dist) const
Insert data in nbh if it is a near neighbor. Return true iff data was added to nbh.
void postprocessNearest(NearQueue &nbhQueue, std::vector< _T > &nbh) const
Convert the internal data structure used for storing neighbors to the vector that NearestNeighbor API...
Node * tree_
The data structure containing the elements stored in this structure.
virtual void clear()
Clear the datastructure.
The class used internally to define the GNAT.
std::vector< Node * > children_
The child nodes of this node. By definition, only internal nodes have child nodes.
double maxRadius_
Maximum distance between the pivot element and the elements stored in data_.
int uniformInt(int lower_bound, int upper_bound)
Generate a random integer within given bounds: [lower_bound, upper_bound].
Definition: RandomNumbers.h:75
unsigned int degree_
The desired degree of each node.
virtual void add(const std::vector< _T > &data)
Add a vector of points.
_T & sample(double r) const
Returns a piece of data from the PDF according to the input sampling value, which must be between 0 a...
Definition: PDF.h:132
std::size_t removedCacheSize_
Maximum number of removed elements that can be stored in the removed_ cache. If the cache is full...
Node(int degree, int capacity, const _T &pivot)
Construct a node of given degree with at most capacity data elements and with given pivot...
bool needToSplit(const GNAT &gnat) const
Return true iff the node needs to be split into child nodes.