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-2025 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 0x170
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
162{
164 template <typename PairType>
165 bool operator()(const PairType& p1, const PairType& p2) const
166 {
167 return p1.second < p2.second;
168 }
169};
170
179template <typename IndexType = size_t, typename DistanceType = double>
181{
182 ResultItem() = default;
183 ResultItem(const IndexType index, const DistanceType distance)
184 : first(index), second(distance)
185 {
186 }
187
188 IndexType first;
189 DistanceType second;
190};
191
196template <
197 typename _DistanceType, typename _IndexType = size_t,
198 typename _CountType = size_t>
200{
201 public:
202 using DistanceType = _DistanceType;
203 using IndexType = _IndexType;
204 using CountType = _CountType;
205
206 private:
207 IndexType* indices;
208 DistanceType* dists;
209 CountType capacity;
210 CountType count;
211
212 public:
213 explicit KNNResultSet(CountType capacity_)
214 : indices(nullptr), dists(nullptr), capacity(capacity_), count(0)
215 {
216 }
217
218 void init(IndexType* indices_, DistanceType* dists_)
219 {
220 indices = indices_;
221 dists = dists_;
222 count = 0;
223 }
224
225 CountType size() const { return count; }
226 bool empty() const { return count == 0; }
227 bool full() const { return count == capacity; }
228
234 bool addPoint(DistanceType dist, IndexType index)
235 {
236 CountType i;
237 for (i = count; i > 0; --i)
238 {
241#ifdef NANOFLANN_FIRST_MATCH
242 if ((dists[i - 1] > dist) ||
243 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
244 {
245#else
246 if (dists[i - 1] > dist)
247 {
248#endif
249 if (i < capacity)
250 {
251 dists[i] = dists[i - 1];
252 indices[i] = indices[i - 1];
253 }
254 }
255 else
256 break;
257 }
258 if (i < capacity)
259 {
260 dists[i] = dist;
261 indices[i] = index;
262 }
263 if (count < capacity) count++;
264
265 // tell caller that the search shall continue
266 return true;
267 }
268
271 DistanceType worstDist() const
272 {
273 return count < capacity ? std::numeric_limits<DistanceType>::max()
274 : dists[count - 1];
275 }
276
277 void sort()
278 {
279 // already sorted
280 }
281};
282
284template <
285 typename _DistanceType, typename _IndexType = size_t,
286 typename _CountType = size_t>
288{
289 public:
290 using DistanceType = _DistanceType;
291 using IndexType = _IndexType;
292 using CountType = _CountType;
293
294 private:
295 IndexType* indices;
296 DistanceType* dists;
297 CountType capacity;
298 CountType count;
299 DistanceType maximumSearchDistanceSquared;
300
301 public:
302 explicit RKNNResultSet(
303 CountType capacity_, DistanceType maximumSearchDistanceSquared_)
304 : indices(nullptr),
305 dists(nullptr),
306 capacity(capacity_),
307 count(0),
308 maximumSearchDistanceSquared(maximumSearchDistanceSquared_)
309 {
310 }
311
312 void init(IndexType* indices_, DistanceType* dists_)
313 {
314 indices = indices_;
315 dists = dists_;
316 count = 0;
317 if (capacity) dists[capacity - 1] = maximumSearchDistanceSquared;
318 }
319
320 CountType size() const { return count; }
321 bool empty() const { return count == 0; }
322 bool full() const { return count == capacity; }
323
329 bool addPoint(DistanceType dist, IndexType index)
330 {
331 CountType i;
332 for (i = count; i > 0; --i)
333 {
336#ifdef NANOFLANN_FIRST_MATCH
337 if ((dists[i - 1] > dist) ||
338 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
339 {
340#else
341 if (dists[i - 1] > dist)
342 {
343#endif
344 if (i < capacity)
345 {
346 dists[i] = dists[i - 1];
347 indices[i] = indices[i - 1];
348 }
349 }
350 else
351 break;
352 }
353 if (i < capacity)
354 {
355 dists[i] = dist;
356 indices[i] = index;
357 }
358 if (count < capacity) count++;
359
360 // tell caller that the search shall continue
361 return true;
362 }
363
366 DistanceType worstDist() const
367 {
368 return count < capacity ? maximumSearchDistanceSquared
369 : dists[count - 1];
370 }
371
372 void sort()
373 {
374 // already sorted
375 }
376};
377
381template <typename _DistanceType, typename _IndexType = size_t>
383{
384 public:
385 using DistanceType = _DistanceType;
386 using IndexType = _IndexType;
387
388 public:
389 const DistanceType radius;
390
391 std::vector<ResultItem<IndexType, DistanceType>>& m_indices_dists;
392
393 explicit RadiusResultSet(
394 DistanceType radius_,
395 std::vector<ResultItem<IndexType, DistanceType>>& indices_dists)
396 : radius(radius_), m_indices_dists(indices_dists)
397 {
398 init();
399 }
400
401 void init() { clear(); }
402 void clear() { m_indices_dists.clear(); }
403
404 size_t size() const { return m_indices_dists.size(); }
405 size_t empty() const { return m_indices_dists.empty(); }
406
407 bool full() const { return true; }
408
414 bool addPoint(DistanceType dist, IndexType index)
415 {
416 if (dist < radius) m_indices_dists.emplace_back(index, dist);
417 return true;
418 }
419
420 DistanceType worstDist() const { return radius; }
421
427 {
428 if (m_indices_dists.empty())
429 throw std::runtime_error(
430 "Cannot invoke RadiusResultSet::worst_item() on "
431 "an empty list of results.");
432 auto it = std::max_element(
433 m_indices_dists.begin(), m_indices_dists.end(), IndexDist_Sorter());
434 return *it;
435 }
436
437 void sort()
438 {
439 std::sort(
440 m_indices_dists.begin(), m_indices_dists.end(), IndexDist_Sorter());
441 }
442};
443
448template <typename T>
449void save_value(std::ostream& stream, const T& value)
450{
451 stream.write(reinterpret_cast<const char*>(&value), sizeof(T));
452}
453
454template <typename T>
455void save_value(std::ostream& stream, const std::vector<T>& value)
456{
457 size_t size = value.size();
458 stream.write(reinterpret_cast<const char*>(&size), sizeof(size_t));
459 stream.write(reinterpret_cast<const char*>(value.data()), sizeof(T) * size);
460}
461
462template <typename T>
463void load_value(std::istream& stream, T& value)
464{
465 stream.read(reinterpret_cast<char*>(&value), sizeof(T));
466}
467
468template <typename T>
469void load_value(std::istream& stream, std::vector<T>& value)
470{
471 size_t size;
472 stream.read(reinterpret_cast<char*>(&size), sizeof(size_t));
473 value.resize(size);
474 stream.read(reinterpret_cast<char*>(value.data()), sizeof(T) * size);
475}
481struct Metric
482{
483};
484
495template <
496 class T, class DataSource, typename _DistanceType = T,
497 typename IndexType = uint32_t>
499{
500 using ElementType = T;
501 using DistanceType = _DistanceType;
502
503 const DataSource& data_source;
504
505 L1_Adaptor(const DataSource& _data_source) : data_source(_data_source) {}
506
507 DistanceType evalMetric(
508 const T* a, const IndexType b_idx, size_t size,
509 DistanceType worst_dist = -1) const
510 {
511 DistanceType result = DistanceType();
512 const T* last = a + size;
513 const T* lastgroup = last - 3;
514 size_t d = 0;
515
516 /* Process 4 items with each loop for efficiency. */
517 while (a < lastgroup)
518 {
519 const DistanceType diff0 =
520 std::abs(a[0] - data_source.kdtree_get_pt(b_idx, d++));
521 const DistanceType diff1 =
522 std::abs(a[1] - data_source.kdtree_get_pt(b_idx, d++));
523 const DistanceType diff2 =
524 std::abs(a[2] - data_source.kdtree_get_pt(b_idx, d++));
525 const DistanceType diff3 =
526 std::abs(a[3] - data_source.kdtree_get_pt(b_idx, d++));
527 result += diff0 + diff1 + diff2 + diff3;
528 a += 4;
529 if ((worst_dist > 0) && (result > worst_dist)) { return result; }
530 }
531 /* Process last 0-3 components. Not needed for standard vector lengths.
532 */
533 while (a < last)
534 {
535 result += std::abs(*a++ - data_source.kdtree_get_pt(b_idx, d++));
536 }
537 return result;
538 }
539
540 template <typename U, typename V>
541 DistanceType accum_dist(const U a, const V b, const size_t) const
542 {
543 return std::abs(a - b);
544 }
545};
546
557template <
558 class T, class DataSource, typename _DistanceType = T,
559 typename IndexType = uint32_t>
561{
562 using ElementType = T;
563 using DistanceType = _DistanceType;
564
565 const DataSource& data_source;
566
567 L2_Adaptor(const DataSource& _data_source) : data_source(_data_source) {}
568
569 DistanceType evalMetric(
570 const T* a, const IndexType b_idx, size_t size,
571 DistanceType worst_dist = -1) const
572 {
573 DistanceType result = DistanceType();
574 const T* last = a + size;
575 const T* lastgroup = last - 3;
576 size_t d = 0;
577
578 /* Process 4 items with each loop for efficiency. */
579 while (a < lastgroup)
580 {
581 const DistanceType diff0 =
582 a[0] - data_source.kdtree_get_pt(b_idx, d++);
583 const DistanceType diff1 =
584 a[1] - data_source.kdtree_get_pt(b_idx, d++);
585 const DistanceType diff2 =
586 a[2] - data_source.kdtree_get_pt(b_idx, d++);
587 const DistanceType diff3 =
588 a[3] - data_source.kdtree_get_pt(b_idx, d++);
589 result +=
590 diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
591 a += 4;
592 if ((worst_dist > 0) && (result > worst_dist)) { return result; }
593 }
594 /* Process last 0-3 components. Not needed for standard vector lengths.
595 */
596 while (a < last)
597 {
598 const DistanceType diff0 =
599 *a++ - data_source.kdtree_get_pt(b_idx, d++);
600 result += diff0 * diff0;
601 }
602 return result;
603 }
604
605 template <typename U, typename V>
606 DistanceType accum_dist(const U a, const V b, const size_t) const
607 {
608 return (a - b) * (a - b);
609 }
610};
611
622template <
623 class T, class DataSource, typename _DistanceType = T,
624 typename IndexType = uint32_t>
626{
627 using ElementType = T;
628 using DistanceType = _DistanceType;
629
630 const DataSource& data_source;
631
632 L2_Simple_Adaptor(const DataSource& _data_source)
633 : data_source(_data_source)
634 {
635 }
636
637 DistanceType evalMetric(
638 const T* a, const IndexType b_idx, size_t size) const
639 {
640 DistanceType result = DistanceType();
641 for (size_t i = 0; i < size; ++i)
642 {
643 const DistanceType diff =
644 a[i] - data_source.kdtree_get_pt(b_idx, i);
645 result += diff * diff;
646 }
647 return result;
648 }
649
650 template <typename U, typename V>
651 DistanceType accum_dist(const U a, const V b, const size_t) const
652 {
653 return (a - b) * (a - b);
654 }
655};
656
667template <
668 class T, class DataSource, typename _DistanceType = T,
669 typename IndexType = uint32_t>
671{
672 using ElementType = T;
673 using DistanceType = _DistanceType;
674
675 const DataSource& data_source;
676
677 SO2_Adaptor(const DataSource& _data_source) : data_source(_data_source) {}
678
679 DistanceType evalMetric(
680 const T* a, const IndexType b_idx, size_t size) const
681 {
682 return accum_dist(
683 a[size - 1], data_source.kdtree_get_pt(b_idx, size - 1), size - 1);
684 }
685
688 template <typename U, typename V>
689 DistanceType accum_dist(const U a, const V b, const size_t) const
690 {
691 DistanceType result = DistanceType();
692 DistanceType PI = pi_const<DistanceType>();
693 result = b - a;
694 if (result > PI)
695 result -= 2 * PI;
696 else if (result < -PI)
697 result += 2 * PI;
698 return result;
699 }
700};
701
712template <
713 class T, class DataSource, typename _DistanceType = T,
714 typename IndexType = uint32_t>
716{
717 using ElementType = T;
718 using DistanceType = _DistanceType;
719
721 distance_L2_Simple;
722
723 SO3_Adaptor(const DataSource& _data_source)
724 : distance_L2_Simple(_data_source)
725 {
726 }
727
728 DistanceType evalMetric(
729 const T* a, const IndexType b_idx, size_t size) const
730 {
731 return distance_L2_Simple.evalMetric(a, b_idx, size);
732 }
733
734 template <typename U, typename V>
735 DistanceType accum_dist(const U a, const V b, const size_t idx) const
736 {
737 return distance_L2_Simple.accum_dist(a, b, idx);
738 }
739};
740
742struct metric_L1 : public Metric
743{
744 template <class T, class DataSource, typename IndexType = uint32_t>
749};
752struct metric_L2 : public Metric
753{
754 template <class T, class DataSource, typename IndexType = uint32_t>
759};
763{
764 template <class T, class DataSource, typename IndexType = uint32_t>
769};
771struct metric_SO2 : public Metric
772{
773 template <class T, class DataSource, typename IndexType = uint32_t>
778};
780struct metric_SO3 : public Metric
781{
782 template <class T, class DataSource, typename IndexType = uint32_t>
787};
788
794enum class KDTreeSingleIndexAdaptorFlags
795{
796 None = 0,
797 SkipInitialBuildIndex = 1
798};
799
800inline std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type operator&(
801 KDTreeSingleIndexAdaptorFlags lhs, KDTreeSingleIndexAdaptorFlags rhs)
802{
803 using underlying =
804 typename std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type;
805 return static_cast<underlying>(lhs) & static_cast<underlying>(rhs);
806}
807
810{
812 size_t _leaf_max_size = 10,
813 KDTreeSingleIndexAdaptorFlags _flags =
814 KDTreeSingleIndexAdaptorFlags::None,
815 unsigned int _n_thread_build = 1)
816 : leaf_max_size(_leaf_max_size),
817 flags(_flags),
818 n_thread_build(_n_thread_build)
819 {
820 }
821
822 size_t leaf_max_size;
823 KDTreeSingleIndexAdaptorFlags flags;
824 unsigned int n_thread_build;
825};
826
829{
830 SearchParameters(float eps_ = 0, bool sorted_ = true)
831 : eps(eps_), sorted(sorted_)
832 {
833 }
834
835 float eps;
836 bool sorted;
838};
859{
860 static constexpr size_t WORDSIZE = 16; // WORDSIZE must >= 8
861 static constexpr size_t BLOCKSIZE = 8192;
862
863 /* We maintain memory alignment to word boundaries by requiring that all
864 allocations be in multiples of the machine wordsize. */
865 /* Size of machine word in bytes. Must be power of 2. */
866 /* Minimum number of bytes requested at a time from the system. Must be
867 * multiple of WORDSIZE. */
868
869 using Size = size_t;
870
871 Size remaining_ = 0;
872 void* base_ = nullptr;
873 void* loc_ = nullptr;
874
875 void internal_init()
876 {
877 remaining_ = 0;
878 base_ = nullptr;
879 usedMemory = 0;
880 wastedMemory = 0;
881 }
882
883 public:
884 Size usedMemory = 0;
885 Size wastedMemory = 0;
886
890 PooledAllocator() { internal_init(); }
891
895 ~PooledAllocator() { free_all(); }
896
898 void free_all()
899 {
900 while (base_ != nullptr)
901 {
902 // Get pointer to prev block
903 void* prev = *(static_cast<void**>(base_));
904 ::free(base_);
905 base_ = prev;
906 }
907 internal_init();
908 }
909
914 void* malloc(const size_t req_size)
915 {
916 /* Round size up to a multiple of wordsize. The following expression
917 only works for WORDSIZE that is a power of 2, by masking last bits
918 of incremented size to zero.
919 */
920 const Size size = (req_size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
921
922 /* Check whether a new block must be allocated. Note that the first
923 word of a block is reserved for a pointer to the previous block.
924 */
925 if (size > remaining_)
926 {
927 wastedMemory += remaining_;
928
929 /* Allocate new storage. */
930 const Size blocksize =
931 size > BLOCKSIZE ? size + WORDSIZE : BLOCKSIZE + WORDSIZE;
932
933 // use the standard C malloc to allocate memory
934 void* m = ::malloc(blocksize);
935 if (!m)
936 {
937 fprintf(stderr, "Failed to allocate memory.\n");
938 throw std::bad_alloc();
939 }
940
941 /* Fill first word of new block with pointer to previous block. */
942 static_cast<void**>(m)[0] = base_;
943 base_ = m;
944
945 remaining_ = blocksize - WORDSIZE;
946 loc_ = static_cast<char*>(m) + WORDSIZE;
947 }
948 void* rloc = loc_;
949 loc_ = static_cast<char*>(loc_) + size;
950 remaining_ -= size;
951
952 usedMemory += size;
953
954 return rloc;
955 }
956
964 template <typename T>
965 T* allocate(const size_t count = 1)
966 {
967 T* mem = static_cast<T*>(this->malloc(sizeof(T) * count));
968 return mem;
969 }
970};
979template <int32_t DIM, typename T>
981{
982 using type = std::array<T, DIM>;
983};
985template <typename T>
986struct array_or_vector<-1, T>
987{
988 using type = std::vector<T>;
989};
990
1007template <
1008 class Derived, typename Distance, class DatasetAdaptor, int32_t DIM = -1,
1009 typename index_t = uint32_t>
1011{
1012 public:
1015 void freeIndex(Derived& obj)
1016 {
1017 obj.pool_.free_all();
1018 obj.root_node_ = nullptr;
1019 obj.size_at_index_build_ = 0;
1020 }
1021
1022 using ElementType = typename Distance::ElementType;
1023 using DistanceType = typename Distance::DistanceType;
1024 using IndexType = index_t;
1025
1029 std::vector<IndexType> vAcc_;
1030
1031 using Offset = typename decltype(vAcc_)::size_type;
1032 using Size = typename decltype(vAcc_)::size_type;
1033 using Dimension = int32_t;
1034
1035 /*---------------------------
1036 * Internal Data Structures
1037 * --------------------------*/
1038 struct Node
1039 {
1042 union
1043 {
1044 struct leaf
1045 {
1046 Offset left, right;
1047 } lr;
1048 struct nonleaf
1049 {
1050 Dimension divfeat;
1052 DistanceType divlow, divhigh;
1053 } sub;
1054 } node_type;
1055
1057 Node *child1 = nullptr, *child2 = nullptr;
1058 };
1059
1060 using NodePtr = Node*;
1061 using NodeConstPtr = const Node*;
1062
1064 {
1065 ElementType low, high;
1066 };
1067
1068 NodePtr root_node_ = nullptr;
1069
1070 Size leaf_max_size_ = 0;
1071
1073 Size n_thread_build_ = 1;
1075 Size size_ = 0;
1077 Size size_at_index_build_ = 0;
1078 Dimension dim_ = 0;
1079
1082 using BoundingBox = typename array_or_vector<DIM, Interval>::type;
1083
1086 using distance_vector_t = typename array_or_vector<DIM, DistanceType>::type;
1087
1090
1099
1101 Size size(const Derived& obj) const { return obj.size_; }
1102
1104 Size veclen(const Derived& obj) { return DIM > 0 ? DIM : obj.dim; }
1105
1107 ElementType dataset_get(
1108 const Derived& obj, IndexType element, Dimension component) const
1109 {
1110 return obj.dataset_.kdtree_get_pt(element, component);
1111 }
1112
1117 Size usedMemory(Derived& obj)
1118 {
1119 return obj.pool_.usedMemory + obj.pool_.wastedMemory +
1120 obj.dataset_.kdtree_get_point_count() *
1121 sizeof(IndexType); // pool memory and vind array memory
1122 }
1123
1124 void computeMinMax(
1125 const Derived& obj, Offset ind, Size count, Dimension element,
1126 ElementType& min_elem, ElementType& max_elem)
1127 {
1128 min_elem = dataset_get(obj, vAcc_[ind], element);
1129 max_elem = min_elem;
1130 for (Offset i = 1; i < count; ++i)
1131 {
1132 ElementType val = dataset_get(obj, vAcc_[ind + i], element);
1133 if (val < min_elem) min_elem = val;
1134 if (val > max_elem) max_elem = val;
1135 }
1136 }
1137
1146 Derived& obj, const Offset left, const Offset right, BoundingBox& bbox)
1147 {
1148 assert(left < obj.dataset_.kdtree_get_point_count());
1149
1150 NodePtr node = obj.pool_.template allocate<Node>(); // allocate memory
1151 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1152
1153 /* If too few exemplars remain, then make this a leaf node. */
1154 if ((right - left) <= static_cast<Offset>(obj.leaf_max_size_))
1155 {
1156 node->child1 = node->child2 = nullptr; /* Mark as leaf node. */
1157 node->node_type.lr.left = left;
1158 node->node_type.lr.right = right;
1159
1160 // compute bounding-box of leaf points
1161 for (Dimension i = 0; i < dims; ++i)
1162 {
1163 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1164 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1165 }
1166 for (Offset k = left + 1; k < right; ++k)
1167 {
1168 for (Dimension i = 0; i < dims; ++i)
1169 {
1170 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1171 if (bbox[i].low > val) bbox[i].low = val;
1172 if (bbox[i].high < val) bbox[i].high = val;
1173 }
1174 }
1175 }
1176 else
1177 {
1178 Offset idx;
1179 Dimension cutfeat;
1180 DistanceType cutval;
1181 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1182
1183 node->node_type.sub.divfeat = cutfeat;
1184
1185 BoundingBox left_bbox(bbox);
1186 left_bbox[cutfeat].high = cutval;
1187 node->child1 = this->divideTree(obj, left, left + idx, left_bbox);
1188
1189 BoundingBox right_bbox(bbox);
1190 right_bbox[cutfeat].low = cutval;
1191 node->child2 = this->divideTree(obj, left + idx, right, right_bbox);
1192
1193 node->node_type.sub.divlow = left_bbox[cutfeat].high;
1194 node->node_type.sub.divhigh = right_bbox[cutfeat].low;
1195
1196 for (Dimension i = 0; i < dims; ++i)
1197 {
1198 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1199 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1200 }
1201 }
1202
1203 return node;
1204 }
1205
1217 Derived& obj, const Offset left, const Offset right, BoundingBox& bbox,
1218 std::atomic<unsigned int>& thread_count, std::mutex& mutex)
1219 {
1220 std::unique_lock<std::mutex> lock(mutex);
1221 NodePtr node = obj.pool_.template allocate<Node>(); // allocate memory
1222 lock.unlock();
1223
1224 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1225
1226 /* If too few exemplars remain, then make this a leaf node. */
1227 if ((right - left) <= static_cast<Offset>(obj.leaf_max_size_))
1228 {
1229 node->child1 = node->child2 = nullptr; /* Mark as leaf node. */
1230 node->node_type.lr.left = left;
1231 node->node_type.lr.right = right;
1232
1233 // compute bounding-box of leaf points
1234 for (Dimension i = 0; i < dims; ++i)
1235 {
1236 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1237 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1238 }
1239 for (Offset k = left + 1; k < right; ++k)
1240 {
1241 for (Dimension i = 0; i < dims; ++i)
1242 {
1243 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1244 if (bbox[i].low > val) bbox[i].low = val;
1245 if (bbox[i].high < val) bbox[i].high = val;
1246 }
1247 }
1248 }
1249 else
1250 {
1251 Offset idx;
1252 Dimension cutfeat;
1253 DistanceType cutval;
1254 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1255
1256 node->node_type.sub.divfeat = cutfeat;
1257
1258 std::future<NodePtr> right_future;
1259
1260 BoundingBox right_bbox(bbox);
1261 right_bbox[cutfeat].low = cutval;
1262 if (++thread_count < n_thread_build_)
1263 {
1264 // Concurrent right sub-tree
1265 right_future = std::async(
1266 std::launch::async, &KDTreeBaseClass::divideTreeConcurrent,
1267 this, std::ref(obj), left + idx, right,
1268 std::ref(right_bbox), std::ref(thread_count),
1269 std::ref(mutex));
1270 }
1271 else { --thread_count; }
1272
1273 BoundingBox left_bbox(bbox);
1274 left_bbox[cutfeat].high = cutval;
1275 node->child1 = this->divideTreeConcurrent(
1276 obj, left, left + idx, left_bbox, thread_count, mutex);
1277
1278 if (right_future.valid())
1279 {
1280 // Block and wait for concurrent right sub-tree
1281 node->child2 = right_future.get();
1282 --thread_count;
1283 }
1284 else
1285 {
1286 node->child2 = this->divideTreeConcurrent(
1287 obj, left + idx, right, right_bbox, thread_count, mutex);
1288 }
1289
1290 node->node_type.sub.divlow = left_bbox[cutfeat].high;
1291 node->node_type.sub.divhigh = right_bbox[cutfeat].low;
1292
1293 for (Dimension i = 0; i < dims; ++i)
1294 {
1295 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1296 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1297 }
1298 }
1299
1300 return node;
1301 }
1302
1303 void middleSplit_(
1304 const Derived& obj, const Offset ind, const Size count, Offset& index,
1305 Dimension& cutfeat, DistanceType& cutval, const BoundingBox& bbox)
1306 {
1307 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1308 const auto EPS = static_cast<DistanceType>(0.00001);
1309 ElementType max_span = bbox[0].high - bbox[0].low;
1310 for (Dimension i = 1; i < dims; ++i)
1311 {
1312 ElementType span = bbox[i].high - bbox[i].low;
1313 if (span > max_span) { max_span = span; }
1314 }
1315 ElementType max_spread = -1;
1316 cutfeat = 0;
1317 ElementType min_elem = 0, max_elem = 0;
1318 for (Dimension i = 0; i < dims; ++i)
1319 {
1320 ElementType span = bbox[i].high - bbox[i].low;
1321 if (span >= (1 - EPS) * max_span)
1322 {
1323 ElementType min_elem_, max_elem_;
1324 computeMinMax(obj, ind, count, i, min_elem_, max_elem_);
1325 ElementType spread = max_elem_ - min_elem_;
1326 if (spread > max_spread)
1327 {
1328 cutfeat = i;
1329 max_spread = spread;
1330 min_elem = min_elem_;
1331 max_elem = max_elem_;
1332 }
1333 }
1334 }
1335 // split in the middle
1336 DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;
1337
1338 if (split_val < min_elem)
1339 cutval = min_elem;
1340 else if (split_val > max_elem)
1341 cutval = max_elem;
1342 else
1343 cutval = split_val;
1344
1345 Offset lim1, lim2;
1346 planeSplit(obj, ind, count, cutfeat, cutval, lim1, lim2);
1347
1348 if (lim1 > count / 2)
1349 index = lim1;
1350 else if (lim2 < count / 2)
1351 index = lim2;
1352 else
1353 index = count / 2;
1354 }
1355
1366 const Derived& obj, const Offset ind, const Size count,
1367 const Dimension cutfeat, const DistanceType& cutval, Offset& lim1,
1368 Offset& lim2)
1369 {
1370 /* Move vector indices for left subtree to front of list. */
1371 Offset left = 0;
1372 Offset right = count - 1;
1373 for (;;)
1374 {
1375 while (left <= right &&
1376 dataset_get(obj, vAcc_[ind + left], cutfeat) < cutval)
1377 ++left;
1378 while (right && left <= right &&
1379 dataset_get(obj, vAcc_[ind + right], cutfeat) >= cutval)
1380 --right;
1381 if (left > right || !right)
1382 break; // "!right" was added to support unsigned Index types
1383 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1384 ++left;
1385 --right;
1386 }
1387 /* If either list is empty, it means that all remaining features
1388 * are identical. Split in the middle to maintain a balanced tree.
1389 */
1390 lim1 = left;
1391 right = count - 1;
1392 for (;;)
1393 {
1394 while (left <= right &&
1395 dataset_get(obj, vAcc_[ind + left], cutfeat) <= cutval)
1396 ++left;
1397 while (right && left <= right &&
1398 dataset_get(obj, vAcc_[ind + right], cutfeat) > cutval)
1399 --right;
1400 if (left > right || !right)
1401 break; // "!right" was added to support unsigned Index types
1402 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1403 ++left;
1404 --right;
1405 }
1406 lim2 = left;
1407 }
1408
1409 DistanceType computeInitialDistances(
1410 const Derived& obj, const ElementType* vec,
1411 distance_vector_t& dists) const
1412 {
1413 assert(vec);
1414 DistanceType dist = DistanceType();
1415
1416 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim_); ++i)
1417 {
1418 if (vec[i] < obj.root_bbox_[i].low)
1419 {
1420 dists[i] =
1421 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].low, i);
1422 dist += dists[i];
1423 }
1424 if (vec[i] > obj.root_bbox_[i].high)
1425 {
1426 dists[i] =
1427 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].high, i);
1428 dist += dists[i];
1429 }
1430 }
1431 return dist;
1432 }
1433
1434 static void save_tree(
1435 const Derived& obj, std::ostream& stream, const NodeConstPtr tree)
1436 {
1437 save_value(stream, *tree);
1438 if (tree->child1 != nullptr) { save_tree(obj, stream, tree->child1); }
1439 if (tree->child2 != nullptr) { save_tree(obj, stream, tree->child2); }
1440 }
1441
1442 static void load_tree(Derived& obj, std::istream& stream, NodePtr& tree)
1443 {
1444 tree = obj.pool_.template allocate<Node>();
1445 load_value(stream, *tree);
1446 if (tree->child1 != nullptr) { load_tree(obj, stream, tree->child1); }
1447 if (tree->child2 != nullptr) { load_tree(obj, stream, tree->child2); }
1448 }
1449
1455 void saveIndex(const Derived& obj, std::ostream& stream) const
1456 {
1457 save_value(stream, obj.size_);
1458 save_value(stream, obj.dim_);
1459 save_value(stream, obj.root_bbox_);
1460 save_value(stream, obj.leaf_max_size_);
1461 save_value(stream, obj.vAcc_);
1462 if (obj.root_node_) save_tree(obj, stream, obj.root_node_);
1463 }
1464
1470 void loadIndex(Derived& obj, std::istream& stream)
1471 {
1472 load_value(stream, obj.size_);
1473 load_value(stream, obj.dim_);
1474 load_value(stream, obj.root_bbox_);
1475 load_value(stream, obj.leaf_max_size_);
1476 load_value(stream, obj.vAcc_);
1477 load_tree(obj, stream, obj.root_node_);
1478 }
1479};
1480
1522template <
1523 typename Distance, class DatasetAdaptor, int32_t DIM = -1,
1524 typename index_t = uint32_t>
1526 : public KDTreeBaseClass<
1527 KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, index_t>,
1528 Distance, DatasetAdaptor, DIM, index_t>
1529{
1530 public:
1534 Distance, DatasetAdaptor, DIM, index_t>&) = delete;
1535
1537 const DatasetAdaptor& dataset_;
1538
1539 const KDTreeSingleIndexAdaptorParams indexParams;
1540
1541 Distance distance_;
1542
1543 using Base = typename nanoflann::KDTreeBaseClass<
1545 Distance, DatasetAdaptor, DIM, index_t>,
1546 Distance, DatasetAdaptor, DIM, index_t>;
1547
1548 using Offset = typename Base::Offset;
1549 using Size = typename Base::Size;
1550 using Dimension = typename Base::Dimension;
1551
1552 using ElementType = typename Base::ElementType;
1553 using DistanceType = typename Base::DistanceType;
1554 using IndexType = typename Base::IndexType;
1555
1556 using Node = typename Base::Node;
1557 using NodePtr = Node*;
1558
1559 using Interval = typename Base::Interval;
1560
1563 using BoundingBox = typename Base::BoundingBox;
1564
1567 using distance_vector_t = typename Base::distance_vector_t;
1568
1589 template <class... Args>
1591 const Dimension dimensionality, const DatasetAdaptor& inputData,
1592 const KDTreeSingleIndexAdaptorParams& params, Args&&... args)
1593 : dataset_(inputData),
1594 indexParams(params),
1595 distance_(inputData, std::forward<Args>(args)...)
1596 {
1597 init(dimensionality, params);
1598 }
1599
1600 explicit KDTreeSingleIndexAdaptor(
1601 const Dimension dimensionality, const DatasetAdaptor& inputData,
1602 const KDTreeSingleIndexAdaptorParams& params = {})
1603 : dataset_(inputData), indexParams(params), distance_(inputData)
1604 {
1605 init(dimensionality, params);
1606 }
1607
1608 private:
1609 void init(
1610 const Dimension dimensionality,
1611 const KDTreeSingleIndexAdaptorParams& params)
1612 {
1613 Base::size_ = dataset_.kdtree_get_point_count();
1614 Base::size_at_index_build_ = Base::size_;
1615 Base::dim_ = dimensionality;
1616 if (DIM > 0) Base::dim_ = DIM;
1617 Base::leaf_max_size_ = params.leaf_max_size;
1618 if (params.n_thread_build > 0)
1619 {
1620 Base::n_thread_build_ = params.n_thread_build;
1621 }
1622 else
1623 {
1624 Base::n_thread_build_ =
1625 std::max(std::thread::hardware_concurrency(), 1u);
1626 }
1627
1628 if (!(params.flags &
1629 KDTreeSingleIndexAdaptorFlags::SkipInitialBuildIndex))
1630 {
1631 // Build KD-tree:
1632 buildIndex();
1633 }
1634 }
1635
1636 public:
1641 {
1642 Base::size_ = dataset_.kdtree_get_point_count();
1643 Base::size_at_index_build_ = Base::size_;
1644 init_vind();
1645 this->freeIndex(*this);
1646 Base::size_at_index_build_ = Base::size_;
1647 if (Base::size_ == 0) return;
1648 computeBoundingBox(Base::root_bbox_);
1649 // construct the tree
1650 if (Base::n_thread_build_ == 1)
1651 {
1652 Base::root_node_ =
1653 this->divideTree(*this, 0, Base::size_, Base::root_bbox_);
1654 }
1655 else
1656 {
1657#ifndef NANOFLANN_NO_THREADS
1658 std::atomic<unsigned int> thread_count(0u);
1659 std::mutex mutex;
1660 Base::root_node_ = this->divideTreeConcurrent(
1661 *this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
1662#else /* NANOFLANN_NO_THREADS */
1663 throw std::runtime_error("Multithreading is disabled");
1664#endif /* NANOFLANN_NO_THREADS */
1665 }
1666 }
1667
1687 template <typename RESULTSET>
1689 RESULTSET& result, const ElementType* vec,
1690 const SearchParameters& searchParams = {}) const
1691 {
1692 assert(vec);
1693 if (this->size(*this) == 0) return false;
1694 if (!Base::root_node_)
1695 throw std::runtime_error(
1696 "[nanoflann] findNeighbors() called before building the "
1697 "index.");
1698 float epsError = 1 + searchParams.eps;
1699
1700 // fixed or variable-sized container (depending on DIM)
1701 distance_vector_t dists;
1702 // Fill it with zeros.
1703 auto zero = static_cast<typename RESULTSET::DistanceType>(0);
1704 assign(dists, (DIM > 0 ? DIM : Base::dim_), zero);
1705 DistanceType dist = this->computeInitialDistances(*this, vec, dists);
1706 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
1707
1708 if (searchParams.sorted) result.sort();
1709
1710 return result.full();
1711 }
1712
1729 const ElementType* query_point, const Size num_closest,
1730 IndexType* out_indices, DistanceType* out_distances) const
1731 {
1733 resultSet.init(out_indices, out_distances);
1734 findNeighbors(resultSet, query_point);
1735 return resultSet.size();
1736 }
1737
1758 const ElementType* query_point, const DistanceType& radius,
1759 std::vector<ResultItem<IndexType, DistanceType>>& IndicesDists,
1760 const SearchParameters& searchParams = {}) const
1761 {
1763 radius, IndicesDists);
1764 const Size nFound =
1765 radiusSearchCustomCallback(query_point, resultSet, searchParams);
1766 return nFound;
1767 }
1768
1774 template <class SEARCH_CALLBACK>
1776 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
1777 const SearchParameters& searchParams = {}) const
1778 {
1779 findNeighbors(resultSet, query_point, searchParams);
1780 return resultSet.size();
1781 }
1782
1800 const ElementType* query_point, const Size num_closest,
1801 IndexType* out_indices, DistanceType* out_distances,
1802 const DistanceType& radius) const
1803 {
1805 num_closest, radius);
1806 resultSet.init(out_indices, out_distances);
1807 findNeighbors(resultSet, query_point);
1808 return resultSet.size();
1809 }
1810
1813 public:
1817 {
1818 // Create a permutable array of indices to the input vectors.
1819 Base::size_ = dataset_.kdtree_get_point_count();
1820 if (Base::vAcc_.size() != Base::size_) Base::vAcc_.resize(Base::size_);
1821 for (IndexType i = 0; i < static_cast<IndexType>(Base::size_); i++)
1822 Base::vAcc_[i] = i;
1823 }
1824
1825 void computeBoundingBox(BoundingBox& bbox)
1826 {
1827 const auto dims = (DIM > 0 ? DIM : Base::dim_);
1828 resize(bbox, dims);
1829 if (dataset_.kdtree_get_bbox(bbox))
1830 {
1831 // Done! It was implemented in derived class
1832 }
1833 else
1834 {
1835 const Size N = dataset_.kdtree_get_point_count();
1836 if (!N)
1837 throw std::runtime_error(
1838 "[nanoflann] computeBoundingBox() called but "
1839 "no data points found.");
1840 for (Dimension i = 0; i < dims; ++i)
1841 {
1842 bbox[i].low = bbox[i].high =
1843 this->dataset_get(*this, Base::vAcc_[0], i);
1844 }
1845 for (Offset k = 1; k < N; ++k)
1846 {
1847 for (Dimension i = 0; i < dims; ++i)
1848 {
1849 const auto val =
1850 this->dataset_get(*this, Base::vAcc_[k], i);
1851 if (val < bbox[i].low) bbox[i].low = val;
1852 if (val > bbox[i].high) bbox[i].high = val;
1853 }
1854 }
1855 }
1856 }
1857
1864 template <class RESULTSET>
1866 RESULTSET& result_set, const ElementType* vec, const NodePtr node,
1867 DistanceType mindist, distance_vector_t& dists,
1868 const float epsError) const
1869 {
1870 /* If this is a leaf node, then do check and return. */
1871 if ((node->child1 == nullptr) && (node->child2 == nullptr))
1872 {
1873 DistanceType worst_dist = result_set.worstDist();
1874 for (Offset i = node->node_type.lr.left;
1875 i < node->node_type.lr.right; ++i)
1876 {
1877 const IndexType accessor = Base::vAcc_[i]; // reorder... : i;
1878 DistanceType dist = distance_.evalMetric(
1879 vec, accessor, (DIM > 0 ? DIM : Base::dim_));
1880 if (dist < worst_dist)
1881 {
1882 if (!result_set.addPoint(dist, Base::vAcc_[i]))
1883 {
1884 // the resultset doesn't want to receive any more
1885 // points, we're done searching!
1886 return false;
1887 }
1888 }
1889 }
1890 return true;
1891 }
1892
1893 /* Which child branch should be taken first? */
1894 Dimension idx = node->node_type.sub.divfeat;
1895 ElementType val = vec[idx];
1896 DistanceType diff1 = val - node->node_type.sub.divlow;
1897 DistanceType diff2 = val - node->node_type.sub.divhigh;
1898
1899 NodePtr bestChild;
1900 NodePtr otherChild;
1901 DistanceType cut_dist;
1902 if ((diff1 + diff2) < 0)
1903 {
1904 bestChild = node->child1;
1905 otherChild = node->child2;
1906 cut_dist =
1907 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
1908 }
1909 else
1910 {
1911 bestChild = node->child2;
1912 otherChild = node->child1;
1913 cut_dist =
1914 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
1915 }
1916
1917 /* Call recursively to search next level down. */
1918 if (!searchLevel(result_set, vec, bestChild, mindist, dists, epsError))
1919 {
1920 // the resultset doesn't want to receive any more points, we're done
1921 // searching!
1922 return false;
1923 }
1924
1925 DistanceType dst = dists[idx];
1926 mindist = mindist + cut_dist - dst;
1927 dists[idx] = cut_dist;
1928 if (mindist * epsError <= result_set.worstDist())
1929 {
1930 if (!searchLevel(
1931 result_set, vec, otherChild, mindist, dists, epsError))
1932 {
1933 // the resultset doesn't want to receive any more points, we're
1934 // done searching!
1935 return false;
1936 }
1937 }
1938 dists[idx] = dst;
1939 return true;
1940 }
1941
1942 public:
1948 void saveIndex(std::ostream& stream) const
1949 {
1950 Base::saveIndex(*this, stream);
1951 }
1952
1958 void loadIndex(std::istream& stream) { Base::loadIndex(*this, stream); }
1959
1960}; // class KDTree
1961
1999template <
2000 typename Distance, class DatasetAdaptor, int32_t DIM = -1,
2001 typename IndexType = uint32_t>
2003 : public KDTreeBaseClass<
2004 KDTreeSingleIndexDynamicAdaptor_<
2005 Distance, DatasetAdaptor, DIM, IndexType>,
2006 Distance, DatasetAdaptor, DIM, IndexType>
2007{
2008 public:
2012 const DatasetAdaptor& dataset_;
2013
2014 KDTreeSingleIndexAdaptorParams index_params_;
2015
2016 std::vector<int>& treeIndex_;
2017
2018 Distance distance_;
2019
2020 using Base = typename nanoflann::KDTreeBaseClass<
2022 Distance, DatasetAdaptor, DIM, IndexType>,
2023 Distance, DatasetAdaptor, DIM, IndexType>;
2024
2025 using ElementType = typename Base::ElementType;
2026 using DistanceType = typename Base::DistanceType;
2027
2028 using Offset = typename Base::Offset;
2029 using Size = typename Base::Size;
2030 using Dimension = typename Base::Dimension;
2031
2032 using Node = typename Base::Node;
2033 using NodePtr = Node*;
2034
2035 using Interval = typename Base::Interval;
2038 using BoundingBox = typename Base::BoundingBox;
2039
2042 using distance_vector_t = typename Base::distance_vector_t;
2043
2060 const Dimension dimensionality, const DatasetAdaptor& inputData,
2061 std::vector<int>& treeIndex,
2062 const KDTreeSingleIndexAdaptorParams& params =
2064 : dataset_(inputData),
2065 index_params_(params),
2066 treeIndex_(treeIndex),
2067 distance_(inputData)
2068 {
2069 Base::size_ = 0;
2070 Base::size_at_index_build_ = 0;
2071 for (auto& v : Base::root_bbox_) v = {};
2072 Base::dim_ = dimensionality;
2073 if (DIM > 0) Base::dim_ = DIM;
2074 Base::leaf_max_size_ = params.leaf_max_size;
2075 if (params.n_thread_build > 0)
2076 {
2077 Base::n_thread_build_ = params.n_thread_build;
2078 }
2079 else
2080 {
2081 Base::n_thread_build_ =
2082 std::max(std::thread::hardware_concurrency(), 1u);
2083 }
2084 }
2085
2088 const KDTreeSingleIndexDynamicAdaptor_& rhs) = default;
2089
2093 {
2095 std::swap(Base::vAcc_, tmp.Base::vAcc_);
2096 std::swap(Base::leaf_max_size_, tmp.Base::leaf_max_size_);
2097 std::swap(index_params_, tmp.index_params_);
2098 std::swap(treeIndex_, tmp.treeIndex_);
2099 std::swap(Base::size_, tmp.Base::size_);
2100 std::swap(Base::size_at_index_build_, tmp.Base::size_at_index_build_);
2101 std::swap(Base::root_node_, tmp.Base::root_node_);
2102 std::swap(Base::root_bbox_, tmp.Base::root_bbox_);
2103 std::swap(Base::pool_, tmp.Base::pool_);
2104 return *this;
2105 }
2106
2111 {
2112 Base::size_ = Base::vAcc_.size();
2113 this->freeIndex(*this);
2114 Base::size_at_index_build_ = Base::size_;
2115 if (Base::size_ == 0) return;
2116 computeBoundingBox(Base::root_bbox_);
2117 // construct the tree
2118 if (Base::n_thread_build_ == 1)
2119 {
2120 Base::root_node_ =
2121 this->divideTree(*this, 0, Base::size_, Base::root_bbox_);
2122 }
2123 else
2124 {
2125#ifndef NANOFLANN_NO_THREADS
2126 std::atomic<unsigned int> thread_count(0u);
2127 std::mutex mutex;
2128 Base::root_node_ = this->divideTreeConcurrent(
2129 *this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
2130#else /* NANOFLANN_NO_THREADS */
2131 throw std::runtime_error("Multithreading is disabled");
2132#endif /* NANOFLANN_NO_THREADS */
2133 }
2134 }
2135
2159 template <typename RESULTSET>
2161 RESULTSET& result, const ElementType* vec,
2162 const SearchParameters& searchParams = {}) const
2163 {
2164 assert(vec);
2165 if (this->size(*this) == 0) return false;
2166 if (!Base::root_node_) return false;
2167 float epsError = 1 + searchParams.eps;
2168
2169 // fixed or variable-sized container (depending on DIM)
2170 distance_vector_t dists;
2171 // Fill it with zeros.
2172 assign(
2173 dists, (DIM > 0 ? DIM : Base::dim_),
2174 static_cast<typename distance_vector_t::value_type>(0));
2175 DistanceType dist = this->computeInitialDistances(*this, vec, dists);
2176 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
2177 return result.full();
2178 }
2179
2195 const ElementType* query_point, const Size num_closest,
2196 IndexType* out_indices, DistanceType* out_distances,
2197 const SearchParameters& searchParams = {}) const
2198 {
2200 resultSet.init(out_indices, out_distances);
2201 findNeighbors(resultSet, query_point, searchParams);
2202 return resultSet.size();
2203 }
2204
2225 const ElementType* query_point, const DistanceType& radius,
2226 std::vector<ResultItem<IndexType, DistanceType>>& IndicesDists,
2227 const SearchParameters& searchParams = {}) const
2228 {
2230 radius, IndicesDists);
2231 const size_t nFound =
2232 radiusSearchCustomCallback(query_point, resultSet, searchParams);
2233 return nFound;
2234 }
2235
2241 template <class SEARCH_CALLBACK>
2243 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
2244 const SearchParameters& searchParams = {}) const
2245 {
2246 findNeighbors(resultSet, query_point, searchParams);
2247 return resultSet.size();
2248 }
2249
2252 public:
2253 void computeBoundingBox(BoundingBox& bbox)
2254 {
2255 const auto dims = (DIM > 0 ? DIM : Base::dim_);
2256 resize(bbox, dims);
2257
2258 if (dataset_.kdtree_get_bbox(bbox))
2259 {
2260 // Done! It was implemented in derived class
2261 }
2262 else
2263 {
2264 const Size N = Base::size_;
2265 if (!N)
2266 throw std::runtime_error(
2267 "[nanoflann] computeBoundingBox() called but "
2268 "no data points found.");
2269 for (Dimension i = 0; i < dims; ++i)
2270 {
2271 bbox[i].low = bbox[i].high =
2272 this->dataset_get(*this, Base::vAcc_[0], i);
2273 }
2274 for (Offset k = 1; k < N; ++k)
2275 {
2276 for (Dimension i = 0; i < dims; ++i)
2277 {
2278 const auto val =
2279 this->dataset_get(*this, Base::vAcc_[k], i);
2280 if (val < bbox[i].low) bbox[i].low = val;
2281 if (val > bbox[i].high) bbox[i].high = val;
2282 }
2283 }
2284 }
2285 }
2286
2291 template <class RESULTSET>
2293 RESULTSET& result_set, const ElementType* vec, const NodePtr node,
2294 DistanceType mindist, distance_vector_t& dists,
2295 const float epsError) const
2296 {
2297 /* If this is a leaf node, then do check and return. */
2298 if ((node->child1 == nullptr) && (node->child2 == nullptr))
2299 {
2300 DistanceType worst_dist = result_set.worstDist();
2301 for (Offset i = node->node_type.lr.left;
2302 i < node->node_type.lr.right; ++i)
2303 {
2304 const IndexType index = Base::vAcc_[i]; // reorder... : i;
2305 if (treeIndex_[index] == -1) continue;
2306 DistanceType dist = distance_.evalMetric(
2307 vec, index, (DIM > 0 ? DIM : Base::dim_));
2308 if (dist < worst_dist)
2309 {
2310 if (!result_set.addPoint(
2311 static_cast<typename RESULTSET::DistanceType>(dist),
2312 static_cast<typename RESULTSET::IndexType>(
2313 Base::vAcc_[i])))
2314 {
2315 // the resultset doesn't want to receive any more
2316 // points, we're done searching!
2317 return; // false;
2318 }
2319 }
2320 }
2321 return;
2322 }
2323
2324 /* Which child branch should be taken first? */
2325 Dimension idx = node->node_type.sub.divfeat;
2326 ElementType val = vec[idx];
2327 DistanceType diff1 = val - node->node_type.sub.divlow;
2328 DistanceType diff2 = val - node->node_type.sub.divhigh;
2329
2330 NodePtr bestChild;
2331 NodePtr otherChild;
2332 DistanceType cut_dist;
2333 if ((diff1 + diff2) < 0)
2334 {
2335 bestChild = node->child1;
2336 otherChild = node->child2;
2337 cut_dist =
2338 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
2339 }
2340 else
2341 {
2342 bestChild = node->child2;
2343 otherChild = node->child1;
2344 cut_dist =
2345 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
2346 }
2347
2348 /* Call recursively to search next level down. */
2349 searchLevel(result_set, vec, bestChild, mindist, dists, epsError);
2350
2351 DistanceType dst = dists[idx];
2352 mindist = mindist + cut_dist - dst;
2353 dists[idx] = cut_dist;
2354 if (mindist * epsError <= result_set.worstDist())
2355 {
2356 searchLevel(result_set, vec, otherChild, mindist, dists, epsError);
2357 }
2358 dists[idx] = dst;
2359 }
2360
2361 public:
2367 void saveIndex(std::ostream& stream) { saveIndex(*this, stream); }
2368
2374 void loadIndex(std::istream& stream) { loadIndex(*this, stream); }
2375};
2376
2391template <
2392 typename Distance, class DatasetAdaptor, int32_t DIM = -1,
2393 typename IndexType = uint32_t>
2395{
2396 public:
2397 using ElementType = typename Distance::ElementType;
2398 using DistanceType = typename Distance::DistanceType;
2399
2400 using Offset = typename KDTreeSingleIndexDynamicAdaptor_<
2401 Distance, DatasetAdaptor, DIM>::Offset;
2402 using Size = typename KDTreeSingleIndexDynamicAdaptor_<
2403 Distance, DatasetAdaptor, DIM>::Size;
2404 using Dimension = typename KDTreeSingleIndexDynamicAdaptor_<
2405 Distance, DatasetAdaptor, DIM>::Dimension;
2406
2407 protected:
2408 Size leaf_max_size_;
2409 Size treeCount_;
2410 Size pointCount_;
2411
2415 const DatasetAdaptor& dataset_;
2416
2419 std::vector<int> treeIndex_;
2420 std::unordered_set<int> removedPoints_;
2421
2422 KDTreeSingleIndexAdaptorParams index_params_;
2423
2424 Dimension dim_;
2425
2427 Distance, DatasetAdaptor, DIM, IndexType>;
2428 std::vector<index_container_t> index_;
2429
2430 public:
2433 const std::vector<index_container_t>& getAllIndices() const
2434 {
2435 return index_;
2436 }
2437
2438 private:
2440 int First0Bit(IndexType num)
2441 {
2442 int pos = 0;
2443 while (num & 1)
2444 {
2445 num = num >> 1;
2446 pos++;
2447 }
2448 return pos;
2449 }
2450
2452 void init()
2453 {
2454 using my_kd_tree_t = KDTreeSingleIndexDynamicAdaptor_<
2455 Distance, DatasetAdaptor, DIM, IndexType>;
2456 std::vector<my_kd_tree_t> index(
2457 treeCount_,
2458 my_kd_tree_t(dim_ /*dim*/, dataset_, treeIndex_, index_params_));
2459 index_ = index;
2460 }
2461
2462 public:
2463 Distance distance_;
2464
2481 const int dimensionality, const DatasetAdaptor& inputData,
2482 const KDTreeSingleIndexAdaptorParams& params =
2484 const size_t maximumPointCount = 1000000000U)
2485 : dataset_(inputData), index_params_(params), distance_(inputData)
2486 {
2487 treeCount_ = static_cast<size_t>(std::log2(maximumPointCount)) + 1;
2488 pointCount_ = 0U;
2489 dim_ = dimensionality;
2490 treeIndex_.clear();
2491 if (DIM > 0) dim_ = DIM;
2492 leaf_max_size_ = params.leaf_max_size;
2493 init();
2494 const size_t num_initial_points = dataset_.kdtree_get_point_count();
2495 if (num_initial_points > 0) { addPoints(0, num_initial_points - 1); }
2496 }
2497
2501 Distance, DatasetAdaptor, DIM, IndexType>&) = delete;
2502
2504 void addPoints(IndexType start, IndexType end)
2505 {
2506 const Size count = end - start + 1;
2507 int maxIndex = 0;
2508 treeIndex_.resize(treeIndex_.size() + count);
2509 for (IndexType idx = start; idx <= end; idx++)
2510 {
2511 const int pos = First0Bit(pointCount_);
2512 maxIndex = std::max(pos, maxIndex);
2513 treeIndex_[pointCount_] = pos;
2514
2515 const auto it = removedPoints_.find(idx);
2516 if (it != removedPoints_.end())
2517 {
2518 removedPoints_.erase(it);
2519 treeIndex_[idx] = pos;
2520 }
2521
2522 for (int i = 0; i < pos; i++)
2523 {
2524 for (int j = 0; j < static_cast<int>(index_[i].vAcc_.size());
2525 j++)
2526 {
2527 index_[pos].vAcc_.push_back(index_[i].vAcc_[j]);
2528 if (treeIndex_[index_[i].vAcc_[j]] != -1)
2529 treeIndex_[index_[i].vAcc_[j]] = pos;
2530 }
2531 index_[i].vAcc_.clear();
2532 }
2533 index_[pos].vAcc_.push_back(idx);
2534 pointCount_++;
2535 }
2536
2537 for (int i = 0; i <= maxIndex; ++i)
2538 {
2539 index_[i].freeIndex(index_[i]);
2540 if (!index_[i].vAcc_.empty()) index_[i].buildIndex();
2541 }
2542 }
2543
2545 void removePoint(size_t idx)
2546 {
2547 if (idx >= pointCount_) return;
2548 removedPoints_.insert(idx);
2549 treeIndex_[idx] = -1;
2550 }
2551
2568 template <typename RESULTSET>
2570 RESULTSET& result, const ElementType* vec,
2571 const SearchParameters& searchParams = {}) const
2572 {
2573 for (size_t i = 0; i < treeCount_; i++)
2574 {
2575 index_[i].findNeighbors(result, &vec[0], searchParams);
2576 }
2577 return result.full();
2578 }
2579};
2580
2606template <
2607 class MatrixType, int32_t DIM = -1, class Distance = nanoflann::metric_L2,
2608 bool row_major = true>
2610{
2611 using self_t =
2613 using num_t = typename MatrixType::Scalar;
2614 using IndexType = typename MatrixType::Index;
2615 using metric_t = typename Distance::template traits<
2616 num_t, self_t, IndexType>::distance_t;
2617
2619 metric_t, self_t,
2620 row_major ? MatrixType::ColsAtCompileTime
2621 : MatrixType::RowsAtCompileTime,
2622 IndexType>;
2623
2624 index_t* index_;
2626
2627 using Offset = typename index_t::Offset;
2628 using Size = typename index_t::Size;
2629 using Dimension = typename index_t::Dimension;
2630
2633 const Dimension dimensionality,
2634 const std::reference_wrapper<const MatrixType>& mat,
2635 const int leaf_max_size = 10, const unsigned int n_thread_build = 1)
2636 : m_data_matrix(mat)
2637 {
2638 const auto dims = row_major ? mat.get().cols() : mat.get().rows();
2639 if (static_cast<Dimension>(dims) != dimensionality)
2640 throw std::runtime_error(
2641 "Error: 'dimensionality' must match column count in data "
2642 "matrix");
2643 if (DIM > 0 && static_cast<int32_t>(dims) != DIM)
2644 throw std::runtime_error(
2645 "Data set dimensionality does not match the 'DIM' template "
2646 "argument");
2647 index_ = new index_t(
2648 dims, *this /* adaptor */,
2650 leaf_max_size, nanoflann::KDTreeSingleIndexAdaptorFlags::None,
2651 n_thread_build));
2652 }
2653
2654 public:
2657
2658 ~KDTreeEigenMatrixAdaptor() { delete index_; }
2659
2660 const std::reference_wrapper<const MatrixType> m_data_matrix;
2661
2670 void query(
2671 const num_t* query_point, const Size num_closest,
2672 IndexType* out_indices, num_t* out_distances) const
2673 {
2674 nanoflann::KNNResultSet<num_t, IndexType> resultSet(num_closest);
2675 resultSet.init(out_indices, out_distances);
2676 index_->findNeighbors(resultSet, query_point);
2677 }
2678
2682 const self_t& derived() const { return *this; }
2683 self_t& derived() { return *this; }
2684
2685 // Must return the number of data points
2686 Size kdtree_get_point_count() const
2687 {
2688 if (row_major)
2689 return m_data_matrix.get().rows();
2690 else
2691 return m_data_matrix.get().cols();
2692 }
2693
2694 // Returns the dim'th component of the idx'th point in the class:
2695 num_t kdtree_get_pt(const IndexType idx, size_t dim) const
2696 {
2697 if (row_major)
2698 return m_data_matrix.get().coeff(idx, IndexType(dim));
2699 else
2700 return m_data_matrix.get().coeff(IndexType(dim), idx);
2701 }
2702
2703 // Optional bounding-box computation: return false to default to a standard
2704 // bbox computation loop.
2705 // Return true if the BBOX was already computed by the class and returned
2706 // in "bb" so it can be avoided to redo it again. Look at bb.size() to
2707 // find out the expected dimensionality (e.g. 2 or 3 for point clouds)
2708 template <class BBOX>
2709 bool kdtree_get_bbox(BBOX& /*bb*/) const
2710 {
2711 return false;
2712 }
2713
2716}; // end of KDTreeEigenMatrixAdaptor
// end of grouping
2720} // namespace nanoflann
Definition nanoflann.hpp:1011
void freeIndex(Derived &obj)
Definition nanoflann.hpp:1015
BoundingBox root_bbox_
Definition nanoflann.hpp:1089
Size veclen(const Derived &obj)
Definition nanoflann.hpp:1104
void saveIndex(const Derived &obj, std::ostream &stream) const
Definition nanoflann.hpp:1455
Size usedMemory(Derived &obj)
Definition nanoflann.hpp:1117
typename array_or_vector< DIM, DistanceType >::type distance_vector_t
Definition nanoflann.hpp:1086
void planeSplit(const Derived &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)
Definition nanoflann.hpp:1365
NodePtr divideTree(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox)
Definition nanoflann.hpp:1145
std::vector< IndexType > vAcc_
Definition nanoflann.hpp:1029
Size size(const Derived &obj) const
Definition nanoflann.hpp:1101
NodePtr divideTreeConcurrent(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex)
Definition nanoflann.hpp:1216
void loadIndex(Derived &obj, std::istream &stream)
Definition nanoflann.hpp:1470
PooledAllocator pool_
Definition nanoflann.hpp:1098
ElementType dataset_get(const Derived &obj, IndexType element, Dimension component) const
Helper accessor to the dataset points:
Definition nanoflann.hpp:1107
typename array_or_vector< DIM, Interval >::type BoundingBox
Definition nanoflann.hpp:1082
Definition nanoflann.hpp:1529
bool searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:1865
void saveIndex(std::ostream &stream) const
Definition nanoflann.hpp:1948
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1757
void init_vind()
Definition nanoflann.hpp:1816
void buildIndex()
Definition nanoflann.hpp:1640
const DatasetAdaptor & dataset_
Definition nanoflann.hpp:1537
KDTreeSingleIndexAdaptor(const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t > &)=delete
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1688
Size rknnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const
Definition nanoflann.hpp:1799
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1775
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:1567
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:1958
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:1563
KDTreeSingleIndexAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params, Args &&... args)
Definition nanoflann.hpp:1590
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances) const
Definition nanoflann.hpp:1728
Definition nanoflann.hpp:2007
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2224
KDTreeSingleIndexDynamicAdaptor_(const Dimension dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
Definition nanoflann.hpp:2059
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:2038
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:2012
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2242
KDTreeSingleIndexDynamicAdaptor_(const KDTreeSingleIndexDynamicAdaptor_ &rhs)=default
void buildIndex()
Definition nanoflann.hpp:2110
void saveIndex(std::ostream &stream)
Definition nanoflann.hpp:2367
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:2042
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:2374
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2194
void searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:2292
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2160
KDTreeSingleIndexDynamicAdaptor_ operator=(const KDTreeSingleIndexDynamicAdaptor_ &rhs)
Definition nanoflann.hpp:2091
Definition nanoflann.hpp:2395
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2569
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:2415
void removePoint(size_t idx)
Definition nanoflann.hpp:2545
void addPoints(IndexType start, IndexType end)
Definition nanoflann.hpp:2504
KDTreeSingleIndexDynamicAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams(), const size_t maximumPointCount=1000000000U)
Definition nanoflann.hpp:2480
std::vector< int > treeIndex_
Definition nanoflann.hpp:2419
const std::vector< index_container_t > & getAllIndices() const
Definition nanoflann.hpp:2433
Dimension dim_
Dimensionality of each data point.
Definition nanoflann.hpp:2424
KDTreeSingleIndexDynamicAdaptor(const KDTreeSingleIndexDynamicAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete
Definition nanoflann.hpp:200
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:234
DistanceType worstDist() const
Definition nanoflann.hpp:271
Definition nanoflann.hpp:859
~PooledAllocator()
Definition nanoflann.hpp:895
void free_all()
Definition nanoflann.hpp:898
void * malloc(const size_t req_size)
Definition nanoflann.hpp:914
T * allocate(const size_t count=1)
Definition nanoflann.hpp:965
PooledAllocator()
Definition nanoflann.hpp:890
Definition nanoflann.hpp:288
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:329
DistanceType worstDist() const
Definition nanoflann.hpp:366
Definition nanoflann.hpp:383
ResultItem< IndexType, DistanceType > worst_item() const
Definition nanoflann.hpp:426
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:414
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:162
bool operator()(const PairType &p1, const PairType &p2) const
Definition nanoflann.hpp:165
Definition nanoflann.hpp:1064
Definition nanoflann.hpp:1039
DistanceType divlow
The values used for subdivision.
Definition nanoflann.hpp:1052
Offset right
Indices of points in leaf node.
Definition nanoflann.hpp:1046
union nanoflann::KDTreeBaseClass::Node::@0 node_type
Dimension divfeat
Definition nanoflann.hpp:1050
Node * child1
Definition nanoflann.hpp:1057
Definition nanoflann.hpp:2610
void query(const num_t *query_point, const Size num_closest, IndexType *out_indices, num_t *out_distances) const
Definition nanoflann.hpp:2670
KDTreeEigenMatrixAdaptor(const self_t &)=delete
typename index_t::Offset Offset
Definition nanoflann.hpp:2627
KDTreeEigenMatrixAdaptor(const Dimension dimensionality, const std::reference_wrapper< const MatrixType > &mat, const int leaf_max_size=10, const unsigned int n_thread_build=1)
Constructor: takes a const ref to the matrix object with the data points.
Definition nanoflann.hpp:2632
Definition nanoflann.hpp:810
Definition nanoflann.hpp:499
Definition nanoflann.hpp:561
Definition nanoflann.hpp:626
Definition nanoflann.hpp:482
Definition nanoflann.hpp:181
DistanceType second
Distance from sample to query point.
Definition nanoflann.hpp:189
IndexType first
Index of the sample in the dataset.
Definition nanoflann.hpp:188
Definition nanoflann.hpp:671
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition nanoflann.hpp:689
Definition nanoflann.hpp:716
Definition nanoflann.hpp:829
bool sorted
distance (default: true)
Definition nanoflann.hpp:836
float eps
search for eps-approximate neighbours (default: 0)
Definition nanoflann.hpp:835
Definition nanoflann.hpp:981
Definition nanoflann.hpp:109
Definition nanoflann.hpp:98
Definition nanoflann.hpp:746
Definition nanoflann.hpp:743
Definition nanoflann.hpp:756
Definition nanoflann.hpp:766
Definition nanoflann.hpp:763
Definition nanoflann.hpp:753
Definition nanoflann.hpp:775
Definition nanoflann.hpp:772
Definition nanoflann.hpp:784
Definition nanoflann.hpp:781