nanoflann.hpp
Go to the documentation of this file.
1 /***********************************************************************
2  * Software License Agreement (BSD License)
3  *
4  * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
5  * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
6  * Copyright 2011-2016 Jose Luis Blanco (joseluisblancoc@gmail.com).
7  * All rights reserved.
8  *
9  * THE BSD LICENSE
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  *
15  * 1. Redistributions of source code must retain the above copyright
16  * notice, this list of conditions and the following disclaimer.
17  * 2. Redistributions in binary form must reproduce the above copyright
18  * notice, this list of conditions and the following disclaimer in the
19  * documentation and/or other materials provided with the distribution.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
23  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
24  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
26  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
30  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31  *************************************************************************/
32 
47 #ifndef NANOFLANN_HPP_
48 #define NANOFLANN_HPP_
49 
50 #include <algorithm>
51 #include <array>
52 #include <cassert>
53 #include <cmath> // for abs()
54 #include <cstdio> // for fwrite()
55 #include <cstdlib> // for abs()
56 #include <functional>
57 #include <limits> // std::reference_wrapper
58 #include <stdexcept>
59 #include <vector>
60 
62 #define NANOFLANN_VERSION 0x130
63 
64 // Avoid conflicting declaration of min/max macros in windows headers
65 #if !defined(NOMINMAX) && \
66  (defined(_WIN32) || defined(_WIN32_) || defined(WIN32) || defined(_WIN64))
67 #define NOMINMAX
68 #ifdef max
69 #undef max
70 #undef min
71 #endif
72 #endif
73 
74 namespace nanoflann {
79 template <typename T> T pi_const() {
80  return static_cast<T>(3.14159265358979323846);
81 }
82 
87 template <typename T, typename = int> struct has_resize : std::false_type {};
88 
89 template <typename T>
90 struct has_resize<T, decltype((void)std::declval<T>().resize(1), 0)>
91  : std::true_type {};
92 
93 template <typename T, typename = int> struct has_assign : std::false_type {};
94 
95 template <typename T>
96 struct has_assign<T, decltype((void)std::declval<T>().assign(1, 0), 0)>
97  : std::true_type {};
98 
102 template <typename Container>
103 inline typename std::enable_if<has_resize<Container>::value, void>::type
104 resize(Container &c, const size_t nElements) {
105  c.resize(nElements);
106 }
107 
112 template <typename Container>
113 inline typename std::enable_if<!has_resize<Container>::value, void>::type
114 resize(Container &c, const size_t nElements) {
115  if (nElements != c.size())
116  throw std::logic_error("Try to change the size of a std::array.");
117 }
118 
122 template <typename Container, typename T>
123 inline typename std::enable_if<has_assign<Container>::value, void>::type
124 assign(Container &c, const size_t nElements, const T &value) {
125  c.assign(nElements, value);
126 }
127 
131 template <typename Container, typename T>
132 inline typename std::enable_if<!has_assign<Container>::value, void>::type
133 assign(Container &c, const size_t nElements, const T &value) {
134  for (size_t i = 0; i < nElements; i++)
135  c[i] = value;
136 }
137 
140 template <typename _DistanceType, typename _IndexType = size_t,
141  typename _CountType = size_t>
143 public:
144  typedef _DistanceType DistanceType;
145  typedef _IndexType IndexType;
146  typedef _CountType CountType;
147 
148 private:
153 
154 public:
155  inline KNNResultSet(CountType capacity_)
156  : indices(0), dists(0), capacity(capacity_), count(0) {}
157 
158  inline void init(IndexType *indices_, DistanceType *dists_) {
159  indices = indices_;
160  dists = dists_;
161  count = 0;
162  if (capacity)
163  dists[capacity - 1] = (std::numeric_limits<DistanceType>::max)();
164  }
165 
166  inline CountType size() const { return count; }
167 
168  inline bool full() const { return count == capacity; }
169 
175  inline bool addPoint(DistanceType dist, IndexType index) {
176  CountType i;
177  for (i = count; i > 0; --i) {
178 #ifdef NANOFLANN_FIRST_MATCH // If defined and two points have the same
179  // distance, the one with the lowest-index will be
180  // returned first.
181  if ((dists[i - 1] > dist) ||
182  ((dist == dists[i - 1]) && (indices[i - 1] > index))) {
183 #else
184  if (dists[i - 1] > dist) {
185 #endif
186  if (i < capacity) {
187  dists[i] = dists[i - 1];
188  indices[i] = indices[i - 1];
189  }
190  } else
191  break;
192  }
193  if (i < capacity) {
194  dists[i] = dist;
195  indices[i] = index;
196  }
197  if (count < capacity)
198  count++;
199 
200  // tell caller that the search shall continue
201  return true;
202  }
203 
204  inline DistanceType worstDist() const { return dists[capacity - 1]; }
205 };
206 
210  template <typename PairType>
211  inline bool operator()(const PairType &p1, const PairType &p2) const {
212  return p1.second < p2.second;
213  }
214 };
215 
219 template <typename _DistanceType, typename _IndexType = size_t>
221 public:
222  typedef _DistanceType DistanceType;
223  typedef _IndexType IndexType;
224 
225 public:
227 
228  std::vector<std::pair<IndexType, DistanceType>> &m_indices_dists;
229 
231  DistanceType radius_,
232  std::vector<std::pair<IndexType, DistanceType>> &indices_dists)
233  : radius(radius_), m_indices_dists(indices_dists) {
234  init();
235  }
236 
237  inline void init() { clear(); }
238  inline void clear() { m_indices_dists.clear(); }
239 
240  inline size_t size() const { return m_indices_dists.size(); }
241 
242  inline bool full() const { return true; }
243 
249  inline bool addPoint(DistanceType dist, IndexType index) {
250  if (dist < radius)
251  m_indices_dists.push_back(std::make_pair(index, dist));
252  return true;
253  }
254 
255  inline DistanceType worstDist() const { return radius; }
256 
261  std::pair<IndexType, DistanceType> worst_item() const {
262  if (m_indices_dists.empty())
263  throw std::runtime_error("Cannot invoke RadiusResultSet::worst_item() on "
264  "an empty list of results.");
265  typedef
266  typename std::vector<std::pair<IndexType, DistanceType>>::const_iterator
267  DistIt;
268  DistIt it = std::max_element(m_indices_dists.begin(), m_indices_dists.end(),
269  IndexDist_Sorter());
270  return *it;
271  }
272 };
273 
278 template <typename T>
279 void save_value(FILE *stream, const T &value, size_t count = 1) {
280  fwrite(&value, sizeof(value), count, stream);
281 }
282 
283 template <typename T>
284 void save_value(FILE *stream, const std::vector<T> &value) {
285  size_t size = value.size();
286  fwrite(&size, sizeof(size_t), 1, stream);
287  fwrite(&value[0], sizeof(T), size, stream);
288 }
289 
290 template <typename T>
291 void load_value(FILE *stream, T &value, size_t count = 1) {
292  size_t read_cnt = fread(&value, sizeof(value), count, stream);
293  if (read_cnt != count) {
294  throw std::runtime_error("Cannot read from file");
295  }
296 }
297 
298 template <typename T> void load_value(FILE *stream, std::vector<T> &value) {
299  size_t size;
300  size_t read_cnt = fread(&size, sizeof(size_t), 1, stream);
301  if (read_cnt != 1) {
302  throw std::runtime_error("Cannot read from file");
303  }
304  value.resize(size);
305  read_cnt = fread(&value[0], sizeof(T), size, stream);
306  if (read_cnt != size) {
307  throw std::runtime_error("Cannot read from file");
308  }
309 }
315 struct Metric {};
316 
323 template <class T, class DataSource, typename _DistanceType = T>
324 struct L1_Adaptor {
325  typedef T ElementType;
326  typedef _DistanceType DistanceType;
327 
328  const DataSource &data_source;
329 
330  L1_Adaptor(const DataSource &_data_source) : data_source(_data_source) {}
331 
332  inline DistanceType evalMetric(const T *a, const size_t b_idx, size_t size,
333  DistanceType worst_dist = -1) const {
334  DistanceType result = DistanceType();
335  const T *last = a + size;
336  const T *lastgroup = last - 3;
337  size_t d = 0;
338 
339  /* Process 4 items with each loop for efficiency. */
340  while (a < lastgroup) {
341  const DistanceType diff0 =
342  std::abs(a[0] - data_source.kdtree_get_pt(b_idx, d++));
343  const DistanceType diff1 =
344  std::abs(a[1] - data_source.kdtree_get_pt(b_idx, d++));
345  const DistanceType diff2 =
346  std::abs(a[2] - data_source.kdtree_get_pt(b_idx, d++));
347  const DistanceType diff3 =
348  std::abs(a[3] - data_source.kdtree_get_pt(b_idx, d++));
349  result += diff0 + diff1 + diff2 + diff3;
350  a += 4;
351  if ((worst_dist > 0) && (result > worst_dist)) {
352  return result;
353  }
354  }
355  /* Process last 0-3 components. Not needed for standard vector lengths. */
356  while (a < last) {
357  result += std::abs(*a++ - data_source.kdtree_get_pt(b_idx, d++));
358  }
359  return result;
360  }
361 
362  template <typename U, typename V>
363  inline DistanceType accum_dist(const U a, const V b, const size_t) const {
364  return std::abs(a - b);
365  }
366 };
367 
374 template <class T, class DataSource, typename _DistanceType = T>
375 struct L2_Adaptor {
376  typedef T ElementType;
377  typedef _DistanceType DistanceType;
378 
379  const DataSource &data_source;
380 
381  L2_Adaptor(const DataSource &_data_source) : data_source(_data_source) {}
382 
383  inline DistanceType evalMetric(const T *a, const size_t b_idx, size_t size,
384  DistanceType worst_dist = -1) const {
385  DistanceType result = DistanceType();
386  const T *last = a + size;
387  const T *lastgroup = last - 3;
388  size_t d = 0;
389 
390  /* Process 4 items with each loop for efficiency. */
391  while (a < lastgroup) {
392  const DistanceType diff0 = a[0] - data_source.kdtree_get_pt(b_idx, d++);
393  const DistanceType diff1 = a[1] - data_source.kdtree_get_pt(b_idx, d++);
394  const DistanceType diff2 = a[2] - data_source.kdtree_get_pt(b_idx, d++);
395  const DistanceType diff3 = a[3] - data_source.kdtree_get_pt(b_idx, d++);
396  result += diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
397  a += 4;
398  if ((worst_dist > 0) && (result > worst_dist)) {
399  return result;
400  }
401  }
402  /* Process last 0-3 components. Not needed for standard vector lengths. */
403  while (a < last) {
404  const DistanceType diff0 = *a++ - data_source.kdtree_get_pt(b_idx, d++);
405  result += diff0 * diff0;
406  }
407  return result;
408  }
409 
410  template <typename U, typename V>
411  inline DistanceType accum_dist(const U a, const V b, const size_t) const {
412  return (a - b) * (a - b);
413  }
414 };
415 
422 template <class T, class DataSource, typename _DistanceType = T>
424  typedef T ElementType;
425  typedef _DistanceType DistanceType;
426 
427  const DataSource &data_source;
428 
429  L2_Simple_Adaptor(const DataSource &_data_source)
430  : data_source(_data_source) {}
431 
432  inline DistanceType evalMetric(const T *a, const size_t b_idx,
433  size_t size) const {
434  DistanceType result = DistanceType();
435  for (size_t i = 0; i < size; ++i) {
436  const DistanceType diff = a[i] - data_source.kdtree_get_pt(b_idx, i);
437  result += diff * diff;
438  }
439  return result;
440  }
441 
442  template <typename U, typename V>
443  inline DistanceType accum_dist(const U a, const V b, const size_t) const {
444  return (a - b) * (a - b);
445  }
446 };
447 
454 template <class T, class DataSource, typename _DistanceType = T>
455 struct SO2_Adaptor {
456  typedef T ElementType;
457  typedef _DistanceType DistanceType;
458 
459  const DataSource &data_source;
460 
461  SO2_Adaptor(const DataSource &_data_source) : data_source(_data_source) {}
462 
463  inline DistanceType evalMetric(const T *a, const size_t b_idx,
464  size_t size) const {
465  return accum_dist(a[size - 1], data_source.kdtree_get_pt(b_idx, size - 1),
466  size - 1);
467  }
468 
470  template <typename U, typename V>
471  inline DistanceType accum_dist(const U a, const V b, const size_t) const {
472  DistanceType result = DistanceType(), PI = pi_const<DistanceType>();
473  result = b - a;
474  if (result > PI)
475  result -= 2 * PI;
476  else if (result < -PI)
477  result += 2 * PI;
478  return result;
479  }
480 };
481 
488 template <class T, class DataSource, typename _DistanceType = T>
489 struct SO3_Adaptor {
490  typedef T ElementType;
491  typedef _DistanceType DistanceType;
492 
494 
495  SO3_Adaptor(const DataSource &_data_source)
496  : distance_L2_Simple(_data_source) {}
497 
498  inline DistanceType evalMetric(const T *a, const size_t b_idx,
499  size_t size) const {
500  return distance_L2_Simple.evalMetric(a, b_idx, size);
501  }
502 
503  template <typename U, typename V>
504  inline DistanceType accum_dist(const U a, const V b, const size_t idx) const {
505  return distance_L2_Simple.accum_dist(a, b, idx);
506  }
507 };
508 
510 struct metric_L1 : public Metric {
511  template <class T, class DataSource> struct traits {
513  };
514 };
516 struct metric_L2 : public Metric {
517  template <class T, class DataSource> struct traits {
519  };
520 };
522 struct metric_L2_Simple : public Metric {
523  template <class T, class DataSource> struct traits {
525  };
526 };
528 struct metric_SO2 : public Metric {
529  template <class T, class DataSource> struct traits {
531  };
532 };
534 struct metric_SO3 : public Metric {
535  template <class T, class DataSource> struct traits {
537  };
538 };
539 
547  KDTreeSingleIndexAdaptorParams(size_t _leaf_max_size = 10)
548  : leaf_max_size(_leaf_max_size) {}
549 
551 };
552 
554 struct SearchParams {
557  SearchParams(int checks_IGNORED_ = 32, float eps_ = 0, bool sorted_ = true)
558  : checks(checks_IGNORED_), eps(eps_), sorted(sorted_) {}
559 
560  int checks;
561  float eps;
563  bool sorted;
564 };
578 template <typename T> inline T *allocate(size_t count = 1) {
579  T *mem = static_cast<T *>(::malloc(sizeof(T) * count));
580  return mem;
581 }
582 
598 const size_t WORDSIZE = 16;
599 const size_t BLOCKSIZE = 8192;
600 
602  /* We maintain memory alignment to word boundaries by requiring that all
603  allocations be in multiples of the machine wordsize. */
604  /* Size of machine word in bytes. Must be power of 2. */
605  /* Minimum number of bytes requested at a time from the system. Must be
606  * multiple of WORDSIZE. */
607 
608  size_t remaining; /* Number of bytes left in current block of storage. */
609  void *base; /* Pointer to base of current block of storage. */
610  void *loc; /* Current location in block to next allocate memory. */
611 
612  void internal_init() {
613  remaining = 0;
614  base = NULL;
615  usedMemory = 0;
616  wastedMemory = 0;
617  }
618 
619 public:
620  size_t usedMemory;
621  size_t wastedMemory;
622 
626  PooledAllocator() { internal_init(); }
627 
631  ~PooledAllocator() { free_all(); }
632 
634  void free_all() {
635  while (base != NULL) {
636  void *prev =
637  *(static_cast<void **>(base)); /* Get pointer to prev block. */
638  ::free(base);
639  base = prev;
640  }
641  internal_init();
642  }
643 
648  void *malloc(const size_t req_size) {
649  /* Round size up to a multiple of wordsize. The following expression
650  only works for WORDSIZE that is a power of 2, by masking last bits of
651  incremented size to zero.
652  */
653  const size_t size = (req_size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
654 
655  /* Check whether a new block must be allocated. Note that the first word
656  of a block is reserved for a pointer to the previous block.
657  */
658  if (size > remaining) {
659 
660  wastedMemory += remaining;
661 
662  /* Allocate new storage. */
663  const size_t blocksize =
664  (size + sizeof(void *) + (WORDSIZE - 1) > BLOCKSIZE)
665  ? size + sizeof(void *) + (WORDSIZE - 1)
666  : BLOCKSIZE;
667 
668  // use the standard C malloc to allocate memory
669  void *m = ::malloc(blocksize);
670  if (!m) {
671  fprintf(stderr, "Failed to allocate memory.\n");
672  return NULL;
673  }
674 
675  /* Fill first word of new block with pointer to previous block. */
676  static_cast<void **>(m)[0] = base;
677  base = m;
678 
679  size_t shift = 0;
680  // int size_t = (WORDSIZE - ( (((size_t)m) + sizeof(void*)) &
681  // (WORDSIZE-1))) & (WORDSIZE-1);
682 
683  remaining = blocksize - sizeof(void *) - shift;
684  loc = (static_cast<char *>(m) + sizeof(void *) + shift);
685  }
686  void *rloc = loc;
687  loc = static_cast<char *>(loc) + size;
688  remaining -= size;
689 
690  usedMemory += size;
691 
692  return rloc;
693  }
694 
702  template <typename T> T *allocate(const size_t count = 1) {
703  T *mem = static_cast<T *>(this->malloc(sizeof(T) * count));
704  return mem;
705  }
706 };
715 template <int DIM, typename T> struct array_or_vector_selector {
716  typedef std::array<T, DIM> container_t;
717 };
719 template <typename T> struct array_or_vector_selector<-1, T> {
720  typedef std::vector<T> container_t;
721 };
722 
737 template <class Derived, typename Distance, class DatasetAdaptor, int DIM = -1,
738  typename IndexType = size_t>
740 
741 public:
744  void freeIndex(Derived &obj) {
745  obj.pool.free_all();
746  obj.root_node = NULL;
747  obj.m_size_at_index_build = 0;
748  }
749 
750  typedef typename Distance::ElementType ElementType;
751  typedef typename Distance::DistanceType DistanceType;
752 
753  /*--------------------- Internal Data Structures --------------------------*/
754  struct Node {
757  union {
758  struct leaf {
759  IndexType left, right;
760  } lr;
761  struct nonleaf {
762  int divfeat;
763  DistanceType divlow, divhigh;
764  } sub;
765  } node_type;
766  Node *child1, *child2;
767  };
768 
769  typedef Node *NodePtr;
770 
771  struct Interval {
773  };
774 
778  std::vector<IndexType> vind;
779 
781 
783 
784  size_t m_size;
786  int dim;
788 
791  typedef
793 
798 
802 
811 
813  size_t size(const Derived &obj) const { return obj.m_size; }
814 
816  size_t veclen(const Derived &obj) {
817  return static_cast<size_t>(DIM > 0 ? DIM : obj.dim);
818  }
819 
821  inline ElementType dataset_get(const Derived &obj, size_t idx,
822  int component) const {
823  return obj.dataset.kdtree_get_pt(idx, component);
824  }
825 
830  size_t usedMemory(Derived &obj) {
831  return obj.pool.usedMemory + obj.pool.wastedMemory +
832  obj.dataset.kdtree_get_point_count() *
833  sizeof(IndexType); // pool memory and vind array memory
834  }
835 
836  void computeMinMax(const Derived &obj, IndexType *ind, IndexType count,
837  int element, ElementType &min_elem,
838  ElementType &max_elem) {
839  min_elem = dataset_get(obj, ind[0], element);
840  max_elem = dataset_get(obj, ind[0], element);
841  for (IndexType i = 1; i < count; ++i) {
842  ElementType val = dataset_get(obj, ind[i], element);
843  if (val < min_elem)
844  min_elem = val;
845  if (val > max_elem)
846  max_elem = val;
847  }
848  }
849 
857  NodePtr divideTree(Derived &obj, const IndexType left, const IndexType right,
858  BoundingBox &bbox) {
859  NodePtr node = obj.pool.template allocate<Node>(); // allocate memory
860 
861  /* If too few exemplars remain, then make this a leaf node. */
862  if ((right - left) <= static_cast<IndexType>(obj.m_leaf_max_size)) {
863  node->child1 = node->child2 = NULL; /* Mark as leaf node. */
864  node->node_type.lr.left = left;
865  node->node_type.lr.right = right;
866 
867  // compute bounding-box of leaf points
868  for (int i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i) {
869  bbox[i].low = dataset_get(obj, obj.vind[left], i);
870  bbox[i].high = dataset_get(obj, obj.vind[left], i);
871  }
872  for (IndexType k = left + 1; k < right; ++k) {
873  for (int i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i) {
874  if (bbox[i].low > dataset_get(obj, obj.vind[k], i))
875  bbox[i].low = dataset_get(obj, obj.vind[k], i);
876  if (bbox[i].high < dataset_get(obj, obj.vind[k], i))
877  bbox[i].high = dataset_get(obj, obj.vind[k], i);
878  }
879  }
880  } else {
881  IndexType idx;
882  int cutfeat;
883  DistanceType cutval;
884  middleSplit_(obj, &obj.vind[0] + left, right - left, idx, cutfeat, cutval,
885  bbox);
886 
887  node->node_type.sub.divfeat = cutfeat;
888 
889  BoundingBox left_bbox(bbox);
890  left_bbox[cutfeat].high = cutval;
891  node->child1 = divideTree(obj, left, left + idx, left_bbox);
892 
893  BoundingBox right_bbox(bbox);
894  right_bbox[cutfeat].low = cutval;
895  node->child2 = divideTree(obj, left + idx, right, right_bbox);
896 
897  node->node_type.sub.divlow = left_bbox[cutfeat].high;
898  node->node_type.sub.divhigh = right_bbox[cutfeat].low;
899 
900  for (int i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i) {
901  bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
902  bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
903  }
904  }
905 
906  return node;
907  }
908 
909  void middleSplit_(Derived &obj, IndexType *ind, IndexType count,
910  IndexType &index, int &cutfeat, DistanceType &cutval,
911  const BoundingBox &bbox) {
912  const DistanceType EPS = static_cast<DistanceType>(0.00001);
913  ElementType max_span = bbox[0].high - bbox[0].low;
914  for (int i = 1; i < (DIM > 0 ? DIM : obj.dim); ++i) {
915  ElementType span = bbox[i].high - bbox[i].low;
916  if (span > max_span) {
917  max_span = span;
918  }
919  }
920  ElementType max_spread = -1;
921  cutfeat = 0;
922  for (int i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i) {
923  ElementType span = bbox[i].high - bbox[i].low;
924  if (span > (1 - EPS) * max_span) {
925  ElementType min_elem, max_elem;
926  computeMinMax(obj, ind, count, i, min_elem, max_elem);
927  ElementType spread = max_elem - min_elem;
928  ;
929  if (spread > max_spread) {
930  cutfeat = i;
931  max_spread = spread;
932  }
933  }
934  }
935  // split in the middle
936  DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;
937  ElementType min_elem, max_elem;
938  computeMinMax(obj, ind, count, cutfeat, min_elem, max_elem);
939 
940  if (split_val < min_elem)
941  cutval = min_elem;
942  else if (split_val > max_elem)
943  cutval = max_elem;
944  else
945  cutval = split_val;
946 
947  IndexType lim1, lim2;
948  planeSplit(obj, ind, count, cutfeat, cutval, lim1, lim2);
949 
950  if (lim1 > count / 2)
951  index = lim1;
952  else if (lim2 < count / 2)
953  index = lim2;
954  else
955  index = count / 2;
956  }
957 
967  void planeSplit(Derived &obj, IndexType *ind, const IndexType count,
968  int cutfeat, DistanceType &cutval, IndexType &lim1,
969  IndexType &lim2) {
970  /* Move vector indices for left subtree to front of list. */
971  IndexType left = 0;
972  IndexType right = count - 1;
973  for (;;) {
974  while (left <= right && dataset_get(obj, ind[left], cutfeat) < cutval)
975  ++left;
976  while (right && left <= right &&
977  dataset_get(obj, ind[right], cutfeat) >= cutval)
978  --right;
979  if (left > right || !right)
980  break; // "!right" was added to support unsigned Index types
981  std::swap(ind[left], ind[right]);
982  ++left;
983  --right;
984  }
985  /* If either list is empty, it means that all remaining features
986  * are identical. Split in the middle to maintain a balanced tree.
987  */
988  lim1 = left;
989  right = count - 1;
990  for (;;) {
991  while (left <= right && dataset_get(obj, ind[left], cutfeat) <= cutval)
992  ++left;
993  while (right && left <= right &&
994  dataset_get(obj, ind[right], cutfeat) > cutval)
995  --right;
996  if (left > right || !right)
997  break; // "!right" was added to support unsigned Index types
998  std::swap(ind[left], ind[right]);
999  ++left;
1000  --right;
1001  }
1002  lim2 = left;
1003  }
1004 
1006  const ElementType *vec,
1007  distance_vector_t &dists) const {
1008  assert(vec);
1009  DistanceType distsq = DistanceType();
1010 
1011  for (int i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i) {
1012  if (vec[i] < obj.root_bbox[i].low) {
1013  dists[i] = obj.distance.accum_dist(vec[i], obj.root_bbox[i].low, i);
1014  distsq += dists[i];
1015  }
1016  if (vec[i] > obj.root_bbox[i].high) {
1017  dists[i] = obj.distance.accum_dist(vec[i], obj.root_bbox[i].high, i);
1018  distsq += dists[i];
1019  }
1020  }
1021  return distsq;
1022  }
1023 
1024  void save_tree(Derived &obj, FILE *stream, NodePtr tree) {
1025  save_value(stream, *tree);
1026  if (tree->child1 != NULL) {
1027  save_tree(obj, stream, tree->child1);
1028  }
1029  if (tree->child2 != NULL) {
1030  save_tree(obj, stream, tree->child2);
1031  }
1032  }
1033 
1034  void load_tree(Derived &obj, FILE *stream, NodePtr &tree) {
1035  tree = obj.pool.template allocate<Node>();
1036  load_value(stream, *tree);
1037  if (tree->child1 != NULL) {
1038  load_tree(obj, stream, tree->child1);
1039  }
1040  if (tree->child2 != NULL) {
1041  load_tree(obj, stream, tree->child2);
1042  }
1043  }
1044 
1050  void saveIndex_(Derived &obj, FILE *stream) {
1051  save_value(stream, obj.m_size);
1052  save_value(stream, obj.dim);
1053  save_value(stream, obj.root_bbox);
1054  save_value(stream, obj.m_leaf_max_size);
1055  save_value(stream, obj.vind);
1056  save_tree(obj, stream, obj.root_node);
1057  }
1058 
1064  void loadIndex_(Derived &obj, FILE *stream) {
1065  load_value(stream, obj.m_size);
1066  load_value(stream, obj.dim);
1067  load_value(stream, obj.root_bbox);
1068  load_value(stream, obj.m_leaf_max_size);
1069  load_value(stream, obj.vind);
1070  load_tree(obj, stream, obj.root_node);
1071  }
1072 };
1073 
1114 template <typename Distance, class DatasetAdaptor, int DIM = -1,
1115  typename IndexType = size_t>
1117  : public KDTreeBaseClass<
1118  KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, IndexType>,
1119  Distance, DatasetAdaptor, DIM, IndexType> {
1120 public:
1124  &) = delete;
1125 
1129  const DatasetAdaptor &dataset;
1130 
1132 
1133  Distance distance;
1134 
1135  typedef typename nanoflann::KDTreeBaseClass<
1136  nanoflann::KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM,
1137  IndexType>,
1138  Distance, DatasetAdaptor, DIM, IndexType>
1140 
1143 
1144  typedef typename BaseClassRef::Node Node;
1145  typedef Node *NodePtr;
1146 
1151 
1155 
1170  KDTreeSingleIndexAdaptor(const int dimensionality,
1171  const DatasetAdaptor &inputData,
1172  const KDTreeSingleIndexAdaptorParams &params =
1174  : dataset(inputData), index_params(params), distance(inputData) {
1175  BaseClassRef::root_node = NULL;
1176  BaseClassRef::m_size = dataset.kdtree_get_point_count();
1177  BaseClassRef::m_size_at_index_build = BaseClassRef::m_size;
1178  BaseClassRef::dim = dimensionality;
1179  if (DIM > 0)
1180  BaseClassRef::dim = DIM;
1181  BaseClassRef::m_leaf_max_size = params.leaf_max_size;
1182 
1183  // Create a permutable array of indices to the input vectors.
1184  init_vind();
1185  }
1186 
1190  void buildIndex() {
1191  BaseClassRef::m_size = dataset.kdtree_get_point_count();
1192  BaseClassRef::m_size_at_index_build = BaseClassRef::m_size;
1193  init_vind();
1194  this->freeIndex(*this);
1195  BaseClassRef::m_size_at_index_build = BaseClassRef::m_size;
1196  if (BaseClassRef::m_size == 0)
1197  return;
1198  computeBoundingBox(BaseClassRef::root_bbox);
1199  BaseClassRef::root_node =
1200  this->divideTree(*this, 0, BaseClassRef::m_size,
1201  BaseClassRef::root_bbox); // construct the tree
1202  }
1203 
1220  template <typename RESULTSET>
1221  bool findNeighbors(RESULTSET &result, const ElementType *vec,
1222  const SearchParams &searchParams) const {
1223  assert(vec);
1224  if (this->size(*this) == 0)
1225  return false;
1226  if (!BaseClassRef::root_node)
1227  throw std::runtime_error(
1228  "[nanoflann] findNeighbors() called before building the index.");
1229  float epsError = 1 + searchParams.eps;
1230 
1232  dists; // fixed or variable-sized container (depending on DIM)
1233  auto zero = static_cast<decltype(result.worstDist())>(0);
1234  assign(dists, (DIM > 0 ? DIM : BaseClassRef::dim),
1235  zero); // Fill it with zeros.
1236  DistanceType distsq = this->computeInitialDistances(*this, vec, dists);
1237  searchLevel(result, vec, BaseClassRef::root_node, distsq, dists,
1238  epsError); // "count_leaf" parameter removed since was neither
1239  // used nor returned to the user.
1240  return result.full();
1241  }
1242 
1252  size_t knnSearch(const ElementType *query_point, const size_t num_closest,
1253  IndexType *out_indices, DistanceType *out_distances_sq,
1254  const int /* nChecks_IGNORED */ = 10) const {
1255  nanoflann::KNNResultSet<DistanceType, IndexType> resultSet(num_closest);
1256  resultSet.init(out_indices, out_distances_sq);
1257  this->findNeighbors(resultSet, query_point, nanoflann::SearchParams());
1258  return resultSet.size();
1259  }
1260 
1277  size_t
1278  radiusSearch(const ElementType *query_point, const DistanceType &radius,
1279  std::vector<std::pair<IndexType, DistanceType>> &IndicesDists,
1280  const SearchParams &searchParams) const {
1281  RadiusResultSet<DistanceType, IndexType> resultSet(radius, IndicesDists);
1282  const size_t nFound =
1283  radiusSearchCustomCallback(query_point, resultSet, searchParams);
1284  if (searchParams.sorted)
1285  std::sort(IndicesDists.begin(), IndicesDists.end(), IndexDist_Sorter());
1286  return nFound;
1287  }
1288 
1294  template <class SEARCH_CALLBACK>
1296  const ElementType *query_point, SEARCH_CALLBACK &resultSet,
1297  const SearchParams &searchParams = SearchParams()) const {
1298  this->findNeighbors(resultSet, query_point, searchParams);
1299  return resultSet.size();
1300  }
1301 
1304 public:
1307  void init_vind() {
1308  // Create a permutable array of indices to the input vectors.
1309  BaseClassRef::m_size = dataset.kdtree_get_point_count();
1310  if (BaseClassRef::vind.size() != BaseClassRef::m_size)
1311  BaseClassRef::vind.resize(BaseClassRef::m_size);
1312  for (size_t i = 0; i < BaseClassRef::m_size; i++)
1313  BaseClassRef::vind[i] = i;
1314  }
1315 
1317  resize(bbox, (DIM > 0 ? DIM : BaseClassRef::dim));
1318  if (dataset.kdtree_get_bbox(bbox)) {
1319  // Done! It was implemented in derived class
1320  } else {
1321  const size_t N = dataset.kdtree_get_point_count();
1322  if (!N)
1323  throw std::runtime_error("[nanoflann] computeBoundingBox() called but "
1324  "no data points found.");
1325  for (int i = 0; i < (DIM > 0 ? DIM : BaseClassRef::dim); ++i) {
1326  bbox[i].low = bbox[i].high = this->dataset_get(*this, 0, i);
1327  }
1328  for (size_t k = 1; k < N; ++k) {
1329  for (int i = 0; i < (DIM > 0 ? DIM : BaseClassRef::dim); ++i) {
1330  if (this->dataset_get(*this, k, i) < bbox[i].low)
1331  bbox[i].low = this->dataset_get(*this, k, i);
1332  if (this->dataset_get(*this, k, i) > bbox[i].high)
1333  bbox[i].high = this->dataset_get(*this, k, i);
1334  }
1335  }
1336  }
1337  }
1338 
1345  template <class RESULTSET>
1346  bool searchLevel(RESULTSET &result_set, const ElementType *vec,
1347  const NodePtr node, DistanceType mindistsq,
1348  distance_vector_t &dists, const float epsError) const {
1349  /* If this is a leaf node, then do check and return. */
1350  if ((node->child1 == NULL) && (node->child2 == NULL)) {
1351  // count_leaf += (node->lr.right-node->lr.left); // Removed since was
1352  // neither used nor returned to the user.
1353  DistanceType worst_dist = result_set.worstDist();
1354  for (IndexType i = node->node_type.lr.left; i < node->node_type.lr.right;
1355  ++i) {
1356  const IndexType index = BaseClassRef::vind[i]; // reorder... : i;
1357  DistanceType dist = distance.evalMetric(
1358  vec, index, (DIM > 0 ? DIM : BaseClassRef::dim));
1359  if (dist < worst_dist) {
1360  if (!result_set.addPoint(dist, BaseClassRef::vind[i])) {
1361  // the resultset doesn't want to receive any more points, we're done
1362  // searching!
1363  return false;
1364  }
1365  }
1366  }
1367  return true;
1368  }
1369 
1370  /* Which child branch should be taken first? */
1371  int idx = node->node_type.sub.divfeat;
1372  ElementType val = vec[idx];
1373  DistanceType diff1 = val - node->node_type.sub.divlow;
1374  DistanceType diff2 = val - node->node_type.sub.divhigh;
1375 
1376  NodePtr bestChild;
1377  NodePtr otherChild;
1378  DistanceType cut_dist;
1379  if ((diff1 + diff2) < 0) {
1380  bestChild = node->child1;
1381  otherChild = node->child2;
1382  cut_dist = distance.accum_dist(val, node->node_type.sub.divhigh, idx);
1383  } else {
1384  bestChild = node->child2;
1385  otherChild = node->child1;
1386  cut_dist = distance.accum_dist(val, node->node_type.sub.divlow, idx);
1387  }
1388 
1389  /* Call recursively to search next level down. */
1390  if (!searchLevel(result_set, vec, bestChild, mindistsq, dists, epsError)) {
1391  // the resultset doesn't want to receive any more points, we're done
1392  // searching!
1393  return false;
1394  }
1395 
1396  DistanceType dst = dists[idx];
1397  mindistsq = mindistsq + cut_dist - dst;
1398  dists[idx] = cut_dist;
1399  if (mindistsq * epsError <= result_set.worstDist()) {
1400  if (!searchLevel(result_set, vec, otherChild, mindistsq, dists,
1401  epsError)) {
1402  // the resultset doesn't want to receive any more points, we're done
1403  // searching!
1404  return false;
1405  }
1406  }
1407  dists[idx] = dst;
1408  return true;
1409  }
1410 
1411 public:
1417  void saveIndex(FILE *stream) { this->saveIndex_(*this, stream); }
1418 
1424  void loadIndex(FILE *stream) { this->loadIndex_(*this, stream); }
1425 
1426 }; // class KDTree
1427 
1464 template <typename Distance, class DatasetAdaptor, int DIM = -1,
1465  typename IndexType = size_t>
1467  : public KDTreeBaseClass<KDTreeSingleIndexDynamicAdaptor_<
1468  Distance, DatasetAdaptor, DIM, IndexType>,
1469  Distance, DatasetAdaptor, DIM, IndexType> {
1470 public:
1474  const DatasetAdaptor &dataset;
1475 
1477 
1478  std::vector<int> &treeIndex;
1479 
1480  Distance distance;
1481 
1482  typedef typename nanoflann::KDTreeBaseClass<
1483  nanoflann::KDTreeSingleIndexDynamicAdaptor_<Distance, DatasetAdaptor, DIM,
1484  IndexType>,
1485  Distance, DatasetAdaptor, DIM, IndexType>
1487 
1490 
1491  typedef typename BaseClassRef::Node Node;
1492  typedef Node *NodePtr;
1493 
1498 
1502 
1518  const int dimensionality, const DatasetAdaptor &inputData,
1519  std::vector<int> &treeIndex_,
1520  const KDTreeSingleIndexAdaptorParams &params =
1522  : dataset(inputData), index_params(params), treeIndex(treeIndex_),
1523  distance(inputData) {
1524  BaseClassRef::root_node = NULL;
1525  BaseClassRef::m_size = 0;
1526  BaseClassRef::m_size_at_index_build = 0;
1527  BaseClassRef::dim = dimensionality;
1528  if (DIM > 0)
1529  BaseClassRef::dim = DIM;
1530  BaseClassRef::m_leaf_max_size = params.leaf_max_size;
1531  }
1532 
1537  std::swap(BaseClassRef::vind, tmp.BaseClassRef::vind);
1538  std::swap(BaseClassRef::m_leaf_max_size, tmp.BaseClassRef::m_leaf_max_size);
1539  std::swap(index_params, tmp.index_params);
1540  std::swap(treeIndex, tmp.treeIndex);
1541  std::swap(BaseClassRef::m_size, tmp.BaseClassRef::m_size);
1542  std::swap(BaseClassRef::m_size_at_index_build,
1543  tmp.BaseClassRef::m_size_at_index_build);
1544  std::swap(BaseClassRef::root_node, tmp.BaseClassRef::root_node);
1545  std::swap(BaseClassRef::root_bbox, tmp.BaseClassRef::root_bbox);
1546  std::swap(BaseClassRef::pool, tmp.BaseClassRef::pool);
1547  return *this;
1548  }
1549 
1553  void buildIndex() {
1554  BaseClassRef::m_size = BaseClassRef::vind.size();
1555  this->freeIndex(*this);
1556  BaseClassRef::m_size_at_index_build = BaseClassRef::m_size;
1557  if (BaseClassRef::m_size == 0)
1558  return;
1559  computeBoundingBox(BaseClassRef::root_bbox);
1560  BaseClassRef::root_node =
1561  this->divideTree(*this, 0, BaseClassRef::m_size,
1562  BaseClassRef::root_bbox); // construct the tree
1563  }
1564 
1581  template <typename RESULTSET>
1582  bool findNeighbors(RESULTSET &result, const ElementType *vec,
1583  const SearchParams &searchParams) const {
1584  assert(vec);
1585  if (this->size(*this) == 0)
1586  return false;
1587  if (!BaseClassRef::root_node)
1588  return false;
1589  float epsError = 1 + searchParams.eps;
1590 
1591  // fixed or variable-sized container (depending on DIM)
1593  // Fill it with zeros.
1594  assign(dists, (DIM > 0 ? DIM : BaseClassRef::dim),
1595  static_cast<typename distance_vector_t::value_type>(0));
1596  DistanceType distsq = this->computeInitialDistances(*this, vec, dists);
1597  searchLevel(result, vec, BaseClassRef::root_node, distsq, dists,
1598  epsError); // "count_leaf" parameter removed since was neither
1599  // used nor returned to the user.
1600  return result.full();
1601  }
1602 
1612  size_t knnSearch(const ElementType *query_point, const size_t num_closest,
1613  IndexType *out_indices, DistanceType *out_distances_sq,
1614  const int /* nChecks_IGNORED */ = 10) const {
1615  nanoflann::KNNResultSet<DistanceType, IndexType> resultSet(num_closest);
1616  resultSet.init(out_indices, out_distances_sq);
1617  this->findNeighbors(resultSet, query_point, nanoflann::SearchParams());
1618  return resultSet.size();
1619  }
1620 
1637  size_t
1638  radiusSearch(const ElementType *query_point, const DistanceType &radius,
1639  std::vector<std::pair<IndexType, DistanceType>> &IndicesDists,
1640  const SearchParams &searchParams) const {
1641  RadiusResultSet<DistanceType, IndexType> resultSet(radius, IndicesDists);
1642  const size_t nFound =
1643  radiusSearchCustomCallback(query_point, resultSet, searchParams);
1644  if (searchParams.sorted)
1645  std::sort(IndicesDists.begin(), IndicesDists.end(), IndexDist_Sorter());
1646  return nFound;
1647  }
1648 
1654  template <class SEARCH_CALLBACK>
1656  const ElementType *query_point, SEARCH_CALLBACK &resultSet,
1657  const SearchParams &searchParams = SearchParams()) const {
1658  this->findNeighbors(resultSet, query_point, searchParams);
1659  return resultSet.size();
1660  }
1661 
1664 public:
1666  resize(bbox, (DIM > 0 ? DIM : BaseClassRef::dim));
1667 
1668  if (dataset.kdtree_get_bbox(bbox)) {
1669  // Done! It was implemented in derived class
1670  } else {
1671  const size_t N = BaseClassRef::m_size;
1672  if (!N)
1673  throw std::runtime_error("[nanoflann] computeBoundingBox() called but "
1674  "no data points found.");
1675  for (int i = 0; i < (DIM > 0 ? DIM : BaseClassRef::dim); ++i) {
1676  bbox[i].low = bbox[i].high =
1677  this->dataset_get(*this, BaseClassRef::vind[0], i);
1678  }
1679  for (size_t k = 1; k < N; ++k) {
1680  for (int i = 0; i < (DIM > 0 ? DIM : BaseClassRef::dim); ++i) {
1681  if (this->dataset_get(*this, BaseClassRef::vind[k], i) < bbox[i].low)
1682  bbox[i].low = this->dataset_get(*this, BaseClassRef::vind[k], i);
1683  if (this->dataset_get(*this, BaseClassRef::vind[k], i) > bbox[i].high)
1684  bbox[i].high = this->dataset_get(*this, BaseClassRef::vind[k], i);
1685  }
1686  }
1687  }
1688  }
1689 
1694  template <class RESULTSET>
1695  void searchLevel(RESULTSET &result_set, const ElementType *vec,
1696  const NodePtr node, DistanceType mindistsq,
1697  distance_vector_t &dists, const float epsError) const {
1698  /* If this is a leaf node, then do check and return. */
1699  if ((node->child1 == NULL) && (node->child2 == NULL)) {
1700  // count_leaf += (node->lr.right-node->lr.left); // Removed since was
1701  // neither used nor returned to the user.
1702  DistanceType worst_dist = result_set.worstDist();
1703  for (IndexType i = node->node_type.lr.left; i < node->node_type.lr.right;
1704  ++i) {
1705  const IndexType index = BaseClassRef::vind[i]; // reorder... : i;
1706  if (treeIndex[index] == -1)
1707  continue;
1708  DistanceType dist = distance.evalMetric(
1709  vec, index, (DIM > 0 ? DIM : BaseClassRef::dim));
1710  if (dist < worst_dist) {
1711  if (!result_set.addPoint(
1712  static_cast<typename RESULTSET::DistanceType>(dist),
1713  static_cast<typename RESULTSET::IndexType>(
1714  BaseClassRef::vind[i]))) {
1715  // the resultset doesn't want to receive any more points, we're done
1716  // searching!
1717  return; // false;
1718  }
1719  }
1720  }
1721  return;
1722  }
1723 
1724  /* Which child branch should be taken first? */
1725  int idx = node->node_type.sub.divfeat;
1726  ElementType val = vec[idx];
1727  DistanceType diff1 = val - node->node_type.sub.divlow;
1728  DistanceType diff2 = val - node->node_type.sub.divhigh;
1729 
1730  NodePtr bestChild;
1731  NodePtr otherChild;
1732  DistanceType cut_dist;
1733  if ((diff1 + diff2) < 0) {
1734  bestChild = node->child1;
1735  otherChild = node->child2;
1736  cut_dist = distance.accum_dist(val, node->node_type.sub.divhigh, idx);
1737  } else {
1738  bestChild = node->child2;
1739  otherChild = node->child1;
1740  cut_dist = distance.accum_dist(val, node->node_type.sub.divlow, idx);
1741  }
1742 
1743  /* Call recursively to search next level down. */
1744  searchLevel(result_set, vec, bestChild, mindistsq, dists, epsError);
1745 
1746  DistanceType dst = dists[idx];
1747  mindistsq = mindistsq + cut_dist - dst;
1748  dists[idx] = cut_dist;
1749  if (mindistsq * epsError <= result_set.worstDist()) {
1750  searchLevel(result_set, vec, otherChild, mindistsq, dists, epsError);
1751  }
1752  dists[idx] = dst;
1753  }
1754 
1755 public:
1761  void saveIndex(FILE *stream) { this->saveIndex_(*this, stream); }
1762 
1768  void loadIndex(FILE *stream) { this->loadIndex_(*this, stream); }
1769 };
1770 
1785 template <typename Distance, class DatasetAdaptor, int DIM = -1,
1786  typename IndexType = size_t>
1788 public:
1789  typedef typename Distance::ElementType ElementType;
1790  typedef typename Distance::DistanceType DistanceType;
1791 
1792 protected:
1794  size_t treeCount;
1795  size_t pointCount;
1796 
1800  const DatasetAdaptor &dataset;
1801 
1802  std::vector<int> treeIndex;
1803 
1807 
1808  int dim;
1809 
1812  std::vector<index_container_t> index;
1813 
1814 public:
1817  const std::vector<index_container_t> &getAllIndices() const { return index; }
1818 
1819 private:
1822  int pos = 0;
1823  while (num & 1) {
1824  num = num >> 1;
1825  pos++;
1826  }
1827  return pos;
1828  }
1829 
1831  void init() {
1833  my_kd_tree_t;
1834  std::vector<my_kd_tree_t> index_(
1835  treeCount, my_kd_tree_t(dim /*dim*/, dataset, treeIndex, index_params));
1836  index = index_;
1837  }
1838 
1839 public:
1840  Distance distance;
1841 
1856  KDTreeSingleIndexDynamicAdaptor(const int dimensionality,
1857  const DatasetAdaptor &inputData,
1858  const KDTreeSingleIndexAdaptorParams &params =
1860  const size_t maximumPointCount = 1000000000U)
1861  : dataset(inputData), index_params(params), distance(inputData) {
1862  treeCount = static_cast<size_t>(std::log2(maximumPointCount));
1863  pointCount = 0U;
1864  dim = dimensionality;
1865  treeIndex.clear();
1866  if (DIM > 0)
1867  dim = DIM;
1868  m_leaf_max_size = params.leaf_max_size;
1869  init();
1870  const size_t num_initial_points = dataset.kdtree_get_point_count();
1871  if (num_initial_points > 0) {
1872  addPoints(0, num_initial_points - 1);
1873  }
1874  }
1875 
1878  const KDTreeSingleIndexDynamicAdaptor<Distance, DatasetAdaptor, DIM,
1879  IndexType> &) = delete;
1880 
1882  void addPoints(IndexType start, IndexType end) {
1883  size_t count = end - start + 1;
1884  treeIndex.resize(treeIndex.size() + count);
1885  for (IndexType idx = start; idx <= end; idx++) {
1886  int pos = First0Bit(pointCount);
1887  index[pos].vind.clear();
1888  treeIndex[pointCount] = pos;
1889  for (int i = 0; i < pos; i++) {
1890  for (int j = 0; j < static_cast<int>(index[i].vind.size()); j++) {
1891  index[pos].vind.push_back(index[i].vind[j]);
1892  if (treeIndex[index[i].vind[j]] != -1)
1893  treeIndex[index[i].vind[j]] = pos;
1894  }
1895  index[i].vind.clear();
1896  index[i].freeIndex(index[i]);
1897  }
1898  index[pos].vind.push_back(idx);
1899  index[pos].buildIndex();
1900  pointCount++;
1901  }
1902  }
1903 
1905  void removePoint(size_t idx) {
1906  if (idx >= pointCount)
1907  return;
1908  treeIndex[idx] = -1;
1909  }
1910 
1924  template <typename RESULTSET>
1925  bool findNeighbors(RESULTSET &result, const ElementType *vec,
1926  const SearchParams &searchParams) const {
1927  for (size_t i = 0; i < treeCount; i++) {
1928  index[i].findNeighbors(result, &vec[0], searchParams);
1929  }
1930  return result.full();
1931  }
1932 };
1933 
1952 template <class MatrixType, int DIM = -1, class Distance = nanoflann::metric_L2>
1955  typedef typename MatrixType::Scalar num_t;
1956  typedef typename MatrixType::Index IndexType;
1957  typedef
1958  typename Distance::template traits<num_t, self_t>::distance_t metric_t;
1960  MatrixType::ColsAtCompileTime, IndexType>
1962 
1964 
1967  KDTreeEigenMatrixAdaptor(const size_t dimensionality,
1968  const std::reference_wrapper<const MatrixType> &mat,
1969  const int leaf_max_size = 10)
1970  : m_data_matrix(mat) {
1971  const auto dims = mat.get().cols();
1972  if (size_t(dims) != dimensionality)
1973  throw std::runtime_error(
1974  "Error: 'dimensionality' must match column count in data matrix");
1975  if (DIM > 0 && int(dims) != DIM)
1976  throw std::runtime_error(
1977  "Data set dimensionality does not match the 'DIM' template argument");
1978  index =
1979  new index_t(static_cast<int>(dims), *this /* adaptor */,
1981  index->buildIndex();
1982  }
1983 
1984 public:
1986  KDTreeEigenMatrixAdaptor(const self_t &) = delete;
1987 
1988  ~KDTreeEigenMatrixAdaptor() { delete index; }
1989 
1990  const std::reference_wrapper<const MatrixType> m_data_matrix;
1991 
1998  inline void query(const num_t *query_point, const size_t num_closest,
1999  IndexType *out_indices, num_t *out_distances_sq,
2000  const int /* nChecks_IGNORED */ = 10) const {
2001  nanoflann::KNNResultSet<num_t, IndexType> resultSet(num_closest);
2002  resultSet.init(out_indices, out_distances_sq);
2003  index->findNeighbors(resultSet, query_point, nanoflann::SearchParams());
2004  }
2005 
2009  const self_t &derived() const { return *this; }
2010  self_t &derived() { return *this; }
2011 
2012  // Must return the number of data points
2013  inline size_t kdtree_get_point_count() const {
2014  return m_data_matrix.get().rows();
2015  }
2016 
2017  // Returns the dim'th component of the idx'th point in the class:
2018  inline num_t kdtree_get_pt(const IndexType idx, size_t dim) const {
2019  return m_data_matrix.get().coeff(idx, IndexType(dim));
2020  }
2021 
2022  // Optional bounding-box computation: return false to default to a standard
2023  // bbox computation loop.
2024  // Return true if the BBOX was already computed by the class and returned in
2025  // "bb" so it can be avoided to redo it again. Look at bb.size() to find out
2026  // the expected dimensionality (e.g. 2 or 3 for point clouds)
2027  template <class BBOX> bool kdtree_get_bbox(BBOX & /*bb*/) const {
2028  return false;
2029  }
2030 
2033 }; // end of KDTreeEigenMatrixAdaptor // end of grouping
2037 } // namespace nanoflann
2038 
2039 #endif /* NANOFLANN_HPP_ */
nanoflann::KDTreeSingleIndexDynamicAdaptor_::BaseClassRef
nanoflann::KDTreeBaseClass< nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >, Distance, DatasetAdaptor, DIM, IndexType > BaseClassRef
Definition: nanoflann.hpp:1486
nanoflann::metric_L2
Definition: nanoflann.hpp:516
nanoflann::KDTreeSingleIndexDynamicAdaptor::findNeighbors
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
Definition: nanoflann.hpp:1925
nanoflann::KDTreeBaseClass::size
size_t size(const Derived &obj) const
Definition: nanoflann.hpp:813
nanoflann::RadiusResultSet
Definition: nanoflann.hpp:220
nanoflann::KDTreeSingleIndexDynamicAdaptor::removePoint
void removePoint(size_t idx)
Definition: nanoflann.hpp:1905
nanoflann::KDTreeEigenMatrixAdaptor::num_t
MatrixType::Scalar num_t
Definition: nanoflann.hpp:1955
nanoflann::L2_Adaptor::evalMetric
DistanceType evalMetric(const T *a, const size_t b_idx, size_t size, DistanceType worst_dist=-1) const
Definition: nanoflann.hpp:383
nanoflann::L2_Simple_Adaptor::accum_dist
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition: nanoflann.hpp:443
nanoflann::L2_Simple_Adaptor
Definition: nanoflann.hpp:423
nanoflann::L2_Adaptor::L2_Adaptor
L2_Adaptor(const DataSource &_data_source)
Definition: nanoflann.hpp:381
nanoflann::KDTreeSingleIndexDynamicAdaptor::addPoints
void addPoints(IndexType start, IndexType end)
Definition: nanoflann.hpp:1882
nanoflann::SO3_Adaptor::distance_L2_Simple
L2_Simple_Adaptor< T, DataSource > distance_L2_Simple
Definition: nanoflann.hpp:493
nanoflann::KDTreeBaseClass::m_leaf_max_size
size_t m_leaf_max_size
Definition: nanoflann.hpp:782
nanoflann::KDTreeSingleIndexAdaptor::findNeighbors
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
Definition: nanoflann.hpp:1221
nanoflann::L2_Simple_Adaptor::data_source
const DataSource & data_source
Definition: nanoflann.hpp:427
nanoflann::KDTreeSingleIndexAdaptor::loadIndex
void loadIndex(FILE *stream)
Definition: nanoflann.hpp:1424
nanoflann::KDTreeBaseClass::save_tree
void save_tree(Derived &obj, FILE *stream, NodePtr tree)
Definition: nanoflann.hpp:1024
nanoflann::L2_Simple_Adaptor::L2_Simple_Adaptor
L2_Simple_Adaptor(const DataSource &_data_source)
Definition: nanoflann.hpp:429
nanoflann::array_or_vector_selector<-1, T >::container_t
std::vector< T > container_t
Definition: nanoflann.hpp:720
nanoflann::KDTreeBaseClass::Interval
Definition: nanoflann.hpp:771
nanoflann::KNNResultSet::DistanceType
_DistanceType DistanceType
Definition: nanoflann.hpp:144
nanoflann::assign
std::enable_if< has_assign< Container >::value, void >::type assign(Container &c, const size_t nElements, const T &value)
Definition: nanoflann.hpp:124
nanoflann::PooledAllocator::free_all
void free_all()
Definition: nanoflann.hpp:634
nanoflann::KDTreeSingleIndexDynamicAdaptor::index_params
KDTreeSingleIndexAdaptorParams index_params
Definition: nanoflann.hpp:1806
nanoflann::KDTreeSingleIndexDynamicAdaptor_::KDTreeSingleIndexDynamicAdaptor_
KDTreeSingleIndexDynamicAdaptor_(const int dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex_, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
Definition: nanoflann.hpp:1517
nanoflann::KDTreeSingleIndexDynamicAdaptor_::operator=
KDTreeSingleIndexDynamicAdaptor_ operator=(const KDTreeSingleIndexDynamicAdaptor_ &rhs)
Definition: nanoflann.hpp:1535
nanoflann::RadiusResultSet::full
bool full() const
Definition: nanoflann.hpp:242
nanoflann::load_value
void load_value(FILE *stream, T &value, size_t count=1)
Definition: nanoflann.hpp:291
nanoflann::KDTreeEigenMatrixAdaptor::index
index_t * index
Definition: nanoflann.hpp:1963
nanoflann::KDTreeBaseClass::BoundingBox
array_or_vector_selector< DIM, Interval >::container_t BoundingBox
Definition: nanoflann.hpp:792
nanoflann::PooledAllocator::wastedMemory
size_t wastedMemory
Definition: nanoflann.hpp:621
nanoflann::RadiusResultSet::m_indices_dists
std::vector< std::pair< IndexType, DistanceType > > & m_indices_dists
Definition: nanoflann.hpp:228
nanoflann::KDTreeSingleIndexDynamicAdaptor::dataset
const DatasetAdaptor & dataset
The source of our data.
Definition: nanoflann.hpp:1800
nanoflann::KDTreeSingleIndexDynamicAdaptor::KDTreeSingleIndexDynamicAdaptor
KDTreeSingleIndexDynamicAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams(), const size_t maximumPointCount=1000000000U)
Definition: nanoflann.hpp:1856
nanoflann::metric_SO2::traits
Definition: nanoflann.hpp:529
nanoflann::KDTreeSingleIndexAdaptor::radiusSearchCustomCallback
size_t radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParams &searchParams=SearchParams()) const
Definition: nanoflann.hpp:1295
nanoflann::SearchParams::checks
int checks
Definition: nanoflann.hpp:560
nanoflann::SO2_Adaptor::SO2_Adaptor
SO2_Adaptor(const DataSource &_data_source)
Definition: nanoflann.hpp:461
nanoflann::metric_L2_Simple
Definition: nanoflann.hpp:522
nanoflann::SearchParams::eps
float eps
search for eps-approximate neighbours (default: 0)
Definition: nanoflann.hpp:562
nanoflann::KNNResultSet::KNNResultSet
KNNResultSet(CountType capacity_)
Definition: nanoflann.hpp:155
nanoflann::KDTreeBaseClass::Node::node_type
union nanoflann::KDTreeBaseClass::Node::@0 node_type
nanoflann::KDTreeSingleIndexAdaptor::DistanceType
BaseClassRef::DistanceType DistanceType
Definition: nanoflann.hpp:1142
nanoflann::KDTreeSingleIndexDynamicAdaptor_::distance
Distance distance
Definition: nanoflann.hpp:1480
nanoflann::RadiusResultSet::worstDist
DistanceType worstDist() const
Definition: nanoflann.hpp:255
nanoflann::KDTreeBaseClass::vind
std::vector< IndexType > vind
Definition: nanoflann.hpp:778
nanoflann::metric_L1::traits::distance_t
L1_Adaptor< T, DataSource > distance_t
Definition: nanoflann.hpp:512
nanoflann::KDTreeBaseClass::saveIndex_
void saveIndex_(Derived &obj, FILE *stream)
Definition: nanoflann.hpp:1050
nanoflann::L1_Adaptor::ElementType
T ElementType
Definition: nanoflann.hpp:325
nanoflann::KDTreeSingleIndexDynamicAdaptor_::ElementType
BaseClassRef::ElementType ElementType
Definition: nanoflann.hpp:1488
nanoflann::PooledAllocator::~PooledAllocator
~PooledAllocator()
Definition: nanoflann.hpp:631
nanoflann::RadiusResultSet::DistanceType
_DistanceType DistanceType
Definition: nanoflann.hpp:222
nanoflann::KDTreeSingleIndexAdaptor::saveIndex
void saveIndex(FILE *stream)
Definition: nanoflann.hpp:1417
nanoflann::L2_Simple_Adaptor::DistanceType
_DistanceType DistanceType
Definition: nanoflann.hpp:425
nanoflann::L1_Adaptor
Definition: nanoflann.hpp:324
nanoflann::metric_L1
Definition: nanoflann.hpp:510
nanoflann::KDTreeEigenMatrixAdaptor
Definition: nanoflann.hpp:1953
nanoflann::KDTreeSingleIndexAdaptor::init_vind
void init_vind()
Definition: nanoflann.hpp:1307
nanoflann::KDTreeBaseClass::freeIndex
void freeIndex(Derived &obj)
Definition: nanoflann.hpp:744
nanoflann
Definition: nanoflann.hpp:74
nanoflann::KDTreeSingleIndexDynamicAdaptor_::loadIndex
void loadIndex(FILE *stream)
Definition: nanoflann.hpp:1768
nanoflann::KDTreeSingleIndexDynamicAdaptor::treeIndex
std::vector< int > treeIndex
Definition: nanoflann.hpp:1802
nanoflann::L2_Adaptor::accum_dist
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition: nanoflann.hpp:411
nanoflann::RadiusResultSet::addPoint
bool addPoint(DistanceType dist, IndexType index)
Definition: nanoflann.hpp:249
nanoflann::PooledAllocator::allocate
T * allocate(const size_t count=1)
Definition: nanoflann.hpp:702
nanoflann::RadiusResultSet::IndexType
_IndexType IndexType
Definition: nanoflann.hpp:223
nanoflann::L2_Adaptor::ElementType
T ElementType
Definition: nanoflann.hpp:376
nanoflann::KNNResultSet::indices
IndexType * indices
Definition: nanoflann.hpp:149
nanoflann::KDTreeBaseClass::m_size
size_t m_size
Number of current points in the dataset.
Definition: nanoflann.hpp:784
nanoflann::PooledAllocator::internal_init
void internal_init()
Definition: nanoflann.hpp:612
nanoflann::KNNResultSet::addPoint
bool addPoint(DistanceType dist, IndexType index)
Definition: nanoflann.hpp:175
nanoflann::KDTreeSingleIndexDynamicAdaptor::index
std::vector< index_container_t > index
Definition: nanoflann.hpp:1812
nanoflann::RadiusResultSet::worst_item
std::pair< IndexType, DistanceType > worst_item() const
Definition: nanoflann.hpp:261
nanoflann::KDTreeSingleIndexDynamicAdaptor_::findNeighbors
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
Definition: nanoflann.hpp:1582
nanoflann::L2_Adaptor
Definition: nanoflann.hpp:375
nanoflann::PooledAllocator::remaining
size_t remaining
Definition: nanoflann.hpp:608
nanoflann::PooledAllocator::malloc
void * malloc(const size_t req_size)
Definition: nanoflann.hpp:648
nanoflann::KDTreeBaseClass::pool
PooledAllocator pool
Definition: nanoflann.hpp:810
nanoflann::allocate
T * allocate(size_t count=1)
Definition: nanoflann.hpp:578
nanoflann::KNNResultSet::count
CountType count
Definition: nanoflann.hpp:152
nanoflann::KDTreeSingleIndexAdaptor::searchLevel
bool searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, distance_vector_t &dists, const float epsError) const
Definition: nanoflann.hpp:1346
nanoflann::KDTreeBaseClass::computeMinMax
void computeMinMax(const Derived &obj, IndexType *ind, IndexType count, int element, ElementType &min_elem, ElementType &max_elem)
Definition: nanoflann.hpp:836
nanoflann::KDTreeSingleIndexDynamicAdaptor::init
void init()
Definition: nanoflann.hpp:1831
nanoflann::metric_SO2
Definition: nanoflann.hpp:528
nanoflann::Metric
Definition: nanoflann.hpp:315
nanoflann::L2_Adaptor::DistanceType
_DistanceType DistanceType
Definition: nanoflann.hpp:377
nanoflann::KDTreeEigenMatrixAdaptor::m_data_matrix
const std::reference_wrapper< const MatrixType > m_data_matrix
Definition: nanoflann.hpp:1990
nanoflann::KDTreeSingleIndexAdaptorParams::leaf_max_size
size_t leaf_max_size
Definition: nanoflann.hpp:550
nanoflann::PooledAllocator::usedMemory
size_t usedMemory
Definition: nanoflann.hpp:620
nanoflann::SO2_Adaptor::accum_dist
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition: nanoflann.hpp:471
nanoflann::KDTreeSingleIndexDynamicAdaptor_::radiusSearchCustomCallback
size_t radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParams &searchParams=SearchParams()) const
Definition: nanoflann.hpp:1655
nanoflann::KDTreeSingleIndexDynamicAdaptor_::Node
BaseClassRef::Node Node
Definition: nanoflann.hpp:1491
nanoflann::metric_L2::traits::distance_t
L2_Adaptor< T, DataSource > distance_t
Definition: nanoflann.hpp:518
nanoflann::KDTreeSingleIndexAdaptor::knnSearch
size_t knnSearch(const ElementType *query_point, const size_t num_closest, IndexType *out_indices, DistanceType *out_distances_sq, const int=10) const
Definition: nanoflann.hpp:1252
nanoflann::KDTreeBaseClass::veclen
size_t veclen(const Derived &obj)
Definition: nanoflann.hpp:816
nanoflann::KDTreeBaseClass
Definition: nanoflann.hpp:739
nanoflann::KDTreeEigenMatrixAdaptor::derived
const self_t & derived() const
Definition: nanoflann.hpp:2009
nanoflann::KDTreeSingleIndexAdaptor::dataset
const DatasetAdaptor & dataset
The source of our data.
Definition: nanoflann.hpp:1129
nanoflann::SearchParams::SearchParams
SearchParams(int checks_IGNORED_=32, float eps_=0, bool sorted_=true)
Definition: nanoflann.hpp:557
nanoflann::KDTreeEigenMatrixAdaptor::kdtree_get_point_count
size_t kdtree_get_point_count() const
Definition: nanoflann.hpp:2013
nanoflann::has_resize
Definition: nanoflann.hpp:87
nanoflann::KDTreeSingleIndexAdaptorParams
Definition: nanoflann.hpp:546
nanoflann::SO3_Adaptor::ElementType
T ElementType
Definition: nanoflann.hpp:490
nanoflann::KNNResultSet::worstDist
DistanceType worstDist() const
Definition: nanoflann.hpp:204
nanoflann::KDTreeSingleIndexDynamicAdaptor_::buildIndex
void buildIndex()
Definition: nanoflann.hpp:1553
nanoflann::metric_SO3::traits::distance_t
SO3_Adaptor< T, DataSource > distance_t
Definition: nanoflann.hpp:536
nanoflann::KDTreeBaseClass::Node::right
IndexType right
Indices of points in leaf node.
Definition: nanoflann.hpp:759
nanoflann::KDTreeSingleIndexAdaptor::BaseClassRef
nanoflann::KDTreeBaseClass< nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >, Distance, DatasetAdaptor, DIM, IndexType > BaseClassRef
Definition: nanoflann.hpp:1139
nanoflann::L1_Adaptor::evalMetric
DistanceType evalMetric(const T *a, const size_t b_idx, size_t size, DistanceType worst_dist=-1) const
Definition: nanoflann.hpp:332
nanoflann::KDTreeSingleIndexAdaptor
Definition: nanoflann.hpp:1116
nanoflann::pi_const
T pi_const()
Definition: nanoflann.hpp:79
nanoflann::KDTreeSingleIndexDynamicAdaptor_::radiusSearch
size_t radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< std::pair< IndexType, DistanceType >> &IndicesDists, const SearchParams &searchParams) const
Definition: nanoflann.hpp:1638
nanoflann::metric_SO3::traits
Definition: nanoflann.hpp:535
nanoflann::RadiusResultSet::size
size_t size() const
Definition: nanoflann.hpp:240
nanoflann::KDTreeBaseClass::root_node
NodePtr root_node
Definition: nanoflann.hpp:780
nanoflann::KDTreeSingleIndexDynamicAdaptor::m_leaf_max_size
size_t m_leaf_max_size
Definition: nanoflann.hpp:1793
nanoflann::KDTreeSingleIndexAdaptorParams::KDTreeSingleIndexAdaptorParams
KDTreeSingleIndexAdaptorParams(size_t _leaf_max_size=10)
Definition: nanoflann.hpp:547
nanoflann::BLOCKSIZE
const size_t BLOCKSIZE
Definition: nanoflann.hpp:599
nanoflann::KDTreeEigenMatrixAdaptor::self_t
KDTreeEigenMatrixAdaptor< MatrixType, DIM, Distance > self_t
Definition: nanoflann.hpp:1954
nanoflann::KDTreeSingleIndexAdaptor::buildIndex
void buildIndex()
Definition: nanoflann.hpp:1190
nanoflann::KDTreeSingleIndexAdaptor::ElementType
BaseClassRef::ElementType ElementType
Definition: nanoflann.hpp:1141
nanoflann::resize
std::enable_if< has_resize< Container >::value, void >::type resize(Container &c, const size_t nElements)
Definition: nanoflann.hpp:104
nanoflann::SO2_Adaptor::evalMetric
DistanceType evalMetric(const T *a, const size_t b_idx, size_t size) const
Definition: nanoflann.hpp:463
nanoflann::array_or_vector_selector::container_t
std::array< T, DIM > container_t
Definition: nanoflann.hpp:716
nanoflann::IndexDist_Sorter
Definition: nanoflann.hpp:208
nanoflann::RadiusResultSet::clear
void clear()
Definition: nanoflann.hpp:238
nanoflann::KDTreeSingleIndexDynamicAdaptor_::BoundingBox
BaseClassRef::BoundingBox BoundingBox
Definition: nanoflann.hpp:1497
nanoflann::KDTreeSingleIndexDynamicAdaptor_::dataset
const DatasetAdaptor & dataset
The source of our data.
Definition: nanoflann.hpp:1474
nanoflann::KDTreeBaseClass::Node::child2
Node * child2
Child nodes (both=NULL mean its a leaf node)
Definition: nanoflann.hpp:766
nanoflann::KDTreeSingleIndexDynamicAdaptor_
Definition: nanoflann.hpp:1466
nanoflann::SearchParams
Definition: nanoflann.hpp:554
nanoflann::SearchParams::sorted
bool sorted
Definition: nanoflann.hpp:563
nanoflann::KDTreeSingleIndexDynamicAdaptor_::DistanceType
BaseClassRef::DistanceType DistanceType
Definition: nanoflann.hpp:1489
nanoflann::KDTreeSingleIndexAdaptor::NodePtr
Node * NodePtr
Definition: nanoflann.hpp:1145
d
d
nanoflann::KDTreeSingleIndexAdaptor::Interval
BaseClassRef::Interval Interval
Definition: nanoflann.hpp:1147
nanoflann::SO3_Adaptor::evalMetric
DistanceType evalMetric(const T *a, const size_t b_idx, size_t size) const
Definition: nanoflann.hpp:498
nanoflann::KDTreeSingleIndexAdaptor::radiusSearch
size_t radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< std::pair< IndexType, DistanceType >> &IndicesDists, const SearchParams &searchParams) const
Definition: nanoflann.hpp:1278
nanoflann::KNNResultSet::full
bool full() const
Definition: nanoflann.hpp:168
nanoflann::SO2_Adaptor::data_source
const DataSource & data_source
Definition: nanoflann.hpp:459
nanoflann::metric_SO2::traits::distance_t
SO2_Adaptor< T, DataSource > distance_t
Definition: nanoflann.hpp:530
nanoflann::L1_Adaptor::L1_Adaptor
L1_Adaptor(const DataSource &_data_source)
Definition: nanoflann.hpp:330
nanoflann::KDTreeBaseClass::Node::sub
struct nanoflann::KDTreeBaseClass::Node::@0::nonleaf sub
nanoflann::KDTreeBaseClass::Node::child1
Node * child1
Definition: nanoflann.hpp:766
nanoflann::KDTreeSingleIndexDynamicAdaptor::getAllIndices
const std::vector< index_container_t > & getAllIndices() const
Definition: nanoflann.hpp:1817
nanoflann::KDTreeBaseClass::root_bbox
BoundingBox root_bbox
Definition: nanoflann.hpp:801
nanoflann::L2_Adaptor::data_source
const DataSource & data_source
Definition: nanoflann.hpp:379
nanoflann::KDTreeBaseClass::ElementType
Distance::ElementType ElementType
Definition: nanoflann.hpp:750
nanoflann::KDTreeSingleIndexAdaptor::distance_vector_t
BaseClassRef::distance_vector_t distance_vector_t
Definition: nanoflann.hpp:1154
nanoflann::KDTreeSingleIndexDynamicAdaptor_::index_params
KDTreeSingleIndexAdaptorParams index_params
Definition: nanoflann.hpp:1476
nanoflann::SO2_Adaptor
Definition: nanoflann.hpp:455
nanoflann::KDTreeSingleIndexAdaptor::distance
Distance distance
Definition: nanoflann.hpp:1133
nanoflann::metric_L2_Simple::traits
Definition: nanoflann.hpp:523
nanoflann::L1_Adaptor::accum_dist
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition: nanoflann.hpp:363
nanoflann::SO3_Adaptor::accum_dist
DistanceType accum_dist(const U a, const V b, const size_t idx) const
Definition: nanoflann.hpp:504
nanoflann::KDTreeBaseClass::dataset_get
ElementType dataset_get(const Derived &obj, size_t idx, int component) const
Helper accessor to the dataset points:
Definition: nanoflann.hpp:821
nanoflann::KDTreeBaseClass::Node::divlow
DistanceType divlow
Definition: nanoflann.hpp:763
nanoflann::PooledAllocator::PooledAllocator
PooledAllocator()
Definition: nanoflann.hpp:626
nanoflann::RadiusResultSet::init
void init()
Definition: nanoflann.hpp:237
nanoflann::KDTreeSingleIndexDynamicAdaptor_::Interval
BaseClassRef::Interval Interval
Definition: nanoflann.hpp:1494
nanoflann::KDTreeSingleIndexDynamicAdaptor_::treeIndex
std::vector< int > & treeIndex
Definition: nanoflann.hpp:1478
nanoflann::KNNResultSet::size
CountType size() const
Definition: nanoflann.hpp:166
nanoflann::KDTreeSingleIndexAdaptor::KDTreeSingleIndexAdaptor
KDTreeSingleIndexAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
Definition: nanoflann.hpp:1170
start
ROSCPP_DECL void start()
nanoflann::KDTreeSingleIndexAdaptor::index_params
const KDTreeSingleIndexAdaptorParams index_params
Definition: nanoflann.hpp:1131
nanoflann::KDTreeSingleIndexDynamicAdaptor_::knnSearch
size_t knnSearch(const ElementType *query_point, const size_t num_closest, IndexType *out_indices, DistanceType *out_distances_sq, const int=10) const
Definition: nanoflann.hpp:1612
nanoflann::KDTreeSingleIndexDynamicAdaptor_::computeBoundingBox
void computeBoundingBox(BoundingBox &bbox)
Definition: nanoflann.hpp:1665
nanoflann::metric_L2_Simple::traits::distance_t
L2_Simple_Adaptor< T, DataSource > distance_t
Definition: nanoflann.hpp:524
nanoflann::KDTreeSingleIndexDynamicAdaptor::First0Bit
int First0Bit(IndexType num)
Definition: nanoflann.hpp:1821
nanoflann::KNNResultSet
Definition: nanoflann.hpp:142
nanoflann::KDTreeSingleIndexDynamicAdaptor::index_container_t
KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM > index_container_t
Definition: nanoflann.hpp:1811
nanoflann::KDTreeEigenMatrixAdaptor::metric_t
Distance::template traits< num_t, self_t >::distance_t metric_t
Definition: nanoflann.hpp:1958
nanoflann::KDTreeBaseClass::Node
Definition: nanoflann.hpp:754
nanoflann::SO3_Adaptor::DistanceType
_DistanceType DistanceType
Definition: nanoflann.hpp:491
nanoflann::KDTreeSingleIndexDynamicAdaptor_::NodePtr
Node * NodePtr
Definition: nanoflann.hpp:1492
nanoflann::KDTreeSingleIndexAdaptor::BoundingBox
BaseClassRef::BoundingBox BoundingBox
Definition: nanoflann.hpp:1150
nanoflann::L1_Adaptor::DistanceType
_DistanceType DistanceType
Definition: nanoflann.hpp:326
nanoflann::KDTreeSingleIndexDynamicAdaptor::dim
int dim
Dimensionality of each data point.
Definition: nanoflann.hpp:1808
nanoflann::L1_Adaptor::data_source
const DataSource & data_source
Definition: nanoflann.hpp:328
nanoflann::KDTreeEigenMatrixAdaptor::~KDTreeEigenMatrixAdaptor
~KDTreeEigenMatrixAdaptor()
Definition: nanoflann.hpp:1988
nanoflann::metric_L1::traits
Definition: nanoflann.hpp:511
nanoflann::KDTreeSingleIndexAdaptor::computeBoundingBox
void computeBoundingBox(BoundingBox &bbox)
Definition: nanoflann.hpp:1316
nanoflann::PooledAllocator::loc
void * loc
Definition: nanoflann.hpp:610
std
nanoflann::KDTreeBaseClass::middleSplit_
void middleSplit_(Derived &obj, IndexType *ind, IndexType count, IndexType &index, int &cutfeat, DistanceType &cutval, const BoundingBox &bbox)
Definition: nanoflann.hpp:909
nanoflann::KDTreeSingleIndexDynamicAdaptor::ElementType
Distance::ElementType ElementType
Definition: nanoflann.hpp:1789
nanoflann::KDTreeSingleIndexDynamicAdaptor::distance
Distance distance
Definition: nanoflann.hpp:1840
nanoflann::KDTreeSingleIndexDynamicAdaptor::DistanceType
Distance::DistanceType DistanceType
Definition: nanoflann.hpp:1790
nanoflann::SO3_Adaptor
Definition: nanoflann.hpp:489
nanoflann::KDTreeBaseClass::usedMemory
size_t usedMemory(Derived &obj)
Definition: nanoflann.hpp:830
nanoflann::KDTreeSingleIndexDynamicAdaptor::pointCount
size_t pointCount
Definition: nanoflann.hpp:1795
nanoflann::PooledAllocator
Definition: nanoflann.hpp:601
nanoflann::KDTreeEigenMatrixAdaptor::query
void query(const num_t *query_point, const size_t num_closest, IndexType *out_indices, num_t *out_distances_sq, const int=10) const
Definition: nanoflann.hpp:1998
nanoflann::KDTreeBaseClass::DistanceType
Distance::DistanceType DistanceType
Definition: nanoflann.hpp:751
nanoflann::RadiusResultSet::RadiusResultSet
RadiusResultSet(DistanceType radius_, std::vector< std::pair< IndexType, DistanceType >> &indices_dists)
Definition: nanoflann.hpp:230
nanoflann::KDTreeEigenMatrixAdaptor::index_t
KDTreeSingleIndexAdaptor< metric_t, self_t, MatrixType::ColsAtCompileTime, IndexType > index_t
Definition: nanoflann.hpp:1961
nanoflann::KDTreeEigenMatrixAdaptor::kdtree_get_pt
num_t kdtree_get_pt(const IndexType idx, size_t dim) const
Definition: nanoflann.hpp:2018
nanoflann::SO2_Adaptor::DistanceType
_DistanceType DistanceType
Definition: nanoflann.hpp:457
nanoflann::KDTreeBaseClass::m_size_at_index_build
size_t m_size_at_index_build
Definition: nanoflann.hpp:785
nanoflann::KNNResultSet::IndexType
_IndexType IndexType
Definition: nanoflann.hpp:145
nanoflann::KDTreeEigenMatrixAdaptor::KDTreeEigenMatrixAdaptor
KDTreeEigenMatrixAdaptor(const size_t dimensionality, const std::reference_wrapper< const MatrixType > &mat, const int leaf_max_size=10)
Constructor: takes a const ref to the matrix object with the data points.
Definition: nanoflann.hpp:1967
nanoflann::has_assign
Definition: nanoflann.hpp:93
nanoflann::KNNResultSet::dists
DistanceType * dists
Definition: nanoflann.hpp:150
nanoflann::KNNResultSet::capacity
CountType capacity
Definition: nanoflann.hpp:151
nanoflann::KDTreeSingleIndexAdaptor::Node
BaseClassRef::Node Node
Definition: nanoflann.hpp:1144
nanoflann::KDTreeBaseClass::Node::divfeat
int divfeat
Dimension used for subdivision.
Definition: nanoflann.hpp:762
nanoflann::SO3_Adaptor::SO3_Adaptor
SO3_Adaptor(const DataSource &_data_source)
Definition: nanoflann.hpp:495
nanoflann::array_or_vector_selector
Definition: nanoflann.hpp:715
nanoflann::metric_SO3
Definition: nanoflann.hpp:534
nanoflann::IndexDist_Sorter::operator()
bool operator()(const PairType &p1, const PairType &p2) const
Definition: nanoflann.hpp:211
nanoflann::KDTreeSingleIndexDynamicAdaptor::treeCount
size_t treeCount
Definition: nanoflann.hpp:1794
nanoflann::metric_L2::traits
Definition: nanoflann.hpp:517
nanoflann::RadiusResultSet::radius
const DistanceType radius
Definition: nanoflann.hpp:226
nanoflann::KDTreeBaseClass::computeInitialDistances
DistanceType computeInitialDistances(const Derived &obj, const ElementType *vec, distance_vector_t &dists) const
Definition: nanoflann.hpp:1005
nanoflann::KDTreeSingleIndexDynamicAdaptor_::saveIndex
void saveIndex(FILE *stream)
Definition: nanoflann.hpp:1761
nanoflann::KDTreeEigenMatrixAdaptor::kdtree_get_bbox
bool kdtree_get_bbox(BBOX &) const
Definition: nanoflann.hpp:2027
nanoflann::KDTreeSingleIndexDynamicAdaptor_::searchLevel
void searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, distance_vector_t &dists, const float epsError) const
Definition: nanoflann.hpp:1695
nanoflann::KDTreeSingleIndexDynamicAdaptor
Definition: nanoflann.hpp:1787
nanoflann::KDTreeBaseClass::Node::lr
struct nanoflann::KDTreeBaseClass::Node::@0::leaf lr
nanoflann::save_value
void save_value(FILE *stream, const T &value, size_t count=1)
Definition: nanoflann.hpp:279
nanoflann::KDTreeEigenMatrixAdaptor::derived
self_t & derived()
Definition: nanoflann.hpp:2010
nanoflann::KDTreeBaseClass::load_tree
void load_tree(Derived &obj, FILE *stream, NodePtr &tree)
Definition: nanoflann.hpp:1034
nanoflann::KDTreeEigenMatrixAdaptor::IndexType
MatrixType::Index IndexType
Definition: nanoflann.hpp:1956
nanoflann::KNNResultSet::CountType
_CountType CountType
Definition: nanoflann.hpp:146
nanoflann::KDTreeBaseClass::divideTree
NodePtr divideTree(Derived &obj, const IndexType left, const IndexType right, BoundingBox &bbox)
Definition: nanoflann.hpp:857
nanoflann::L2_Simple_Adaptor::ElementType
T ElementType
Definition: nanoflann.hpp:424
nanoflann::KDTreeBaseClass::NodePtr
Node * NodePtr
Definition: nanoflann.hpp:769
nanoflann::WORDSIZE
const size_t WORDSIZE
Definition: nanoflann.hpp:598
nanoflann::L2_Simple_Adaptor::evalMetric
DistanceType evalMetric(const T *a, const size_t b_idx, size_t size) const
Definition: nanoflann.hpp:432
nanoflann::KNNResultSet::init
void init(IndexType *indices_, DistanceType *dists_)
Definition: nanoflann.hpp:158
nanoflann::KDTreeBaseClass::distance_vector_t
array_or_vector_selector< DIM, DistanceType >::container_t distance_vector_t
Definition: nanoflann.hpp:797
nanoflann::KDTreeBaseClass::loadIndex_
void loadIndex_(Derived &obj, FILE *stream)
Definition: nanoflann.hpp:1064
nanoflann::KDTreeSingleIndexDynamicAdaptor_::distance_vector_t
BaseClassRef::distance_vector_t distance_vector_t
Definition: nanoflann.hpp:1501
nanoflann::SO2_Adaptor::ElementType
T ElementType
Definition: nanoflann.hpp:456
nanoflann::KDTreeBaseClass::Interval::low
ElementType low
Definition: nanoflann.hpp:772
nanoflann::KDTreeBaseClass::planeSplit
void planeSplit(Derived &obj, IndexType *ind, const IndexType count, int cutfeat, DistanceType &cutval, IndexType &lim1, IndexType &lim2)
Definition: nanoflann.hpp:967
nanoflann::PooledAllocator::base
void * base
Definition: nanoflann.hpp:609


slam_toolbox
Author(s): Steve Macenski
autogenerated on Thu Jan 11 2024 03:37:55