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-2023 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 <cstdlib> // for abs()
53#include <functional> // std::reference_wrapper
54#include <future>
55#include <istream>
56#include <limits> // std::numeric_limits
57#include <ostream>
58#include <stdexcept>
59#include <unordered_set>
60#include <vector>
61
63#define NANOFLANN_VERSION 0x151
64
65// Avoid conflicting declaration of min/max macros in Windows headers
66#if !defined(NOMINMAX) && \
67 (defined(_WIN32) || defined(_WIN32_) || defined(WIN32) || defined(_WIN64))
68#define NOMINMAX
69#ifdef max
70#undef max
71#undef min
72#endif
73#endif
74// Avoid conflicts with X11 headers
75#ifdef None
76#undef None
77#endif
78
79namespace nanoflann
80{
85template <typename T>
87{
88 return static_cast<T>(3.14159265358979323846);
89}
90
95template <typename T, typename = int>
96struct has_resize : std::false_type
97{
98};
99
100template <typename T>
101struct has_resize<T, decltype((void)std::declval<T>().resize(1), 0)>
102 : std::true_type
103{
104};
105
106template <typename T, typename = int>
107struct has_assign : std::false_type
108{
109};
110
111template <typename T>
112struct has_assign<T, decltype((void)std::declval<T>().assign(1, 0), 0)>
113 : std::true_type
114{
115};
116
120template <typename Container>
121inline typename std::enable_if<has_resize<Container>::value, void>::type resize(
122 Container& c, const size_t nElements)
123{
124 c.resize(nElements);
125}
126
131template <typename Container>
132inline typename std::enable_if<!has_resize<Container>::value, void>::type
133 resize(Container& c, const size_t nElements)
134{
135 if (nElements != c.size())
136 throw std::logic_error("Try to change the size of a std::array.");
137}
138
142template <typename Container, typename T>
143inline typename std::enable_if<has_assign<Container>::value, void>::type assign(
144 Container& c, const size_t nElements, const T& value)
145{
146 c.assign(nElements, value);
147}
148
152template <typename Container, typename T>
153inline typename std::enable_if<!has_assign<Container>::value, void>::type
154 assign(Container& c, const size_t nElements, const T& value)
155{
156 for (size_t i = 0; i < nElements; i++) c[i] = value;
157}
158
163template <
164 typename _DistanceType, typename _IndexType = size_t,
165 typename _CountType = size_t>
167{
168 public:
169 using DistanceType = _DistanceType;
170 using IndexType = _IndexType;
171 using CountType = _CountType;
172
173 private:
174 IndexType* indices;
175 DistanceType* dists;
176 CountType capacity;
177 CountType count;
178
179 public:
180 explicit KNNResultSet(CountType capacity_)
181 : indices(nullptr), dists(nullptr), capacity(capacity_), count(0)
182 {
183 }
184
185 void init(IndexType* indices_, DistanceType* dists_)
186 {
187 indices = indices_;
188 dists = dists_;
189 count = 0;
190 if (capacity)
191 dists[capacity - 1] = (std::numeric_limits<DistanceType>::max)();
192 }
193
194 CountType size() const { return count; }
195 bool empty() const { return count == 0; }
196 bool full() const { return count == capacity; }
197
203 bool addPoint(DistanceType dist, IndexType index)
204 {
205 CountType i;
206 for (i = count; i > 0; --i)
207 {
210#ifdef NANOFLANN_FIRST_MATCH
211 if ((dists[i - 1] > dist) ||
212 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
213 {
214#else
215 if (dists[i - 1] > dist)
216 {
217#endif
218 if (i < capacity)
219 {
220 dists[i] = dists[i - 1];
221 indices[i] = indices[i - 1];
222 }
223 }
224 else
225 break;
226 }
227 if (i < capacity)
228 {
229 dists[i] = dist;
230 indices[i] = index;
231 }
232 if (count < capacity) count++;
233
234 // tell caller that the search shall continue
235 return true;
236 }
237
238 DistanceType worstDist() const { return dists[capacity - 1]; }
239};
240
242template <
243 typename _DistanceType, typename _IndexType = size_t,
244 typename _CountType = size_t>
246{
247 public:
248 using DistanceType = _DistanceType;
249 using IndexType = _IndexType;
250 using CountType = _CountType;
251
252 private:
253 IndexType* indices;
254 DistanceType* dists;
255 CountType capacity;
256 CountType count;
257 DistanceType maximumSearchDistanceSquared;
258
259 public:
260 explicit RKNNResultSet(
261 CountType capacity_, DistanceType maximumSearchDistanceSquared_)
262 : indices(nullptr),
263 dists(nullptr),
264 capacity(capacity_),
265 count(0),
266 maximumSearchDistanceSquared(maximumSearchDistanceSquared_)
267 {
268 }
269
270 void init(IndexType* indices_, DistanceType* dists_)
271 {
272 indices = indices_;
273 dists = dists_;
274 count = 0;
275 if (capacity)
276 dists[capacity - 1] = maximumSearchDistanceSquared;
277 }
278
279 CountType size() const { return count; }
280 bool empty() const { return count == 0; }
281 bool full() const { return count == capacity; }
282
288 bool addPoint(DistanceType dist, IndexType index)
289 {
290 CountType i;
291 for (i = count; i > 0; --i)
292 {
295#ifdef NANOFLANN_FIRST_MATCH
296 if ((dists[i - 1] > dist) ||
297 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
298 {
299#else
300 if (dists[i - 1] > dist)
301 {
302#endif
303 if (i < capacity)
304 {
305 dists[i] = dists[i - 1];
306 indices[i] = indices[i - 1];
307 }
308 }
309 else
310 break;
311 }
312 if (i < capacity)
313 {
314 dists[i] = dist;
315 indices[i] = index;
316 }
317 if (count < capacity) count++;
318
319 // tell caller that the search shall continue
320 return true;
321 }
322
323 DistanceType worstDist() const { return dists[capacity - 1]; }
324};
325
328{
330 template <typename PairType>
331 bool operator()(const PairType& p1, const PairType& p2) const
332 {
333 return p1.second < p2.second;
334 }
335};
336
345template <typename IndexType = size_t, typename DistanceType = double>
347{
348 ResultItem() = default;
349 ResultItem(const IndexType index, const DistanceType distance)
350 : first(index), second(distance)
351 {
352 }
353
354 IndexType first;
355 DistanceType second;
356};
357
361template <typename _DistanceType, typename _IndexType = size_t>
363{
364 public:
365 using DistanceType = _DistanceType;
366 using IndexType = _IndexType;
367
368 public:
369 const DistanceType radius;
370
371 std::vector<ResultItem<IndexType, DistanceType>>& m_indices_dists;
372
373 explicit RadiusResultSet(
374 DistanceType radius_,
375 std::vector<ResultItem<IndexType, DistanceType>>& indices_dists)
376 : radius(radius_), m_indices_dists(indices_dists)
377 {
378 init();
379 }
380
381 void init() { clear(); }
382 void clear() { m_indices_dists.clear(); }
383
384 size_t size() const { return m_indices_dists.size(); }
385 size_t empty() const { return m_indices_dists.empty(); }
386
387 bool full() const { return true; }
388
394 bool addPoint(DistanceType dist, IndexType index)
395 {
396 if (dist < radius) m_indices_dists.emplace_back(index, dist);
397 return true;
398 }
399
400 DistanceType worstDist() const { return radius; }
401
407 {
408 if (m_indices_dists.empty())
409 throw std::runtime_error(
410 "Cannot invoke RadiusResultSet::worst_item() on "
411 "an empty list of results.");
412 auto it = std::max_element(
413 m_indices_dists.begin(), m_indices_dists.end(), IndexDist_Sorter());
414 return *it;
415 }
416};
417
422template <typename T>
423void save_value(std::ostream& stream, const T& value)
424{
425 stream.write(reinterpret_cast<const char*>(&value), sizeof(T));
426}
427
428template <typename T>
429void save_value(std::ostream& stream, const std::vector<T>& value)
430{
431 size_t size = value.size();
432 stream.write(reinterpret_cast<const char*>(&size), sizeof(size_t));
433 stream.write(reinterpret_cast<const char*>(value.data()), sizeof(T) * size);
434}
435
436template <typename T>
437void load_value(std::istream& stream, T& value)
438{
439 stream.read(reinterpret_cast<char*>(&value), sizeof(T));
440}
441
442template <typename T>
443void load_value(std::istream& stream, std::vector<T>& value)
444{
445 size_t size;
446 stream.read(reinterpret_cast<char*>(&size), sizeof(size_t));
447 value.resize(size);
448 stream.read(reinterpret_cast<char*>(value.data()), sizeof(T) * size);
449}
455struct Metric
456{
457};
458
469template <
470 class T, class DataSource, typename _DistanceType = T,
471 typename IndexType = uint32_t>
473{
474 using ElementType = T;
475 using DistanceType = _DistanceType;
476
477 const DataSource& data_source;
478
479 L1_Adaptor(const DataSource& _data_source) : data_source(_data_source) {}
480
481 DistanceType evalMetric(
482 const T* a, const IndexType b_idx, size_t size,
483 DistanceType worst_dist = -1) const
484 {
485 DistanceType result = DistanceType();
486 const T* last = a + size;
487 const T* lastgroup = last - 3;
488 size_t d = 0;
489
490 /* Process 4 items with each loop for efficiency. */
491 while (a < lastgroup)
492 {
493 const DistanceType diff0 =
494 std::abs(a[0] - data_source.kdtree_get_pt(b_idx, d++));
495 const DistanceType diff1 =
496 std::abs(a[1] - data_source.kdtree_get_pt(b_idx, d++));
497 const DistanceType diff2 =
498 std::abs(a[2] - data_source.kdtree_get_pt(b_idx, d++));
499 const DistanceType diff3 =
500 std::abs(a[3] - data_source.kdtree_get_pt(b_idx, d++));
501 result += diff0 + diff1 + diff2 + diff3;
502 a += 4;
503 if ((worst_dist > 0) && (result > worst_dist)) { return result; }
504 }
505 /* Process last 0-3 components. Not needed for standard vector lengths.
506 */
507 while (a < last)
508 {
509 result += std::abs(*a++ - data_source.kdtree_get_pt(b_idx, d++));
510 }
511 return result;
512 }
513
514 template <typename U, typename V>
515 DistanceType accum_dist(const U a, const V b, const size_t) const
516 {
517 return std::abs(a - b);
518 }
519};
520
531template <
532 class T, class DataSource, typename _DistanceType = T,
533 typename IndexType = uint32_t>
535{
536 using ElementType = T;
537 using DistanceType = _DistanceType;
538
539 const DataSource& data_source;
540
541 L2_Adaptor(const DataSource& _data_source) : data_source(_data_source) {}
542
543 DistanceType evalMetric(
544 const T* a, const IndexType b_idx, size_t size,
545 DistanceType worst_dist = -1) const
546 {
547 DistanceType result = DistanceType();
548 const T* last = a + size;
549 const T* lastgroup = last - 3;
550 size_t d = 0;
551
552 /* Process 4 items with each loop for efficiency. */
553 while (a < lastgroup)
554 {
555 const DistanceType diff0 =
556 a[0] - data_source.kdtree_get_pt(b_idx, d++);
557 const DistanceType diff1 =
558 a[1] - data_source.kdtree_get_pt(b_idx, d++);
559 const DistanceType diff2 =
560 a[2] - data_source.kdtree_get_pt(b_idx, d++);
561 const DistanceType diff3 =
562 a[3] - data_source.kdtree_get_pt(b_idx, d++);
563 result +=
564 diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
565 a += 4;
566 if ((worst_dist > 0) && (result > worst_dist)) { return result; }
567 }
568 /* Process last 0-3 components. Not needed for standard vector lengths.
569 */
570 while (a < last)
571 {
572 const DistanceType diff0 =
573 *a++ - data_source.kdtree_get_pt(b_idx, d++);
574 result += diff0 * diff0;
575 }
576 return result;
577 }
578
579 template <typename U, typename V>
580 DistanceType accum_dist(const U a, const V b, const size_t) const
581 {
582 return (a - b) * (a - b);
583 }
584};
585
596template <
597 class T, class DataSource, typename _DistanceType = T,
598 typename IndexType = uint32_t>
600{
601 using ElementType = T;
602 using DistanceType = _DistanceType;
603
604 const DataSource& data_source;
605
606 L2_Simple_Adaptor(const DataSource& _data_source)
607 : data_source(_data_source)
608 {
609 }
610
611 DistanceType evalMetric(
612 const T* a, const IndexType b_idx, size_t size) const
613 {
614 DistanceType result = DistanceType();
615 for (size_t i = 0; i < size; ++i)
616 {
617 const DistanceType diff =
618 a[i] - data_source.kdtree_get_pt(b_idx, i);
619 result += diff * diff;
620 }
621 return result;
622 }
623
624 template <typename U, typename V>
625 DistanceType accum_dist(const U a, const V b, const size_t) const
626 {
627 return (a - b) * (a - b);
628 }
629};
630
641template <
642 class T, class DataSource, typename _DistanceType = T,
643 typename IndexType = uint32_t>
645{
646 using ElementType = T;
647 using DistanceType = _DistanceType;
648
649 const DataSource& data_source;
650
651 SO2_Adaptor(const DataSource& _data_source) : data_source(_data_source) {}
652
653 DistanceType evalMetric(
654 const T* a, const IndexType b_idx, size_t size) const
655 {
656 return accum_dist(
657 a[size - 1], data_source.kdtree_get_pt(b_idx, size - 1), size - 1);
658 }
659
662 template <typename U, typename V>
663 DistanceType accum_dist(const U a, const V b, const size_t) const
664 {
665 DistanceType result = DistanceType();
666 DistanceType PI = pi_const<DistanceType>();
667 result = b - a;
668 if (result > PI)
669 result -= 2 * PI;
670 else if (result < -PI)
671 result += 2 * PI;
672 return result;
673 }
674};
675
686template <
687 class T, class DataSource, typename _DistanceType = T,
688 typename IndexType = uint32_t>
690{
691 using ElementType = T;
692 using DistanceType = _DistanceType;
693
695 distance_L2_Simple;
696
697 SO3_Adaptor(const DataSource& _data_source)
698 : distance_L2_Simple(_data_source)
699 {
700 }
701
702 DistanceType evalMetric(
703 const T* a, const IndexType b_idx, size_t size) const
704 {
705 return distance_L2_Simple.evalMetric(a, b_idx, size);
706 }
707
708 template <typename U, typename V>
709 DistanceType accum_dist(const U a, const V b, const size_t idx) const
710 {
711 return distance_L2_Simple.accum_dist(a, b, idx);
712 }
713};
714
716struct metric_L1 : public Metric
717{
718 template <class T, class DataSource, typename IndexType = uint32_t>
723};
726struct metric_L2 : public Metric
727{
728 template <class T, class DataSource, typename IndexType = uint32_t>
733};
737{
738 template <class T, class DataSource, typename IndexType = uint32_t>
743};
745struct metric_SO2 : public Metric
746{
747 template <class T, class DataSource, typename IndexType = uint32_t>
752};
754struct metric_SO3 : public Metric
755{
756 template <class T, class DataSource, typename IndexType = uint32_t>
761};
762
768enum class KDTreeSingleIndexAdaptorFlags
769{
770 None = 0,
771 SkipInitialBuildIndex = 1
772};
773
774inline std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type operator&(
775 KDTreeSingleIndexAdaptorFlags lhs, KDTreeSingleIndexAdaptorFlags rhs)
776{
777 using underlying =
778 typename std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type;
779 return static_cast<underlying>(lhs) & static_cast<underlying>(rhs);
780}
781
784{
786 size_t _leaf_max_size = 10,
787 KDTreeSingleIndexAdaptorFlags _flags =
788 KDTreeSingleIndexAdaptorFlags::None,
789 unsigned int _n_thread_build = 1)
790 : leaf_max_size(_leaf_max_size),
791 flags(_flags),
792 n_thread_build(_n_thread_build)
793 {
794 }
795
796 size_t leaf_max_size;
797 KDTreeSingleIndexAdaptorFlags flags;
798 unsigned int n_thread_build;
799};
800
803{
804 SearchParameters(float eps_ = 0, bool sorted_ = true)
805 : eps(eps_), sorted(sorted_)
806 {
807 }
808
809 float eps;
810 bool sorted;
812};
833{
834 static constexpr size_t WORDSIZE = 16;
835 static constexpr size_t BLOCKSIZE = 8192;
836
837 /* We maintain memory alignment to word boundaries by requiring that all
838 allocations be in multiples of the machine wordsize. */
839 /* Size of machine word in bytes. Must be power of 2. */
840 /* Minimum number of bytes requested at a time from the system. Must be
841 * multiple of WORDSIZE. */
842
843 using Offset = uint32_t;
844 using Size = uint32_t;
845 using Dimension = int32_t;
846
847 Size remaining_ = 0;
848 void* base_ = nullptr;
849 void* loc_ = nullptr;
850
851 void internal_init()
852 {
853 remaining_ = 0;
854 base_ = nullptr;
855 usedMemory = 0;
856 wastedMemory = 0;
857 }
858
859 public:
860 Size usedMemory = 0;
861 Size wastedMemory = 0;
862
866 PooledAllocator() { internal_init(); }
867
871 ~PooledAllocator() { free_all(); }
872
874 void free_all()
875 {
876 while (base_ != nullptr)
877 {
878 // Get pointer to prev block
879 void* prev = *(static_cast<void**>(base_));
880 ::free(base_);
881 base_ = prev;
882 }
883 internal_init();
884 }
885
890 void* malloc(const size_t req_size)
891 {
892 /* Round size up to a multiple of wordsize. The following expression
893 only works for WORDSIZE that is a power of 2, by masking last bits
894 of incremented size to zero.
895 */
896 const Size size = (req_size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
897
898 /* Check whether a new block must be allocated. Note that the first
899 word of a block is reserved for a pointer to the previous block.
900 */
901 if (size > remaining_)
902 {
903 wastedMemory += remaining_;
904
905 /* Allocate new storage. */
906 const Size blocksize =
907 (size + sizeof(void*) + (WORDSIZE - 1) > BLOCKSIZE)
908 ? size + sizeof(void*) + (WORDSIZE - 1)
909 : BLOCKSIZE;
910
911 // use the standard C malloc to allocate memory
912 void* m = ::malloc(blocksize);
913 if (!m)
914 {
915 fprintf(stderr, "Failed to allocate memory.\n");
916 throw std::bad_alloc();
917 }
918
919 /* Fill first word of new block with pointer to previous block. */
920 static_cast<void**>(m)[0] = base_;
921 base_ = m;
922
923 Size shift = 0;
924 // int size_t = (WORDSIZE - ( (((size_t)m) + sizeof(void*)) &
925 // (WORDSIZE-1))) & (WORDSIZE-1);
926
927 remaining_ = blocksize - sizeof(void*) - shift;
928 loc_ = (static_cast<char*>(m) + sizeof(void*) + shift);
929 }
930 void* rloc = loc_;
931 loc_ = static_cast<char*>(loc_) + size;
932 remaining_ -= size;
933
934 usedMemory += size;
935
936 return rloc;
937 }
938
946 template <typename T>
947 T* allocate(const size_t count = 1)
948 {
949 T* mem = static_cast<T*>(this->malloc(sizeof(T) * count));
950 return mem;
951 }
952};
961template <int32_t DIM, typename T>
963{
964 using type = std::array<T, DIM>;
965};
967template <typename T>
968struct array_or_vector<-1, T>
969{
970 using type = std::vector<T>;
971};
972
989template <
990 class Derived, typename Distance, class DatasetAdaptor, int32_t DIM = -1,
991 typename IndexType = uint32_t>
993{
994 public:
997 void freeIndex(Derived& obj)
998 {
999 obj.pool_.free_all();
1000 obj.root_node_ = nullptr;
1001 obj.size_at_index_build_ = 0;
1002 }
1003
1004 using ElementType = typename Distance::ElementType;
1005 using DistanceType = typename Distance::DistanceType;
1006
1010 std::vector<IndexType> vAcc_;
1011
1012 using Offset = typename decltype(vAcc_)::size_type;
1013 using Size = typename decltype(vAcc_)::size_type;
1014 using Dimension = int32_t;
1015
1016 /*---------------------------
1017 * Internal Data Structures
1018 * --------------------------*/
1019 struct Node
1020 {
1023 union
1024 {
1025 struct leaf
1026 {
1027 Offset left, right;
1028 } lr;
1029 struct nonleaf
1030 {
1031 Dimension divfeat;
1033 DistanceType divlow, divhigh;
1034 } sub;
1035 } node_type;
1036
1038 Node *child1 = nullptr, *child2 = nullptr;
1039 };
1040
1041 using NodePtr = Node*;
1042 using NodeConstPtr = const Node*;
1043
1045 {
1046 ElementType low, high;
1047 };
1048
1049 NodePtr root_node_ = nullptr;
1050
1051 Size leaf_max_size_ = 0;
1052
1054 Size n_thread_build_ = 1;
1056 Size size_ = 0;
1058 Size size_at_index_build_ = 0;
1059 Dimension dim_ = 0;
1060
1063 using BoundingBox = typename array_or_vector<DIM, Interval>::type;
1064
1067 using distance_vector_t = typename array_or_vector<DIM, DistanceType>::type;
1068
1071
1080
1082 Size size(const Derived& obj) const { return obj.size_; }
1083
1085 Size veclen(const Derived& obj) { return DIM > 0 ? DIM : obj.dim; }
1086
1088 ElementType dataset_get(
1089 const Derived& obj, IndexType element, Dimension component) const
1090 {
1091 return obj.dataset_.kdtree_get_pt(element, component);
1092 }
1093
1098 Size usedMemory(Derived& obj)
1099 {
1100 return obj.pool_.usedMemory + obj.pool_.wastedMemory +
1101 obj.dataset_.kdtree_get_point_count() *
1102 sizeof(IndexType); // pool memory and vind array memory
1103 }
1104
1105 void computeMinMax(
1106 const Derived& obj, Offset ind, Size count, Dimension element,
1107 ElementType& min_elem, ElementType& max_elem)
1108 {
1109 min_elem = dataset_get(obj, vAcc_[ind], element);
1110 max_elem = min_elem;
1111 for (Offset i = 1; i < count; ++i)
1112 {
1113 ElementType val = dataset_get(obj, vAcc_[ind + i], element);
1114 if (val < min_elem) min_elem = val;
1115 if (val > max_elem) max_elem = val;
1116 }
1117 }
1118
1127 Derived& obj, const Offset left, const Offset right, BoundingBox& bbox)
1128 {
1129 NodePtr node = obj.pool_.template allocate<Node>(); // allocate memory
1130 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1131
1132 /* If too few exemplars remain, then make this a leaf node. */
1133 if ((right - left) <= static_cast<Offset>(obj.leaf_max_size_))
1134 {
1135 node->child1 = node->child2 = nullptr; /* Mark as leaf node. */
1136 node->node_type.lr.left = left;
1137 node->node_type.lr.right = right;
1138
1139 // compute bounding-box of leaf points
1140 for (Dimension i = 0; i < dims; ++i)
1141 {
1142 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1143 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1144 }
1145 for (Offset k = left + 1; k < right; ++k)
1146 {
1147 for (Dimension i = 0; i < dims; ++i)
1148 {
1149 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1150 if (bbox[i].low > val) bbox[i].low = val;
1151 if (bbox[i].high < val) bbox[i].high = val;
1152 }
1153 }
1154 }
1155 else
1156 {
1157 Offset idx;
1158 Dimension cutfeat;
1159 DistanceType cutval;
1160 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1161
1162 node->node_type.sub.divfeat = cutfeat;
1163
1164 BoundingBox left_bbox(bbox);
1165 left_bbox[cutfeat].high = cutval;
1166 node->child1 = this->divideTree(obj, left, left + idx, left_bbox);
1167
1168 BoundingBox right_bbox(bbox);
1169 right_bbox[cutfeat].low = cutval;
1170 node->child2 = this->divideTree(obj, left + idx, right, right_bbox);
1171
1172 node->node_type.sub.divlow = left_bbox[cutfeat].high;
1173 node->node_type.sub.divhigh = right_bbox[cutfeat].low;
1174
1175 for (Dimension i = 0; i < dims; ++i)
1176 {
1177 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1178 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1179 }
1180 }
1181
1182 return node;
1183 }
1184
1196 Derived& obj, const Offset left, const Offset right, BoundingBox& bbox,
1197 std::atomic<unsigned int>& thread_count, std::mutex& mutex)
1198 {
1199 std::unique_lock<std::mutex> lock(mutex);
1200 NodePtr node = obj.pool_.template allocate<Node>(); // allocate memory
1201 lock.unlock();
1202
1203 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1204
1205 /* If too few exemplars remain, then make this a leaf node. */
1206 if ((right - left) <= static_cast<Offset>(obj.leaf_max_size_))
1207 {
1208 node->child1 = node->child2 = nullptr; /* Mark as leaf node. */
1209 node->node_type.lr.left = left;
1210 node->node_type.lr.right = right;
1211
1212 // compute bounding-box of leaf points
1213 for (Dimension i = 0; i < dims; ++i)
1214 {
1215 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1216 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1217 }
1218 for (Offset k = left + 1; k < right; ++k)
1219 {
1220 for (Dimension i = 0; i < dims; ++i)
1221 {
1222 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1223 if (bbox[i].low > val) bbox[i].low = val;
1224 if (bbox[i].high < val) bbox[i].high = val;
1225 }
1226 }
1227 }
1228 else
1229 {
1230 Offset idx;
1231 Dimension cutfeat;
1232 DistanceType cutval;
1233 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1234
1235 node->node_type.sub.divfeat = cutfeat;
1236
1237 std::future<NodePtr> left_future, right_future;
1238
1239 BoundingBox left_bbox(bbox);
1240 left_bbox[cutfeat].high = cutval;
1241 if (++thread_count < n_thread_build_)
1242 {
1243 left_future = std::async(
1244 std::launch::async, &KDTreeBaseClass::divideTreeConcurrent,
1245 this, std::ref(obj), left, left + idx, std::ref(left_bbox),
1246 std::ref(thread_count), std::ref(mutex));
1247 }
1248 else
1249 {
1250 --thread_count;
1251 node->child1 = this->divideTreeConcurrent(
1252 obj, left, left + idx, left_bbox, thread_count, mutex);
1253 }
1254
1255 BoundingBox right_bbox(bbox);
1256 right_bbox[cutfeat].low = cutval;
1257 if (++thread_count < n_thread_build_)
1258 {
1259 right_future = std::async(
1260 std::launch::async, &KDTreeBaseClass::divideTreeConcurrent,
1261 this, std::ref(obj), left + idx, right,
1262 std::ref(right_bbox), std::ref(thread_count),
1263 std::ref(mutex));
1264 }
1265 else
1266 {
1267 --thread_count;
1268 node->child2 = this->divideTreeConcurrent(
1269 obj, left + idx, right, right_bbox, thread_count, mutex);
1270 }
1271
1272 if (left_future.valid())
1273 {
1274 node->child1 = left_future.get();
1275 --thread_count;
1276 }
1277 if (right_future.valid())
1278 {
1279 node->child2 = right_future.get();
1280 --thread_count;
1281 }
1282
1283 node->node_type.sub.divlow = left_bbox[cutfeat].high;
1284 node->node_type.sub.divhigh = right_bbox[cutfeat].low;
1285
1286 for (Dimension i = 0; i < dims; ++i)
1287 {
1288 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1289 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1290 }
1291 }
1292
1293 return node;
1294 }
1295
1296 void middleSplit_(
1297 const Derived& obj, const Offset ind, const Size count, Offset& index,
1298 Dimension& cutfeat, DistanceType& cutval, const BoundingBox& bbox)
1299 {
1300 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1301 const auto EPS = static_cast<DistanceType>(0.00001);
1302 ElementType max_span = bbox[0].high - bbox[0].low;
1303 for (Dimension i = 1; i < dims; ++i)
1304 {
1305 ElementType span = bbox[i].high - bbox[i].low;
1306 if (span > max_span) { max_span = span; }
1307 }
1308 ElementType max_spread = -1;
1309 cutfeat = 0;
1310 ElementType min_elem = 0, max_elem = 0;
1311 for (Dimension i = 0; i < dims; ++i)
1312 {
1313 ElementType span = bbox[i].high - bbox[i].low;
1314 if (span > (1 - EPS) * max_span)
1315 {
1316 ElementType min_elem_, max_elem_;
1317 computeMinMax(obj, ind, count, i, min_elem_, max_elem_);
1318 ElementType spread = max_elem_ - min_elem_;
1319 if (spread > max_spread)
1320 {
1321 cutfeat = i;
1322 max_spread = spread;
1323 min_elem = min_elem_;
1324 max_elem = max_elem_;
1325 }
1326 }
1327 }
1328 // split in the middle
1329 DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;
1330
1331 if (split_val < min_elem)
1332 cutval = min_elem;
1333 else if (split_val > max_elem)
1334 cutval = max_elem;
1335 else
1336 cutval = split_val;
1337
1338 Offset lim1, lim2;
1339 planeSplit(obj, ind, count, cutfeat, cutval, lim1, lim2);
1340
1341 if (lim1 > count / 2)
1342 index = lim1;
1343 else if (lim2 < count / 2)
1344 index = lim2;
1345 else
1346 index = count / 2;
1347 }
1348
1359 const Derived& obj, const Offset ind, const Size count,
1360 const Dimension cutfeat, const DistanceType& cutval, Offset& lim1,
1361 Offset& lim2)
1362 {
1363 /* Move vector indices for left subtree to front of list. */
1364 Offset left = 0;
1365 Offset right = count - 1;
1366 for (;;)
1367 {
1368 while (left <= right &&
1369 dataset_get(obj, vAcc_[ind + left], cutfeat) < cutval)
1370 ++left;
1371 while (right && left <= right &&
1372 dataset_get(obj, vAcc_[ind + right], cutfeat) >= cutval)
1373 --right;
1374 if (left > right || !right)
1375 break; // "!right" was added to support unsigned Index types
1376 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1377 ++left;
1378 --right;
1379 }
1380 /* If either list is empty, it means that all remaining features
1381 * are identical. Split in the middle to maintain a balanced tree.
1382 */
1383 lim1 = left;
1384 right = count - 1;
1385 for (;;)
1386 {
1387 while (left <= right &&
1388 dataset_get(obj, vAcc_[ind + left], cutfeat) <= cutval)
1389 ++left;
1390 while (right && left <= right &&
1391 dataset_get(obj, vAcc_[ind + right], cutfeat) > cutval)
1392 --right;
1393 if (left > right || !right)
1394 break; // "!right" was added to support unsigned Index types
1395 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1396 ++left;
1397 --right;
1398 }
1399 lim2 = left;
1400 }
1401
1402 DistanceType computeInitialDistances(
1403 const Derived& obj, const ElementType* vec,
1404 distance_vector_t& dists) const
1405 {
1406 assert(vec);
1407 DistanceType dist = DistanceType();
1408
1409 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim_); ++i)
1410 {
1411 if (vec[i] < obj.root_bbox_[i].low)
1412 {
1413 dists[i] =
1414 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].low, i);
1415 dist += dists[i];
1416 }
1417 if (vec[i] > obj.root_bbox_[i].high)
1418 {
1419 dists[i] =
1420 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].high, i);
1421 dist += dists[i];
1422 }
1423 }
1424 return dist;
1425 }
1426
1427 static void save_tree(
1428 const Derived& obj, std::ostream& stream, const NodeConstPtr tree)
1429 {
1430 save_value(stream, *tree);
1431 if (tree->child1 != nullptr) { save_tree(obj, stream, tree->child1); }
1432 if (tree->child2 != nullptr) { save_tree(obj, stream, tree->child2); }
1433 }
1434
1435 static void load_tree(Derived& obj, std::istream& stream, NodePtr& tree)
1436 {
1437 tree = obj.pool_.template allocate<Node>();
1438 load_value(stream, *tree);
1439 if (tree->child1 != nullptr) { load_tree(obj, stream, tree->child1); }
1440 if (tree->child2 != nullptr) { load_tree(obj, stream, tree->child2); }
1441 }
1442
1448 void saveIndex(const Derived& obj, std::ostream& stream) const
1449 {
1450 save_value(stream, obj.size_);
1451 save_value(stream, obj.dim_);
1452 save_value(stream, obj.root_bbox_);
1453 save_value(stream, obj.leaf_max_size_);
1454 save_value(stream, obj.vAcc_);
1455 if (obj.root_node_) save_tree(obj, stream, obj.root_node_);
1456 }
1457
1463 void loadIndex(Derived& obj, std::istream& stream)
1464 {
1465 load_value(stream, obj.size_);
1466 load_value(stream, obj.dim_);
1467 load_value(stream, obj.root_bbox_);
1468 load_value(stream, obj.leaf_max_size_);
1469 load_value(stream, obj.vAcc_);
1470 load_tree(obj, stream, obj.root_node_);
1471 }
1472};
1473
1515template <
1516 typename Distance, class DatasetAdaptor, int32_t DIM = -1,
1517 typename IndexType = uint32_t>
1519 : public KDTreeBaseClass<
1520 KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, IndexType>,
1521 Distance, DatasetAdaptor, DIM, IndexType>
1522{
1523 public:
1527 Distance, DatasetAdaptor, DIM, IndexType>&) = delete;
1528
1530 const DatasetAdaptor& dataset_;
1531
1532 const KDTreeSingleIndexAdaptorParams indexParams;
1533
1534 Distance distance_;
1535
1536 using Base = typename nanoflann::KDTreeBaseClass<
1538 Distance, DatasetAdaptor, DIM, IndexType>,
1539 Distance, DatasetAdaptor, DIM, IndexType>;
1540
1541 using Offset = typename Base::Offset;
1542 using Size = typename Base::Size;
1543 using Dimension = typename Base::Dimension;
1544
1545 using ElementType = typename Base::ElementType;
1546 using DistanceType = typename Base::DistanceType;
1547
1548 using Node = typename Base::Node;
1549 using NodePtr = Node*;
1550
1551 using Interval = typename Base::Interval;
1552
1555 using BoundingBox = typename Base::BoundingBox;
1556
1559 using distance_vector_t = typename Base::distance_vector_t;
1560
1581 template <class... Args>
1583 const Dimension dimensionality, const DatasetAdaptor& inputData,
1584 const KDTreeSingleIndexAdaptorParams& params, Args&&... args)
1585 : dataset_(inputData),
1586 indexParams(params),
1587 distance_(inputData, std::forward<Args>(args)...)
1588 {
1589 init(dimensionality, params);
1590 }
1591
1592 explicit KDTreeSingleIndexAdaptor(
1593 const Dimension dimensionality, const DatasetAdaptor& inputData,
1594 const KDTreeSingleIndexAdaptorParams& params = {})
1595 : dataset_(inputData), indexParams(params), distance_(inputData)
1596 {
1597 init(dimensionality, params);
1598 }
1599
1600 private:
1601 void init(
1602 const Dimension dimensionality,
1603 const KDTreeSingleIndexAdaptorParams& params)
1604 {
1605 Base::size_ = dataset_.kdtree_get_point_count();
1606 Base::size_at_index_build_ = Base::size_;
1607 Base::dim_ = dimensionality;
1608 if (DIM > 0) Base::dim_ = DIM;
1609 Base::leaf_max_size_ = params.leaf_max_size;
1610 if (params.n_thread_build > 0)
1611 {
1612 Base::n_thread_build_ = params.n_thread_build;
1613 }
1614 else
1615 {
1616 Base::n_thread_build_ =
1617 std::max(std::thread::hardware_concurrency(), 1u);
1618 }
1619
1620 if (!(params.flags &
1621 KDTreeSingleIndexAdaptorFlags::SkipInitialBuildIndex))
1622 {
1623 // Build KD-tree:
1624 buildIndex();
1625 }
1626 }
1627
1628 public:
1633 {
1634 Base::size_ = dataset_.kdtree_get_point_count();
1635 Base::size_at_index_build_ = Base::size_;
1636 init_vind();
1637 this->freeIndex(*this);
1638 Base::size_at_index_build_ = Base::size_;
1639 if (Base::size_ == 0) return;
1640 computeBoundingBox(Base::root_bbox_);
1641 // construct the tree
1642 if (Base::n_thread_build_ == 1)
1643 {
1644 Base::root_node_ =
1645 this->divideTree(*this, 0, Base::size_, Base::root_bbox_);
1646 }
1647 else
1648 {
1649 std::atomic<unsigned int> thread_count(0u);
1650 std::mutex mutex;
1651 Base::root_node_ = this->divideTreeConcurrent(
1652 *this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
1653 }
1654 }
1655
1675 template <typename RESULTSET>
1677 RESULTSET& result, const ElementType* vec,
1678 const SearchParameters& searchParams = {}) const
1679 {
1680 assert(vec);
1681 if (this->size(*this) == 0) return false;
1682 if (!Base::root_node_)
1683 throw std::runtime_error(
1684 "[nanoflann] findNeighbors() called before building the "
1685 "index.");
1686 float epsError = 1 + searchParams.eps;
1687
1688 // fixed or variable-sized container (depending on DIM)
1689 distance_vector_t dists;
1690 // Fill it with zeros.
1691 auto zero = static_cast<decltype(result.worstDist())>(0);
1692 assign(dists, (DIM > 0 ? DIM : Base::dim_), zero);
1693 DistanceType dist = this->computeInitialDistances(*this, vec, dists);
1694 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
1695 return result.full();
1696 }
1697
1714 const ElementType* query_point, const Size num_closest,
1715 IndexType* out_indices, DistanceType* out_distances) const
1716 {
1718 resultSet.init(out_indices, out_distances);
1719 findNeighbors(resultSet, query_point);
1720 return resultSet.size();
1721 }
1722
1743 const ElementType* query_point, const DistanceType& radius,
1744 std::vector<ResultItem<IndexType, DistanceType>>& IndicesDists,
1745 const SearchParameters& searchParams = {}) const
1746 {
1748 radius, IndicesDists);
1749 const Size nFound =
1750 radiusSearchCustomCallback(query_point, resultSet, searchParams);
1751 if (searchParams.sorted)
1752 std::sort(
1753 IndicesDists.begin(), IndicesDists.end(), IndexDist_Sorter());
1754 return nFound;
1755 }
1756
1762 template <class SEARCH_CALLBACK>
1764 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
1765 const SearchParameters& searchParams = {}) const
1766 {
1767 findNeighbors(resultSet, query_point, searchParams);
1768 return resultSet.size();
1769 }
1770
1788 const ElementType* query_point, const Size num_closest,
1789 IndexType* out_indices, DistanceType* out_distances,
1790 const DistanceType& radius) const
1791 {
1793 num_closest, radius);
1794 resultSet.init(out_indices, out_distances);
1795 findNeighbors(resultSet, query_point);
1796 return resultSet.size();
1797 }
1798
1801 public:
1805 {
1806 // Create a permutable array of indices to the input vectors.
1807 Base::size_ = dataset_.kdtree_get_point_count();
1808 if (Base::vAcc_.size() != Base::size_) Base::vAcc_.resize(Base::size_);
1809 for (Size i = 0; i < Base::size_; i++) Base::vAcc_[i] = i;
1810 }
1811
1812 void computeBoundingBox(BoundingBox& bbox)
1813 {
1814 const auto dims = (DIM > 0 ? DIM : Base::dim_);
1815 resize(bbox, dims);
1816 if (dataset_.kdtree_get_bbox(bbox))
1817 {
1818 // Done! It was implemented in derived class
1819 }
1820 else
1821 {
1822 const Size N = dataset_.kdtree_get_point_count();
1823 if (!N)
1824 throw std::runtime_error(
1825 "[nanoflann] computeBoundingBox() called but "
1826 "no data points found.");
1827 for (Dimension i = 0; i < dims; ++i)
1828 {
1829 bbox[i].low = bbox[i].high =
1830 this->dataset_get(*this, Base::vAcc_[0], i);
1831 }
1832 for (Offset k = 1; k < N; ++k)
1833 {
1834 for (Dimension i = 0; i < dims; ++i)
1835 {
1836 const auto val =
1837 this->dataset_get(*this, Base::vAcc_[k], i);
1838 if (val < bbox[i].low) bbox[i].low = val;
1839 if (val > bbox[i].high) bbox[i].high = val;
1840 }
1841 }
1842 }
1843 }
1844
1851 template <class RESULTSET>
1853 RESULTSET& result_set, const ElementType* vec, const NodePtr node,
1854 DistanceType mindist, distance_vector_t& dists,
1855 const float epsError) const
1856 {
1857 /* If this is a leaf node, then do check and return. */
1858 if ((node->child1 == nullptr) && (node->child2 == nullptr))
1859 {
1860 DistanceType worst_dist = result_set.worstDist();
1861 for (Offset i = node->node_type.lr.left;
1862 i < node->node_type.lr.right; ++i)
1863 {
1864 const IndexType accessor = Base::vAcc_[i]; // reorder... : i;
1865 DistanceType dist = distance_.evalMetric(
1866 vec, accessor, (DIM > 0 ? DIM : Base::dim_));
1867 if (dist < worst_dist)
1868 {
1869 if (!result_set.addPoint(dist, Base::vAcc_[i]))
1870 {
1871 // the resultset doesn't want to receive any more
1872 // points, we're done searching!
1873 return false;
1874 }
1875 }
1876 }
1877 return true;
1878 }
1879
1880 /* Which child branch should be taken first? */
1881 Dimension idx = node->node_type.sub.divfeat;
1882 ElementType val = vec[idx];
1883 DistanceType diff1 = val - node->node_type.sub.divlow;
1884 DistanceType diff2 = val - node->node_type.sub.divhigh;
1885
1886 NodePtr bestChild;
1887 NodePtr otherChild;
1888 DistanceType cut_dist;
1889 if ((diff1 + diff2) < 0)
1890 {
1891 bestChild = node->child1;
1892 otherChild = node->child2;
1893 cut_dist =
1894 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
1895 }
1896 else
1897 {
1898 bestChild = node->child2;
1899 otherChild = node->child1;
1900 cut_dist =
1901 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
1902 }
1903
1904 /* Call recursively to search next level down. */
1905 if (!searchLevel(result_set, vec, bestChild, mindist, dists, epsError))
1906 {
1907 // the resultset doesn't want to receive any more points, we're done
1908 // searching!
1909 return false;
1910 }
1911
1912 DistanceType dst = dists[idx];
1913 mindist = mindist + cut_dist - dst;
1914 dists[idx] = cut_dist;
1915 if (mindist * epsError <= result_set.worstDist())
1916 {
1917 if (!searchLevel(
1918 result_set, vec, otherChild, mindist, dists, epsError))
1919 {
1920 // the resultset doesn't want to receive any more points, we're
1921 // done searching!
1922 return false;
1923 }
1924 }
1925 dists[idx] = dst;
1926 return true;
1927 }
1928
1929 public:
1935 void saveIndex(std::ostream& stream) const
1936 {
1937 Base::saveIndex(*this, stream);
1938 }
1939
1945 void loadIndex(std::istream& stream) { Base::loadIndex(*this, stream); }
1946
1947}; // class KDTree
1948
1986template <
1987 typename Distance, class DatasetAdaptor, int32_t DIM = -1,
1988 typename IndexType = uint32_t>
1990 : public KDTreeBaseClass<
1991 KDTreeSingleIndexDynamicAdaptor_<
1992 Distance, DatasetAdaptor, DIM, IndexType>,
1993 Distance, DatasetAdaptor, DIM, IndexType>
1994{
1995 public:
1999 const DatasetAdaptor& dataset_;
2000
2001 KDTreeSingleIndexAdaptorParams index_params_;
2002
2003 std::vector<int>& treeIndex_;
2004
2005 Distance distance_;
2006
2007 using Base = typename nanoflann::KDTreeBaseClass<
2009 Distance, DatasetAdaptor, DIM, IndexType>,
2010 Distance, DatasetAdaptor, DIM, IndexType>;
2011
2012 using ElementType = typename Base::ElementType;
2013 using DistanceType = typename Base::DistanceType;
2014
2015 using Offset = typename Base::Offset;
2016 using Size = typename Base::Size;
2017 using Dimension = typename Base::Dimension;
2018
2019 using Node = typename Base::Node;
2020 using NodePtr = Node*;
2021
2022 using Interval = typename Base::Interval;
2025 using BoundingBox = typename Base::BoundingBox;
2026
2029 using distance_vector_t = typename Base::distance_vector_t;
2030
2047 const Dimension dimensionality, const DatasetAdaptor& inputData,
2048 std::vector<int>& treeIndex,
2049 const KDTreeSingleIndexAdaptorParams& params =
2051 : dataset_(inputData),
2052 index_params_(params),
2053 treeIndex_(treeIndex),
2054 distance_(inputData)
2055 {
2056 Base::size_ = 0;
2057 Base::size_at_index_build_ = 0;
2058 for (auto& v : Base::root_bbox_) v = {};
2059 Base::dim_ = dimensionality;
2060 if (DIM > 0) Base::dim_ = DIM;
2061 Base::leaf_max_size_ = params.leaf_max_size;
2062 if (params.n_thread_build > 0)
2063 {
2064 Base::n_thread_build_ = params.n_thread_build;
2065 }
2066 else
2067 {
2068 Base::n_thread_build_ =
2069 std::max(std::thread::hardware_concurrency(), 1u);
2070 }
2071 }
2072
2075 const KDTreeSingleIndexDynamicAdaptor_& rhs) = default;
2076
2080 {
2082 std::swap(Base::vAcc_, tmp.Base::vAcc_);
2083 std::swap(Base::leaf_max_size_, tmp.Base::leaf_max_size_);
2084 std::swap(index_params_, tmp.index_params_);
2085 std::swap(treeIndex_, tmp.treeIndex_);
2086 std::swap(Base::size_, tmp.Base::size_);
2087 std::swap(Base::size_at_index_build_, tmp.Base::size_at_index_build_);
2088 std::swap(Base::root_node_, tmp.Base::root_node_);
2089 std::swap(Base::root_bbox_, tmp.Base::root_bbox_);
2090 std::swap(Base::pool_, tmp.Base::pool_);
2091 return *this;
2092 }
2093
2098 {
2099 Base::size_ = Base::vAcc_.size();
2100 this->freeIndex(*this);
2101 Base::size_at_index_build_ = Base::size_;
2102 if (Base::size_ == 0) return;
2103 computeBoundingBox(Base::root_bbox_);
2104 // construct the tree
2105 if (Base::n_thread_build_ == 1)
2106 {
2107 Base::root_node_ =
2108 this->divideTree(*this, 0, Base::size_, Base::root_bbox_);
2109 }
2110 else
2111 {
2112 std::atomic<unsigned int> thread_count(0u);
2113 std::mutex mutex;
2114 Base::root_node_ = this->divideTreeConcurrent(
2115 *this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
2116 }
2117 }
2118
2142 template <typename RESULTSET>
2144 RESULTSET& result, const ElementType* vec,
2145 const SearchParameters& searchParams = {}) const
2146 {
2147 assert(vec);
2148 if (this->size(*this) == 0) return false;
2149 if (!Base::root_node_) return false;
2150 float epsError = 1 + searchParams.eps;
2151
2152 // fixed or variable-sized container (depending on DIM)
2153 distance_vector_t dists;
2154 // Fill it with zeros.
2155 assign(
2156 dists, (DIM > 0 ? DIM : Base::dim_),
2157 static_cast<typename distance_vector_t::value_type>(0));
2158 DistanceType dist = this->computeInitialDistances(*this, vec, dists);
2159 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
2160 return result.full();
2161 }
2162
2178 const ElementType* query_point, const Size num_closest,
2179 IndexType* out_indices, DistanceType* out_distances,
2180 const SearchParameters& searchParams = {}) const
2181 {
2183 resultSet.init(out_indices, out_distances);
2184 findNeighbors(resultSet, query_point, searchParams);
2185 return resultSet.size();
2186 }
2187
2208 const ElementType* query_point, const DistanceType& radius,
2209 std::vector<ResultItem<IndexType, DistanceType>>& IndicesDists,
2210 const SearchParameters& searchParams = {}) const
2211 {
2213 radius, IndicesDists);
2214 const size_t nFound =
2215 radiusSearchCustomCallback(query_point, resultSet, searchParams);
2216 if (searchParams.sorted)
2217 std::sort(
2218 IndicesDists.begin(), IndicesDists.end(), IndexDist_Sorter());
2219 return nFound;
2220 }
2221
2227 template <class SEARCH_CALLBACK>
2229 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
2230 const SearchParameters& searchParams = {}) const
2231 {
2232 findNeighbors(resultSet, query_point, searchParams);
2233 return resultSet.size();
2234 }
2235
2238 public:
2239 void computeBoundingBox(BoundingBox& bbox)
2240 {
2241 const auto dims = (DIM > 0 ? DIM : Base::dim_);
2242 resize(bbox, dims);
2243
2244 if (dataset_.kdtree_get_bbox(bbox))
2245 {
2246 // Done! It was implemented in derived class
2247 }
2248 else
2249 {
2250 const Size N = Base::size_;
2251 if (!N)
2252 throw std::runtime_error(
2253 "[nanoflann] computeBoundingBox() called but "
2254 "no data points found.");
2255 for (Dimension i = 0; i < dims; ++i)
2256 {
2257 bbox[i].low = bbox[i].high =
2258 this->dataset_get(*this, Base::vAcc_[0], i);
2259 }
2260 for (Offset k = 1; k < N; ++k)
2261 {
2262 for (Dimension i = 0; i < dims; ++i)
2263 {
2264 const auto val =
2265 this->dataset_get(*this, Base::vAcc_[k], i);
2266 if (val < bbox[i].low) bbox[i].low = val;
2267 if (val > bbox[i].high) bbox[i].high = val;
2268 }
2269 }
2270 }
2271 }
2272
2277 template <class RESULTSET>
2279 RESULTSET& result_set, const ElementType* vec, const NodePtr node,
2280 DistanceType mindist, distance_vector_t& dists,
2281 const float epsError) const
2282 {
2283 /* If this is a leaf node, then do check and return. */
2284 if ((node->child1 == nullptr) && (node->child2 == nullptr))
2285 {
2286 DistanceType worst_dist = result_set.worstDist();
2287 for (Offset i = node->node_type.lr.left;
2288 i < node->node_type.lr.right; ++i)
2289 {
2290 const IndexType index = Base::vAcc_[i]; // reorder... : i;
2291 if (treeIndex_[index] == -1) continue;
2292 DistanceType dist = distance_.evalMetric(
2293 vec, index, (DIM > 0 ? DIM : Base::dim_));
2294 if (dist < worst_dist)
2295 {
2296 if (!result_set.addPoint(
2297 static_cast<typename RESULTSET::DistanceType>(dist),
2298 static_cast<typename RESULTSET::IndexType>(
2299 Base::vAcc_[i])))
2300 {
2301 // the resultset doesn't want to receive any more
2302 // points, we're done searching!
2303 return; // false;
2304 }
2305 }
2306 }
2307 return;
2308 }
2309
2310 /* Which child branch should be taken first? */
2311 Dimension idx = node->node_type.sub.divfeat;
2312 ElementType val = vec[idx];
2313 DistanceType diff1 = val - node->node_type.sub.divlow;
2314 DistanceType diff2 = val - node->node_type.sub.divhigh;
2315
2316 NodePtr bestChild;
2317 NodePtr otherChild;
2318 DistanceType cut_dist;
2319 if ((diff1 + diff2) < 0)
2320 {
2321 bestChild = node->child1;
2322 otherChild = node->child2;
2323 cut_dist =
2324 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
2325 }
2326 else
2327 {
2328 bestChild = node->child2;
2329 otherChild = node->child1;
2330 cut_dist =
2331 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
2332 }
2333
2334 /* Call recursively to search next level down. */
2335 searchLevel(result_set, vec, bestChild, mindist, dists, epsError);
2336
2337 DistanceType dst = dists[idx];
2338 mindist = mindist + cut_dist - dst;
2339 dists[idx] = cut_dist;
2340 if (mindist * epsError <= result_set.worstDist())
2341 {
2342 searchLevel(result_set, vec, otherChild, mindist, dists, epsError);
2343 }
2344 dists[idx] = dst;
2345 }
2346
2347 public:
2353 void saveIndex(std::ostream& stream) { saveIndex(*this, stream); }
2354
2360 void loadIndex(std::istream& stream) { loadIndex(*this, stream); }
2361};
2362
2377template <
2378 typename Distance, class DatasetAdaptor, int32_t DIM = -1,
2379 typename IndexType = uint32_t>
2381{
2382 public:
2383 using ElementType = typename Distance::ElementType;
2384 using DistanceType = typename Distance::DistanceType;
2385
2386 using Offset = typename KDTreeSingleIndexDynamicAdaptor_<
2387 Distance, DatasetAdaptor, DIM>::Offset;
2388 using Size = typename KDTreeSingleIndexDynamicAdaptor_<
2389 Distance, DatasetAdaptor, DIM>::Size;
2390 using Dimension = typename KDTreeSingleIndexDynamicAdaptor_<
2391 Distance, DatasetAdaptor, DIM>::Dimension;
2392
2393 protected:
2394 Size leaf_max_size_;
2395 Size treeCount_;
2396 Size pointCount_;
2397
2401 const DatasetAdaptor& dataset_;
2402
2405 std::vector<int> treeIndex_;
2406 std::unordered_set<int> removedPoints_;
2407
2408 KDTreeSingleIndexAdaptorParams index_params_;
2409
2410 Dimension dim_;
2411
2413 Distance, DatasetAdaptor, DIM, IndexType>;
2414 std::vector<index_container_t> index_;
2415
2416 public:
2419 const std::vector<index_container_t>& getAllIndices() const
2420 {
2421 return index_;
2422 }
2423
2424 private:
2426 int First0Bit(IndexType num)
2427 {
2428 int pos = 0;
2429 while (num & 1)
2430 {
2431 num = num >> 1;
2432 pos++;
2433 }
2434 return pos;
2435 }
2436
2438 void init()
2439 {
2440 using my_kd_tree_t = KDTreeSingleIndexDynamicAdaptor_<
2441 Distance, DatasetAdaptor, DIM, IndexType>;
2442 std::vector<my_kd_tree_t> index(
2443 treeCount_,
2444 my_kd_tree_t(dim_ /*dim*/, dataset_, treeIndex_, index_params_));
2445 index_ = index;
2446 }
2447
2448 public:
2449 Distance distance_;
2450
2467 const int dimensionality, const DatasetAdaptor& inputData,
2468 const KDTreeSingleIndexAdaptorParams& params =
2470 const size_t maximumPointCount = 1000000000U)
2471 : dataset_(inputData), index_params_(params), distance_(inputData)
2472 {
2473 treeCount_ = static_cast<size_t>(std::log2(maximumPointCount)) + 1;
2474 pointCount_ = 0U;
2475 dim_ = dimensionality;
2476 treeIndex_.clear();
2477 if (DIM > 0) dim_ = DIM;
2478 leaf_max_size_ = params.leaf_max_size;
2479 init();
2480 const size_t num_initial_points = dataset_.kdtree_get_point_count();
2481 if (num_initial_points > 0) { addPoints(0, num_initial_points - 1); }
2482 }
2483
2487 Distance, DatasetAdaptor, DIM, IndexType>&) = delete;
2488
2490 void addPoints(IndexType start, IndexType end)
2491 {
2492 const Size count = end - start + 1;
2493 int maxIndex = 0;
2494 treeIndex_.resize(treeIndex_.size() + count);
2495 for (IndexType idx = start; idx <= end; idx++)
2496 {
2497 const int pos = First0Bit(pointCount_);
2498 maxIndex = std::max(pos, maxIndex);
2499 treeIndex_[pointCount_] = pos;
2500
2501 const auto it = removedPoints_.find(idx);
2502 if (it != removedPoints_.end())
2503 {
2504 removedPoints_.erase(it);
2505 treeIndex_[idx] = pos;
2506 }
2507
2508 for (int i = 0; i < pos; i++)
2509 {
2510 for (int j = 0; j < static_cast<int>(index_[i].vAcc_.size());
2511 j++)
2512 {
2513 index_[pos].vAcc_.push_back(index_[i].vAcc_[j]);
2514 if (treeIndex_[index_[i].vAcc_[j]] != -1)
2515 treeIndex_[index_[i].vAcc_[j]] = pos;
2516 }
2517 index_[i].vAcc_.clear();
2518 }
2519 index_[pos].vAcc_.push_back(idx);
2520 pointCount_++;
2521 }
2522
2523 for (int i = 0; i <= maxIndex; ++i)
2524 {
2525 index_[i].freeIndex(index_[i]);
2526 if (!index_[i].vAcc_.empty()) index_[i].buildIndex();
2527 }
2528 }
2529
2531 void removePoint(size_t idx)
2532 {
2533 if (idx >= pointCount_) return;
2534 removedPoints_.insert(idx);
2535 treeIndex_[idx] = -1;
2536 }
2537
2554 template <typename RESULTSET>
2556 RESULTSET& result, const ElementType* vec,
2557 const SearchParameters& searchParams = {}) const
2558 {
2559 for (size_t i = 0; i < treeCount_; i++)
2560 {
2561 index_[i].findNeighbors(result, &vec[0], searchParams);
2562 }
2563 return result.full();
2564 }
2565};
2566
2592template <
2593 class MatrixType, int32_t DIM = -1, class Distance = nanoflann::metric_L2,
2594 bool row_major = true>
2596{
2597 using self_t =
2599 using num_t = typename MatrixType::Scalar;
2600 using IndexType = typename MatrixType::Index;
2601 using metric_t = typename Distance::template traits<
2602 num_t, self_t, IndexType>::distance_t;
2603
2605 metric_t, self_t,
2606 row_major ? MatrixType::ColsAtCompileTime
2607 : MatrixType::RowsAtCompileTime,
2608 IndexType>;
2609
2610 index_t* index_;
2612
2613 using Offset = typename index_t::Offset;
2614 using Size = typename index_t::Size;
2615 using Dimension = typename index_t::Dimension;
2616
2619 const Dimension dimensionality,
2620 const std::reference_wrapper<const MatrixType>& mat,
2621 const int leaf_max_size = 10)
2622 : m_data_matrix(mat)
2623 {
2624 const auto dims = row_major ? mat.get().cols() : mat.get().rows();
2625 if (static_cast<Dimension>(dims) != dimensionality)
2626 throw std::runtime_error(
2627 "Error: 'dimensionality' must match column count in data "
2628 "matrix");
2629 if (DIM > 0 && static_cast<int32_t>(dims) != DIM)
2630 throw std::runtime_error(
2631 "Data set dimensionality does not match the 'DIM' template "
2632 "argument");
2633 index_ = new index_t(
2634 dims, *this /* adaptor */,
2636 }
2637
2638 public:
2641
2642 ~KDTreeEigenMatrixAdaptor() { delete index_; }
2643
2644 const std::reference_wrapper<const MatrixType> m_data_matrix;
2645
2654 void query(
2655 const num_t* query_point, const Size num_closest,
2656 IndexType* out_indices, num_t* out_distances) const
2657 {
2658 nanoflann::KNNResultSet<num_t, IndexType> resultSet(num_closest);
2659 resultSet.init(out_indices, out_distances);
2660 index_->findNeighbors(resultSet, query_point);
2661 }
2662
2666 const self_t& derived() const { return *this; }
2667 self_t& derived() { return *this; }
2668
2669 // Must return the number of data points
2670 Size kdtree_get_point_count() const
2671 {
2672 if (row_major)
2673 return m_data_matrix.get().rows();
2674 else
2675 return m_data_matrix.get().cols();
2676 }
2677
2678 // Returns the dim'th component of the idx'th point in the class:
2679 num_t kdtree_get_pt(const IndexType idx, size_t dim) const
2680 {
2681 if (row_major)
2682 return m_data_matrix.get().coeff(idx, IndexType(dim));
2683 else
2684 return m_data_matrix.get().coeff(IndexType(dim), idx);
2685 }
2686
2687 // Optional bounding-box computation: return false to default to a standard
2688 // bbox computation loop.
2689 // Return true if the BBOX was already computed by the class and returned
2690 // in "bb" so it can be avoided to redo it again. Look at bb.size() to
2691 // find out the expected dimensionality (e.g. 2 or 3 for point clouds)
2692 template <class BBOX>
2693 bool kdtree_get_bbox(BBOX& /*bb*/) const
2694 {
2695 return false;
2696 }
2697
2700}; // end of KDTreeEigenMatrixAdaptor
// end of grouping
2704} // namespace nanoflann
Definition nanoflann.hpp:993
Size usedMemory(Derived &obj)
Definition nanoflann.hpp:1098
NodePtr divideTreeConcurrent(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex)
Definition nanoflann.hpp:1195
void planeSplit(const Derived &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)
Definition nanoflann.hpp:1358
typename array_or_vector< DIM, DistanceType >::type distance_vector_t
Definition nanoflann.hpp:1067
std::vector< IndexType > vAcc_
Definition nanoflann.hpp:1010
Size size(const Derived &obj) const
Definition nanoflann.hpp:1082
void freeIndex(Derived &obj)
Definition nanoflann.hpp:997
void loadIndex(Derived &obj, std::istream &stream)
Definition nanoflann.hpp:1463
typename array_or_vector< DIM, Interval >::type BoundingBox
Definition nanoflann.hpp:1063
BoundingBox root_bbox_
Definition nanoflann.hpp:1070
void saveIndex(const Derived &obj, std::ostream &stream) const
Definition nanoflann.hpp:1448
PooledAllocator pool_
Definition nanoflann.hpp:1079
NodePtr divideTree(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox)
Definition nanoflann.hpp:1126
ElementType dataset_get(const Derived &obj, IndexType element, Dimension component) const
Helper accessor to the dataset points:
Definition nanoflann.hpp:1088
Size veclen(const Derived &obj)
Definition nanoflann.hpp:1085
Definition nanoflann.hpp:1522
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1763
Size rknnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const
Definition nanoflann.hpp:1787
KDTreeSingleIndexAdaptor(const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete
KDTreeSingleIndexAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params, Args &&... args)
Definition nanoflann.hpp:1582
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1742
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:1559
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:1945
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:1555
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances) const
Definition nanoflann.hpp:1713
void init_vind()
Definition nanoflann.hpp:1804
const DatasetAdaptor & dataset_
Definition nanoflann.hpp:1530
void saveIndex(std::ostream &stream) const
Definition nanoflann.hpp:1935
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1676
void buildIndex()
Definition nanoflann.hpp:1632
bool searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:1852
Definition nanoflann.hpp:1994
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2207
KDTreeSingleIndexDynamicAdaptor_(const Dimension dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
Definition nanoflann.hpp:2046
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:2025
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:1999
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2228
KDTreeSingleIndexDynamicAdaptor_(const KDTreeSingleIndexDynamicAdaptor_ &rhs)=default
void buildIndex()
Definition nanoflann.hpp:2097
void saveIndex(std::ostream &stream)
Definition nanoflann.hpp:2353
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:2029
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:2360
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2177
void searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:2278
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2143
KDTreeSingleIndexDynamicAdaptor_ operator=(const KDTreeSingleIndexDynamicAdaptor_ &rhs)
Definition nanoflann.hpp:2078
Definition nanoflann.hpp:2381
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2555
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:2401
void removePoint(size_t idx)
Definition nanoflann.hpp:2531
void addPoints(IndexType start, IndexType end)
Definition nanoflann.hpp:2490
KDTreeSingleIndexDynamicAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams(), const size_t maximumPointCount=1000000000U)
Definition nanoflann.hpp:2466
std::vector< int > treeIndex_
Definition nanoflann.hpp:2405
const std::vector< index_container_t > & getAllIndices() const
Definition nanoflann.hpp:2419
Dimension dim_
Dimensionality of each data point.
Definition nanoflann.hpp:2410
KDTreeSingleIndexDynamicAdaptor(const KDTreeSingleIndexDynamicAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete
Definition nanoflann.hpp:167
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:203
Definition nanoflann.hpp:833
~PooledAllocator()
Definition nanoflann.hpp:871
void free_all()
Definition nanoflann.hpp:874
void * malloc(const size_t req_size)
Definition nanoflann.hpp:890
T * allocate(const size_t count=1)
Definition nanoflann.hpp:947
PooledAllocator()
Definition nanoflann.hpp:866
Definition nanoflann.hpp:246
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:288
Definition nanoflann.hpp:363
ResultItem< IndexType, DistanceType > worst_item() const
Definition nanoflann.hpp:406
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:394
std::enable_if< has_assign< Container >::value, void >::type assign(Container &c, const size_t nElements, const T &value)
Definition nanoflann.hpp:143
T pi_const()
Definition nanoflann.hpp:86
std::enable_if< has_resize< Container >::value, void >::type resize(Container &c, const size_t nElements)
Definition nanoflann.hpp:121
Definition nanoflann.hpp:328
bool operator()(const PairType &p1, const PairType &p2) const
Definition nanoflann.hpp:331
Definition nanoflann.hpp:1045
Definition nanoflann.hpp:1020
DistanceType divlow
The values used for subdivision.
Definition nanoflann.hpp:1033
Node * child1
Definition nanoflann.hpp:1038
Dimension divfeat
Definition nanoflann.hpp:1031
Offset right
Indices of points in leaf node.
Definition nanoflann.hpp:1027
union nanoflann::KDTreeBaseClass::Node::@0 node_type
Definition nanoflann.hpp:2596
void query(const num_t *query_point, const Size num_closest, IndexType *out_indices, num_t *out_distances) const
Definition nanoflann.hpp:2654
KDTreeEigenMatrixAdaptor(const Dimension dimensionality, const std::reference_wrapper< const MatrixType > &mat, const int leaf_max_size=10)
Constructor: takes a const ref to the matrix object with the data points.
Definition nanoflann.hpp:2618
KDTreeEigenMatrixAdaptor(const self_t &)=delete
typename index_t::Offset Offset
Definition nanoflann.hpp:2613
Definition nanoflann.hpp:784
Definition nanoflann.hpp:473
Definition nanoflann.hpp:535
Definition nanoflann.hpp:600
Definition nanoflann.hpp:456
Definition nanoflann.hpp:347
DistanceType second
Distance from sample to query point.
Definition nanoflann.hpp:355
IndexType first
Index of the sample in the dataset.
Definition nanoflann.hpp:354
Definition nanoflann.hpp:645
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition nanoflann.hpp:663
Definition nanoflann.hpp:690
Definition nanoflann.hpp:803
bool sorted
distance (default: true)
Definition nanoflann.hpp:810
float eps
search for eps-approximate neighbours (default: 0)
Definition nanoflann.hpp:809
Definition nanoflann.hpp:963
Definition nanoflann.hpp:108
Definition nanoflann.hpp:97
Definition nanoflann.hpp:720
Definition nanoflann.hpp:717
Definition nanoflann.hpp:730
Definition nanoflann.hpp:740
Definition nanoflann.hpp:737
Definition nanoflann.hpp:727
Definition nanoflann.hpp:749
Definition nanoflann.hpp:746
Definition nanoflann.hpp:758
Definition nanoflann.hpp:755