NearestNeighborsGNATNoThreadSafety.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_NO_THREAD_SAFETY_
38 #define OMPL_DATASTRUCTURES_NEAREST_NEIGHBORS_GNAT_NO_THREAD_SAFETY_
39 
40 #include "ompl/datastructures/NearestNeighbors.h"
41 #include "ompl/datastructures/GreedyKCenters.h"
42 #include "ompl/datastructures/Permutation.h"
43 #ifdef GNAT_SAMPLER
44 #include "ompl/datastructures/PDF.h"
45 #endif
46 #include "ompl/util/Exception.h"
47 #include <unordered_set>
48 #include <queue>
49 #include <algorithm>
50 #include <utility>
51 
52 namespace ompl
53 {
70  template <typename _T>
71  class NearestNeighborsGNATNoThreadSafety : public NearestNeighbors<_T>
72  {
73  protected:
75  // internally, we use a priority queue for nearest neighbors, paired
76  // with their distance to the query point
77  using NearQueue = std::priority_queue<std::pair<double, const _T *>>;
79 
80  public:
81  NearestNeighborsGNATNoThreadSafety(unsigned int degree = 8, unsigned int minDegree = 4,
82  unsigned int maxDegree = 12, unsigned int maxNumPtsPerLeaf = 50,
83  unsigned int removedCacheSize = 500, bool rebalancing = false
84 #ifdef GNAT_SAMPLER
85  ,
86  double estimatedDimension = 6.0
87 #endif
88  )
89  : NearestNeighbors<_T>()
90  , degree_(degree)
91  , minDegree_(std::min(degree, minDegree))
92  , maxDegree_(std::max(maxDegree, degree))
93  , maxNumPtsPerLeaf_(maxNumPtsPerLeaf)
94  , rebuildSize_(rebalancing ? maxNumPtsPerLeaf * degree : std::numeric_limits<std::size_t>::max())
95  , removedCacheSize_(removedCacheSize)
98 #ifdef GNAT_SAMPLER
99  , estimatedDimension_(estimatedDimension)
100 #endif
101  {
102  }
103 
105  {
106  delete tree_;
107  }
109  void setDistanceFunction(const typename NearestNeighbors<_T>::DistanceFunction &distFun) override
110  {
112  pivotSelector_.setDistanceFunction(distFun);
113  if (tree_)
115  }
116 
117  void clear() override
118  {
119  if (tree_)
120  {
121  delete tree_;
122  tree_ = nullptr;
123  }
124  size_ = 0;
125  removed_.clear();
126  if (rebuildSize_ != std::numeric_limits<std::size_t>::max())
128  }
129 
130  bool reportsSortedResults() const override
131  {
132  return true;
133  }
134 
135  void add(const _T &data) override
136  {
137  if (tree_)
138  {
139  if (isRemoved(data))
141  tree_->add(*this, data);
142  }
143  else
144  {
145  tree_ = new Node(degree_, maxNumPtsPerLeaf_, data);
146  size_ = 1;
147  }
148  }
149  void add(const std::vector<_T> &data) override
150  {
151  if (tree_)
153  else if (!data.empty())
154  {
155  tree_ = new Node(degree_, maxNumPtsPerLeaf_, data[0]);
156 #ifdef GNAT_SAMPLER
157  tree_->subtreeSize_ = data.size();
158 #endif
159  tree_->data_.insert(tree_->data_.end(), data.begin() + 1, data.end());
160  size_ += data.size();
161  if (tree_->needToSplit(*this))
162  tree_->split(*this);
163  }
164  }
166  void rebuildDataStructure()
167  {
168  std::vector<_T> lst;
169  list(lst);
170  clear();
171  add(lst);
172  }
178  bool remove(const _T &data) override
179  {
180  if (size_ == 0u)
181  return false;
182  // find data in tree
183  bool isPivot = nearestKInternal(data, 1);
184  const _T *d = nearQueue_.top().second;
185  nearQueue_.pop();
186  if (*d != data)
187  return false;
188  removed_.insert(d);
189  size_--;
190  // if we removed a pivot or if the capacity of removed elements
191  // has been reached, we rebuild the entire GNAT
192  if (isPivot || removed_.size() >= removedCacheSize_)
194  return true;
195  }
196 
197  _T nearest(const _T &data) const override
198  {
199  if (size_)
200  {
201  nearestKInternal(data, 1);
202  if (!nearQueue_.empty())
203  {
204  _T result = *nearQueue_.top().second;
205  nearQueue_.pop();
206  return result;
207  }
208  }
209  throw Exception("No elements found in nearest neighbors data structure");
210  }
211 
213  void nearestK(const _T &data, std::size_t k, std::vector<_T> &nbh) const override
214  {
215  nbh.clear();
216  if (k == 0)
217  return;
218  if (size_)
219  {
220  nearestKInternal(data, k);
221  postprocessNearest(nbh);
222  }
223  }
224 
226  void nearestR(const _T &data, double radius, std::vector<_T> &nbh) const override
227  {
228  nbh.clear();
229  if (size_)
230  {
231  nearestRInternal(data, radius);
232  postprocessNearest(nbh);
233  }
234  assert(nearQueue_.empty());
235  assert(nodeQueue_.empty());
236  }
237 
238  std::size_t size() const override
239  {
240  return size_;
241  }
242 
243 #ifdef GNAT_SAMPLER
244  const _T &sample(RNG &rng) const
246  {
247  if (!size())
248  throw Exception("Cannot sample from an empty tree");
249  else
250  return tree_->sample(*this, rng);
251  }
252 #endif
253 
254  void list(std::vector<_T> &data) const override
255  {
256  data.clear();
257  data.reserve(size());
258  if (tree_)
259  tree_->list(*this, data);
260  }
261 
263  friend std::ostream &operator<<(std::ostream &out, const NearestNeighborsGNATNoThreadSafety<_T> &gnat)
264  {
265  if (gnat.tree_)
266  {
267  out << *gnat.tree_;
268  if (!gnat.removed_.empty())
269  {
270  out << "Elements marked for removal:\n";
271  for (const auto &elt : gnat.removed_)
272  out << *elt << '\t';
273  out << std::endl;
274  }
275  }
276  return out;
277  }
278 
279  // for debugging purposes
280  void integrityCheck()
281  {
282  std::vector<_T> lst;
283  std::unordered_set<const _T *> tmp;
284  // get all elements, including those marked for removal
285  removed_.swap(tmp);
286  list(lst);
287  // check if every element marked for removal is also in the tree
288  for (const auto &elt : tmp)
289  {
290  unsigned int i;
291  for (i = 0; i < lst.size(); ++i)
292  if (lst[i] == *elt)
293  break;
294  if (i == lst.size())
295  {
296  // an element marked for removal is not actually in the tree
297  std::cout << "***** FAIL!! ******\n" << *this << '\n';
298  for (const auto &l : lst)
299  std::cout << l << '\t';
300  std::cout << std::endl;
301  }
302  assert(i != lst.size());
303  }
304  // restore
305  removed_.swap(tmp);
306  // get elements in the tree with elements marked for removal purged from the list
307  list(lst);
308  if (lst.size() != size_)
309  std::cout << "#########################################\n" << *this << std::endl;
310  assert(lst.size() == size_);
311  }
312 
313  protected:
314  using GNAT = NearestNeighborsGNATNoThreadSafety<_T>;
315 
317  bool isRemoved(const _T &data) const
318  {
319  return !removed_.empty() && removed_.find(&data) != removed_.end();
320  }
325  bool nearestKInternal(const _T &data, std::size_t k) const
326  {
327  bool isPivot;
328  double dist;
329  Node *node;
330 
332  isPivot = tree_->insertNeighborK(nearQueue_, k, tree_->pivot_, data, tree_->distToPivot_);
333  tree_->nearestK(*this, data, k, isPivot);
334  while (!nodeQueue_.empty())
335  {
336  dist = nearQueue_.top().first; // note the difference with nearestRInternal
337  node = nodeQueue_.top();
338  nodeQueue_.pop();
339  if (nearQueue_.size() == k &&
340  (node->distToPivot_ > node->maxRadius_ + dist || node->distToPivot_ < node->minRadius_ - dist))
341  continue;
342  node->nearestK(*this, data, k, isPivot);
343  }
344  return isPivot;
345  }
347  void nearestRInternal(const _T &data, double radius) const
348  {
349  double dist = radius; // note the difference with nearestKInternal
350  Node *node;
351 
352  tree_->insertNeighborR(nearQueue_, radius, tree_->pivot_,
354  tree_->nearestR(*this, data, radius);
355  while (!nodeQueue_.empty())
356  {
357  node = nodeQueue_.top();
358  nodeQueue_.pop();
359  if (node->distToPivot_ > node->maxRadius_ + dist || node->distToPivot_ < node->minRadius_ - dist)
360  continue;
361  node->nearestR(*this, data, radius);
362  }
363  }
366  void postprocessNearest(std::vector<_T> &nbh) const
367  {
368  nbh.resize(nearQueue_.size());
369  for (auto it = nbh.rbegin(); it != nbh.rend(); it++, nearQueue_.pop())
370  *it = *nearQueue_.top().second;
371  }
372 
374  class Node
375  {
376  public:
379  Node(int degree, int capacity, _T pivot)
380  : degree_(degree)
381  , pivot_(std::move(pivot))
382  , minRadius_(std::numeric_limits<double>::infinity())
384  , minRange_(degree, minRadius_)
385  , maxRange_(degree, maxRadius_)
386 #ifdef GNAT_SAMPLER
387  , subtreeSize_(1)
388  , activity_(0)
389 #endif
390  {
391  // The "+1" is needed because we add an element before we check whether to split
392  data_.reserve(capacity + 1);
393  }
394 
395  ~Node()
396  {
397  for (auto &child : children_)
398  delete child;
399  }
400 
403  void updateRadius(double dist)
404  {
405  if (minRadius_ > dist)
406  minRadius_ = dist;
407 #ifndef GNAT_SAMPLER
408  if (maxRadius_ < dist)
409  maxRadius_ = dist;
410 #else
411  if (maxRadius_ < dist)
412  {
413  maxRadius_ = dist;
414  activity_ = 0;
415  }
416  else
417  activity_ = std::max(-32, activity_ - 1);
418 #endif
419  }
423  void updateRange(unsigned int i, double dist)
424  {
425  if (minRange_[i] > dist)
426  minRange_[i] = dist;
427  if (maxRange_[i] < dist)
428  maxRange_[i] = dist;
429  }
431  void add(GNAT &gnat, const _T &data)
432  {
433 #ifdef GNAT_SAMPLER
434  subtreeSize_++;
435 #endif
436  if (children_.empty())
437  {
438  data_.push_back(data);
439  gnat.size_++;
440  if (needToSplit(gnat))
441  {
442  if (!gnat.removed_.empty())
443  gnat.rebuildDataStructure();
444  else if (gnat.size_ >= gnat.rebuildSize_)
445  {
446  gnat.rebuildSize_ <<= 1;
447  gnat.rebuildDataStructure();
448  }
449  else
450  split(gnat);
451  }
452  }
453  else
454  {
455  double minDist = children_[0]->distToPivot_ = gnat.distFun_(data, children_[0]->pivot_);
456  int minInd = 0;
457 
458  for (unsigned int i = 1; i < children_.size(); ++i)
459  if ((children_[i]->distToPivot_ = gnat.distFun_(data, children_[i]->pivot_)) < minDist)
460  {
461  minDist = children_[i]->distToPivot_;
462  minInd = i;
463  }
464  for (unsigned int i = 0; i < children_.size(); ++i)
465  children_[i]->updateRange(minInd, children_[i]->distToPivot_);
466  children_[minInd]->updateRadius(minDist);
467  children_[minInd]->add(gnat, data);
468  }
469  }
471  bool needToSplit(const GNAT &gnat) const
472  {
473  unsigned int sz = data_.size();
474  return sz > gnat.maxNumPtsPerLeaf_ && sz > degree_;
475  }
479  void split(GNAT &gnat)
480  {
481  typename GreedyKCenters<_T>::Matrix &dists = gnat.distances_;
482  std::vector<unsigned int> &pivots = gnat.pivots_;
483 
484  children_.reserve(degree_);
485  gnat.pivotSelector_.kcenters(data_, degree_, pivots, dists);
486  for (unsigned int &pivot : pivots)
487  children_.push_back(new Node(degree_, gnat.maxNumPtsPerLeaf_, data_[pivot]));
488  degree_ = pivots.size(); // in case fewer than degree_ pivots were found
489  for (unsigned int j = 0; j < data_.size(); ++j)
490  {
491  unsigned int k = 0;
492  for (unsigned int i = 1; i < degree_; ++i)
493  if (dists(j, i) < dists(j, k))
494  k = i;
495  Node *child = children_[k];
496  if (j != pivots[k])
497  {
498  child->data_.push_back(data_[j]);
499  child->updateRadius(dists(j, k));
500  }
501  for (unsigned int i = 0; i < degree_; ++i)
502  children_[i]->updateRange(k, dists(j, i));
503  }
504 
505  for (auto &child : children_)
506  {
507  // make sure degree lies between minDegree_ and maxDegree_
508  child->degree_ =
509  std::min(std::max((unsigned int)((degree_ * child->data_.size()) / data_.size()),
510  gnat.minDegree_),
511  gnat.maxDegree_);
512  // singleton
513  if (child->minRadius_ >= std::numeric_limits<double>::infinity())
514  child->minRadius_ = child->maxRadius_ = 0.;
515 #ifdef GNAT_SAMPLER
516  // set subtree size
517  child->subtreeSize_ = child->data_.size() + 1;
518 #endif
519  }
520  // this does more than clear(); it also sets capacity to 0 and frees the memory
521  std::vector<_T> tmp;
522  data_.swap(tmp);
523  // check if new leaves need to be split
524  for (auto &child : children_)
525  if (child->needToSplit(gnat))
526  child->split(gnat);
527  }
528 
530  bool insertNeighborK(NearQueue &nbh, std::size_t k, const _T &data, const _T &key, double dist) const
531  {
532  if (nbh.size() < k)
533  {
534  nbh.emplace(dist, &data);
535  return true;
536  }
537  if (dist < nbh.top().first || (dist < std::numeric_limits<double>::epsilon() && data == key))
538  {
539  nbh.pop();
540  nbh.emplace(dist, &data);
541  return true;
542  }
543  return false;
544  }
545 
550  void nearestK(const GNAT &gnat, const _T &data, std::size_t k, bool &isPivot) const
551  {
552  NearQueue &nbh = gnat.nearQueue_;
553  for (const auto &d : data_)
554  if (!gnat.isRemoved(d))
555  {
556  if (insertNeighborK(nbh, k, d, data, gnat.distFun_(data, d)))
557  isPivot = false;
558  }
559  if (!children_.empty())
560  {
561  double dist;
562  Node *child;
563  Permutation &permutation = gnat.permutation_;
564  permutation.permute(children_.size());
565 
566  for (unsigned int i = 0; i < children_.size(); ++i)
567  if (permutation[i] >= 0)
568  {
569  child = children_[permutation[i]];
570  child->distToPivot_ = gnat.distFun_(data, child->pivot_);
571  if (insertNeighborK(nbh, k, child->pivot_, data, child->distToPivot_))
572  isPivot = true;
573  if (nbh.size() == k)
574  {
575  dist = nbh.top().first; // note difference with nearestR
576  for (unsigned int j = 0; j < children_.size(); ++j)
577  if (permutation[j] >= 0 && i != j &&
578  (child->distToPivot_ - dist > child->maxRange_[permutation[j]] ||
579  child->distToPivot_ + dist < child->minRange_[permutation[j]]))
580  permutation[j] = -1;
581  }
582  }
583 
584  dist = nbh.top().first;
585  for (unsigned int i = 0; i < children_.size(); ++i)
586  if (permutation[i] >= 0)
587  {
588  child = children_[permutation[i]];
589  if (nbh.size() < k || (child->distToPivot_ - dist <= child->maxRadius_ &&
590  child->distToPivot_ + dist >= child->minRadius_))
591  gnat.nodeQueue_.push(child);
592  }
593  }
594  }
596  void insertNeighborR(NearQueue &nbh, double r, const _T &data, double dist) const
597  {
598  if (dist <= r)
599  nbh.emplace(dist, &data);
600  }
602  void nearestR(const GNAT &gnat, const _T &data, double r) const
603  {
604  NearQueue &nbh = gnat.nearQueue_;
605  double dist = r; // note difference with nearestK
606 
607  for (const auto &d : data_)
608  if (!gnat.isRemoved(d))
609  insertNeighborR(nbh, r, d, gnat.distFun_(data, d));
610  if (!children_.empty())
611  {
612  Node *child;
613  Permutation &permutation = gnat.permutation_;
614  permutation.permute(children_.size());
615 
616  for (unsigned int i = 0; i < children_.size(); ++i)
617  if (permutation[i] >= 0)
618  {
619  child = children_[permutation[i]];
620  child->distToPivot_ = gnat.distFun_(data, child->pivot_);
621  insertNeighborR(nbh, r, child->pivot_, child->distToPivot_);
622  for (unsigned int j = 0; j < children_.size(); ++j)
623  if (permutation[j] >= 0 && i != j &&
624  (child->distToPivot_ - dist > child->maxRange_[permutation[j]] ||
625  child->distToPivot_ + dist < child->minRange_[permutation[j]]))
626  permutation[j] = -1;
627  }
628 
629  for (unsigned int i = 0; i < children_.size(); ++i)
630  if (permutation[i] >= 0)
631  {
632  child = children_[permutation[i]];
633  if (child->distToPivot_ - dist <= child->maxRadius_ &&
634  child->distToPivot_ + dist >= child->minRadius_)
635  gnat.nodeQueue_.push(child);
636  }
637  }
638  }
639 
640 #ifdef GNAT_SAMPLER
641  double getSamplingWeight(const GNAT &gnat) const
642  {
643  double minR = std::numeric_limits<double>::max();
644  for (auto minRange : minRange_)
645  if (minRange < minR && minRange > 0.0)
646  minR = minRange;
647  minR = std::max(minR, maxRadius_);
648  return std::pow(minR, gnat.estimatedDimension_) / (double)subtreeSize_;
649  }
650  const _T &sample(const GNAT &gnat, RNG &rng) const
651  {
652  if (children_.size() != 0)
653  {
654  if (rng.uniform01() < 1. / (double)subtreeSize_)
655  return pivot_;
656  PDF<const Node *> distribution;
657  for (const auto &child : children_)
658  distribution.add(child, child->getSamplingWeight(gnat));
659  return distribution.sample(rng.uniform01())->sample(gnat, rng);
660  }
661  else
662  {
663  unsigned int i = rng.uniformInt(0, data_.size());
664  return (i == data_.size()) ? pivot_ : data_[i];
665  }
666  }
667 #endif
668 
669  void list(const GNAT &gnat, std::vector<_T> &data) const
670  {
671  if (!gnat.isRemoved(pivot_))
672  data.push_back(pivot_);
673  for (const auto &d : data_)
674  if (!gnat.isRemoved(d))
675  data.push_back(d);
676  for (const auto &child : children_)
677  child->list(gnat, data);
678  }
679 
680  friend std::ostream &operator<<(std::ostream &out, const Node &node)
681  {
682  out << "\ndegree:\t" << node.degree_;
683  out << "\nminRadius:\t" << node.minRadius_;
684  out << "\nmaxRadius:\t" << node.maxRadius_;
685  out << "\nminRange:\t";
686  for (auto minR : node.minRange_)
687  out << minR << '\t';
688  out << "\nmaxRange: ";
689  for (auto maxR : node.maxRange_)
690  out << maxR << '\t';
691  out << "\npivot:\t" << node.pivot_;
692  out << "\ndata: ";
693  for (auto &data : node.data_)
694  out << data << '\t';
695  out << "\nthis:\t" << &node;
696 #ifdef GNAT_SAMPLER
697  out << "\nsubtree size:\t" << node.subtreeSize_;
698  out << "\nactivity:\t" << node.activity_;
699 #endif
700  out << "\nchildren:\n";
701  for (auto &child : node.children_)
702  out << child << '\t';
703  out << '\n';
704  for (auto &child : node.children_)
705  out << *child << '\n';
706  return out;
707  }
708 
710  unsigned int degree_;
712  const _T pivot_;
714  double minRadius_;
716  double maxRadius_;
719  std::vector<double> minRange_;
722  std::vector<double> maxRange_;
725  std::vector<_T> data_;
728  std::vector<Node *> children_;
729 
731  mutable double distToPivot_;
732 
733 #ifdef GNAT_SAMPLER
734  unsigned int subtreeSize_;
740  int activity_;
741 #endif
742  };
743 
745  // another internal data structure is a priority queue of nodes to
746  // check next for possible nearest neighbors
747  struct NodeCompare
748  {
749  bool operator()(const Node *n0, const Node *n1) const
750  {
751  return (n0->distToPivot_ - n0->maxRadius_) > (n1->distToPivot_ - n1->maxRadius_);
752  }
753  };
754  using NodeQueue = std::priority_queue<Node *, std::vector<Node *>, NodeCompare>;
756 
758  Node *tree_{nullptr};
760  unsigned int degree_;
765  unsigned int minDegree_;
770  unsigned int maxDegree_;
773  unsigned int maxNumPtsPerLeaf_;
775  std::size_t size_{0};
778  std::size_t rebuildSize_;
782  std::size_t removedCacheSize_;
786  std::unordered_set<const _T *> removed_;
787 
791  mutable NearQueue nearQueue_;
793  mutable NodeQueue nodeQueue_;
797  mutable std::vector<unsigned int> pivots_;
799  mutable typename GreedyKCenters<_T>::Matrix distances_;
801 
802 #ifdef GNAT_SAMPLER
803  double estimatedDimension_;
805 #endif
806  };
807 }
808 
809 #endif
Random number generation. An instance of this class cannot be used by multiple threads at once (membe...
Definition: RandomNumbers.h:89
NodeQueue nodeQueue_
Nodes yet to be processed for possible nearest neighbors.
Eigen::MatrixXd Matrix
A matrix type for storing distances between points and centers.
void insertNeighborR(NearQueue &nbh, double r, const _T &data, double dist) const
Insert data in nbh if it is a near neighbor.
std::unordered_set< const _T * > removed_
Cache of removed elements.
virtual void add(const _T &data)=0
Add an element to the datastructure.
bool needToSplit(const GNAT &gnat) const
Return true iff the node needs to be split into child nodes.
friend std::ostream & operator<<(std::ostream &out, const NearestNeighborsGNATNoThreadSafety< _T > &gnat)
Print a GNAT structure (mostly useful for debugging purposes).
std::size_t removedCacheSize_
Maximum number of removed elements that can be stored in the removed_ cache. If the cache is full,...
bool remove(const _T &data) override
Remove data from the tree. The element won't actually be removed immediately, but just marked for rem...
void updateRadius(double dist)
Update minRadius_ and maxRadius_, given that an element was added with distance dist to the pivot.
void permute(unsigned int n)
Create a permutation of the numbers 0, ..., n - 1.
Definition: Permutation.h:122
void nearestR(const GNAT &gnat, const _T &data, double r) const
Return all elements that are within distance r in nbh.
std::vector< double > maxRange_
The i-th element in maxRange_ is the maximum distance between the pivot and any data_ element in the ...
Geometric Near-neighbor Access Tree (GNAT), a data structure for nearest neighbor search.
void add(GNAT &gnat, const _T &data)
Add an element to the tree rooted at this node.
void setDistanceFunction(const typename NearestNeighbors< _T >::DistanceFunction &distFun) override
Set the distance function to use.
An instance of this class can be used to greedily select a given number of representatives from a set...
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...
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.
A permutation of indices into an array.
Definition: Permutation.h:81
void nearestK(const _T &data, std::size_t k, std::vector< _T > &nbh) const override
Return the k nearest neighbors in sorted order.
GreedyKCenters< _T > pivotSelector_
The data structure used to split data into subtrees.
void nearestR(const _T &data, double radius, std::vector< _T > &nbh) const override
Return the nearest neighbors within distance radius in sorted order.
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 maxDegree_
After splitting a Node, each child Node has degree equal to the default degree times the fraction of ...
double maxRadius_
Maximum distance between the pivot element and the elements stored in data_.
std::function< double(const _T &, const _T &)> DistanceFunction
The definition of a distance function.
std::size_t size_
Number of elements stored in the tree.
unsigned int minDegree_
After splitting a Node, each child Node has degree equal to the default degree times the fraction of ...
Node(int degree, int capacity, _T pivot)
Construct a node of given degree with at most capacity data elements and with given pivot.
std::vector< _T > data_
The data elements stored in this node (in addition to the pivot element). An internal node has no ele...
bool nearestKInternal(const _T &data, std::size_t k) const
Return in nearQueue_ the k nearest neighbors of data. For k=1, return true if the nearest neighbor is...
Node * tree_
The data structure containing the elements stored in this structure.
void add(const _T &data) override
Add an element to the datastructure.
DistanceFunction distFun_
The used distance function.
void nearestRInternal(const _T &data, double radius) const
Return in nearQueue_ the elements that are within distance radius of data.
std::size_t rebuildSize_
If size_ exceeds rebuildSize_, the tree will be rebuilt (and automatically rebalanced),...
unsigned int maxNumPtsPerLeaf_
Maximum number of elements allowed to be stored in a Node before it needs to be split into several no...
unsigned int degree_
The desired degree of each node.
double minRadius_
Minimum distance between the pivot element and the elements stored in data_.
bool reportsSortedResults() const override
Return true if the solutions reported by this data structure are sorted, when calling nearestK / near...
void nearestK(const GNAT &gnat, const _T &data, std::size_t k, bool &isPivot) const
Compute the k nearest neighbors of data in the tree. For k=1, isPivot is true if the nearest neighbor...
Permutation permutation_
Permutation of indices to process children of a node in random order.
void postprocessNearest(std::vector< _T > &nbh) const
Convert the internal data structure used for storing neighbors to the vector that NearestNeighbor API...
void split(GNAT &gnat)
The split operation finds pivot elements for the child nodes and moves each data element of this node...
std::size_t size() const override
Get the number of elements in the datastructure.
bool isRemoved(const _T &data) const
Return true iff data has been marked for removal.
double distToPivot_
Scratch space to store distance to pivot during nearest neighbor queries.
void rebuildDataStructure()
Rebuild the internal data structure.
std::vector< Node * > children_
The child nodes of this node. By definition, only internal nodes have child nodes.
The exception type for ompl.
Definition: Exception.h:78
GreedyKCenters< _T >::Matrix distances_
Matrix of distances to pivots.
_T nearest(const _T &data) const override
Get the nearest neighbor of a point.
std::vector< unsigned int > pivots_
Pivot indices within a vector of elements as selected by GreedyKCenters.
void list(std::vector< _T > &data) const override
Get all the elements in the datastructure.
Main namespace. Contains everything in this library.
virtual void setDistanceFunction(const DistanceFunction &distFun)
Set the distance function to use.