NearestNeighborsFLANN.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 */
36 
37 #ifndef OMPL_DATASTRUCTURES_NEAREST_NEIGHBORS_FLANN_
38 #define OMPL_DATASTRUCTURES_NEAREST_NEIGHBORS_FLANN_
39 
40 #include "ompl/config.h"
41 #if OMPL_HAVE_FLANN == 0
42 # error FLANN is not available. Please use a different NearestNeighbors data structure.
43 #else
44 
45 #include "ompl/datastructures/NearestNeighbors.h"
46 #include "ompl/base/StateSpace.h"
47 
48 #include <flann/flann.hpp>
49 
50 namespace ompl
51 {
55  template<typename _T>
57  {
58  public:
59  typedef _T ElementType;
60  typedef double ResultType;
61 
63  : distFun_(distFun)
64  {
65  }
66 
67  template <typename Iterator1, typename Iterator2>
68  ResultType operator()(Iterator1 a, Iterator2 b,
69  size_t /*size*/, ResultType /*worst_dist*/ = -1) const
70  {
71  return distFun_(*a, *b);
72  }
73  protected:
74  const typename NearestNeighbors<_T>::DistanceFunction& distFun_;
75  };
76 
86  template<typename _T, typename _Dist = FLANNDistance<_T> >
88  {
89  public:
90 
91  NearestNeighborsFLANN(const boost::shared_ptr<flann::IndexParams> &params)
92  : index_(0), params_(params), searchParams_(32, 0., true), dimension_(1)
93  {
94  }
95 
96  virtual ~NearestNeighborsFLANN()
97  {
98  if (index_)
99  delete index_;
100  }
101 
102  virtual void clear()
103  {
104  if (index_)
105  {
106  delete index_;
107  index_ = NULL;
108  }
109  data_.clear();
110  }
111 
112  virtual bool reportsSortedResults() const
113  {
114  return searchParams_.sorted;
115  }
116 
117  virtual void setDistanceFunction(const typename NearestNeighbors<_T>::DistanceFunction &distFun)
118  {
120  rebuildIndex();
121  }
122 
123  virtual void add(const _T &data)
124  {
125  bool rebuild = index_ && (data_.size() + 1 > data_.capacity());
126 
127  if (rebuild)
128  rebuildIndex(2 * data_.capacity());
129 
130  data_.push_back(data);
131  const flann::Matrix<_T> mat(&data_.back(), 1, dimension_);
132 
133  if (index_)
134  index_->addPoints(mat, std::numeric_limits<float>::max()/size());
135  else
136  createIndex(mat);
137  }
138  virtual void add(const std::vector<_T> &data)
139  {
140  unsigned int oldSize = data_.size();
141  unsigned int newSize = oldSize + data.size();
142  bool rebuild = index_ && (newSize > data_.capacity());
143 
144  if (rebuild)
145  rebuildIndex(std::max(2 * oldSize, newSize));
146 
147  if (index_)
148  {
149  std::copy(data.begin(), data.end(), data_.begin() + oldSize);
150  const flann::Matrix<_T> mat(&data_[oldSize], data.size(), dimension_);
151  index_->addPoints(mat, std::numeric_limits<float>::max()/size());
152  }
153  else
154  {
155  data_ = data;
156  const flann::Matrix<_T> mat(&data_[0], data_.size(), dimension_);
157  createIndex(mat);
158  }
159  }
160  virtual bool remove(const _T& data)
161  {
162  if (!index_) return false;
163  _T& elt = const_cast<_T&>(data);
164  const flann::Matrix<_T> query(&elt, 1, dimension_);
165  std::vector<std::vector<size_t> > indices(1);
166  std::vector<std::vector<double> > dists(1);
167  index_->knnSearch(query, indices, dists, 1, searchParams_);
168  if (*index_->getPoint(indices[0][0]) == data)
169  {
170  index_->removePoint(indices[0][0]);
171  rebuildIndex();
172  return true;
173  }
174  return false;
175  }
176  virtual _T nearest(const _T &data) const
177  {
178  if (size())
179  {
180  _T& elt = const_cast<_T&>(data);
181  const flann::Matrix<_T> query(&elt, 1, dimension_);
182  std::vector<std::vector<size_t> > indices(1);
183  std::vector<std::vector<double> > dists(1);
184  index_->knnSearch(query, indices, dists, 1, searchParams_);
185  return *index_->getPoint(indices[0][0]);
186  }
187  throw Exception("No elements found in nearest neighbors data structure");
188  }
191  virtual void nearestK(const _T &data, std::size_t k, std::vector<_T> &nbh) const
192  {
193  _T& elt = const_cast<_T&>(data);
194  const flann::Matrix<_T> query(&elt, 1, dimension_);
195  std::vector<std::vector<size_t> > indices;
196  std::vector<std::vector<double> > dists;
197  k = index_ ? index_->knnSearch(query, indices, dists, k, searchParams_) : 0;
198  nbh.resize(k);
199  for (std::size_t i = 0 ; i < k ; ++i)
200  nbh[i] = *index_->getPoint(indices[0][i]);
201  }
204  virtual void nearestR(const _T &data, double radius, std::vector<_T> &nbh) const
205  {
206  _T& elt = const_cast<_T&>(data);
207  flann::Matrix<_T> query(&elt, 1, dimension_);
208  std::vector<std::vector<size_t> > indices;
209  std::vector<std::vector<double> > dists;
210  int k = index_ ? index_->radiusSearch(query, indices, dists, radius, searchParams_) : 0;
211  nbh.resize(k);
212  for (int i = 0 ; i < k ; ++i)
213  nbh[i] = *index_->getPoint(indices[0][i]);
214  }
215 
216  virtual std::size_t size() const
217  {
218  return index_ ? index_->size() : 0;
219  }
220 
221  virtual void list(std::vector<_T> &data) const
222  {
223  std::size_t sz = size();
224  if (sz == 0)
225  {
226  data.resize(0);
227  return;
228  }
229  const _T& dummy = *index_->getPoint(0);
230  int checks = searchParams_.checks;
231  searchParams_.checks = size();
232  nearestK(dummy, sz, data);
233  searchParams_.checks = checks;
234  }
235 
240  virtual void setIndexParams(const boost::shared_ptr<flann::IndexParams> &params)
241  {
242  params_ = params;
243  rebuildIndex();
244  }
245 
247  virtual const boost::shared_ptr<flann::IndexParams>& getIndexParams() const
248  {
249  return params_;
250  }
251 
254  virtual void setSearchParams(const flann::SearchParams& searchParams)
255  {
256  searchParams_ = searchParams;
257  }
258 
261  flann::SearchParams& getSearchParams()
262  {
263  return searchParams_;
264  }
265 
268  const flann::SearchParams& getSearchParams() const
269  {
270  return searchParams_;
271  }
272 
273  unsigned int getContainerSize() const
274  {
275  return dimension_;
276  }
277 
278  protected:
279 
282  void createIndex(const flann::Matrix<_T>& mat)
283  {
284  index_ = new flann::Index<_Dist>(mat, *params_, _Dist(NearestNeighbors<_T>::distFun_));
285  index_->buildIndex();
286  }
287 
290  void rebuildIndex(unsigned int capacity = 0)
291  {
292  if (index_)
293  {
294  std::vector<_T> data;
295  list(data);
296  clear();
297  if (capacity)
298  data_.reserve(capacity);
299  add(data);
300  }
301  }
302 
305  std::vector<_T> data_;
306 
308  flann::Index<_Dist>* index_;
309 
312  boost::shared_ptr<flann::IndexParams> params_;
313 
315  mutable flann::SearchParams searchParams_;
316 
320  unsigned int dimension_;
321  };
322 
323  template<>
325  const flann::Matrix<double>& mat)
326  {
327  index_ = new flann::Index<flann::L2<double> >(mat, *params_);
328  index_->buildIndex();
329  }
330 
331  template<typename _T, typename _Dist = FLANNDistance<_T> >
333  {
334  public:
337  boost::shared_ptr<flann::LinearIndexParams>(
338  new flann::LinearIndexParams()))
339  {
340  }
341  };
342 
343  template<typename _T, typename _Dist = FLANNDistance<_T> >
345  {
346  public:
349  boost::shared_ptr<flann::HierarchicalClusteringIndexParams>(
350  new flann::HierarchicalClusteringIndexParams()))
351  {
352  }
353  };
354 
355 }
356 #endif
357 
358 #endif
unsigned int dimension_
If each element has an array-like structure that is exposed to FLANN, then the dimension_ needs to be...
boost::function< double(const _T &, const _T &)> DistanceFunction
The definition of a distance function.
Wrapper class to allow FLANN access to the NearestNeighbors::distFun_ callback function.
virtual _T nearest(const _T &data) const
Get the nearest neighbor of a point.
boost::shared_ptr< flann::IndexParams > params_
The FLANN index parameters. This contains both the type of index and the parameters for that type...
flann::SearchParams & getSearchParams()
Get the FLANN parameters used during nearest neighbor searches.
virtual void add(const std::vector< _T > &data)
Add a vector of points.
virtual void nearestR(const _T &data, double radius, std::vector< _T > &nbh) const
Return the nearest neighbors within distance radius in sorted order if searchParams_.sorted==true (the default)
virtual void clear()
Clear the datastructure.
Main namespace. Contains everything in this library.
Definition: Cost.h:42
std::vector< _T > data_
vector of data stored in FLANN's index. FLANN only indexes references, so we need store the original ...
virtual std::size_t size() const
Get the number of elements in the datastructure.
virtual void list(std::vector< _T > &data) const
Get all the elements in the datastructure.
Wrapper class for nearest neighbor data structures in the FLANN library.
virtual void setDistanceFunction(const DistanceFunction &distFun)
Set the distance function to use.
const flann::SearchParams & getSearchParams() const
Get the FLANN parameters used during nearest neighbor searches.
virtual const boost::shared_ptr< flann::IndexParams > & getIndexParams() const
Get the FLANN parameters used to build the current index.
flann::Index< _Dist > * index_
The FLANN index (the actual index type depends on params_).
flann::SearchParams searchParams_
The parameters used to seach for nearest neighbors.
Abstract representation of a container that can perform nearest neighbors queries.
void rebuildIndex(unsigned int capacity=0)
Rebuild the nearest neighbor data structure (necessary when changing the distance function or index p...
void createIndex(const flann::Matrix< _T > &mat)
Internal function to construct nearest neighbor data structure with initial elements stored in mat...
The exception type for ompl.
Definition: Exception.h:47
virtual void setIndexParams(const boost::shared_ptr< flann::IndexParams > &params)
Set the FLANN index parameters.
virtual bool reportsSortedResults() const
Return true if the solutions reported by this data structure are sorted, when calling nearestK / near...
virtual void add(const _T &data)
Add an element to the datastructure.
virtual void nearestK(const _T &data, std::size_t k, std::vector< _T > &nbh) const
Return the k nearest neighbors in sorted order if searchParams_.sorted==true (the default) ...
virtual void setSearchParams(const flann::SearchParams &searchParams)
Set the FLANN parameters to be used during nearest neighbor searches.