nanoflann
C++ header-only ANN library
Loading...
Searching...
No Matches
nanoflann.hpp
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-2024 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
45#pragma once
46
47#include <algorithm>
48#include <array>
49#include <atomic>
50#include <cassert>
51#include <cmath> // for abs()
52#include <cstdint>
53#include <cstdlib> // for abs()
54#include <functional> // std::reference_wrapper
55#include <future>
56#include <istream>
57#include <limits> // std::numeric_limits
58#include <ostream>
59#include <stdexcept>
60#include <unordered_set>
61#include <vector>
62
64#define NANOFLANN_VERSION 0x155
65
66// Avoid conflicting declaration of min/max macros in Windows headers
67#if !defined(NOMINMAX) && \
68 (defined(_WIN32) || defined(_WIN32_) || defined(WIN32) || defined(_WIN64))
69#define NOMINMAX
70#ifdef max
71#undef max
72#undef min
73#endif
74#endif
75// Avoid conflicts with X11 headers
76#ifdef None
77#undef None
78#endif
79
80namespace nanoflann
81{
86template <typename T>
88{
89 return static_cast<T>(3.14159265358979323846);
90}
91
96template <typename T, typename = int>
97struct has_resize : std::false_type
98{
99};
100
101template <typename T>
102struct has_resize<T, decltype((void)std::declval<T>().resize(1), 0)>
103 : std::true_type
104{
105};
106
107template <typename T, typename = int>
108struct has_assign : std::false_type
109{
110};
111
112template <typename T>
113struct has_assign<T, decltype((void)std::declval<T>().assign(1, 0), 0)>
114 : std::true_type
115{
116};
117
121template <typename Container>
122inline typename std::enable_if<has_resize<Container>::value, void>::type resize(
123 Container& c, const size_t nElements)
124{
125 c.resize(nElements);
126}
127
132template <typename Container>
133inline typename std::enable_if<!has_resize<Container>::value, void>::type
134 resize(Container& c, const size_t nElements)
135{
136 if (nElements != c.size())
137 throw std::logic_error("Try to change the size of a std::array.");
138}
139
143template <typename Container, typename T>
144inline typename std::enable_if<has_assign<Container>::value, void>::type assign(
145 Container& c, const size_t nElements, const T& value)
146{
147 c.assign(nElements, value);
148}
149
153template <typename Container, typename T>
154inline typename std::enable_if<!has_assign<Container>::value, void>::type
155 assign(Container& c, const size_t nElements, const T& value)
156{
157 for (size_t i = 0; i < nElements; i++) c[i] = value;
158}
159
160
163{
165 template <typename PairType>
166 bool operator()(const PairType& p1, const PairType& p2) const
167 {
168 return p1.second < p2.second;
169 }
170};
171
180template <typename IndexType = size_t, typename DistanceType = double>
182{
183 ResultItem() = default;
184 ResultItem(const IndexType index, const DistanceType distance)
185 : first(index), second(distance)
186 {
187 }
188
189 IndexType first;
190 DistanceType second;
191};
192
197template <
198 typename _DistanceType, typename _IndexType = size_t,
199 typename _CountType = size_t>
201{
202 public:
203 using DistanceType = _DistanceType;
204 using IndexType = _IndexType;
205 using CountType = _CountType;
206
207 private:
208 IndexType* indices;
209 DistanceType* dists;
210 CountType capacity;
211 CountType count;
212
213 public:
214 explicit KNNResultSet(CountType capacity_)
215 : indices(nullptr), dists(nullptr), capacity(capacity_), count(0)
216 {
217 }
218
219 void init(IndexType* indices_, DistanceType* dists_)
220 {
221 indices = indices_;
222 dists = dists_;
223 count = 0;
224 if (capacity)
225 dists[capacity - 1] = (std::numeric_limits<DistanceType>::max)();
226 }
227
228 CountType size() const { return count; }
229 bool empty() const { return count == 0; }
230 bool full() const { return count == capacity; }
231
237 bool addPoint(DistanceType dist, IndexType index)
238 {
239 CountType i;
240 for (i = count; i > 0; --i)
241 {
244#ifdef NANOFLANN_FIRST_MATCH
245 if ((dists[i - 1] > dist) ||
246 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
247 {
248#else
249 if (dists[i - 1] > dist)
250 {
251#endif
252 if (i < capacity)
253 {
254 dists[i] = dists[i - 1];
255 indices[i] = indices[i - 1];
256 }
257 }
258 else
259 break;
260 }
261 if (i < capacity)
262 {
263 dists[i] = dist;
264 indices[i] = index;
265 }
266 if (count < capacity) count++;
267
268 // tell caller that the search shall continue
269 return true;
270 }
271
272 DistanceType worstDist() const { return dists[capacity - 1]; }
273
274 void sort()
275 {
276 // already sorted
277 }
278};
279
281template <
282 typename _DistanceType, typename _IndexType = size_t,
283 typename _CountType = size_t>
285{
286 public:
287 using DistanceType = _DistanceType;
288 using IndexType = _IndexType;
289 using CountType = _CountType;
290
291 private:
292 IndexType* indices;
293 DistanceType* dists;
294 CountType capacity;
295 CountType count;
296 DistanceType maximumSearchDistanceSquared;
297
298 public:
299 explicit RKNNResultSet(
300 CountType capacity_, DistanceType maximumSearchDistanceSquared_)
301 : indices(nullptr),
302 dists(nullptr),
303 capacity(capacity_),
304 count(0),
305 maximumSearchDistanceSquared(maximumSearchDistanceSquared_)
306 {
307 }
308
309 void init(IndexType* indices_, DistanceType* dists_)
310 {
311 indices = indices_;
312 dists = dists_;
313 count = 0;
314 if (capacity) dists[capacity - 1] = maximumSearchDistanceSquared;
315 }
316
317 CountType size() const { return count; }
318 bool empty() const { return count == 0; }
319 bool full() const { return count == capacity; }
320
326 bool addPoint(DistanceType dist, IndexType index)
327 {
328 CountType i;
329 for (i = count; i > 0; --i)
330 {
333#ifdef NANOFLANN_FIRST_MATCH
334 if ((dists[i - 1] > dist) ||
335 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
336 {
337#else
338 if (dists[i - 1] > dist)
339 {
340#endif
341 if (i < capacity)
342 {
343 dists[i] = dists[i - 1];
344 indices[i] = indices[i - 1];
345 }
346 }
347 else
348 break;
349 }
350 if (i < capacity)
351 {
352 dists[i] = dist;
353 indices[i] = index;
354 }
355 if (count < capacity) count++;
356
357 // tell caller that the search shall continue
358 return true;
359 }
360
361 DistanceType worstDist() const { return dists[capacity - 1]; }
362
363 void sort()
364 {
365 // already sorted
366 }
367};
368
372template <typename _DistanceType, typename _IndexType = size_t>
374{
375 public:
376 using DistanceType = _DistanceType;
377 using IndexType = _IndexType;
378
379 public:
380 const DistanceType radius;
381
382 std::vector<ResultItem<IndexType, DistanceType>>& m_indices_dists;
383
384 explicit RadiusResultSet(
385 DistanceType radius_,
386 std::vector<ResultItem<IndexType, DistanceType>>& indices_dists)
387 : radius(radius_), m_indices_dists(indices_dists)
388 {
389 init();
390 }
391
392 void init() { clear(); }
393 void clear() { m_indices_dists.clear(); }
394
395 size_t size() const { return m_indices_dists.size(); }
396 size_t empty() const { return m_indices_dists.empty(); }
397
398 bool full() const { return true; }
399
405 bool addPoint(DistanceType dist, IndexType index)
406 {
407 if (dist < radius) m_indices_dists.emplace_back(index, dist);
408 return true;
409 }
410
411 DistanceType worstDist() const { return radius; }
412
418 {
419 if (m_indices_dists.empty())
420 throw std::runtime_error(
421 "Cannot invoke RadiusResultSet::worst_item() on "
422 "an empty list of results.");
423 auto it = std::max_element(
424 m_indices_dists.begin(), m_indices_dists.end(), IndexDist_Sorter());
425 return *it;
426 }
427
428 void sort()
429 {
430 std::sort(
431 m_indices_dists.begin(), m_indices_dists.end(), IndexDist_Sorter());
432 }
433};
434
439template <typename T>
440void save_value(std::ostream& stream, const T& value)
441{
442 stream.write(reinterpret_cast<const char*>(&value), sizeof(T));
443}
444
445template <typename T>
446void save_value(std::ostream& stream, const std::vector<T>& value)
447{
448 size_t size = value.size();
449 stream.write(reinterpret_cast<const char*>(&size), sizeof(size_t));
450 stream.write(reinterpret_cast<const char*>(value.data()), sizeof(T) * size);
451}
452
453template <typename T>
454void load_value(std::istream& stream, T& value)
455{
456 stream.read(reinterpret_cast<char*>(&value), sizeof(T));
457}
458
459template <typename T>
460void load_value(std::istream& stream, std::vector<T>& value)
461{
462 size_t size;
463 stream.read(reinterpret_cast<char*>(&size), sizeof(size_t));
464 value.resize(size);
465 stream.read(reinterpret_cast<char*>(value.data()), sizeof(T) * size);
466}
472struct Metric
473{
474};
475
486template <
487 class T, class DataSource, typename _DistanceType = T,
488 typename IndexType = uint32_t>
490{
491 using ElementType = T;
492 using DistanceType = _DistanceType;
493
494 const DataSource& data_source;
495
496 L1_Adaptor(const DataSource& _data_source) : data_source(_data_source) {}
497
498 DistanceType evalMetric(
499 const T* a, const IndexType b_idx, size_t size,
500 DistanceType worst_dist = -1) const
501 {
502 DistanceType result = DistanceType();
503 const T* last = a + size;
504 const T* lastgroup = last - 3;
505 size_t d = 0;
506
507 /* Process 4 items with each loop for efficiency. */
508 while (a < lastgroup)
509 {
510 const DistanceType diff0 =
511 std::abs(a[0] - data_source.kdtree_get_pt(b_idx, d++));
512 const DistanceType diff1 =
513 std::abs(a[1] - data_source.kdtree_get_pt(b_idx, d++));
514 const DistanceType diff2 =
515 std::abs(a[2] - data_source.kdtree_get_pt(b_idx, d++));
516 const DistanceType diff3 =
517 std::abs(a[3] - data_source.kdtree_get_pt(b_idx, d++));
518 result += diff0 + diff1 + diff2 + diff3;
519 a += 4;
520 if ((worst_dist > 0) && (result > worst_dist)) { return result; }
521 }
522 /* Process last 0-3 components. Not needed for standard vector lengths.
523 */
524 while (a < last)
525 {
526 result += std::abs(*a++ - data_source.kdtree_get_pt(b_idx, d++));
527 }
528 return result;
529 }
530
531 template <typename U, typename V>
532 DistanceType accum_dist(const U a, const V b, const size_t) const
533 {
534 return std::abs(a - b);
535 }
536};
537
548template <
549 class T, class DataSource, typename _DistanceType = T,
550 typename IndexType = uint32_t>
552{
553 using ElementType = T;
554 using DistanceType = _DistanceType;
555
556 const DataSource& data_source;
557
558 L2_Adaptor(const DataSource& _data_source) : data_source(_data_source) {}
559
560 DistanceType evalMetric(
561 const T* a, const IndexType b_idx, size_t size,
562 DistanceType worst_dist = -1) const
563 {
564 DistanceType result = DistanceType();
565 const T* last = a + size;
566 const T* lastgroup = last - 3;
567 size_t d = 0;
568
569 /* Process 4 items with each loop for efficiency. */
570 while (a < lastgroup)
571 {
572 const DistanceType diff0 =
573 a[0] - data_source.kdtree_get_pt(b_idx, d++);
574 const DistanceType diff1 =
575 a[1] - data_source.kdtree_get_pt(b_idx, d++);
576 const DistanceType diff2 =
577 a[2] - data_source.kdtree_get_pt(b_idx, d++);
578 const DistanceType diff3 =
579 a[3] - data_source.kdtree_get_pt(b_idx, d++);
580 result +=
581 diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
582 a += 4;
583 if ((worst_dist > 0) && (result > worst_dist)) { return result; }
584 }
585 /* Process last 0-3 components. Not needed for standard vector lengths.
586 */
587 while (a < last)
588 {
589 const DistanceType diff0 =
590 *a++ - data_source.kdtree_get_pt(b_idx, d++);
591 result += diff0 * diff0;
592 }
593 return result;
594 }
595
596 template <typename U, typename V>
597 DistanceType accum_dist(const U a, const V b, const size_t) const
598 {
599 return (a - b) * (a - b);
600 }
601};
602
613template <
614 class T, class DataSource, typename _DistanceType = T,
615 typename IndexType = uint32_t>
617{
618 using ElementType = T;
619 using DistanceType = _DistanceType;
620
621 const DataSource& data_source;
622
623 L2_Simple_Adaptor(const DataSource& _data_source)
624 : data_source(_data_source)
625 {
626 }
627
628 DistanceType evalMetric(
629 const T* a, const IndexType b_idx, size_t size) const
630 {
631 DistanceType result = DistanceType();
632 for (size_t i = 0; i < size; ++i)
633 {
634 const DistanceType diff =
635 a[i] - data_source.kdtree_get_pt(b_idx, i);
636 result += diff * diff;
637 }
638 return result;
639 }
640
641 template <typename U, typename V>
642 DistanceType accum_dist(const U a, const V b, const size_t) const
643 {
644 return (a - b) * (a - b);
645 }
646};
647
658template <
659 class T, class DataSource, typename _DistanceType = T,
660 typename IndexType = uint32_t>
662{
663 using ElementType = T;
664 using DistanceType = _DistanceType;
665
666 const DataSource& data_source;
667
668 SO2_Adaptor(const DataSource& _data_source) : data_source(_data_source) {}
669
670 DistanceType evalMetric(
671 const T* a, const IndexType b_idx, size_t size) const
672 {
673 return accum_dist(
674 a[size - 1], data_source.kdtree_get_pt(b_idx, size - 1), size - 1);
675 }
676
679 template <typename U, typename V>
680 DistanceType accum_dist(const U a, const V b, const size_t) const
681 {
682 DistanceType result = DistanceType();
683 DistanceType PI = pi_const<DistanceType>();
684 result = b - a;
685 if (result > PI)
686 result -= 2 * PI;
687 else if (result < -PI)
688 result += 2 * PI;
689 return result;
690 }
691};
692
703template <
704 class T, class DataSource, typename _DistanceType = T,
705 typename IndexType = uint32_t>
707{
708 using ElementType = T;
709 using DistanceType = _DistanceType;
710
712 distance_L2_Simple;
713
714 SO3_Adaptor(const DataSource& _data_source)
715 : distance_L2_Simple(_data_source)
716 {
717 }
718
719 DistanceType evalMetric(
720 const T* a, const IndexType b_idx, size_t size) const
721 {
722 return distance_L2_Simple.evalMetric(a, b_idx, size);
723 }
724
725 template <typename U, typename V>
726 DistanceType accum_dist(const U a, const V b, const size_t idx) const
727 {
728 return distance_L2_Simple.accum_dist(a, b, idx);
729 }
730};
731
733struct metric_L1 : public Metric
734{
735 template <class T, class DataSource, typename IndexType = uint32_t>
740};
743struct metric_L2 : public Metric
744{
745 template <class T, class DataSource, typename IndexType = uint32_t>
750};
754{
755 template <class T, class DataSource, typename IndexType = uint32_t>
760};
762struct metric_SO2 : public Metric
763{
764 template <class T, class DataSource, typename IndexType = uint32_t>
769};
771struct metric_SO3 : public Metric
772{
773 template <class T, class DataSource, typename IndexType = uint32_t>
778};
779
785enum class KDTreeSingleIndexAdaptorFlags
786{
787 None = 0,
788 SkipInitialBuildIndex = 1
789};
790
791inline std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type operator&(
792 KDTreeSingleIndexAdaptorFlags lhs, KDTreeSingleIndexAdaptorFlags rhs)
793{
794 using underlying =
795 typename std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type;
796 return static_cast<underlying>(lhs) & static_cast<underlying>(rhs);
797}
798
801{
803 size_t _leaf_max_size = 10,
804 KDTreeSingleIndexAdaptorFlags _flags =
805 KDTreeSingleIndexAdaptorFlags::None,
806 unsigned int _n_thread_build = 1)
807 : leaf_max_size(_leaf_max_size),
808 flags(_flags),
809 n_thread_build(_n_thread_build)
810 {
811 }
812
813 size_t leaf_max_size;
814 KDTreeSingleIndexAdaptorFlags flags;
815 unsigned int n_thread_build;
816};
817
820{
821 SearchParameters(float eps_ = 0, bool sorted_ = true)
822 : eps(eps_), sorted(sorted_)
823 {
824 }
825
826 float eps;
827 bool sorted;
829};
850{
851 static constexpr size_t WORDSIZE = 16; // WORDSIZE must >= 8
852 static constexpr size_t BLOCKSIZE = 8192;
853
854 /* We maintain memory alignment to word boundaries by requiring that all
855 allocations be in multiples of the machine wordsize. */
856 /* Size of machine word in bytes. Must be power of 2. */
857 /* Minimum number of bytes requested at a time from the system. Must be
858 * multiple of WORDSIZE. */
859
860 using Size = size_t;
861
862 Size remaining_ = 0;
863 void* base_ = nullptr;
864 void* loc_ = nullptr;
865
866 void internal_init()
867 {
868 remaining_ = 0;
869 base_ = nullptr;
870 usedMemory = 0;
871 wastedMemory = 0;
872 }
873
874 public:
875 Size usedMemory = 0;
876 Size wastedMemory = 0;
877
881 PooledAllocator() { internal_init(); }
882
886 ~PooledAllocator() { free_all(); }
887
889 void free_all()
890 {
891 while (base_ != nullptr)
892 {
893 // Get pointer to prev block
894 void* prev = *(static_cast<void**>(base_));
895 ::free(base_);
896 base_ = prev;
897 }
898 internal_init();
899 }
900
905 void* malloc(const size_t req_size)
906 {
907 /* Round size up to a multiple of wordsize. The following expression
908 only works for WORDSIZE that is a power of 2, by masking last bits
909 of incremented size to zero.
910 */
911 const Size size = (req_size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
912
913 /* Check whether a new block must be allocated. Note that the first
914 word of a block is reserved for a pointer to the previous block.
915 */
916 if (size > remaining_)
917 {
918 wastedMemory += remaining_;
919
920 /* Allocate new storage. */
921 const Size blocksize =
922 size > BLOCKSIZE ? size + WORDSIZE : BLOCKSIZE + WORDSIZE;
923
924 // use the standard C malloc to allocate memory
925 void* m = ::malloc(blocksize);
926 if (!m)
927 {
928 fprintf(stderr, "Failed to allocate memory.\n");
929 throw std::bad_alloc();
930 }
931
932 /* Fill first word of new block with pointer to previous block. */
933 static_cast<void**>(m)[0] = base_;
934 base_ = m;
935
936 remaining_ = blocksize - WORDSIZE;
937 loc_ = static_cast<char*>(m) + WORDSIZE;
938 }
939 void* rloc = loc_;
940 loc_ = static_cast<char*>(loc_) + size;
941 remaining_ -= size;
942
943 usedMemory += size;
944
945 return rloc;
946 }
947
955 template <typename T>
956 T* allocate(const size_t count = 1)
957 {
958 T* mem = static_cast<T*>(this->malloc(sizeof(T) * count));
959 return mem;
960 }
961};
970template <int32_t DIM, typename T>
972{
973 using type = std::array<T, DIM>;
974};
976template <typename T>
977struct array_or_vector<-1, T>
978{
979 using type = std::vector<T>;
980};
981
998template <
999 class Derived, typename Distance, class DatasetAdaptor, int32_t DIM = -1,
1000 typename index_t = uint32_t>
1002{
1003 public:
1006 void freeIndex(Derived& obj)
1007 {
1008 obj.pool_.free_all();
1009 obj.root_node_ = nullptr;
1010 obj.size_at_index_build_ = 0;
1011 }
1012
1013 using ElementType = typename Distance::ElementType;
1014 using DistanceType = typename Distance::DistanceType;
1015 using IndexType = index_t;
1016
1020 std::vector<IndexType> vAcc_;
1021
1022 using Offset = typename decltype(vAcc_)::size_type;
1023 using Size = typename decltype(vAcc_)::size_type;
1024 using Dimension = int32_t;
1025
1026 /*---------------------------
1027 * Internal Data Structures
1028 * --------------------------*/
1029 struct Node
1030 {
1033 union
1034 {
1035 struct leaf
1036 {
1037 Offset left, right;
1038 } lr;
1039 struct nonleaf
1040 {
1041 Dimension divfeat;
1043 DistanceType divlow, divhigh;
1044 } sub;
1045 } node_type;
1046
1048 Node *child1 = nullptr, *child2 = nullptr;
1049 };
1050
1051 using NodePtr = Node*;
1052 using NodeConstPtr = const Node*;
1053
1055 {
1056 ElementType low, high;
1057 };
1058
1059 NodePtr root_node_ = nullptr;
1060
1061 Size leaf_max_size_ = 0;
1062
1064 Size n_thread_build_ = 1;
1066 Size size_ = 0;
1068 Size size_at_index_build_ = 0;
1069 Dimension dim_ = 0;
1070
1073 using BoundingBox = typename array_or_vector<DIM, Interval>::type;
1074
1077 using distance_vector_t = typename array_or_vector<DIM, DistanceType>::type;
1078
1081
1090
1092 Size size(const Derived& obj) const { return obj.size_; }
1093
1095 Size veclen(const Derived& obj) { return DIM > 0 ? DIM : obj.dim; }
1096
1098 ElementType dataset_get(
1099 const Derived& obj, IndexType element, Dimension component) const
1100 {
1101 return obj.dataset_.kdtree_get_pt(element, component);
1102 }
1103
1108 Size usedMemory(Derived& obj)
1109 {
1110 return obj.pool_.usedMemory + obj.pool_.wastedMemory +
1111 obj.dataset_.kdtree_get_point_count() *
1112 sizeof(IndexType); // pool memory and vind array memory
1113 }
1114
1115 void computeMinMax(
1116 const Derived& obj, Offset ind, Size count, Dimension element,
1117 ElementType& min_elem, ElementType& max_elem)
1118 {
1119 min_elem = dataset_get(obj, vAcc_[ind], element);
1120 max_elem = min_elem;
1121 for (Offset i = 1; i < count; ++i)
1122 {
1123 ElementType val = dataset_get(obj, vAcc_[ind + i], element);
1124 if (val < min_elem) min_elem = val;
1125 if (val > max_elem) max_elem = val;
1126 }
1127 }
1128
1137 Derived& obj, const Offset left, const Offset right, BoundingBox& bbox)
1138 {
1139 NodePtr node = obj.pool_.template allocate<Node>(); // allocate memory
1140 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1141
1142 /* If too few exemplars remain, then make this a leaf node. */
1143 if ((right - left) <= static_cast<Offset>(obj.leaf_max_size_))
1144 {
1145 node->child1 = node->child2 = nullptr; /* Mark as leaf node. */
1146 node->node_type.lr.left = left;
1147 node->node_type.lr.right = right;
1148
1149 // compute bounding-box of leaf points
1150 for (Dimension i = 0; i < dims; ++i)
1151 {
1152 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1153 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1154 }
1155 for (Offset k = left + 1; k < right; ++k)
1156 {
1157 for (Dimension i = 0; i < dims; ++i)
1158 {
1159 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1160 if (bbox[i].low > val) bbox[i].low = val;
1161 if (bbox[i].high < val) bbox[i].high = val;
1162 }
1163 }
1164 }
1165 else
1166 {
1167 Offset idx;
1168 Dimension cutfeat;
1169 DistanceType cutval;
1170 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1171
1172 node->node_type.sub.divfeat = cutfeat;
1173
1174 BoundingBox left_bbox(bbox);
1175 left_bbox[cutfeat].high = cutval;
1176 node->child1 = this->divideTree(obj, left, left + idx, left_bbox);
1177
1178 BoundingBox right_bbox(bbox);
1179 right_bbox[cutfeat].low = cutval;
1180 node->child2 = this->divideTree(obj, left + idx, right, right_bbox);
1181
1182 node->node_type.sub.divlow = left_bbox[cutfeat].high;
1183 node->node_type.sub.divhigh = right_bbox[cutfeat].low;
1184
1185 for (Dimension i = 0; i < dims; ++i)
1186 {
1187 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1188 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1189 }
1190 }
1191
1192 return node;
1193 }
1194
1206 Derived& obj, const Offset left, const Offset right, BoundingBox& bbox,
1207 std::atomic<unsigned int>& thread_count, std::mutex& mutex)
1208 {
1209 std::unique_lock<std::mutex> lock(mutex);
1210 NodePtr node = obj.pool_.template allocate<Node>(); // allocate memory
1211 lock.unlock();
1212
1213 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1214
1215 /* If too few exemplars remain, then make this a leaf node. */
1216 if ((right - left) <= static_cast<Offset>(obj.leaf_max_size_))
1217 {
1218 node->child1 = node->child2 = nullptr; /* Mark as leaf node. */
1219 node->node_type.lr.left = left;
1220 node->node_type.lr.right = right;
1221
1222 // compute bounding-box of leaf points
1223 for (Dimension i = 0; i < dims; ++i)
1224 {
1225 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1226 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1227 }
1228 for (Offset k = left + 1; k < right; ++k)
1229 {
1230 for (Dimension i = 0; i < dims; ++i)
1231 {
1232 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1233 if (bbox[i].low > val) bbox[i].low = val;
1234 if (bbox[i].high < val) bbox[i].high = val;
1235 }
1236 }
1237 }
1238 else
1239 {
1240 Offset idx;
1241 Dimension cutfeat;
1242 DistanceType cutval;
1243 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1244
1245 node->node_type.sub.divfeat = cutfeat;
1246
1247 std::future<NodePtr> right_future;
1248
1249 BoundingBox right_bbox(bbox);
1250 right_bbox[cutfeat].low = cutval;
1251 if (++thread_count < n_thread_build_)
1252 {
1253 // Concurrent right sub-tree
1254 right_future = std::async(
1255 std::launch::async, &KDTreeBaseClass::divideTreeConcurrent,
1256 this, std::ref(obj), left + idx, right,
1257 std::ref(right_bbox), std::ref(thread_count),
1258 std::ref(mutex));
1259 }
1260 else { --thread_count; }
1261
1262 BoundingBox left_bbox(bbox);
1263 left_bbox[cutfeat].high = cutval;
1264 node->child1 = this->divideTreeConcurrent(
1265 obj, left, left + idx, left_bbox, thread_count, mutex);
1266
1267 if (right_future.valid())
1268 {
1269 // Block and wait for concurrent right sub-tree
1270 node->child2 = right_future.get();
1271 --thread_count;
1272 }
1273 else
1274 {
1275 node->child2 = this->divideTreeConcurrent(
1276 obj, left + idx, right, right_bbox, thread_count, mutex);
1277 }
1278
1279 node->node_type.sub.divlow = left_bbox[cutfeat].high;
1280 node->node_type.sub.divhigh = right_bbox[cutfeat].low;
1281
1282 for (Dimension i = 0; i < dims; ++i)
1283 {
1284 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1285 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1286 }
1287 }
1288
1289 return node;
1290 }
1291
1292 void middleSplit_(
1293 const Derived& obj, const Offset ind, const Size count, Offset& index,
1294 Dimension& cutfeat, DistanceType& cutval, const BoundingBox& bbox)
1295 {
1296 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1297 const auto EPS = static_cast<DistanceType>(0.00001);
1298 ElementType max_span = bbox[0].high - bbox[0].low;
1299 for (Dimension i = 1; i < dims; ++i)
1300 {
1301 ElementType span = bbox[i].high - bbox[i].low;
1302 if (span > max_span) { max_span = span; }
1303 }
1304 ElementType max_spread = -1;
1305 cutfeat = 0;
1306 ElementType min_elem = 0, max_elem = 0;
1307 for (Dimension i = 0; i < dims; ++i)
1308 {
1309 ElementType span = bbox[i].high - bbox[i].low;
1310 if (span > (1 - EPS) * max_span)
1311 {
1312 ElementType min_elem_, max_elem_;
1313 computeMinMax(obj, ind, count, i, min_elem_, max_elem_);
1314 ElementType spread = max_elem_ - min_elem_;
1315 if (spread > max_spread)
1316 {
1317 cutfeat = i;
1318 max_spread = spread;
1319 min_elem = min_elem_;
1320 max_elem = max_elem_;
1321 }
1322 }
1323 }
1324 // split in the middle
1325 DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;
1326
1327 if (split_val < min_elem)
1328 cutval = min_elem;
1329 else if (split_val > max_elem)
1330 cutval = max_elem;
1331 else
1332 cutval = split_val;
1333
1334 Offset lim1, lim2;
1335 planeSplit(obj, ind, count, cutfeat, cutval, lim1, lim2);
1336
1337 if (lim1 > count / 2)
1338 index = lim1;
1339 else if (lim2 < count / 2)
1340 index = lim2;
1341 else
1342 index = count / 2;
1343 }
1344
1355 const Derived& obj, const Offset ind, const Size count,
1356 const Dimension cutfeat, const DistanceType& cutval, Offset& lim1,
1357 Offset& lim2)
1358 {
1359 /* Move vector indices for left subtree to front of list. */
1360 Offset left = 0;
1361 Offset right = count - 1;
1362 for (;;)
1363 {
1364 while (left <= right &&
1365 dataset_get(obj, vAcc_[ind + left], cutfeat) < cutval)
1366 ++left;
1367 while (right && left <= right &&
1368 dataset_get(obj, vAcc_[ind + right], cutfeat) >= cutval)
1369 --right;
1370 if (left > right || !right)
1371 break; // "!right" was added to support unsigned Index types
1372 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1373 ++left;
1374 --right;
1375 }
1376 /* If either list is empty, it means that all remaining features
1377 * are identical. Split in the middle to maintain a balanced tree.
1378 */
1379 lim1 = left;
1380 right = count - 1;
1381 for (;;)
1382 {
1383 while (left <= right &&
1384 dataset_get(obj, vAcc_[ind + left], cutfeat) <= cutval)
1385 ++left;
1386 while (right && left <= right &&
1387 dataset_get(obj, vAcc_[ind + right], cutfeat) > cutval)
1388 --right;
1389 if (left > right || !right)
1390 break; // "!right" was added to support unsigned Index types
1391 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1392 ++left;
1393 --right;
1394 }
1395 lim2 = left;
1396 }
1397
1398 DistanceType computeInitialDistances(
1399 const Derived& obj, const ElementType* vec,
1400 distance_vector_t& dists) const
1401 {
1402 assert(vec);
1403 DistanceType dist = DistanceType();
1404
1405 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim_); ++i)
1406 {
1407 if (vec[i] < obj.root_bbox_[i].low)
1408 {
1409 dists[i] =
1410 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].low, i);
1411 dist += dists[i];
1412 }
1413 if (vec[i] > obj.root_bbox_[i].high)
1414 {
1415 dists[i] =
1416 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].high, i);
1417 dist += dists[i];
1418 }
1419 }
1420 return dist;
1421 }
1422
1423 static void save_tree(
1424 const Derived& obj, std::ostream& stream, const NodeConstPtr tree)
1425 {
1426 save_value(stream, *tree);
1427 if (tree->child1 != nullptr) { save_tree(obj, stream, tree->child1); }
1428 if (tree->child2 != nullptr) { save_tree(obj, stream, tree->child2); }
1429 }
1430
1431 static void load_tree(Derived& obj, std::istream& stream, NodePtr& tree)
1432 {
1433 tree = obj.pool_.template allocate<Node>();
1434 load_value(stream, *tree);
1435 if (tree->child1 != nullptr) { load_tree(obj, stream, tree->child1); }
1436 if (tree->child2 != nullptr) { load_tree(obj, stream, tree->child2); }
1437 }
1438
1444 void saveIndex(const Derived& obj, std::ostream& stream) const
1445 {
1446 save_value(stream, obj.size_);
1447 save_value(stream, obj.dim_);
1448 save_value(stream, obj.root_bbox_);
1449 save_value(stream, obj.leaf_max_size_);
1450 save_value(stream, obj.vAcc_);
1451 if (obj.root_node_) save_tree(obj, stream, obj.root_node_);
1452 }
1453
1459 void loadIndex(Derived& obj, std::istream& stream)
1460 {
1461 load_value(stream, obj.size_);
1462 load_value(stream, obj.dim_);
1463 load_value(stream, obj.root_bbox_);
1464 load_value(stream, obj.leaf_max_size_);
1465 load_value(stream, obj.vAcc_);
1466 load_tree(obj, stream, obj.root_node_);
1467 }
1468};
1469
1511template <
1512 typename Distance, class DatasetAdaptor, int32_t DIM = -1,
1513 typename index_t = uint32_t>
1515 : public KDTreeBaseClass<
1516 KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, index_t>,
1517 Distance, DatasetAdaptor, DIM, index_t>
1518{
1519 public:
1523 Distance, DatasetAdaptor, DIM, index_t>&) = delete;
1524
1526 const DatasetAdaptor& dataset_;
1527
1528 const KDTreeSingleIndexAdaptorParams indexParams;
1529
1530 Distance distance_;
1531
1532 using Base = typename nanoflann::KDTreeBaseClass<
1534 Distance, DatasetAdaptor, DIM, index_t>,
1535 Distance, DatasetAdaptor, DIM, index_t>;
1536
1537 using Offset = typename Base::Offset;
1538 using Size = typename Base::Size;
1539 using Dimension = typename Base::Dimension;
1540
1541 using ElementType = typename Base::ElementType;
1542 using DistanceType = typename Base::DistanceType;
1543 using IndexType = typename Base::IndexType;
1544
1545 using Node = typename Base::Node;
1546 using NodePtr = Node*;
1547
1548 using Interval = typename Base::Interval;
1549
1552 using BoundingBox = typename Base::BoundingBox;
1553
1556 using distance_vector_t = typename Base::distance_vector_t;
1557
1578 template <class... Args>
1580 const Dimension dimensionality, const DatasetAdaptor& inputData,
1581 const KDTreeSingleIndexAdaptorParams& params, Args&&... args)
1582 : dataset_(inputData),
1583 indexParams(params),
1584 distance_(inputData, std::forward<Args>(args)...)
1585 {
1586 init(dimensionality, params);
1587 }
1588
1589 explicit KDTreeSingleIndexAdaptor(
1590 const Dimension dimensionality, const DatasetAdaptor& inputData,
1591 const KDTreeSingleIndexAdaptorParams& params = {})
1592 : dataset_(inputData), indexParams(params), distance_(inputData)
1593 {
1594 init(dimensionality, params);
1595 }
1596
1597 private:
1598 void init(
1599 const Dimension dimensionality,
1600 const KDTreeSingleIndexAdaptorParams& params)
1601 {
1602 Base::size_ = dataset_.kdtree_get_point_count();
1603 Base::size_at_index_build_ = Base::size_;
1604 Base::dim_ = dimensionality;
1605 if (DIM > 0) Base::dim_ = DIM;
1606 Base::leaf_max_size_ = params.leaf_max_size;
1607 if (params.n_thread_build > 0)
1608 {
1609 Base::n_thread_build_ = params.n_thread_build;
1610 }
1611 else
1612 {
1613 Base::n_thread_build_ =
1614 std::max(std::thread::hardware_concurrency(), 1u);
1615 }
1616
1617 if (!(params.flags &
1618 KDTreeSingleIndexAdaptorFlags::SkipInitialBuildIndex))
1619 {
1620 // Build KD-tree:
1621 buildIndex();
1622 }
1623 }
1624
1625 public:
1630 {
1631 Base::size_ = dataset_.kdtree_get_point_count();
1632 Base::size_at_index_build_ = Base::size_;
1633 init_vind();
1634 this->freeIndex(*this);
1635 Base::size_at_index_build_ = Base::size_;
1636 if (Base::size_ == 0) return;
1637 computeBoundingBox(Base::root_bbox_);
1638 // construct the tree
1639 if (Base::n_thread_build_ == 1)
1640 {
1641 Base::root_node_ =
1642 this->divideTree(*this, 0, Base::size_, Base::root_bbox_);
1643 }
1644 else
1645 {
1646#ifndef NANOFLANN_NO_THREADS
1647 std::atomic<unsigned int> thread_count(0u);
1648 std::mutex mutex;
1649 Base::root_node_ = this->divideTreeConcurrent(
1650 *this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
1651#else /* NANOFLANN_NO_THREADS */
1652 throw std::runtime_error("Multithreading is disabled");
1653#endif /* NANOFLANN_NO_THREADS */
1654 }
1655 }
1656
1676 template <typename RESULTSET>
1678 RESULTSET& result, const ElementType* vec,
1679 const SearchParameters& searchParams = {}) const
1680 {
1681 assert(vec);
1682 if (this->size(*this) == 0) return false;
1683 if (!Base::root_node_)
1684 throw std::runtime_error(
1685 "[nanoflann] findNeighbors() called before building the "
1686 "index.");
1687 float epsError = 1 + searchParams.eps;
1688
1689 // fixed or variable-sized container (depending on DIM)
1690 distance_vector_t dists;
1691 // Fill it with zeros.
1692 auto zero = static_cast<decltype(result.worstDist())>(0);
1693 assign(dists, (DIM > 0 ? DIM : Base::dim_), zero);
1694 DistanceType dist = this->computeInitialDistances(*this, vec, dists);
1695 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
1696
1697 if (searchParams.sorted) result.sort();
1698
1699 return result.full();
1700 }
1701
1718 const ElementType* query_point, const Size num_closest,
1719 IndexType* out_indices, DistanceType* out_distances) const
1720 {
1722 resultSet.init(out_indices, out_distances);
1723 findNeighbors(resultSet, query_point);
1724 return resultSet.size();
1725 }
1726
1747 const ElementType* query_point, const DistanceType& radius,
1748 std::vector<ResultItem<IndexType, DistanceType>>& IndicesDists,
1749 const SearchParameters& searchParams = {}) const
1750 {
1752 radius, IndicesDists);
1753 const Size nFound =
1754 radiusSearchCustomCallback(query_point, resultSet, searchParams);
1755 return nFound;
1756 }
1757
1763 template <class SEARCH_CALLBACK>
1765 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
1766 const SearchParameters& searchParams = {}) const
1767 {
1768 findNeighbors(resultSet, query_point, searchParams);
1769 return resultSet.size();
1770 }
1771
1789 const ElementType* query_point, const Size num_closest,
1790 IndexType* out_indices, DistanceType* out_distances,
1791 const DistanceType& radius) const
1792 {
1794 num_closest, radius);
1795 resultSet.init(out_indices, out_distances);
1796 findNeighbors(resultSet, query_point);
1797 return resultSet.size();
1798 }
1799
1802 public:
1806 {
1807 // Create a permutable array of indices to the input vectors.
1808 Base::size_ = dataset_.kdtree_get_point_count();
1809 if (Base::vAcc_.size() != Base::size_) Base::vAcc_.resize(Base::size_);
1810 for (Size i = 0; i < Base::size_; i++) Base::vAcc_[i] = i;
1811 }
1812
1813 void computeBoundingBox(BoundingBox& bbox)
1814 {
1815 const auto dims = (DIM > 0 ? DIM : Base::dim_);
1816 resize(bbox, dims);
1817 if (dataset_.kdtree_get_bbox(bbox))
1818 {
1819 // Done! It was implemented in derived class
1820 }
1821 else
1822 {
1823 const Size N = dataset_.kdtree_get_point_count();
1824 if (!N)
1825 throw std::runtime_error(
1826 "[nanoflann] computeBoundingBox() called but "
1827 "no data points found.");
1828 for (Dimension i = 0; i < dims; ++i)
1829 {
1830 bbox[i].low = bbox[i].high =
1831 this->dataset_get(*this, Base::vAcc_[0], i);
1832 }
1833 for (Offset k = 1; k < N; ++k)
1834 {
1835 for (Dimension i = 0; i < dims; ++i)
1836 {
1837 const auto val =
1838 this->dataset_get(*this, Base::vAcc_[k], i);
1839 if (val < bbox[i].low) bbox[i].low = val;
1840 if (val > bbox[i].high) bbox[i].high = val;
1841 }
1842 }
1843 }
1844 }
1845
1852 template <class RESULTSET>
1854 RESULTSET& result_set, const ElementType* vec, const NodePtr node,
1855 DistanceType mindist, distance_vector_t& dists,
1856 const float epsError) const
1857 {
1858 /* If this is a leaf node, then do check and return. */
1859 if ((node->child1 == nullptr) && (node->child2 == nullptr))
1860 {
1861 DistanceType worst_dist = result_set.worstDist();
1862 for (Offset i = node->node_type.lr.left;
1863 i < node->node_type.lr.right; ++i)
1864 {
1865 const IndexType accessor = Base::vAcc_[i]; // reorder... : i;
1866 DistanceType dist = distance_.evalMetric(
1867 vec, accessor, (DIM > 0 ? DIM : Base::dim_));
1868 if (dist < worst_dist)
1869 {
1870 if (!result_set.addPoint(dist, Base::vAcc_[i]))
1871 {
1872 // the resultset doesn't want to receive any more
1873 // points, we're done searching!
1874 return false;
1875 }
1876 }
1877 }
1878 return true;
1879 }
1880
1881 /* Which child branch should be taken first? */
1882 Dimension idx = node->node_type.sub.divfeat;
1883 ElementType val = vec[idx];
1884 DistanceType diff1 = val - node->node_type.sub.divlow;
1885 DistanceType diff2 = val - node->node_type.sub.divhigh;
1886
1887 NodePtr bestChild;
1888 NodePtr otherChild;
1889 DistanceType cut_dist;
1890 if ((diff1 + diff2) < 0)
1891 {
1892 bestChild = node->child1;
1893 otherChild = node->child2;
1894 cut_dist =
1895 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
1896 }
1897 else
1898 {
1899 bestChild = node->child2;
1900 otherChild = node->child1;
1901 cut_dist =
1902 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
1903 }
1904
1905 /* Call recursively to search next level down. */
1906 if (!searchLevel(result_set, vec, bestChild, mindist, dists, epsError))
1907 {
1908 // the resultset doesn't want to receive any more points, we're done
1909 // searching!
1910 return false;
1911 }
1912
1913 DistanceType dst = dists[idx];
1914 mindist = mindist + cut_dist - dst;
1915 dists[idx] = cut_dist;
1916 if (mindist * epsError <= result_set.worstDist())
1917 {
1918 if (!searchLevel(
1919 result_set, vec, otherChild, mindist, dists, epsError))
1920 {
1921 // the resultset doesn't want to receive any more points, we're
1922 // done searching!
1923 return false;
1924 }
1925 }
1926 dists[idx] = dst;
1927 return true;
1928 }
1929
1930 public:
1936 void saveIndex(std::ostream& stream) const
1937 {
1938 Base::saveIndex(*this, stream);
1939 }
1940
1946 void loadIndex(std::istream& stream) { Base::loadIndex(*this, stream); }
1947
1948}; // class KDTree
1949
1987template <
1988 typename Distance, class DatasetAdaptor, int32_t DIM = -1,
1989 typename IndexType = uint32_t>
1991 : public KDTreeBaseClass<
1992 KDTreeSingleIndexDynamicAdaptor_<
1993 Distance, DatasetAdaptor, DIM, IndexType>,
1994 Distance, DatasetAdaptor, DIM, IndexType>
1995{
1996 public:
2000 const DatasetAdaptor& dataset_;
2001
2002 KDTreeSingleIndexAdaptorParams index_params_;
2003
2004 std::vector<int>& treeIndex_;
2005
2006 Distance distance_;
2007
2008 using Base = typename nanoflann::KDTreeBaseClass<
2010 Distance, DatasetAdaptor, DIM, IndexType>,
2011 Distance, DatasetAdaptor, DIM, IndexType>;
2012
2013 using ElementType = typename Base::ElementType;
2014 using DistanceType = typename Base::DistanceType;
2015
2016 using Offset = typename Base::Offset;
2017 using Size = typename Base::Size;
2018 using Dimension = typename Base::Dimension;
2019
2020 using Node = typename Base::Node;
2021 using NodePtr = Node*;
2022
2023 using Interval = typename Base::Interval;
2026 using BoundingBox = typename Base::BoundingBox;
2027
2030 using distance_vector_t = typename Base::distance_vector_t;
2031
2048 const Dimension dimensionality, const DatasetAdaptor& inputData,
2049 std::vector<int>& treeIndex,
2050 const KDTreeSingleIndexAdaptorParams& params =
2052 : dataset_(inputData),
2053 index_params_(params),
2054 treeIndex_(treeIndex),
2055 distance_(inputData)
2056 {
2057 Base::size_ = 0;
2058 Base::size_at_index_build_ = 0;
2059 for (auto& v : Base::root_bbox_) v = {};
2060 Base::dim_ = dimensionality;
2061 if (DIM > 0) Base::dim_ = DIM;
2062 Base::leaf_max_size_ = params.leaf_max_size;
2063 if (params.n_thread_build > 0)
2064 {
2065 Base::n_thread_build_ = params.n_thread_build;
2066 }
2067 else
2068 {
2069 Base::n_thread_build_ =
2070 std::max(std::thread::hardware_concurrency(), 1u);
2071 }
2072 }
2073
2076 const KDTreeSingleIndexDynamicAdaptor_& rhs) = default;
2077
2081 {
2083 std::swap(Base::vAcc_, tmp.Base::vAcc_);
2084 std::swap(Base::leaf_max_size_, tmp.Base::leaf_max_size_);
2085 std::swap(index_params_, tmp.index_params_);
2086 std::swap(treeIndex_, tmp.treeIndex_);
2087 std::swap(Base::size_, tmp.Base::size_);
2088 std::swap(Base::size_at_index_build_, tmp.Base::size_at_index_build_);
2089 std::swap(Base::root_node_, tmp.Base::root_node_);
2090 std::swap(Base::root_bbox_, tmp.Base::root_bbox_);
2091 std::swap(Base::pool_, tmp.Base::pool_);
2092 return *this;
2093 }
2094
2099 {
2100 Base::size_ = Base::vAcc_.size();
2101 this->freeIndex(*this);
2102 Base::size_at_index_build_ = Base::size_;
2103 if (Base::size_ == 0) return;
2104 computeBoundingBox(Base::root_bbox_);
2105 // construct the tree
2106 if (Base::n_thread_build_ == 1)
2107 {
2108 Base::root_node_ =
2109 this->divideTree(*this, 0, Base::size_, Base::root_bbox_);
2110 }
2111 else
2112 {
2113#ifndef NANOFLANN_NO_THREADS
2114 std::atomic<unsigned int> thread_count(0u);
2115 std::mutex mutex;
2116 Base::root_node_ = this->divideTreeConcurrent(
2117 *this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
2118#else /* NANOFLANN_NO_THREADS */
2119 throw std::runtime_error("Multithreading is disabled");
2120#endif /* NANOFLANN_NO_THREADS */
2121 }
2122 }
2123
2147 template <typename RESULTSET>
2149 RESULTSET& result, const ElementType* vec,
2150 const SearchParameters& searchParams = {}) const
2151 {
2152 assert(vec);
2153 if (this->size(*this) == 0) return false;
2154 if (!Base::root_node_) return false;
2155 float epsError = 1 + searchParams.eps;
2156
2157 // fixed or variable-sized container (depending on DIM)
2158 distance_vector_t dists;
2159 // Fill it with zeros.
2160 assign(
2161 dists, (DIM > 0 ? DIM : Base::dim_),
2162 static_cast<typename distance_vector_t::value_type>(0));
2163 DistanceType dist = this->computeInitialDistances(*this, vec, dists);
2164 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
2165 return result.full();
2166 }
2167
2183 const ElementType* query_point, const Size num_closest,
2184 IndexType* out_indices, DistanceType* out_distances,
2185 const SearchParameters& searchParams = {}) const
2186 {
2188 resultSet.init(out_indices, out_distances);
2189 findNeighbors(resultSet, query_point, searchParams);
2190 return resultSet.size();
2191 }
2192
2213 const ElementType* query_point, const DistanceType& radius,
2214 std::vector<ResultItem<IndexType, DistanceType>>& IndicesDists,
2215 const SearchParameters& searchParams = {}) const
2216 {
2218 radius, IndicesDists);
2219 const size_t nFound =
2220 radiusSearchCustomCallback(query_point, resultSet, searchParams);
2221 return nFound;
2222 }
2223
2229 template <class SEARCH_CALLBACK>
2231 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
2232 const SearchParameters& searchParams = {}) const
2233 {
2234 findNeighbors(resultSet, query_point, searchParams);
2235 return resultSet.size();
2236 }
2237
2240 public:
2241 void computeBoundingBox(BoundingBox& bbox)
2242 {
2243 const auto dims = (DIM > 0 ? DIM : Base::dim_);
2244 resize(bbox, dims);
2245
2246 if (dataset_.kdtree_get_bbox(bbox))
2247 {
2248 // Done! It was implemented in derived class
2249 }
2250 else
2251 {
2252 const Size N = Base::size_;
2253 if (!N)
2254 throw std::runtime_error(
2255 "[nanoflann] computeBoundingBox() called but "
2256 "no data points found.");
2257 for (Dimension i = 0; i < dims; ++i)
2258 {
2259 bbox[i].low = bbox[i].high =
2260 this->dataset_get(*this, Base::vAcc_[0], i);
2261 }
2262 for (Offset k = 1; k < N; ++k)
2263 {
2264 for (Dimension i = 0; i < dims; ++i)
2265 {
2266 const auto val =
2267 this->dataset_get(*this, Base::vAcc_[k], i);
2268 if (val < bbox[i].low) bbox[i].low = val;
2269 if (val > bbox[i].high) bbox[i].high = val;
2270 }
2271 }
2272 }
2273 }
2274
2279 template <class RESULTSET>
2281 RESULTSET& result_set, const ElementType* vec, const NodePtr node,
2282 DistanceType mindist, distance_vector_t& dists,
2283 const float epsError) const
2284 {
2285 /* If this is a leaf node, then do check and return. */
2286 if ((node->child1 == nullptr) && (node->child2 == nullptr))
2287 {
2288 DistanceType worst_dist = result_set.worstDist();
2289 for (Offset i = node->node_type.lr.left;
2290 i < node->node_type.lr.right; ++i)
2291 {
2292 const IndexType index = Base::vAcc_[i]; // reorder... : i;
2293 if (treeIndex_[index] == -1) continue;
2294 DistanceType dist = distance_.evalMetric(
2295 vec, index, (DIM > 0 ? DIM : Base::dim_));
2296 if (dist < worst_dist)
2297 {
2298 if (!result_set.addPoint(
2299 static_cast<typename RESULTSET::DistanceType>(dist),
2300 static_cast<typename RESULTSET::IndexType>(
2301 Base::vAcc_[i])))
2302 {
2303 // the resultset doesn't want to receive any more
2304 // points, we're done searching!
2305 return; // false;
2306 }
2307 }
2308 }
2309 return;
2310 }
2311
2312 /* Which child branch should be taken first? */
2313 Dimension idx = node->node_type.sub.divfeat;
2314 ElementType val = vec[idx];
2315 DistanceType diff1 = val - node->node_type.sub.divlow;
2316 DistanceType diff2 = val - node->node_type.sub.divhigh;
2317
2318 NodePtr bestChild;
2319 NodePtr otherChild;
2320 DistanceType cut_dist;
2321 if ((diff1 + diff2) < 0)
2322 {
2323 bestChild = node->child1;
2324 otherChild = node->child2;
2325 cut_dist =
2326 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
2327 }
2328 else
2329 {
2330 bestChild = node->child2;
2331 otherChild = node->child1;
2332 cut_dist =
2333 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
2334 }
2335
2336 /* Call recursively to search next level down. */
2337 searchLevel(result_set, vec, bestChild, mindist, dists, epsError);
2338
2339 DistanceType dst = dists[idx];
2340 mindist = mindist + cut_dist - dst;
2341 dists[idx] = cut_dist;
2342 if (mindist * epsError <= result_set.worstDist())
2343 {
2344 searchLevel(result_set, vec, otherChild, mindist, dists, epsError);
2345 }
2346 dists[idx] = dst;
2347 }
2348
2349 public:
2355 void saveIndex(std::ostream& stream) { saveIndex(*this, stream); }
2356
2362 void loadIndex(std::istream& stream) { loadIndex(*this, stream); }
2363};
2364
2379template <
2380 typename Distance, class DatasetAdaptor, int32_t DIM = -1,
2381 typename IndexType = uint32_t>
2383{
2384 public:
2385 using ElementType = typename Distance::ElementType;
2386 using DistanceType = typename Distance::DistanceType;
2387
2388 using Offset = typename KDTreeSingleIndexDynamicAdaptor_<
2389 Distance, DatasetAdaptor, DIM>::Offset;
2390 using Size = typename KDTreeSingleIndexDynamicAdaptor_<
2391 Distance, DatasetAdaptor, DIM>::Size;
2392 using Dimension = typename KDTreeSingleIndexDynamicAdaptor_<
2393 Distance, DatasetAdaptor, DIM>::Dimension;
2394
2395 protected:
2396 Size leaf_max_size_;
2397 Size treeCount_;
2398 Size pointCount_;
2399
2403 const DatasetAdaptor& dataset_;
2404
2407 std::vector<int> treeIndex_;
2408 std::unordered_set<int> removedPoints_;
2409
2410 KDTreeSingleIndexAdaptorParams index_params_;
2411
2412 Dimension dim_;
2413
2415 Distance, DatasetAdaptor, DIM, IndexType>;
2416 std::vector<index_container_t> index_;
2417
2418 public:
2421 const std::vector<index_container_t>& getAllIndices() const
2422 {
2423 return index_;
2424 }
2425
2426 private:
2428 int First0Bit(IndexType num)
2429 {
2430 int pos = 0;
2431 while (num & 1)
2432 {
2433 num = num >> 1;
2434 pos++;
2435 }
2436 return pos;
2437 }
2438
2440 void init()
2441 {
2442 using my_kd_tree_t = KDTreeSingleIndexDynamicAdaptor_<
2443 Distance, DatasetAdaptor, DIM, IndexType>;
2444 std::vector<my_kd_tree_t> index(
2445 treeCount_,
2446 my_kd_tree_t(dim_ /*dim*/, dataset_, treeIndex_, index_params_));
2447 index_ = index;
2448 }
2449
2450 public:
2451 Distance distance_;
2452
2469 const int dimensionality, const DatasetAdaptor& inputData,
2470 const KDTreeSingleIndexAdaptorParams& params =
2472 const size_t maximumPointCount = 1000000000U)
2473 : dataset_(inputData), index_params_(params), distance_(inputData)
2474 {
2475 treeCount_ = static_cast<size_t>(std::log2(maximumPointCount)) + 1;
2476 pointCount_ = 0U;
2477 dim_ = dimensionality;
2478 treeIndex_.clear();
2479 if (DIM > 0) dim_ = DIM;
2480 leaf_max_size_ = params.leaf_max_size;
2481 init();
2482 const size_t num_initial_points = dataset_.kdtree_get_point_count();
2483 if (num_initial_points > 0) { addPoints(0, num_initial_points - 1); }
2484 }
2485
2489 Distance, DatasetAdaptor, DIM, IndexType>&) = delete;
2490
2492 void addPoints(IndexType start, IndexType end)
2493 {
2494 const Size count = end - start + 1;
2495 int maxIndex = 0;
2496 treeIndex_.resize(treeIndex_.size() + count);
2497 for (IndexType idx = start; idx <= end; idx++)
2498 {
2499 const int pos = First0Bit(pointCount_);
2500 maxIndex = std::max(pos, maxIndex);
2501 treeIndex_[pointCount_] = pos;
2502
2503 const auto it = removedPoints_.find(idx);
2504 if (it != removedPoints_.end())
2505 {
2506 removedPoints_.erase(it);
2507 treeIndex_[idx] = pos;
2508 }
2509
2510 for (int i = 0; i < pos; i++)
2511 {
2512 for (int j = 0; j < static_cast<int>(index_[i].vAcc_.size());
2513 j++)
2514 {
2515 index_[pos].vAcc_.push_back(index_[i].vAcc_[j]);
2516 if (treeIndex_[index_[i].vAcc_[j]] != -1)
2517 treeIndex_[index_[i].vAcc_[j]] = pos;
2518 }
2519 index_[i].vAcc_.clear();
2520 }
2521 index_[pos].vAcc_.push_back(idx);
2522 pointCount_++;
2523 }
2524
2525 for (int i = 0; i <= maxIndex; ++i)
2526 {
2527 index_[i].freeIndex(index_[i]);
2528 if (!index_[i].vAcc_.empty()) index_[i].buildIndex();
2529 }
2530 }
2531
2533 void removePoint(size_t idx)
2534 {
2535 if (idx >= pointCount_) return;
2536 removedPoints_.insert(idx);
2537 treeIndex_[idx] = -1;
2538 }
2539
2556 template <typename RESULTSET>
2558 RESULTSET& result, const ElementType* vec,
2559 const SearchParameters& searchParams = {}) const
2560 {
2561 for (size_t i = 0; i < treeCount_; i++)
2562 {
2563 index_[i].findNeighbors(result, &vec[0], searchParams);
2564 }
2565 return result.full();
2566 }
2567};
2568
2594template <
2595 class MatrixType, int32_t DIM = -1, class Distance = nanoflann::metric_L2,
2596 bool row_major = true>
2598{
2599 using self_t =
2601 using num_t = typename MatrixType::Scalar;
2602 using IndexType = typename MatrixType::Index;
2603 using metric_t = typename Distance::template traits<
2604 num_t, self_t, IndexType>::distance_t;
2605
2607 metric_t, self_t,
2608 row_major ? MatrixType::ColsAtCompileTime
2609 : MatrixType::RowsAtCompileTime,
2610 IndexType>;
2611
2612 index_t* index_;
2614
2615 using Offset = typename index_t::Offset;
2616 using Size = typename index_t::Size;
2617 using Dimension = typename index_t::Dimension;
2618
2621 const Dimension dimensionality,
2622 const std::reference_wrapper<const MatrixType>& mat,
2623 const int leaf_max_size = 10)
2624 : m_data_matrix(mat)
2625 {
2626 const auto dims = row_major ? mat.get().cols() : mat.get().rows();
2627 if (static_cast<Dimension>(dims) != dimensionality)
2628 throw std::runtime_error(
2629 "Error: 'dimensionality' must match column count in data "
2630 "matrix");
2631 if (DIM > 0 && static_cast<int32_t>(dims) != DIM)
2632 throw std::runtime_error(
2633 "Data set dimensionality does not match the 'DIM' template "
2634 "argument");
2635 index_ = new index_t(
2636 dims, *this /* adaptor */,
2638 }
2639
2640 public:
2643
2644 ~KDTreeEigenMatrixAdaptor() { delete index_; }
2645
2646 const std::reference_wrapper<const MatrixType> m_data_matrix;
2647
2656 void query(
2657 const num_t* query_point, const Size num_closest,
2658 IndexType* out_indices, num_t* out_distances) const
2659 {
2660 nanoflann::KNNResultSet<num_t, IndexType> resultSet(num_closest);
2661 resultSet.init(out_indices, out_distances);
2662 index_->findNeighbors(resultSet, query_point);
2663 }
2664
2668 const self_t& derived() const { return *this; }
2669 self_t& derived() { return *this; }
2670
2671 // Must return the number of data points
2672 Size kdtree_get_point_count() const
2673 {
2674 if (row_major)
2675 return m_data_matrix.get().rows();
2676 else
2677 return m_data_matrix.get().cols();
2678 }
2679
2680 // Returns the dim'th component of the idx'th point in the class:
2681 num_t kdtree_get_pt(const IndexType idx, size_t dim) const
2682 {
2683 if (row_major)
2684 return m_data_matrix.get().coeff(idx, IndexType(dim));
2685 else
2686 return m_data_matrix.get().coeff(IndexType(dim), idx);
2687 }
2688
2689 // Optional bounding-box computation: return false to default to a standard
2690 // bbox computation loop.
2691 // Return true if the BBOX was already computed by the class and returned
2692 // in "bb" so it can be avoided to redo it again. Look at bb.size() to
2693 // find out the expected dimensionality (e.g. 2 or 3 for point clouds)
2694 template <class BBOX>
2695 bool kdtree_get_bbox(BBOX& /*bb*/) const
2696 {
2697 return false;
2698 }
2699
2702}; // end of KDTreeEigenMatrixAdaptor
// end of grouping
2706} // namespace nanoflann
Definition nanoflann.hpp:1002
void freeIndex(Derived &obj)
Definition nanoflann.hpp:1006
BoundingBox root_bbox_
Definition nanoflann.hpp:1080
Size veclen(const Derived &obj)
Definition nanoflann.hpp:1095
void saveIndex(const Derived &obj, std::ostream &stream) const
Definition nanoflann.hpp:1444
Size usedMemory(Derived &obj)
Definition nanoflann.hpp:1108
typename array_or_vector< DIM, DistanceType >::type distance_vector_t
Definition nanoflann.hpp:1077
void planeSplit(const Derived &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)
Definition nanoflann.hpp:1354
NodePtr divideTree(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox)
Definition nanoflann.hpp:1136
std::vector< IndexType > vAcc_
Definition nanoflann.hpp:1020
Size size(const Derived &obj) const
Definition nanoflann.hpp:1092
NodePtr divideTreeConcurrent(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex)
Definition nanoflann.hpp:1205
void loadIndex(Derived &obj, std::istream &stream)
Definition nanoflann.hpp:1459
PooledAllocator pool_
Definition nanoflann.hpp:1089
ElementType dataset_get(const Derived &obj, IndexType element, Dimension component) const
Helper accessor to the dataset points:
Definition nanoflann.hpp:1098
typename array_or_vector< DIM, Interval >::type BoundingBox
Definition nanoflann.hpp:1073
Definition nanoflann.hpp:1518
bool searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:1853
void saveIndex(std::ostream &stream) const
Definition nanoflann.hpp:1936
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1746
void init_vind()
Definition nanoflann.hpp:1805
void buildIndex()
Definition nanoflann.hpp:1629
const DatasetAdaptor & dataset_
Definition nanoflann.hpp:1526
KDTreeSingleIndexAdaptor(const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t > &)=delete
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1677
Size rknnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const
Definition nanoflann.hpp:1788
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1764
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:1556
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:1946
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:1552
KDTreeSingleIndexAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params, Args &&... args)
Definition nanoflann.hpp:1579
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances) const
Definition nanoflann.hpp:1717
Definition nanoflann.hpp:1995
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2212
KDTreeSingleIndexDynamicAdaptor_(const Dimension dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
Definition nanoflann.hpp:2047
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:2026
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:2000
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2230
KDTreeSingleIndexDynamicAdaptor_(const KDTreeSingleIndexDynamicAdaptor_ &rhs)=default
void buildIndex()
Definition nanoflann.hpp:2098
void saveIndex(std::ostream &stream)
Definition nanoflann.hpp:2355
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:2030
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:2362
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2182
void searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:2280
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2148
KDTreeSingleIndexDynamicAdaptor_ operator=(const KDTreeSingleIndexDynamicAdaptor_ &rhs)
Definition nanoflann.hpp:2079
Definition nanoflann.hpp:2383
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2557
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:2403
void removePoint(size_t idx)
Definition nanoflann.hpp:2533
void addPoints(IndexType start, IndexType end)
Definition nanoflann.hpp:2492
KDTreeSingleIndexDynamicAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams(), const size_t maximumPointCount=1000000000U)
Definition nanoflann.hpp:2468
std::vector< int > treeIndex_
Definition nanoflann.hpp:2407
const std::vector< index_container_t > & getAllIndices() const
Definition nanoflann.hpp:2421
Dimension dim_
Dimensionality of each data point.
Definition nanoflann.hpp:2412
KDTreeSingleIndexDynamicAdaptor(const KDTreeSingleIndexDynamicAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete
Definition nanoflann.hpp:201
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:237
Definition nanoflann.hpp:850
~PooledAllocator()
Definition nanoflann.hpp:886
void free_all()
Definition nanoflann.hpp:889
void * malloc(const size_t req_size)
Definition nanoflann.hpp:905
T * allocate(const size_t count=1)
Definition nanoflann.hpp:956
PooledAllocator()
Definition nanoflann.hpp:881
Definition nanoflann.hpp:285
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:326
Definition nanoflann.hpp:374
ResultItem< IndexType, DistanceType > worst_item() const
Definition nanoflann.hpp:417
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:405
std::enable_if< has_assign< Container >::value, void >::type assign(Container &c, const size_t nElements, const T &value)
Definition nanoflann.hpp:144
T pi_const()
Definition nanoflann.hpp:87
std::enable_if< has_resize< Container >::value, void >::type resize(Container &c, const size_t nElements)
Definition nanoflann.hpp:122
Definition nanoflann.hpp:163
bool operator()(const PairType &p1, const PairType &p2) const
Definition nanoflann.hpp:166
Definition nanoflann.hpp:1055
Definition nanoflann.hpp:1030
DistanceType divlow
The values used for subdivision.
Definition nanoflann.hpp:1043
Offset right
Indices of points in leaf node.
Definition nanoflann.hpp:1037
union nanoflann::KDTreeBaseClass::Node::@0 node_type
Dimension divfeat
Definition nanoflann.hpp:1041
Node * child1
Definition nanoflann.hpp:1048
Definition nanoflann.hpp:2598
void query(const num_t *query_point, const Size num_closest, IndexType *out_indices, num_t *out_distances) const
Definition nanoflann.hpp:2656
KDTreeEigenMatrixAdaptor(const Dimension 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:2620
KDTreeEigenMatrixAdaptor(const self_t &)=delete
typename index_t::Offset Offset
Definition nanoflann.hpp:2615
Definition nanoflann.hpp:801
Definition nanoflann.hpp:490
Definition nanoflann.hpp:552
Definition nanoflann.hpp:617
Definition nanoflann.hpp:473
Definition nanoflann.hpp:182
DistanceType second
Distance from sample to query point.
Definition nanoflann.hpp:190
IndexType first
Index of the sample in the dataset.
Definition nanoflann.hpp:189
Definition nanoflann.hpp:662
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition nanoflann.hpp:680
Definition nanoflann.hpp:707
Definition nanoflann.hpp:820
bool sorted
distance (default: true)
Definition nanoflann.hpp:827
float eps
search for eps-approximate neighbours (default: 0)
Definition nanoflann.hpp:826
Definition nanoflann.hpp:972
Definition nanoflann.hpp:109
Definition nanoflann.hpp:98
Definition nanoflann.hpp:737
Definition nanoflann.hpp:734
Definition nanoflann.hpp:747
Definition nanoflann.hpp:757
Definition nanoflann.hpp:754
Definition nanoflann.hpp:744
Definition nanoflann.hpp:766
Definition nanoflann.hpp:763
Definition nanoflann.hpp:775
Definition nanoflann.hpp:772