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