All Classes Namespaces Functions Variables Typedefs Enumerations Enumerator Friends
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(void)
97  {
98  if (index_)
99  delete index_;
100  }
101 
102  virtual void clear(void)
103  {
104  if (index_)
105  {
106  delete index_;
107  index_ = NULL;
108  }
109  data_.clear();
110  }
111 
112  virtual void setDistanceFunction(const typename NearestNeighbors<_T>::DistanceFunction &distFun)
113  {
115  rebuildIndex();
116  }
117 
118  virtual void add(const _T &data)
119  {
120  bool rebuild = index_ && (data_.size() + 1 > data_.capacity());
121 
122  if (rebuild)
123  rebuildIndex(2 * data_.capacity());
124 
125  data_.push_back(data);
126  const flann::Matrix<_T> mat(&data_.back(), 1, dimension_);
127 
128  if (index_)
129  index_->addPoints(mat, std::numeric_limits<float>::max()/size());
130  else
131  createIndex(mat);
132  }
133  virtual void add(const std::vector<_T> &data)
134  {
135  unsigned int oldSize = data_.size();
136  unsigned int newSize = oldSize + data.size();
137  bool rebuild = index_ && (newSize > data_.capacity());
138 
139  if (rebuild)
140  rebuildIndex(std::max(2 * oldSize, newSize));
141 
142  if (index_)
143  {
144  std::copy(data.begin(), data.end(), data_.begin() + oldSize);
145  const flann::Matrix<_T> mat(&data_[oldSize], data.size(), dimension_);
146  index_->addPoints(mat, std::numeric_limits<float>::max()/size());
147  }
148  else
149  {
150  data_ = data;
151  const flann::Matrix<_T> mat(&data_[0], data_.size(), dimension_);
152  createIndex(mat);
153  }
154  }
155  virtual bool remove(const _T& data)
156  {
157  if (!index_) return false;
158  _T& elt = const_cast<_T&>(data);
159  const flann::Matrix<_T> query(&elt, 1, dimension_);
160  std::vector<std::vector<size_t> > indices(1);
161  std::vector<std::vector<double> > dists(1);
162  index_->knnSearch(query, indices, dists, 1, searchParams_);
163  if (*index_->getPoint(indices[0][0]) == data)
164  {
165  index_->removePoint(indices[0][0]);
166  rebuildIndex();
167  return true;
168  }
169  return false;
170  }
171  virtual _T nearest(const _T &data) const
172  {
173  if (size())
174  {
175  _T& elt = const_cast<_T&>(data);
176  const flann::Matrix<_T> query(&elt, 1, dimension_);
177  std::vector<std::vector<size_t> > indices(1);
178  std::vector<std::vector<double> > dists(1);
179  index_->knnSearch(query, indices, dists, 1, searchParams_);
180  return *index_->getPoint(indices[0][0]);
181  }
182  throw Exception("No elements found in nearest neighbors data structure");
183  }
186  virtual void nearestK(const _T &data, std::size_t k, std::vector<_T> &nbh) const
187  {
188  _T& elt = const_cast<_T&>(data);
189  const flann::Matrix<_T> query(&elt, 1, dimension_);
190  std::vector<std::vector<size_t> > indices;
191  std::vector<std::vector<double> > dists;
192  k = index_ ? index_->knnSearch(query, indices, dists, k, searchParams_) : 0;
193  nbh.resize(k);
194  for (std::size_t i = 0 ; i < k ; ++i)
195  nbh[i] = *index_->getPoint(indices[0][i]);
196  }
199  virtual void nearestR(const _T &data, double radius, std::vector<_T> &nbh) const
200  {
201  _T& elt = const_cast<_T&>(data);
202  flann::Matrix<_T> query(&elt, 1, dimension_);
203  std::vector<std::vector<size_t> > indices;
204  std::vector<std::vector<double> > dists;
205  int k = index_ ? index_->radiusSearch(query, indices, dists, radius, searchParams_) : 0;
206  nbh.resize(k);
207  for (int i = 0 ; i < k ; ++i)
208  nbh[i] = *index_->getPoint(indices[0][i]);
209  }
210 
211  virtual std::size_t size(void) const
212  {
213  return index_ ? index_->size() : 0;
214  }
215 
216  virtual void list(std::vector<_T> &data) const
217  {
218  std::size_t sz = size();
219  if (sz == 0)
220  {
221  data.resize(0);
222  return;
223  }
224  const _T& dummy = *index_->getPoint(0);
225  int checks = searchParams_.checks;
226  searchParams_.checks = size();
227  nearestK(dummy, sz, data);
228  searchParams_.checks = checks;
229  }
230 
235  virtual void setIndexParams(const boost::shared_ptr<flann::IndexParams> &params)
236  {
237  params_ = params;
238  rebuildIndex();
239  }
240 
242  virtual const boost::shared_ptr<flann::IndexParams>& getIndexParams(void) const
243  {
244  return params_;
245  }
246 
249  virtual void setSearchParams(const flann::SearchParams& searchParams)
250  {
251  searchParams_ = searchParams;
252  }
253 
256  flann::SearchParams& getSearchParams(void)
257  {
258  return searchParams_;
259  }
260 
263  const flann::SearchParams& getSearchParams(void) const
264  {
265  return searchParams_;
266  }
267 
268  unsigned int getContainerSize(void) const
269  {
270  return dimension_;
271  }
272 
273  protected:
274 
277  void createIndex(const flann::Matrix<_T>& mat)
278  {
279  index_ = new flann::Index<_Dist>(mat, *params_, _Dist(NearestNeighbors<_T>::distFun_));
280  index_->buildIndex();
281  }
282 
285  void rebuildIndex(unsigned int capacity = 0)
286  {
287  if (index_)
288  {
289  std::vector<_T> data;
290  list(data);
291  clear();
292  if (capacity)
293  data_.reserve(capacity);
294  add(data);
295  }
296  }
297 
300  std::vector<_T> data_;
301 
303  flann::Index<_Dist>* index_;
304 
307  boost::shared_ptr<flann::IndexParams> params_;
308 
310  mutable flann::SearchParams searchParams_;
311 
315  unsigned int dimension_;
316  };
317 
318  template<>
320  const flann::Matrix<double>& mat)
321  {
322  index_ = new flann::Index<flann::L2<double> >(mat, *params_);
323  index_->buildIndex();
324  }
325 
326  template<typename _T, typename _Dist = FLANNDistance<_T> >
328  {
329  public:
332  boost::shared_ptr<flann::LinearIndexParams>(
333  new flann::LinearIndexParams()))
334  {
335  }
336  };
337 
338  template<typename _T, typename _Dist = FLANNDistance<_T> >
340  {
341  public:
344  boost::shared_ptr<flann::HierarchicalClusteringIndexParams>(
345  new flann::HierarchicalClusteringIndexParams()))
346  {
347  }
348  };
349 
350 }
351 #endif
352 
353 #endif
flann::SearchParams & getSearchParams(void)
Get the FLANN parameters used during nearest neighbor searches.
virtual std::size_t size(void) const
Get the number of elements in the datastructure.
virtual void clear(void)
Clear the datastructure.
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...
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)
std::vector< _T > data_
vector of data stored in FLANN's index. FLANN only indexes references, so we need store the original ...
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.
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.
const flann::SearchParams & getSearchParams(void) const
Get the FLANN parameters used during nearest neighbor searches.
virtual const boost::shared_ptr< flann::IndexParams > & getIndexParams(void) const
Get the FLANN parameters used to build the current index.
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.