OpenLB 1.7
Loading...
Searching...
No Matches
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-2014 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
33#ifndef NANOFLANN_HPP_
34#define NANOFLANN_HPP_
35
36#include <vector>
37#include <cassert>
38#include <algorithm>
39#include <stdexcept>
40#include <cstdio> // for fwrite()
41#include <cmath> // for fabs(),...
42#include <limits>
43
44// Avoid conflicting declaration of min/max macros in windows headers
45#if !defined(NOMINMAX) && (defined(_WIN32) || defined(_WIN32_) || defined(WIN32) || defined(_WIN64))
46# define NOMINMAX
47# ifdef max
48# undef max
49# undef min
50# endif
51#endif
52
53namespace nanoflann {
58#define NANOFLANN_VERSION 0x119
59
62template<typename DistanceType, typename IndexType = size_t,
63 typename CountType = size_t>
65 IndexType * indices;
66 DistanceType* dists;
67 CountType capacity;
68 CountType count;
69
70 public:
71 inline KNNResultSet(CountType capacity_)
72 : indices(0),
73 dists(0),
74 capacity(capacity_),
75 count(0) {
76 }
77
78 inline void init(IndexType* indices_, DistanceType* dists_) {
79 indices = indices_;
80 dists = dists_;
81 count = 0;
82 dists[capacity - 1] = (std::numeric_limits<DistanceType>::max)();
83 }
84
85 inline CountType size() const {
86 return count;
87 }
88
89 inline bool full() const {
90 return count == capacity;
91 }
92
93 inline void addPoint(DistanceType dist, IndexType index) {
94 CountType i;
95 for (i = count; i > 0; --i) {
96#ifdef NANOFLANN_FIRST_MATCH // If defined and two poins have the same distance, the one with the lowest-index will be returned first.
97 if ( (dists[i-1]>dist) || ((dist==dists[i-1])&&(indices[i-1]>index)) ) {
98#else
99 if (dists[i - 1] > dist) {
100#endif
101 if (i < capacity) {
102 dists[i] = dists[i - 1];
103 indices[i] = indices[i - 1];
104 }
105 } else
106 break;
107 }
108 if (i < capacity) {
109 dists[i] = dist;
110 indices[i] = index;
111 }
112 if (count < capacity)
113 count++;
114 }
115
116 inline DistanceType worstDist() const {
117 return dists[capacity - 1];
118 }
119};
120
124template<typename DistanceType, typename IndexType = size_t>
126 public:
127 const DistanceType radius;
128
129 std::vector<std::pair<IndexType, DistanceType> >& m_indices_dists;
130
132 DistanceType radius_,
133 std::vector<std::pair<IndexType, DistanceType> >& indices_dists)
134 : radius(radius_),
135 m_indices_dists(indices_dists) {
136 init();
137 }
138
140 }
141
142 inline void init() {
143 clear();
144 }
145 inline void clear() {
146 m_indices_dists.clear();
147 }
148
149 inline size_t size() const {
150 return m_indices_dists.size();
151 }
152
153 inline bool full() const {
154 return true;
155 }
156
157 inline void addPoint(DistanceType dist, IndexType index) {
158 if (dist < radius)
159 m_indices_dists.push_back(std::make_pair(index, dist));
160 }
161
162 inline DistanceType worstDist() const {
163 return radius;
164 }
165
167 inline void set_radius_and_clear(const DistanceType r) {
168 radius = r;
169 clear();
170 }
171
176 std::pair<IndexType, DistanceType> worst_item() const {
177 if (m_indices_dists.empty())
178 throw std::runtime_error(
179 "Cannot invoke RadiusResultSet::worst_item() on an empty list of results.");
180 typedef typename std::vector<std::pair<IndexType, DistanceType> >::const_iterator DistIt;
181 DistIt it = std::max_element(m_indices_dists.begin(),
182 m_indices_dists.end());
183 return *it;
184 }
185};
186
187template<typename DistanceType, typename IndexType = size_t>
189 public:
190 const DistanceType radius;
191
192// std::vector<std::pair<IndexType,DistanceType> >& m_indices_dists;
193 std::list<IndexType>& m_indices_list;
194
195 inline RadiusResultList(DistanceType radius_,
196 std::list<IndexType>& indices_list)
197 : radius(radius_),
198 m_indices_list(indices_list) {
199 init();
200 }
201
203 }
204
205 inline void init() {
206 clear();
207 }
208 inline void clear() {
209 m_indices_list.clear();
210 }
211
212 inline size_t size() const {
213 return m_indices_list.size();
214 }
215
216 inline bool full() const {
217 return true;
218 }
219
220 inline void addPoint(DistanceType dist, IndexType index) {
221 if (dist < radius)
222 m_indices_list.push_back(index);
223 }
224
225 inline DistanceType worstDist() const {
226 return radius;
227 }
228
230 inline void set_radius_and_clear(const DistanceType r) {
231 radius = r;
232 clear();
233 }
234
239 std::pair<IndexType, DistanceType> worst_item() const {
240 if (m_indices_list.empty())
241 throw std::runtime_error(
242 "Cannot invoke RadiusResultSet::worst_item() on an empty list of results.");
243 typedef typename std::vector<std::pair<IndexType, DistanceType> >::const_iterator DistIt;
244 DistIt it = std::max_element(m_indices_list.begin(), m_indices_list.end());
245 return *it;
246 }
247};
248
252 template<typename PairType>
253 inline bool operator()(const PairType &p1, const PairType &p2) const {
254 return p1.second < p2.second;
255 }
256};
257
262template<typename T>
263void save_value(FILE* stream, const T& value, size_t count = 1) {
264 fwrite(&value, sizeof(value), count, stream);
265}
266
267template<typename T>
268void save_value(FILE* stream, const std::vector<T>& value) {
269 size_t size = value.size();
270 fwrite(&size, sizeof(size_t), 1, stream);
271 fwrite(&value[0], sizeof(T), size, stream);
272}
273
274template<typename T>
275void load_value(FILE* stream, T& value, size_t count = 1) {
276 size_t read_cnt = fread(&value, sizeof(value), count, stream);
277 if (read_cnt != count) {
278 throw std::runtime_error("Cannot read from file");
279 }
280}
281
282template<typename T>
283void load_value(FILE* stream, std::vector<T>& value) {
284 size_t size;
285 size_t read_cnt = fread(&size, sizeof(size_t), 1, stream);
286 if (read_cnt != 1) {
287 throw std::runtime_error("Cannot read from file");
288 }
289 value.resize(size);
290 read_cnt = fread(&value[0], sizeof(T), size, stream);
291 if (read_cnt != size) {
292 throw std::runtime_error("Cannot read from file");
293 }
294}
300template<typename T> inline T abs(T x) {
301 return (x < 0) ? -x : x;
302}
303template<> inline int abs<int>(int x) {
304 return ::abs(x);
305}
306template<> inline float abs<float>(float x) {
307 return olb::util::fabsf(x);
308}
309template<> inline double abs<double>(double x) {
310 return olb::util::fabs(x);
311}
312template<> inline long double abs<long double>(long double x) {
313 return olb::util::fabsl(x);
314}
315
321template<class T, class DataSource, typename _DistanceType = T>
323 typedef T ElementType;
324 typedef _DistanceType DistanceType;
325
326 const DataSource &data_source;
327
328 L1_Adaptor(const DataSource &_data_source)
329 : data_source(_data_source) {
330 }
331
332 inline DistanceType operator()(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 = nanoflann::abs(
342 a[0] - data_source.kdtree_get_pt(b_idx, d++));
343 const DistanceType diff1 = nanoflann::abs(
344 a[1] - data_source.kdtree_get_pt(b_idx, d++));
345 const DistanceType diff2 = nanoflann::abs(
346 a[2] - data_source.kdtree_get_pt(b_idx, d++));
347 const DistanceType diff3 = nanoflann::abs(
348 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 += nanoflann::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, int) const {
364 return nanoflann::abs(a - b);
365 }
366};
367
373template<class T, class DataSource, typename _DistanceType = T>
375 typedef T ElementType;
376 typedef _DistanceType DistanceType;
377
378 const DataSource &data_source;
379
380 L2_Adaptor(const DataSource &_data_source)
381 : data_source(_data_source) {
382 }
383
384 inline DistanceType operator()(const T* a, const size_t b_idx, size_t size,
385 DistanceType worst_dist = -1) const {
386 DistanceType result = DistanceType();
387 const T* last = a + size;
388 const T* lastgroup = last - 3;
389 size_t d = 0;
390
391 /* Process 4 items with each loop for efficiency. */
392 while (a < lastgroup) {
393 const DistanceType diff0 = a[0] - data_source.kdtree_get_pt(b_idx, d++);
394 const DistanceType diff1 = a[1] - data_source.kdtree_get_pt(b_idx, d++);
395 const DistanceType diff2 = a[2] - data_source.kdtree_get_pt(b_idx, d++);
396 const DistanceType diff3 = a[3] - data_source.kdtree_get_pt(b_idx, d++);
397 result += diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
398 a += 4;
399 if ((worst_dist > 0) && (result > worst_dist)) {
400 return result;
401 }
402 }
403 /* Process last 0-3 components. Not needed for standard vector lengths. */
404 while (a < last) {
405 const DistanceType diff0 = *a++ - data_source.kdtree_get_pt(b_idx, d++);
406 result += diff0 * diff0;
407 }
408 return result;
409 }
410
411 template<typename U, typename V>
412 inline DistanceType accum_dist(const U a, const V b, int) const {
413 return (a - b) * (a - b);
414 }
415};
416
422template<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
433 inline DistanceType operator()(const T* a, const size_t b_idx,
434 size_t size) const {
435 return data_source.kdtree_distance(a, b_idx, size);
436 }
437
438 template<typename U, typename V>
439 inline DistanceType accum_dist(const U a, const V b, int) const {
440 return (a - b) * (a - b);
441 }
442};
443
445struct metric_L1 {
446 template<class T, class DataSource>
450};
452struct metric_L2 {
453 template<class T, class DataSource>
457};
460 template<class T, class DataSource>
464};
465
474 KDTreeSingleIndexAdaptorParams(size_t _leaf_max_size = 10, int dim_ = -1)
475 : leaf_max_size(_leaf_max_size),
476 dim(dim_) {
477 }
478
480 int dim;
481};
482
486 SearchParams(int checks_IGNORED_ = 32, float eps_ = 0, bool sorted_ = true)
487 : checks(checks_IGNORED_),
488 eps(eps_),
489 sorted(sorted_) {
490 }
491
492 int checks;
493 float eps;
494 bool sorted;
495};
508template<typename T>
509inline T* allocate(size_t count = 1) {
510 T* mem = (T*) ::malloc(sizeof(T) * count);
511 return mem;
512}
513
529const size_t WORDSIZE = 16;
530const size_t BLOCKSIZE = 8192;
531
533 /* We maintain memory alignment to word boundaries by requiring that all
534 allocations be in multiples of the machine wordsize. */
535 /* Size of machine word in bytes. Must be power of 2. */
536 /* Minimum number of bytes requested at a time from the system. Must be multiple of WORDSIZE. */
537
538 size_t remaining; /* Number of bytes left in current block of storage. */
539 void* base; /* Pointer to base of current block of storage. */
540 void* loc; /* Current location in block to next allocate memory. */
541 size_t blocksize;
542
543 void internal_init() {
544 remaining = 0;
545 base = NULL;
546 usedMemory = 0;
547 wastedMemory = 0;
548 }
549
550 public:
553
557 PooledAllocator(const size_t blocksize_ = BLOCKSIZE)
558 : blocksize(blocksize_) {
559 internal_init();
560 }
561
566 free_all();
567 }
568
570 void free_all() {
571 while (base != NULL) {
572 void *prev = *((void**) base); /* Get pointer to prev block. */
573 ::free(base);
574 base = prev;
575 }
576 internal_init();
577 }
578
583 void* malloc(const size_t req_size) {
584 /* Round size up to a multiple of wordsize. The following expression
585 only works for WORDSIZE that is a power of 2, by masking last bits of
586 incremented size to zero.
587 */
588 const size_t size = (req_size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
589
590 /* Check whether a new block must be allocated. Note that the first word
591 of a block is reserved for a pointer to the previous block.
592 */
593 if (size > remaining) {
594
595 wastedMemory += remaining;
596
597 /* Allocate new storage. */
598 const size_t blocksize =
599 (size + sizeof(void*) + (WORDSIZE - 1) > BLOCKSIZE) ?
600 size + sizeof(void*) + (WORDSIZE - 1) : BLOCKSIZE;
601
602 // use the standard C malloc to allocate memory
603 void* m = ::malloc(blocksize);
604 if (!m) {
605 fprintf(stderr, "Failed to allocate memory.\n");
606 return NULL;
607 }
608
609 /* Fill first word of new block with pointer to previous block. */
610 ((void**) m)[0] = base;
611 base = m;
612
613 size_t shift = 0;
614 //int size_t = (WORDSIZE - ( (((size_t)m) + sizeof(void*)) & (WORDSIZE-1))) & (WORDSIZE-1);
615
616 remaining = blocksize - sizeof(void*) - shift;
617 loc = ((char*) m + sizeof(void*) + shift);
618 }
619 void* rloc = loc;
620 loc = (char*) loc + size;
621 remaining -= size;
622
623 usedMemory += size;
624
625 return rloc;
626 }
627
635 template<typename T>
636 T* allocate(const size_t count = 1) {
637 T* mem = (T*) this->malloc(sizeof(T) * count);
638 return mem;
639 }
640
641};
647// ---------------- CArray -------------------------
673template<typename T, std::size_t N>
674class CArray {
675 public:
676 T elems[N]; // fixed-size array of elements of type T
677
678 public:
679 // type definitions
680 typedef T value_type;
681 typedef T* iterator;
682 typedef const T* const_iterator;
683 typedef T& reference;
684 typedef const T& const_reference;
685 typedef std::size_t size_type;
686 typedef std::ptrdiff_t difference_type;
687
688 // iterator support
689 inline iterator begin() {
690 return elems;
691 }
692 inline const_iterator begin() const {
693 return elems;
694 }
695 inline iterator end() {
696 return elems + N;
697 }
698 inline const_iterator end() const {
699 return elems + N;
700 }
701
702 // reverse iterator support
703#if !defined(BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION) && !defined(BOOST_MSVC_STD_ITERATOR) && !defined(BOOST_NO_STD_ITERATOR_TRAITS)
704 typedef std::reverse_iterator<iterator> reverse_iterator;
705 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
706#elif defined(_MSC_VER) && (_MSC_VER == 1300) && defined(BOOST_DINKUMWARE_STDLIB) && (BOOST_DINKUMWARE_STDLIB == 310)
707 // workaround for broken reverse_iterator in VC7
708 typedef std::reverse_iterator<std::_Ptrit<value_type, difference_type, iterator,
710 typedef std::reverse_iterator<std::_Ptrit<value_type, difference_type, const_iterator,
712#else
713 // workaround for broken reverse_iterator implementations
714 typedef std::reverse_iterator<iterator,T> reverse_iterator;
715 typedef std::reverse_iterator<const_iterator,T> const_reverse_iterator;
716#endif
717
719 return reverse_iterator(end());
720 }
722 return const_reverse_iterator(end());
723 }
725 return reverse_iterator(begin());
726 }
728 return const_reverse_iterator(begin());
729 }
730 // operator[]
732 return elems[i];
733 }
735 return elems[i];
736 }
737 // at() with range check
739 rangecheck(i);
740 return elems[i];
741 }
743 rangecheck(i);
744 return elems[i];
745 }
746 // front() and back()
748 return elems[0];
749 }
751 return elems[0];
752 }
754 return elems[N - 1];
755 }
757 return elems[N - 1];
758 }
759 // size is constant
760 static inline size_type size() {
761 return N;
762 }
763 static bool empty() {
764 return false;
765 }
767 return N;
768 }
769 enum {
770 static_size = N
771 };
773 inline void resize(const size_t nElements) {
774 if (nElements != N)
775 throw std::logic_error("Try to change the size of a CArray.");
776 }
777 // swap (note: linear complexity in N, constant for given instantiation)
779 std::swap_ranges(begin(), end(), y.begin());
780 }
781 // direct access to data (read-only)
782 const T* data() const {
783 return elems;
784 }
785 // use array as C array (direct read/write access to data)
786 T* data() {
787 return elems;
788 }
789 // assignment with type conversion
790 template<typename T2> CArray<T, N>& operator=(const CArray<T2, N>& rhs) {
791 std::copy(rhs.begin(), rhs.end(), begin());
792 return *this;
793 }
794 // assign one value to all elements
795 inline void assign(const T& value) {
796 for (size_t i = 0; i < N; i++)
797 elems[i] = value;
798 }
799 // assign (compatible with std::vector's one) (by JLBC for MRPT)
800 void assign(const size_t n, const T& value) {
801 assert(N == n);
802 for (size_t i = 0; i < N; i++)
803 elems[i] = value;
804 }
805 private:
806 // check range (may be private because it is static)
807 static void rangecheck(size_type i) {
808 if (i >= size()) {
809 throw std::out_of_range("CArray<>: index out of range");
810 }
811 }
812};
813// end of CArray
814
818template<int DIM, typename T>
823template<typename T>
825 typedef std::vector<T> container_t;
826};
867template<typename Distance, class DatasetAdaptor, int DIM = -1,
868 typename IndexType = size_t>
870 private:
874 public:
875 typedef typename Distance::ElementType ElementType;
876 typedef typename Distance::DistanceType DistanceType;
877 protected:
878
882 std::vector<IndexType> vind;
883
885
889 const DatasetAdaptor &dataset;
890
892
893 size_t m_size;
894 int dim;
895
896 /*--------------------- Internal Data Structures --------------------------*/
897 struct Node {
898 union {
899 struct {
903 IndexType left, right;
904 } lr;
905 struct {
914 } sub;
915 };
919 Node* child1, *child2;
920 };
921 typedef Node* NodePtr;
922
923 struct Interval {
925 };
926
929
932
937 template<typename T, typename DistanceType>
939 T node; /* Tree node at which search resumes */
940 DistanceType mindist; /* Minimum distance to query for all nodes below. */
941
943 }
944 BranchStruct(const T& aNode, DistanceType dist)
945 : node(aNode),
946 mindist(dist) {
947 }
948
949 inline bool operator<(const BranchStruct<T, DistanceType>& rhs) const {
950 return mindist < rhs.mindist;
951 }
952 };
953
959 typedef BranchSt* Branch;
960
962
971
972 public:
973
974 Distance distance;
975
983 KDTreeSingleIndexAdaptor(const int dimensionality,
984 const DatasetAdaptor& inputData,
985 const KDTreeSingleIndexAdaptorParams& params =
987 : m_leaf_max_size(0),
988 dataset(inputData),
989 index_params(params),
990 m_size(0),
991 dim(dimensionality),
992 root_node(NULL),
993 distance(inputData) {
994 m_size = 0;
995 if (DIM > 0)
996 dim = DIM;
997 else {
998 if (params.dim > 0)
999 dim = params.dim;
1000 }
1001 m_leaf_max_size = params.leaf_max_size;
1002 }
1003
1004 void init() {
1005 m_size = dataset.kdtree_get_point_count();
1006
1007 // Create a permutable array of indices to the input vectors.
1008 init_vind();
1009 }
1010
1016
1018 void freeIndex() {
1019 pool.free_all();
1020 root_node = NULL;
1021 }
1022
1026 void buildIndex() {
1027 init_vind();
1028 freeIndex();
1029 if (m_size == 0)
1030 return;
1031 computeBoundingBox(root_bbox);
1032 root_node = divideTree(0, m_size, root_bbox); // construct the tree
1033 }
1034
1038 size_t size() const {
1039 return m_size;
1040 }
1041
1045 size_t veclen() const {
1046 return static_cast<size_t>(DIM > 0 ? DIM : dim);
1047 }
1048
1053 size_t usedMemory() const {
1054 return pool.usedMemory + pool.wastedMemory
1055 + dataset.kdtree_get_point_count() * sizeof(IndexType); // pool memory and vind array memory
1056 }
1057
1072 template<typename RESULTSET>
1073 void findNeighbors(RESULTSET& result, const ElementType* vec,
1074 const SearchParams& searchParams) const {
1075 assert(vec);
1076 if (!root_node)
1077 throw std::runtime_error(
1078 "[nanoflann] findNeighbors() called before building the index or no data points.");
1079 float epsError = 1 + searchParams.eps;
1080
1081 distance_vector_t dists; // fixed or variable-sized container (depending on DIM)
1082 dists.assign((DIM > 0 ? DIM : dim), 0); // Fill it with zeros.
1083 DistanceType distsq = computeInitialDistances(vec, dists);
1084 searchLevel(result, vec, root_node, distsq, dists, epsError); // "count_leaf" parameter removed since was neither used nor returned to the user.
1085 }
1086
1093 inline void knnSearch(const ElementType *query_point,
1094 const size_t num_closest, IndexType *out_indices,
1095 DistanceType *out_distances_sq,
1096 const int /* nChecks_IGNORED */= 10) const {
1098 resultSet.init(out_indices, out_distances_sq);
1099 this->findNeighbors(resultSet, query_point, nanoflann::SearchParams());
1100 }
1101
1115 const ElementType *query_point, const DistanceType radius,
1116 std::vector<std::pair<IndexType, DistanceType> >& IndicesDists,
1117 const SearchParams& searchParams) const {
1118 RadiusResultSet<DistanceType, IndexType> resultSet(radius, IndicesDists);
1119 this->findNeighbors(resultSet, query_point, searchParams);
1120
1121 if (searchParams.sorted)
1122 std::sort(IndicesDists.begin(), IndicesDists.end(), IndexDist_Sorter());
1123
1124 return resultSet.size();
1125 }
1126
1127 size_t radiusSearch(const ElementType *query_point, const DistanceType radius,
1128 std::list<IndexType>& IndicesDists,
1129 const SearchParams& searchParams) const {
1130 RadiusResultList<DistanceType, IndexType> resultList(radius, IndicesDists);
1131 this->findNeighbors(resultList, query_point, searchParams);
1132
1133 if (searchParams.sorted)
1134 IndicesDists.sort();
1135
1136 return resultList.size();
1137 }
1138
1141 private:
1143 void init_vind() {
1144 // Create a permutable array of indices to the input vectors.
1145 m_size = dataset.kdtree_get_point_count();
1146 if (vind.size() != m_size)
1147 vind.resize(m_size);
1148 for (size_t i = 0; i < m_size; i++)
1149 vind[i] = i;
1150 }
1151
1153 inline ElementType dataset_get(size_t idx, int component) const {
1154 return dataset.kdtree_get_pt(idx, component);
1155 }
1156
1157 void save_tree(FILE* stream, NodePtr tree) {
1158 save_value(stream, *tree);
1159 if (tree->child1 != NULL) {
1160 save_tree(stream, tree->child1);
1161 }
1162 if (tree->child2 != NULL) {
1163 save_tree(stream, tree->child2);
1164 }
1165 }
1166
1167 void load_tree(FILE* stream, NodePtr& tree) {
1168 tree = pool.allocate<Node>();
1169 load_value(stream, *tree);
1170 if (tree->child1 != NULL) {
1171 load_tree(stream, tree->child1);
1172 }
1173 if (tree->child2 != NULL) {
1174 load_tree(stream, tree->child2);
1175 }
1176 }
1177
1178 void computeBoundingBox(BoundingBox& bbox) {
1179 bbox.resize((DIM > 0 ? DIM : dim));
1180 if (dataset.kdtree_get_bbox(bbox)) {
1181 // Done! It was implemented in derived class
1182 } else {
1183 const size_t N = dataset.kdtree_get_point_count();
1184 if (!N)
1185 throw std::runtime_error(
1186 "[nanoflann] computeBoundingBox() called but no data points found.");
1187 for (int i = 0; i < (DIM > 0 ? DIM : dim); ++i) {
1188 bbox[i].low = bbox[i].high = dataset_get(0, i);
1189 }
1190 for (size_t k = 1; k < N; ++k) {
1191 for (int i = 0; i < (DIM > 0 ? DIM : dim); ++i) {
1192 if (dataset_get(k, i) < bbox[i].low)
1193 bbox[i].low = dataset_get(k, i);
1194 if (dataset_get(k, i) > bbox[i].high)
1195 bbox[i].high = dataset_get(k, i);
1196 }
1197 }
1198 }
1199 }
1200
1210 NodePtr divideTree(const IndexType left, const IndexType right,
1211 BoundingBox& bbox) {
1212 NodePtr node = pool.allocate<Node>(); // allocate memory
1213
1214 /* If too few exemplars remain, then make this a leaf node. */
1215 if ((right - left) <= m_leaf_max_size) {
1216 node->child1 = node->child2 = NULL; /* Mark as leaf node. */
1217 node->lr.left = left;
1218 node->lr.right = right;
1219
1220 // compute bounding-box of leaf points
1221 for (int i = 0; i < (DIM > 0 ? DIM : dim); ++i) {
1222 bbox[i].low = dataset_get(vind[left], i);
1223 bbox[i].high = dataset_get(vind[left], i);
1224 }
1225 for (IndexType k = left + 1; k < right; ++k) {
1226 for (int i = 0; i < (DIM > 0 ? DIM : dim); ++i) {
1227 if (bbox[i].low > dataset_get(vind[k], i))
1228 bbox[i].low = dataset_get(vind[k], i);
1229 if (bbox[i].high < dataset_get(vind[k], i))
1230 bbox[i].high = dataset_get(vind[k], i);
1231 }
1232 }
1233 } else {
1234 IndexType idx;
1235 int cutfeat;
1236 DistanceType cutval;
1237 middleSplit_(&vind[0] + left, right - left, idx, cutfeat, cutval, bbox);
1238
1239 node->sub.divfeat = cutfeat;
1240
1241 BoundingBox left_bbox(bbox);
1242 left_bbox[cutfeat].high = cutval;
1243 node->child1 = divideTree(left, left + idx, left_bbox);
1244
1245 BoundingBox right_bbox(bbox);
1246 right_bbox[cutfeat].low = cutval;
1247 node->child2 = divideTree(left + idx, right, right_bbox);
1248
1249 node->sub.divlow = left_bbox[cutfeat].high;
1250 node->sub.divhigh = right_bbox[cutfeat].low;
1251
1252 for (int i = 0; i < (DIM > 0 ? DIM : dim); ++i) {
1253 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1254 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1255 }
1256 }
1257
1258 return node;
1259 }
1260
1261 void computeMinMax(IndexType* ind, IndexType count, int element,
1262 ElementType& min_elem, ElementType& max_elem) {
1263 min_elem = dataset_get(ind[0], element);
1264 max_elem = dataset_get(ind[0], element);
1265 for (IndexType i = 1; i < count; ++i) {
1266 ElementType val = dataset_get(ind[i], element);
1267 if (val < min_elem)
1268 min_elem = val;
1269 if (val > max_elem)
1270 max_elem = val;
1271 }
1272 }
1273
1274 void middleSplit(IndexType* ind, IndexType count, IndexType& index,
1275 int& cutfeat, DistanceType& cutval,
1276 const BoundingBox& bbox) {
1277 // find the largest span from the approximate bounding box
1278 ElementType max_span = bbox[0].high - bbox[0].low;
1279 cutfeat = 0;
1280 cutval = (bbox[0].high + bbox[0].low) / 2;
1281 for (int i = 1; i < (DIM > 0 ? DIM : dim); ++i) {
1282 ElementType span = bbox[i].low - bbox[i].low;
1283 if (span > max_span) {
1284 max_span = span;
1285 cutfeat = i;
1286 cutval = (bbox[i].high + bbox[i].low) / 2;
1287 }
1288 }
1289
1290 // compute exact span on the found dimension
1291 ElementType min_elem, max_elem;
1292 computeMinMax(ind, count, cutfeat, min_elem, max_elem);
1293 cutval = (min_elem + max_elem) / 2;
1294 max_span = max_elem - min_elem;
1295
1296 // check if a dimension of a largest span exists
1297 size_t k = cutfeat;
1298 for (size_t i = 0; i < (DIM > 0 ? DIM : dim); ++i) {
1299 if (i == k)
1300 continue;
1301 ElementType span = bbox[i].high - bbox[i].low;
1302 if (span > max_span) {
1303 computeMinMax(ind, count, i, min_elem, max_elem);
1304 span = max_elem - min_elem;
1305 if (span > max_span) {
1306 max_span = span;
1307 cutfeat = i;
1308 cutval = (min_elem + max_elem) / 2;
1309 }
1310 }
1311 }
1312 IndexType lim1, lim2;
1313 planeSplit(ind, count, cutfeat, cutval, lim1, lim2);
1314
1315 if (lim1 > count / 2)
1316 index = lim1;
1317 else if (lim2 < count / 2)
1318 index = lim2;
1319 else
1320 index = count / 2;
1321 }
1322
1323 void middleSplit_(IndexType* ind, IndexType count, IndexType& index,
1324 int& cutfeat, DistanceType& cutval,
1325 const BoundingBox& bbox) {
1326 const DistanceType EPS = static_cast<DistanceType>(0.00001);
1327 ElementType max_span = bbox[0].high - bbox[0].low;
1328 for (int i = 1; i < (DIM > 0 ? DIM : dim); ++i) {
1329 ElementType span = bbox[i].high - bbox[i].low;
1330 if (span > max_span) {
1331 max_span = span;
1332 }
1333 }
1334 ElementType max_spread = -1;
1335 cutfeat = 0;
1336 for (int i = 0; i < (DIM > 0 ? DIM : dim); ++i) {
1337 ElementType span = bbox[i].high - bbox[i].low;
1338 if (span > (1 - EPS) * max_span) {
1339 ElementType min_elem, max_elem;
1340 computeMinMax(ind, count, cutfeat, min_elem, max_elem);
1341 ElementType spread = max_elem - min_elem;
1342 ;
1343 if (spread > max_spread) {
1344 cutfeat = i;
1345 max_spread = spread;
1346 }
1347 }
1348 }
1349 // split in the middle
1350 DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;
1351 ElementType min_elem, max_elem;
1352 computeMinMax(ind, count, cutfeat, min_elem, max_elem);
1353
1354 if (split_val < min_elem)
1355 cutval = min_elem;
1356 else if (split_val > max_elem)
1357 cutval = max_elem;
1358 else
1359 cutval = split_val;
1360
1361 IndexType lim1, lim2;
1362 planeSplit(ind, count, cutfeat, cutval, lim1, lim2);
1363
1364 if (lim1 > count / 2)
1365 index = lim1;
1366 else if (lim2 < count / 2)
1367 index = lim2;
1368 else
1369 index = count / 2;
1370 }
1371
1381 void planeSplit(IndexType* ind, const IndexType count, int cutfeat,
1382 DistanceType cutval, IndexType& lim1, IndexType& lim2) {
1383 /* Move vector indices for left subtree to front of list. */
1384 IndexType left = 0;
1385 IndexType right = count - 1;
1386 for (;;) {
1387 while (left <= right && dataset_get(ind[left], cutfeat) < cutval)
1388 ++left;
1389 while (right && left <= right
1390 && dataset_get(ind[right], cutfeat) >= cutval)
1391 --right;
1392 if (left > right || !right)
1393 break; // "!right" was added to support unsigned Index types
1394 std::swap(ind[left], ind[right]);
1395 ++left;
1396 --right;
1397 }
1398 /* If either list is empty, it means that all remaining features
1399 * are identical. Split in the middle to maintain a balanced tree.
1400 */
1401 lim1 = left;
1402 right = count - 1;
1403 for (;;) {
1404 while (left <= right && dataset_get(ind[left], cutfeat) <= cutval)
1405 ++left;
1406 while (right && left <= right && dataset_get(ind[right], cutfeat) > cutval)
1407 --right;
1408 if (left > right || !right)
1409 break; // "!right" was added to support unsigned Index types
1410 std::swap(ind[left], ind[right]);
1411 ++left;
1412 --right;
1413 }
1414 lim2 = left;
1415 }
1416
1417 DistanceType computeInitialDistances(const ElementType* vec,
1418 distance_vector_t& dists) const {
1419 assert(vec);
1420 DistanceType distsq = 0.0;
1421
1422 for (int i = 0; i < (DIM > 0 ? DIM : dim); ++i) {
1423 if (vec[i] < root_bbox[i].low) {
1424 dists[i] = distance.accum_dist(vec[i], root_bbox[i].low, i);
1425 distsq += dists[i];
1426 }
1427 if (vec[i] > root_bbox[i].high) {
1428 dists[i] = distance.accum_dist(vec[i], root_bbox[i].high, i);
1429 distsq += dists[i];
1430 }
1431 }
1432
1433 return distsq;
1434 }
1435
1440 template<class RESULTSET>
1441 void searchLevel(RESULTSET& result_set, const ElementType* vec,
1442 const NodePtr node, DistanceType mindistsq,
1443 distance_vector_t& dists, const float epsError) const {
1444 /* If this is a leaf node, then do check and return. */
1445 if ((node->child1 == NULL) && (node->child2 == NULL)) {
1446 //count_leaf += (node->lr.right-node->lr.left); // Removed since was neither used nor returned to the user.
1447 DistanceType worst_dist = result_set.worstDist();
1448 for (IndexType i = node->lr.left; i < node->lr.right; ++i) {
1449 const IndexType index = vind[i]; // reorder... : i;
1450 DistanceType dist = distance(vec, index, (DIM > 0 ? DIM : dim));
1451 if (dist < worst_dist) {
1452 result_set.addPoint(dist, vind[i]);
1453 }
1454 }
1455 return;
1456 }
1457
1458 /* Which child branch should be taken first? */
1459 int idx = node->sub.divfeat;
1460 ElementType val = vec[idx];
1461 DistanceType diff1 = val - node->sub.divlow;
1462 DistanceType diff2 = val - node->sub.divhigh;
1463
1464 NodePtr bestChild;
1465 NodePtr otherChild;
1466 DistanceType cut_dist;
1467 if ((diff1 + diff2) < 0) {
1468 bestChild = node->child1;
1469 otherChild = node->child2;
1470 cut_dist = distance.accum_dist(val, node->sub.divhigh, idx);
1471 } else {
1472 bestChild = node->child2;
1473 otherChild = node->child1;
1474 cut_dist = distance.accum_dist(val, node->sub.divlow, idx);
1475 }
1476
1477 /* Call recursively to search next level down. */
1478 searchLevel(result_set, vec, bestChild, mindistsq, dists, epsError);
1479
1480 DistanceType dst = dists[idx];
1481 mindistsq = mindistsq + cut_dist - dst;
1482 dists[idx] = cut_dist;
1483 if (mindistsq * epsError <= result_set.worstDist()) {
1484 searchLevel(result_set, vec, otherChild, mindistsq, dists, epsError);
1485 }
1486 dists[idx] = dst;
1487 }
1488
1489 public:
1494 void saveIndex(FILE* stream) {
1495 save_value(stream, m_size);
1496 save_value(stream, dim);
1497 save_value(stream, root_bbox);
1498 save_value(stream, m_leaf_max_size);
1499 save_value(stream, vind);
1500 save_tree(stream, root_node);
1501 }
1502
1507 void loadIndex(FILE* stream) {
1508 load_value(stream, m_size);
1509 load_value(stream, dim);
1510 load_value(stream, root_bbox);
1511 load_value(stream, m_leaf_max_size);
1512 load_value(stream, vind);
1513 load_tree(stream, root_node);
1514 }
1515
1516};
1517// class KDTree
1518
1538template<class MatrixType, int DIM = -1, class Distance = nanoflann::metric_L2,
1539 typename IndexType = size_t>
1542 typedef typename MatrixType::Scalar num_t;
1543 typedef typename Distance::template traits<num_t, self_t>::distance_t metric_t;
1545
1547
1549 KDTreeEigenMatrixAdaptor(const int dimensionality, const MatrixType &mat,
1550 const int leaf_max_size = 10)
1551 : m_data_matrix(mat) {
1552 const size_t dims = mat.cols();
1553 if (DIM > 0 && static_cast<int>(dims) != DIM)
1554 throw std::runtime_error(
1555 "Data set dimensionality does not match the 'DIM' template argument");
1556 index = new index_t(
1557 dims, *this /* adaptor */,
1558 nanoflann::KDTreeSingleIndexAdaptorParams(leaf_max_size, dims));
1559 index->buildIndex();
1560 }
1561 private:
1563 KDTreeEigenMatrixAdaptor(const self_t&);
1564 public:
1565
1567 delete index;
1568 }
1569
1570 const MatrixType &m_data_matrix;
1571
1577 inline void query(const num_t *query_point, const size_t num_closest,
1578 IndexType *out_indices, num_t *out_distances_sq,
1579 const int /* nChecks_IGNORED */= 10) const {
1581 num_closest);
1582 resultSet.init(out_indices, out_distances_sq);
1583 index->findNeighbors(resultSet, query_point, nanoflann::SearchParams());
1584 }
1585
1589 const self_t & derived() const {
1590 return *this;
1591 }
1593 return *this;
1594 }
1595
1596 // Must return the number of data points
1597 inline size_t kdtree_get_point_count() const {
1598 return m_data_matrix.rows();
1599 }
1600
1601 // Returns the L2 distance between the vector "p1[0:size-1]" and the data point with index "idx_p2" stored in the class:
1602 inline num_t kdtree_distance(const num_t *p1, const size_t idx_p2,
1603 size_t size) const {
1604 num_t s = 0;
1605 for (size_t i = 0; i < size; i++) {
1606 const num_t d = p1[i] - m_data_matrix.coeff(idx_p2, i);
1607 s += d * d;
1608 }
1609 return s;
1610 }
1611
1612 // Returns the dim'th component of the idx'th point in the class:
1613 inline num_t kdtree_get_pt(const size_t idx, int dim) const {
1614 return m_data_matrix.coeff(idx, dim);
1615 }
1616
1617 // Optional bounding-box computation: return false to default to a standard bbox computation loop.
1618 // Return true if the BBOX was already computed by the class and returned in "bb" so it can be avoided to redo it again.
1619 // Look at bb.size() to find out the expected dimensionality (e.g. 2 or 3 for point clouds)
1620 template<class BBOX>
1621 bool kdtree_get_bbox(BBOX &bb) const {
1622 return false;
1623 }
1624
1627};
1628// end of KDTreeEigenMatrixAdaptor
1631// end of grouping
1632}// end of NS
1633
1634#endif /* NANOFLANN_HPP_ */
A STL container (as wrapper) for arrays of constant size defined at compile time (class imported from...
reverse_iterator rend()
const T * const_iterator
reference front()
void assign(const size_t n, const T &value)
const_reference front() const
std::size_t size_type
CArray< T, N > & operator=(const CArray< T2, N > &rhs)
const_reference operator[](size_type i) const
reference back()
void swap(CArray< T, N > &y)
reference operator[](size_type i)
const_reference at(size_type i) const
static bool empty()
reference at(size_type i)
std::ptrdiff_t difference_type
void resize(const size_t nElements)
This method has no effects in this class, but raises an exception if the expected size does not match...
const_reference back() const
static size_type max_size()
const_reverse_iterator rend() const
std::reverse_iterator< iterator > reverse_iterator
static size_type size()
const_reverse_iterator rbegin() const
const T & const_reference
const_iterator begin() const
const T * data() const
void assign(const T &value)
reverse_iterator rbegin()
std::reverse_iterator< const_iterator > const_reverse_iterator
const_iterator end() const
size_t size() const
Returns size of index.
size_t radiusSearch(const ElementType *query_point, const DistanceType radius, std::list< IndexType > &IndicesDists, const SearchParams &searchParams) const
const KDTreeSingleIndexAdaptorParams index_params
~KDTreeSingleIndexAdaptor()
Standard destructor.
int dim
Dimensionality of each data point.
NodePtr root_node
Array of k-d trees used to find neighbours.
void saveIndex(FILE *stream)
Stores the index in a binary file.
Distance::ElementType ElementType
void knnSearch(const ElementType *query_point, const size_t num_closest, IndexType *out_indices, DistanceType *out_distances_sq, const int=10) const
Find the "num_closest" nearest neighbors to the query_point[0:dim-1].
size_t usedMemory() const
Computes the inde memory usage Returns: memory used by the index.
size_t veclen() const
Returns the length of an index feature.
KDTreeSingleIndexAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
KDTree constructor.
std::vector< IndexType > vind
Array of indices to vectors in the dataset.
void freeIndex()
Frees the previously-built index.
const DatasetAdaptor & dataset
The dataset used by this index.
size_t radiusSearch(const ElementType *query_point, const DistanceType radius, std::vector< std::pair< IndexType, DistanceType > > &IndicesDists, const SearchParams &searchParams) const
Find all the neighbors to query_point[0:dim-1] within a maximum radius.
void loadIndex(FILE *stream)
Loads a previous index from a binary file.
BranchStruct< NodePtr, DistanceType > BranchSt
Distance::DistanceType DistanceType
void buildIndex()
Builds the index.
PooledAllocator pool
Pooled memory allocator.
array_or_vector_selector< DIM, Interval >::container_t BoundingBox
Define "BoundingBox" as a fixed-size or variable-size container depending on "DIM".
void findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
Find set of nearest neighbors to vec[0:dim-1].
array_or_vector_selector< DIM, DistanceType >::container_t distance_vector_t
Define "distance_vector_t" as a fixed-size or variable-size container depending on "DIM".
void init(IndexType *indices_, DistanceType *dists_)
Definition nanoflann.hpp:78
void addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:93
CountType size() const
Definition nanoflann.hpp:85
KNNResultSet(CountType capacity_)
Definition nanoflann.hpp:71
DistanceType worstDist() const
PooledAllocator(const size_t blocksize_=BLOCKSIZE)
Default constructor.
void free_all()
Frees all allocated memory chunks.
void * malloc(const size_t req_size)
Returns a pointer to a piece of new memory of the given size in bytes allocated from the pool.
T * allocate(const size_t count=1)
Allocates (using this pool) a generic type T.
DistanceType worstDist() const
const DistanceType radius
void set_radius_and_clear(const DistanceType r)
Clears the result set and adjusts the search radius.
std::pair< IndexType, DistanceType > worst_item() const
Find the worst result (furtherest neighbor) without copying or sorting Pre-conditions: size() > 0.
void addPoint(DistanceType dist, IndexType index)
std::list< IndexType > & m_indices_list
RadiusResultList(DistanceType radius_, std::list< IndexType > &indices_list)
A result-set class used when performing a radius based search.
std::pair< IndexType, DistanceType > worst_item() const
Find the worst result (furtherest neighbor) without copying or sorting Pre-conditions: size() > 0.
void addPoint(DistanceType dist, IndexType index)
const DistanceType radius
DistanceType worstDist() const
RadiusResultSet(DistanceType radius_, std::vector< std::pair< IndexType, DistanceType > > &indices_dists)
std::vector< std::pair< IndexType, DistanceType > > & m_indices_dists
void set_radius_and_clear(const DistanceType r)
Clears the result set and adjusts the search radius.
void load_value(FILE *stream, T &value, size_t count=1)
void save_value(FILE *stream, const T &value, size_t count=1)
const size_t WORDSIZE
Pooled storage allocator.
T * allocate(size_t count=1)
Allocates (using C's malloc) a generic type T.
const size_t BLOCKSIZE
long double abs< long double >(long double x)
float abs< float >(float x)
double abs< double >(double x)
int abs< int >(int x)
T abs(T x)
ThreadPool & pool()
Definition olbInit.cpp:37
ADf< long double, DIM > fabsl(const ADf< long double, DIM > &a)
Definition aDiff.h:1013
bool distance(S &distance, const Vector< S, D > &origin, const Vector< S, D > &direction, S precision, S pitch, F1 isInside, F2 isInsideBoundingBox)
ADf< float, DIM > fabsf(const ADf< float, DIM > &a)
Definition aDiff.h:1007
cpu::simd::Pack< T > fabs(cpu::simd::Pack< T > value)
Definition pack.h:106
operator "<" for std::sort()
bool operator()(const PairType &p1, const PairType &p2) const
PairType will be typically: std::pair<IndexType,DistanceType>
An L2-metric KD-tree adaptor for working with data directly stored in an Eigen Matrix,...
void query(const num_t *query_point, const size_t num_closest, IndexType *out_indices, num_t *out_distances_sq, const int=10) const
Query for the num_closest closest points to a given point (entered as query_point[0:dim-1]).
KDTreeSingleIndexAdaptor< metric_t, self_t, DIM, IndexType > index_t
KDTreeEigenMatrixAdaptor< MatrixType, DIM, Distance, IndexType > self_t
bool kdtree_get_bbox(BBOX &bb) const
num_t kdtree_get_pt(const size_t idx, int dim) const
KDTreeEigenMatrixAdaptor(const int dimensionality, const MatrixType &mat, const int leaf_max_size=10)
The kd-tree index for the user to call its methods as usual with any other FLANN index.
Distance::template traits< num_t, self_t >::distance_t metric_t
num_t kdtree_distance(const num_t *p1, const size_t idx_p2, size_t size) const
Parameters (see http://code.google.com/p/nanoflann/ for help choosing the parameters)
KDTreeSingleIndexAdaptorParams(size_t _leaf_max_size=10, int dim_=-1)
This record represents a branch point when finding neighbors in the tree.
bool operator<(const BranchStruct< T, DistanceType > &rhs) const
BranchStruct(const T &aNode, DistanceType dist)
IndexType left
Indices of points in leaf node.
int divfeat
Dimension used for subdivision.
Manhattan distance functor (generic version, optimized for high-dimensionality data sets).
_DistanceType DistanceType
L1_Adaptor(const DataSource &_data_source)
DistanceType operator()(const T *a, const size_t b_idx, size_t size, DistanceType worst_dist=-1) const
DistanceType accum_dist(const U a, const V b, int) const
const DataSource & data_source
Squared Euclidean distance functor (generic version, optimized for high-dimensionality data sets).
_DistanceType DistanceType
DistanceType operator()(const T *a, const size_t b_idx, size_t size, DistanceType worst_dist=-1) const
L2_Adaptor(const DataSource &_data_source)
DistanceType accum_dist(const U a, const V b, int) const
const DataSource & data_source
Squared Euclidean (L2) distance functor (suitable for low-dimensionality datasets,...
DistanceType accum_dist(const U a, const V b, int) const
const DataSource & data_source
L2_Simple_Adaptor(const DataSource &_data_source)
DistanceType operator()(const T *a, const size_t b_idx, size_t size) const
Search options for KDTreeSingleIndexAdaptor::findNeighbors()
bool sorted
only for radius search, require neighbours sorted by distance (default: true)
SearchParams(int checks_IGNORED_=32, float eps_=0, bool sorted_=true)
Note: The first argument (checks_IGNORED_) is ignored, but kept for compatibility with the FLANN inte...
float eps
search for eps-approximate neighbours (default: 0)
int checks
Ignored parameter (Kept for compatibility with the FLANN interface).
Used to declare fixed-size arrays when DIM>0, dynamically-allocated vectors when DIM=-1.
L1_Adaptor< T, DataSource > distance_t
Metaprogramming helper traits class for the L1 (Manhattan) metric.
L2_Adaptor< T, DataSource > distance_t
L2_Simple_Adaptor< T, DataSource > distance_t
Metaprogramming helper traits class for the L2_simple (Euclidean) metric.
Metaprogramming helper traits class for the L2 (Euclidean) metric.