nanoflann
C++ header-only ANN library
Loading...
Searching...
No Matches
nanoflann.hpp
1/***********************************************************************
2 * Software License Agreement (BSD License)
3 *
4 * Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
5 * Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
6 * Copyright 2011-2024 Jose Luis Blanco (joseluisblancoc@gmail.com).
7 * All rights reserved.
8 *
9 * THE BSD LICENSE
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 *
15 * 1. Redistributions of source code must retain the above copyright
16 * notice, this list of conditions and the following disclaimer.
17 * 2. Redistributions in binary form must reproduce the above copyright
18 * notice, this list of conditions and the following disclaimer in the
19 * documentation and/or other materials provided with the distribution.
20 *
21 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
22 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
23 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
24 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
25 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
26 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
30 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 *************************************************************************/
32
45#pragma once
46
47#include <algorithm>
48#include <array>
49#include <atomic>
50#include <cassert>
51#include <cmath> // for abs()
52#include <cstdint>
53#include <cstdlib> // for abs()
54#include <functional> // std::reference_wrapper
55#include <future>
56#include <istream>
57#include <limits> // std::numeric_limits
58#include <ostream>
59#include <stdexcept>
60#include <unordered_set>
61#include <vector>
62
64#define NANOFLANN_VERSION 0x155
65
66// Avoid conflicting declaration of min/max macros in Windows headers
67#if !defined(NOMINMAX) && \
68 (defined(_WIN32) || defined(_WIN32_) || defined(WIN32) || defined(_WIN64))
69#define NOMINMAX
70#ifdef max
71#undef max
72#undef min
73#endif
74#endif
75// Avoid conflicts with X11 headers
76#ifdef None
77#undef None
78#endif
79
80namespace nanoflann
81{
86template <typename T>
88{
89 return static_cast<T>(3.14159265358979323846);
90}
91
96template <typename T, typename = int>
97struct has_resize : std::false_type
98{
99};
100
101template <typename T>
102struct has_resize<T, decltype((void)std::declval<T>().resize(1), 0)>
103 : std::true_type
104{
105};
106
107template <typename T, typename = int>
108struct has_assign : std::false_type
109{
110};
111
112template <typename T>
113struct has_assign<T, decltype((void)std::declval<T>().assign(1, 0), 0)>
114 : std::true_type
115{
116};
117
121template <typename Container>
122inline typename std::enable_if<has_resize<Container>::value, void>::type resize(
123 Container& c, const size_t nElements)
124{
125 c.resize(nElements);
126}
127
132template <typename Container>
133inline typename std::enable_if<!has_resize<Container>::value, void>::type
134 resize(Container& c, const size_t nElements)
135{
136 if (nElements != c.size())
137 throw std::logic_error("Try to change the size of a std::array.");
138}
139
143template <typename Container, typename T>
144inline typename std::enable_if<has_assign<Container>::value, void>::type assign(
145 Container& c, const size_t nElements, const T& value)
146{
147 c.assign(nElements, value);
148}
149
153template <typename Container, typename T>
154inline typename std::enable_if<!has_assign<Container>::value, void>::type
155 assign(Container& c, const size_t nElements, const T& value)
156{
157 for (size_t i = 0; i < nElements; i++) c[i] = value;
158}
159
164template <
165 typename _DistanceType, typename _IndexType = size_t,
166 typename _CountType = size_t>
168{
169 public:
170 using DistanceType = _DistanceType;
171 using IndexType = _IndexType;
172 using CountType = _CountType;
173
174 private:
175 IndexType* indices;
176 DistanceType* dists;
177 CountType capacity;
178 CountType count;
179
180 public:
181 explicit KNNResultSet(CountType capacity_)
182 : indices(nullptr), dists(nullptr), capacity(capacity_), count(0)
183 {
184 }
185
186 void init(IndexType* indices_, DistanceType* dists_)
187 {
188 indices = indices_;
189 dists = dists_;
190 count = 0;
191 if (capacity)
192 dists[capacity - 1] = (std::numeric_limits<DistanceType>::max)();
193 }
194
195 CountType size() const { return count; }
196 bool empty() const { return count == 0; }
197 bool full() const { return count == capacity; }
198
204 bool addPoint(DistanceType dist, IndexType index)
205 {
206 CountType i;
207 for (i = count; i > 0; --i)
208 {
211#ifdef NANOFLANN_FIRST_MATCH
212 if ((dists[i - 1] > dist) ||
213 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
214 {
215#else
216 if (dists[i - 1] > dist)
217 {
218#endif
219 if (i < capacity)
220 {
221 dists[i] = dists[i - 1];
222 indices[i] = indices[i - 1];
223 }
224 }
225 else
226 break;
227 }
228 if (i < capacity)
229 {
230 dists[i] = dist;
231 indices[i] = index;
232 }
233 if (count < capacity) count++;
234
235 // tell caller that the search shall continue
236 return true;
237 }
238
239 DistanceType worstDist() const { return dists[capacity - 1]; }
240};
241
243template <
244 typename _DistanceType, typename _IndexType = size_t,
245 typename _CountType = size_t>
247{
248 public:
249 using DistanceType = _DistanceType;
250 using IndexType = _IndexType;
251 using CountType = _CountType;
252
253 private:
254 IndexType* indices;
255 DistanceType* dists;
256 CountType capacity;
257 CountType count;
258 DistanceType maximumSearchDistanceSquared;
259
260 public:
261 explicit RKNNResultSet(
262 CountType capacity_, DistanceType maximumSearchDistanceSquared_)
263 : indices(nullptr),
264 dists(nullptr),
265 capacity(capacity_),
266 count(0),
267 maximumSearchDistanceSquared(maximumSearchDistanceSquared_)
268 {
269 }
270
271 void init(IndexType* indices_, DistanceType* dists_)
272 {
273 indices = indices_;
274 dists = dists_;
275 count = 0;
276 if (capacity) 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; // WORDSIZE must >= 8
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 Size = size_t;
844
845 Size remaining_ = 0;
846 void* base_ = nullptr;
847 void* loc_ = nullptr;
848
849 void internal_init()
850 {
851 remaining_ = 0;
852 base_ = nullptr;
853 usedMemory = 0;
854 wastedMemory = 0;
855 }
856
857 public:
858 Size usedMemory = 0;
859 Size wastedMemory = 0;
860
864 PooledAllocator() { internal_init(); }
865
869 ~PooledAllocator() { free_all(); }
870
872 void free_all()
873 {
874 while (base_ != nullptr)
875 {
876 // Get pointer to prev block
877 void* prev = *(static_cast<void**>(base_));
878 ::free(base_);
879 base_ = prev;
880 }
881 internal_init();
882 }
883
888 void* malloc(const size_t req_size)
889 {
890 /* Round size up to a multiple of wordsize. The following expression
891 only works for WORDSIZE that is a power of 2, by masking last bits
892 of incremented size to zero.
893 */
894 const Size size = (req_size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
895
896 /* Check whether a new block must be allocated. Note that the first
897 word of a block is reserved for a pointer to the previous block.
898 */
899 if (size > remaining_)
900 {
901 wastedMemory += remaining_;
902
903 /* Allocate new storage. */
904 const Size blocksize =
905 size > BLOCKSIZE ? size + WORDSIZE : BLOCKSIZE + WORDSIZE;
906
907 // use the standard C malloc to allocate memory
908 void* m = ::malloc(blocksize);
909 if (!m)
910 {
911 fprintf(stderr, "Failed to allocate memory.\n");
912 throw std::bad_alloc();
913 }
914
915 /* Fill first word of new block with pointer to previous block. */
916 static_cast<void**>(m)[0] = base_;
917 base_ = m;
918
919 remaining_ = blocksize - WORDSIZE;
920 loc_ = static_cast<char*>(m) + WORDSIZE;
921 }
922 void* rloc = loc_;
923 loc_ = static_cast<char*>(loc_) + size;
924 remaining_ -= size;
925
926 usedMemory += size;
927
928 return rloc;
929 }
930
938 template <typename T>
939 T* allocate(const size_t count = 1)
940 {
941 T* mem = static_cast<T*>(this->malloc(sizeof(T) * count));
942 return mem;
943 }
944};
953template <int32_t DIM, typename T>
955{
956 using type = std::array<T, DIM>;
957};
959template <typename T>
960struct array_or_vector<-1, T>
961{
962 using type = std::vector<T>;
963};
964
981template <
982 class Derived, typename Distance, class DatasetAdaptor, int32_t DIM = -1,
983 typename IndexType = uint32_t>
985{
986 public:
989 void freeIndex(Derived& obj)
990 {
991 obj.pool_.free_all();
992 obj.root_node_ = nullptr;
993 obj.size_at_index_build_ = 0;
994 }
995
996 using ElementType = typename Distance::ElementType;
997 using DistanceType = typename Distance::DistanceType;
998
1002 std::vector<IndexType> vAcc_;
1003
1004 using Offset = typename decltype(vAcc_)::size_type;
1005 using Size = typename decltype(vAcc_)::size_type;
1006 using Dimension = int32_t;
1007
1008 /*---------------------------
1009 * Internal Data Structures
1010 * --------------------------*/
1011 struct Node
1012 {
1015 union
1016 {
1017 struct leaf
1018 {
1019 Offset left, right;
1020 } lr;
1021 struct nonleaf
1022 {
1023 Dimension divfeat;
1025 DistanceType divlow, divhigh;
1026 } sub;
1027 } node_type;
1028
1030 Node *child1 = nullptr, *child2 = nullptr;
1031 };
1032
1033 using NodePtr = Node*;
1034 using NodeConstPtr = const Node*;
1035
1037 {
1038 ElementType low, high;
1039 };
1040
1041 NodePtr root_node_ = nullptr;
1042
1043 Size leaf_max_size_ = 0;
1044
1046 Size n_thread_build_ = 1;
1048 Size size_ = 0;
1050 Size size_at_index_build_ = 0;
1051 Dimension dim_ = 0;
1052
1055 using BoundingBox = typename array_or_vector<DIM, Interval>::type;
1056
1059 using distance_vector_t = typename array_or_vector<DIM, DistanceType>::type;
1060
1063
1072
1074 Size size(const Derived& obj) const { return obj.size_; }
1075
1077 Size veclen(const Derived& obj) { return DIM > 0 ? DIM : obj.dim; }
1078
1080 ElementType dataset_get(
1081 const Derived& obj, IndexType element, Dimension component) const
1082 {
1083 return obj.dataset_.kdtree_get_pt(element, component);
1084 }
1085
1090 Size usedMemory(Derived& obj)
1091 {
1092 return obj.pool_.usedMemory + obj.pool_.wastedMemory +
1093 obj.dataset_.kdtree_get_point_count() *
1094 sizeof(IndexType); // pool memory and vind array memory
1095 }
1096
1097 void computeMinMax(
1098 const Derived& obj, Offset ind, Size count, Dimension element,
1099 ElementType& min_elem, ElementType& max_elem)
1100 {
1101 min_elem = dataset_get(obj, vAcc_[ind], element);
1102 max_elem = min_elem;
1103 for (Offset i = 1; i < count; ++i)
1104 {
1105 ElementType val = dataset_get(obj, vAcc_[ind + i], element);
1106 if (val < min_elem) min_elem = val;
1107 if (val > max_elem) max_elem = val;
1108 }
1109 }
1110
1119 Derived& obj, const Offset left, const Offset right, BoundingBox& bbox)
1120 {
1121 NodePtr node = obj.pool_.template allocate<Node>(); // allocate memory
1122 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1123
1124 /* If too few exemplars remain, then make this a leaf node. */
1125 if ((right - left) <= static_cast<Offset>(obj.leaf_max_size_))
1126 {
1127 node->child1 = node->child2 = nullptr; /* Mark as leaf node. */
1128 node->node_type.lr.left = left;
1129 node->node_type.lr.right = right;
1130
1131 // compute bounding-box of leaf points
1132 for (Dimension i = 0; i < dims; ++i)
1133 {
1134 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1135 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1136 }
1137 for (Offset k = left + 1; k < right; ++k)
1138 {
1139 for (Dimension i = 0; i < dims; ++i)
1140 {
1141 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1142 if (bbox[i].low > val) bbox[i].low = val;
1143 if (bbox[i].high < val) bbox[i].high = val;
1144 }
1145 }
1146 }
1147 else
1148 {
1149 Offset idx;
1150 Dimension cutfeat;
1151 DistanceType cutval;
1152 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1153
1154 node->node_type.sub.divfeat = cutfeat;
1155
1156 BoundingBox left_bbox(bbox);
1157 left_bbox[cutfeat].high = cutval;
1158 node->child1 = this->divideTree(obj, left, left + idx, left_bbox);
1159
1160 BoundingBox right_bbox(bbox);
1161 right_bbox[cutfeat].low = cutval;
1162 node->child2 = this->divideTree(obj, left + idx, right, right_bbox);
1163
1164 node->node_type.sub.divlow = left_bbox[cutfeat].high;
1165 node->node_type.sub.divhigh = right_bbox[cutfeat].low;
1166
1167 for (Dimension i = 0; i < dims; ++i)
1168 {
1169 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1170 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1171 }
1172 }
1173
1174 return node;
1175 }
1176
1188 Derived& obj, const Offset left, const Offset right, BoundingBox& bbox,
1189 std::atomic<unsigned int>& thread_count, std::mutex& mutex)
1190 {
1191 std::unique_lock<std::mutex> lock(mutex);
1192 NodePtr node = obj.pool_.template allocate<Node>(); // allocate memory
1193 lock.unlock();
1194
1195 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1196
1197 /* If too few exemplars remain, then make this a leaf node. */
1198 if ((right - left) <= static_cast<Offset>(obj.leaf_max_size_))
1199 {
1200 node->child1 = node->child2 = nullptr; /* Mark as leaf node. */
1201 node->node_type.lr.left = left;
1202 node->node_type.lr.right = right;
1203
1204 // compute bounding-box of leaf points
1205 for (Dimension i = 0; i < dims; ++i)
1206 {
1207 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1208 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1209 }
1210 for (Offset k = left + 1; k < right; ++k)
1211 {
1212 for (Dimension i = 0; i < dims; ++i)
1213 {
1214 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1215 if (bbox[i].low > val) bbox[i].low = val;
1216 if (bbox[i].high < val) bbox[i].high = val;
1217 }
1218 }
1219 }
1220 else
1221 {
1222 Offset idx;
1223 Dimension cutfeat;
1224 DistanceType cutval;
1225 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1226
1227 node->node_type.sub.divfeat = cutfeat;
1228
1229 std::future<NodePtr> right_future;
1230
1231 BoundingBox right_bbox(bbox);
1232 right_bbox[cutfeat].low = cutval;
1233 if (++thread_count < n_thread_build_)
1234 {
1235 // Concurrent right sub-tree
1236 right_future = std::async(
1237 std::launch::async, &KDTreeBaseClass::divideTreeConcurrent,
1238 this, std::ref(obj), left + idx, right,
1239 std::ref(right_bbox), std::ref(thread_count),
1240 std::ref(mutex));
1241 }
1242 else
1243 {
1244 --thread_count;
1245 }
1246
1247 BoundingBox left_bbox(bbox);
1248 left_bbox[cutfeat].high = cutval;
1249 node->child1 = this->divideTreeConcurrent(
1250 obj, left, left + idx, left_bbox, thread_count, mutex);
1251
1252 if (right_future.valid())
1253 {
1254 // Block and wait for concurrent right sub-tree
1255 node->child2 = right_future.get();
1256 --thread_count;
1257 }
1258 else
1259 {
1260 node->child2 = this->divideTreeConcurrent(
1261 obj, left + idx, right, right_bbox, thread_count, mutex);
1262 }
1263
1264 node->node_type.sub.divlow = left_bbox[cutfeat].high;
1265 node->node_type.sub.divhigh = right_bbox[cutfeat].low;
1266
1267 for (Dimension i = 0; i < dims; ++i)
1268 {
1269 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1270 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1271 }
1272 }
1273
1274 return node;
1275 }
1276
1277 void middleSplit_(
1278 const Derived& obj, const Offset ind, const Size count, Offset& index,
1279 Dimension& cutfeat, DistanceType& cutval, const BoundingBox& bbox)
1280 {
1281 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1282 const auto EPS = static_cast<DistanceType>(0.00001);
1283 ElementType max_span = bbox[0].high - bbox[0].low;
1284 for (Dimension i = 1; i < dims; ++i)
1285 {
1286 ElementType span = bbox[i].high - bbox[i].low;
1287 if (span > max_span) { max_span = span; }
1288 }
1289 ElementType max_spread = -1;
1290 cutfeat = 0;
1291 ElementType min_elem = 0, max_elem = 0;
1292 for (Dimension i = 0; i < dims; ++i)
1293 {
1294 ElementType span = bbox[i].high - bbox[i].low;
1295 if (span > (1 - EPS) * max_span)
1296 {
1297 ElementType min_elem_, max_elem_;
1298 computeMinMax(obj, ind, count, i, min_elem_, max_elem_);
1299 ElementType spread = max_elem_ - min_elem_;
1300 if (spread > max_spread)
1301 {
1302 cutfeat = i;
1303 max_spread = spread;
1304 min_elem = min_elem_;
1305 max_elem = max_elem_;
1306 }
1307 }
1308 }
1309 // split in the middle
1310 DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;
1311
1312 if (split_val < min_elem)
1313 cutval = min_elem;
1314 else if (split_val > max_elem)
1315 cutval = max_elem;
1316 else
1317 cutval = split_val;
1318
1319 Offset lim1, lim2;
1320 planeSplit(obj, ind, count, cutfeat, cutval, lim1, lim2);
1321
1322 if (lim1 > count / 2)
1323 index = lim1;
1324 else if (lim2 < count / 2)
1325 index = lim2;
1326 else
1327 index = count / 2;
1328 }
1329
1340 const Derived& obj, const Offset ind, const Size count,
1341 const Dimension cutfeat, const DistanceType& cutval, Offset& lim1,
1342 Offset& lim2)
1343 {
1344 /* Move vector indices for left subtree to front of list. */
1345 Offset left = 0;
1346 Offset right = count - 1;
1347 for (;;)
1348 {
1349 while (left <= right &&
1350 dataset_get(obj, vAcc_[ind + left], cutfeat) < cutval)
1351 ++left;
1352 while (right && left <= right &&
1353 dataset_get(obj, vAcc_[ind + right], cutfeat) >= cutval)
1354 --right;
1355 if (left > right || !right)
1356 break; // "!right" was added to support unsigned Index types
1357 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1358 ++left;
1359 --right;
1360 }
1361 /* If either list is empty, it means that all remaining features
1362 * are identical. Split in the middle to maintain a balanced tree.
1363 */
1364 lim1 = left;
1365 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 lim2 = left;
1381 }
1382
1383 DistanceType computeInitialDistances(
1384 const Derived& obj, const ElementType* vec,
1385 distance_vector_t& dists) const
1386 {
1387 assert(vec);
1388 DistanceType dist = DistanceType();
1389
1390 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim_); ++i)
1391 {
1392 if (vec[i] < obj.root_bbox_[i].low)
1393 {
1394 dists[i] =
1395 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].low, i);
1396 dist += dists[i];
1397 }
1398 if (vec[i] > obj.root_bbox_[i].high)
1399 {
1400 dists[i] =
1401 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].high, i);
1402 dist += dists[i];
1403 }
1404 }
1405 return dist;
1406 }
1407
1408 static void save_tree(
1409 const Derived& obj, std::ostream& stream, const NodeConstPtr tree)
1410 {
1411 save_value(stream, *tree);
1412 if (tree->child1 != nullptr) { save_tree(obj, stream, tree->child1); }
1413 if (tree->child2 != nullptr) { save_tree(obj, stream, tree->child2); }
1414 }
1415
1416 static void load_tree(Derived& obj, std::istream& stream, NodePtr& tree)
1417 {
1418 tree = obj.pool_.template allocate<Node>();
1419 load_value(stream, *tree);
1420 if (tree->child1 != nullptr) { load_tree(obj, stream, tree->child1); }
1421 if (tree->child2 != nullptr) { load_tree(obj, stream, tree->child2); }
1422 }
1423
1429 void saveIndex(const Derived& obj, std::ostream& stream) const
1430 {
1431 save_value(stream, obj.size_);
1432 save_value(stream, obj.dim_);
1433 save_value(stream, obj.root_bbox_);
1434 save_value(stream, obj.leaf_max_size_);
1435 save_value(stream, obj.vAcc_);
1436 if (obj.root_node_) save_tree(obj, stream, obj.root_node_);
1437 }
1438
1444 void loadIndex(Derived& obj, std::istream& stream)
1445 {
1446 load_value(stream, obj.size_);
1447 load_value(stream, obj.dim_);
1448 load_value(stream, obj.root_bbox_);
1449 load_value(stream, obj.leaf_max_size_);
1450 load_value(stream, obj.vAcc_);
1451 load_tree(obj, stream, obj.root_node_);
1452 }
1453};
1454
1496template <
1497 typename Distance, class DatasetAdaptor, int32_t DIM = -1,
1498 typename IndexType = uint32_t>
1500 : public KDTreeBaseClass<
1501 KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, IndexType>,
1502 Distance, DatasetAdaptor, DIM, IndexType>
1503{
1504 public:
1508 Distance, DatasetAdaptor, DIM, IndexType>&) = delete;
1509
1511 const DatasetAdaptor& dataset_;
1512
1513 const KDTreeSingleIndexAdaptorParams indexParams;
1514
1515 Distance distance_;
1516
1517 using Base = typename nanoflann::KDTreeBaseClass<
1519 Distance, DatasetAdaptor, DIM, IndexType>,
1520 Distance, DatasetAdaptor, DIM, IndexType>;
1521
1522 using Offset = typename Base::Offset;
1523 using Size = typename Base::Size;
1524 using Dimension = typename Base::Dimension;
1525
1526 using ElementType = typename Base::ElementType;
1527 using DistanceType = typename Base::DistanceType;
1528
1529 using Node = typename Base::Node;
1530 using NodePtr = Node*;
1531
1532 using Interval = typename Base::Interval;
1533
1536 using BoundingBox = typename Base::BoundingBox;
1537
1540 using distance_vector_t = typename Base::distance_vector_t;
1541
1562 template <class... Args>
1564 const Dimension dimensionality, const DatasetAdaptor& inputData,
1565 const KDTreeSingleIndexAdaptorParams& params, Args&&... args)
1566 : dataset_(inputData),
1567 indexParams(params),
1568 distance_(inputData, std::forward<Args>(args)...)
1569 {
1570 init(dimensionality, params);
1571 }
1572
1573 explicit KDTreeSingleIndexAdaptor(
1574 const Dimension dimensionality, const DatasetAdaptor& inputData,
1575 const KDTreeSingleIndexAdaptorParams& params = {})
1576 : dataset_(inputData), indexParams(params), distance_(inputData)
1577 {
1578 init(dimensionality, params);
1579 }
1580
1581 private:
1582 void init(
1583 const Dimension dimensionality,
1584 const KDTreeSingleIndexAdaptorParams& params)
1585 {
1586 Base::size_ = dataset_.kdtree_get_point_count();
1587 Base::size_at_index_build_ = Base::size_;
1588 Base::dim_ = dimensionality;
1589 if (DIM > 0) Base::dim_ = DIM;
1590 Base::leaf_max_size_ = params.leaf_max_size;
1591 if (params.n_thread_build > 0)
1592 {
1593 Base::n_thread_build_ = params.n_thread_build;
1594 }
1595 else
1596 {
1597 Base::n_thread_build_ =
1598 std::max(std::thread::hardware_concurrency(), 1u);
1599 }
1600
1601 if (!(params.flags &
1602 KDTreeSingleIndexAdaptorFlags::SkipInitialBuildIndex))
1603 {
1604 // Build KD-tree:
1605 buildIndex();
1606 }
1607 }
1608
1609 public:
1614 {
1615 Base::size_ = dataset_.kdtree_get_point_count();
1616 Base::size_at_index_build_ = Base::size_;
1617 init_vind();
1618 this->freeIndex(*this);
1619 Base::size_at_index_build_ = Base::size_;
1620 if (Base::size_ == 0) return;
1621 computeBoundingBox(Base::root_bbox_);
1622 // construct the tree
1623 if (Base::n_thread_build_ == 1)
1624 {
1625 Base::root_node_ =
1626 this->divideTree(*this, 0, Base::size_, Base::root_bbox_);
1627 }
1628 else
1629 {
1630 std::atomic<unsigned int> thread_count(0u);
1631 std::mutex mutex;
1632 Base::root_node_ = this->divideTreeConcurrent(
1633 *this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
1634 }
1635 }
1636
1656 template <typename RESULTSET>
1658 RESULTSET& result, const ElementType* vec,
1659 const SearchParameters& searchParams = {}) const
1660 {
1661 assert(vec);
1662 if (this->size(*this) == 0) return false;
1663 if (!Base::root_node_)
1664 throw std::runtime_error(
1665 "[nanoflann] findNeighbors() called before building the "
1666 "index.");
1667 float epsError = 1 + searchParams.eps;
1668
1669 // fixed or variable-sized container (depending on DIM)
1670 distance_vector_t dists;
1671 // Fill it with zeros.
1672 auto zero = static_cast<decltype(result.worstDist())>(0);
1673 assign(dists, (DIM > 0 ? DIM : Base::dim_), zero);
1674 DistanceType dist = this->computeInitialDistances(*this, vec, dists);
1675 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
1676 return result.full();
1677 }
1678
1695 const ElementType* query_point, const Size num_closest,
1696 IndexType* out_indices, DistanceType* out_distances) const
1697 {
1699 resultSet.init(out_indices, out_distances);
1700 findNeighbors(resultSet, query_point);
1701 return resultSet.size();
1702 }
1703
1724 const ElementType* query_point, const DistanceType& radius,
1725 std::vector<ResultItem<IndexType, DistanceType>>& IndicesDists,
1726 const SearchParameters& searchParams = {}) const
1727 {
1729 radius, IndicesDists);
1730 const Size nFound =
1731 radiusSearchCustomCallback(query_point, resultSet, searchParams);
1732 if (searchParams.sorted)
1733 std::sort(
1734 IndicesDists.begin(), IndicesDists.end(), IndexDist_Sorter());
1735 return nFound;
1736 }
1737
1743 template <class SEARCH_CALLBACK>
1745 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
1746 const SearchParameters& searchParams = {}) const
1747 {
1748 findNeighbors(resultSet, query_point, searchParams);
1749 return resultSet.size();
1750 }
1751
1769 const ElementType* query_point, const Size num_closest,
1770 IndexType* out_indices, DistanceType* out_distances,
1771 const DistanceType& radius) const
1772 {
1774 num_closest, radius);
1775 resultSet.init(out_indices, out_distances);
1776 findNeighbors(resultSet, query_point);
1777 return resultSet.size();
1778 }
1779
1782 public:
1786 {
1787 // Create a permutable array of indices to the input vectors.
1788 Base::size_ = dataset_.kdtree_get_point_count();
1789 if (Base::vAcc_.size() != Base::size_) Base::vAcc_.resize(Base::size_);
1790 for (Size i = 0; i < Base::size_; i++) Base::vAcc_[i] = i;
1791 }
1792
1793 void computeBoundingBox(BoundingBox& bbox)
1794 {
1795 const auto dims = (DIM > 0 ? DIM : Base::dim_);
1796 resize(bbox, dims);
1797 if (dataset_.kdtree_get_bbox(bbox))
1798 {
1799 // Done! It was implemented in derived class
1800 }
1801 else
1802 {
1803 const Size N = dataset_.kdtree_get_point_count();
1804 if (!N)
1805 throw std::runtime_error(
1806 "[nanoflann] computeBoundingBox() called but "
1807 "no data points found.");
1808 for (Dimension i = 0; i < dims; ++i)
1809 {
1810 bbox[i].low = bbox[i].high =
1811 this->dataset_get(*this, Base::vAcc_[0], i);
1812 }
1813 for (Offset k = 1; k < N; ++k)
1814 {
1815 for (Dimension i = 0; i < dims; ++i)
1816 {
1817 const auto val =
1818 this->dataset_get(*this, Base::vAcc_[k], i);
1819 if (val < bbox[i].low) bbox[i].low = val;
1820 if (val > bbox[i].high) bbox[i].high = val;
1821 }
1822 }
1823 }
1824 }
1825
1832 template <class RESULTSET>
1834 RESULTSET& result_set, const ElementType* vec, const NodePtr node,
1835 DistanceType mindist, distance_vector_t& dists,
1836 const float epsError) const
1837 {
1838 /* If this is a leaf node, then do check and return. */
1839 if ((node->child1 == nullptr) && (node->child2 == nullptr))
1840 {
1841 DistanceType worst_dist = result_set.worstDist();
1842 for (Offset i = node->node_type.lr.left;
1843 i < node->node_type.lr.right; ++i)
1844 {
1845 const IndexType accessor = Base::vAcc_[i]; // reorder... : i;
1846 DistanceType dist = distance_.evalMetric(
1847 vec, accessor, (DIM > 0 ? DIM : Base::dim_));
1848 if (dist < worst_dist)
1849 {
1850 if (!result_set.addPoint(dist, Base::vAcc_[i]))
1851 {
1852 // the resultset doesn't want to receive any more
1853 // points, we're done searching!
1854 return false;
1855 }
1856 }
1857 }
1858 return true;
1859 }
1860
1861 /* Which child branch should be taken first? */
1862 Dimension idx = node->node_type.sub.divfeat;
1863 ElementType val = vec[idx];
1864 DistanceType diff1 = val - node->node_type.sub.divlow;
1865 DistanceType diff2 = val - node->node_type.sub.divhigh;
1866
1867 NodePtr bestChild;
1868 NodePtr otherChild;
1869 DistanceType cut_dist;
1870 if ((diff1 + diff2) < 0)
1871 {
1872 bestChild = node->child1;
1873 otherChild = node->child2;
1874 cut_dist =
1875 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
1876 }
1877 else
1878 {
1879 bestChild = node->child2;
1880 otherChild = node->child1;
1881 cut_dist =
1882 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
1883 }
1884
1885 /* Call recursively to search next level down. */
1886 if (!searchLevel(result_set, vec, bestChild, mindist, dists, epsError))
1887 {
1888 // the resultset doesn't want to receive any more points, we're done
1889 // searching!
1890 return false;
1891 }
1892
1893 DistanceType dst = dists[idx];
1894 mindist = mindist + cut_dist - dst;
1895 dists[idx] = cut_dist;
1896 if (mindist * epsError <= result_set.worstDist())
1897 {
1898 if (!searchLevel(
1899 result_set, vec, otherChild, mindist, dists, epsError))
1900 {
1901 // the resultset doesn't want to receive any more points, we're
1902 // done searching!
1903 return false;
1904 }
1905 }
1906 dists[idx] = dst;
1907 return true;
1908 }
1909
1910 public:
1916 void saveIndex(std::ostream& stream) const
1917 {
1918 Base::saveIndex(*this, stream);
1919 }
1920
1926 void loadIndex(std::istream& stream) { Base::loadIndex(*this, stream); }
1927
1928}; // class KDTree
1929
1967template <
1968 typename Distance, class DatasetAdaptor, int32_t DIM = -1,
1969 typename IndexType = uint32_t>
1971 : public KDTreeBaseClass<
1972 KDTreeSingleIndexDynamicAdaptor_<
1973 Distance, DatasetAdaptor, DIM, IndexType>,
1974 Distance, DatasetAdaptor, DIM, IndexType>
1975{
1976 public:
1980 const DatasetAdaptor& dataset_;
1981
1982 KDTreeSingleIndexAdaptorParams index_params_;
1983
1984 std::vector<int>& treeIndex_;
1985
1986 Distance distance_;
1987
1988 using Base = typename nanoflann::KDTreeBaseClass<
1990 Distance, DatasetAdaptor, DIM, IndexType>,
1991 Distance, DatasetAdaptor, DIM, IndexType>;
1992
1993 using ElementType = typename Base::ElementType;
1994 using DistanceType = typename Base::DistanceType;
1995
1996 using Offset = typename Base::Offset;
1997 using Size = typename Base::Size;
1998 using Dimension = typename Base::Dimension;
1999
2000 using Node = typename Base::Node;
2001 using NodePtr = Node*;
2002
2003 using Interval = typename Base::Interval;
2006 using BoundingBox = typename Base::BoundingBox;
2007
2010 using distance_vector_t = typename Base::distance_vector_t;
2011
2028 const Dimension dimensionality, const DatasetAdaptor& inputData,
2029 std::vector<int>& treeIndex,
2030 const KDTreeSingleIndexAdaptorParams& params =
2032 : dataset_(inputData),
2033 index_params_(params),
2034 treeIndex_(treeIndex),
2035 distance_(inputData)
2036 {
2037 Base::size_ = 0;
2038 Base::size_at_index_build_ = 0;
2039 for (auto& v : Base::root_bbox_) v = {};
2040 Base::dim_ = dimensionality;
2041 if (DIM > 0) Base::dim_ = DIM;
2042 Base::leaf_max_size_ = params.leaf_max_size;
2043 if (params.n_thread_build > 0)
2044 {
2045 Base::n_thread_build_ = params.n_thread_build;
2046 }
2047 else
2048 {
2049 Base::n_thread_build_ =
2050 std::max(std::thread::hardware_concurrency(), 1u);
2051 }
2052 }
2053
2056 const KDTreeSingleIndexDynamicAdaptor_& rhs) = default;
2057
2061 {
2063 std::swap(Base::vAcc_, tmp.Base::vAcc_);
2064 std::swap(Base::leaf_max_size_, tmp.Base::leaf_max_size_);
2065 std::swap(index_params_, tmp.index_params_);
2066 std::swap(treeIndex_, tmp.treeIndex_);
2067 std::swap(Base::size_, tmp.Base::size_);
2068 std::swap(Base::size_at_index_build_, tmp.Base::size_at_index_build_);
2069 std::swap(Base::root_node_, tmp.Base::root_node_);
2070 std::swap(Base::root_bbox_, tmp.Base::root_bbox_);
2071 std::swap(Base::pool_, tmp.Base::pool_);
2072 return *this;
2073 }
2074
2079 {
2080 Base::size_ = Base::vAcc_.size();
2081 this->freeIndex(*this);
2082 Base::size_at_index_build_ = Base::size_;
2083 if (Base::size_ == 0) return;
2084 computeBoundingBox(Base::root_bbox_);
2085 // construct the tree
2086 if (Base::n_thread_build_ == 1)
2087 {
2088 Base::root_node_ =
2089 this->divideTree(*this, 0, Base::size_, Base::root_bbox_);
2090 }
2091 else
2092 {
2093 std::atomic<unsigned int> thread_count(0u);
2094 std::mutex mutex;
2095 Base::root_node_ = this->divideTreeConcurrent(
2096 *this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
2097 }
2098 }
2099
2123 template <typename RESULTSET>
2125 RESULTSET& result, const ElementType* vec,
2126 const SearchParameters& searchParams = {}) const
2127 {
2128 assert(vec);
2129 if (this->size(*this) == 0) return false;
2130 if (!Base::root_node_) return false;
2131 float epsError = 1 + searchParams.eps;
2132
2133 // fixed or variable-sized container (depending on DIM)
2134 distance_vector_t dists;
2135 // Fill it with zeros.
2136 assign(
2137 dists, (DIM > 0 ? DIM : Base::dim_),
2138 static_cast<typename distance_vector_t::value_type>(0));
2139 DistanceType dist = this->computeInitialDistances(*this, vec, dists);
2140 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
2141 return result.full();
2142 }
2143
2159 const ElementType* query_point, const Size num_closest,
2160 IndexType* out_indices, DistanceType* out_distances,
2161 const SearchParameters& searchParams = {}) const
2162 {
2164 resultSet.init(out_indices, out_distances);
2165 findNeighbors(resultSet, query_point, searchParams);
2166 return resultSet.size();
2167 }
2168
2189 const ElementType* query_point, const DistanceType& radius,
2190 std::vector<ResultItem<IndexType, DistanceType>>& IndicesDists,
2191 const SearchParameters& searchParams = {}) const
2192 {
2194 radius, IndicesDists);
2195 const size_t nFound =
2196 radiusSearchCustomCallback(query_point, resultSet, searchParams);
2197 if (searchParams.sorted)
2198 std::sort(
2199 IndicesDists.begin(), IndicesDists.end(), IndexDist_Sorter());
2200 return nFound;
2201 }
2202
2208 template <class SEARCH_CALLBACK>
2210 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
2211 const SearchParameters& searchParams = {}) const
2212 {
2213 findNeighbors(resultSet, query_point, searchParams);
2214 return resultSet.size();
2215 }
2216
2219 public:
2220 void computeBoundingBox(BoundingBox& bbox)
2221 {
2222 const auto dims = (DIM > 0 ? DIM : Base::dim_);
2223 resize(bbox, dims);
2224
2225 if (dataset_.kdtree_get_bbox(bbox))
2226 {
2227 // Done! It was implemented in derived class
2228 }
2229 else
2230 {
2231 const Size N = Base::size_;
2232 if (!N)
2233 throw std::runtime_error(
2234 "[nanoflann] computeBoundingBox() called but "
2235 "no data points found.");
2236 for (Dimension i = 0; i < dims; ++i)
2237 {
2238 bbox[i].low = bbox[i].high =
2239 this->dataset_get(*this, Base::vAcc_[0], i);
2240 }
2241 for (Offset k = 1; k < N; ++k)
2242 {
2243 for (Dimension i = 0; i < dims; ++i)
2244 {
2245 const auto val =
2246 this->dataset_get(*this, Base::vAcc_[k], i);
2247 if (val < bbox[i].low) bbox[i].low = val;
2248 if (val > bbox[i].high) bbox[i].high = val;
2249 }
2250 }
2251 }
2252 }
2253
2258 template <class RESULTSET>
2260 RESULTSET& result_set, const ElementType* vec, const NodePtr node,
2261 DistanceType mindist, distance_vector_t& dists,
2262 const float epsError) const
2263 {
2264 /* If this is a leaf node, then do check and return. */
2265 if ((node->child1 == nullptr) && (node->child2 == nullptr))
2266 {
2267 DistanceType worst_dist = result_set.worstDist();
2268 for (Offset i = node->node_type.lr.left;
2269 i < node->node_type.lr.right; ++i)
2270 {
2271 const IndexType index = Base::vAcc_[i]; // reorder... : i;
2272 if (treeIndex_[index] == -1) continue;
2273 DistanceType dist = distance_.evalMetric(
2274 vec, index, (DIM > 0 ? DIM : Base::dim_));
2275 if (dist < worst_dist)
2276 {
2277 if (!result_set.addPoint(
2278 static_cast<typename RESULTSET::DistanceType>(dist),
2279 static_cast<typename RESULTSET::IndexType>(
2280 Base::vAcc_[i])))
2281 {
2282 // the resultset doesn't want to receive any more
2283 // points, we're done searching!
2284 return; // false;
2285 }
2286 }
2287 }
2288 return;
2289 }
2290
2291 /* Which child branch should be taken first? */
2292 Dimension idx = node->node_type.sub.divfeat;
2293 ElementType val = vec[idx];
2294 DistanceType diff1 = val - node->node_type.sub.divlow;
2295 DistanceType diff2 = val - node->node_type.sub.divhigh;
2296
2297 NodePtr bestChild;
2298 NodePtr otherChild;
2299 DistanceType cut_dist;
2300 if ((diff1 + diff2) < 0)
2301 {
2302 bestChild = node->child1;
2303 otherChild = node->child2;
2304 cut_dist =
2305 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
2306 }
2307 else
2308 {
2309 bestChild = node->child2;
2310 otherChild = node->child1;
2311 cut_dist =
2312 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
2313 }
2314
2315 /* Call recursively to search next level down. */
2316 searchLevel(result_set, vec, bestChild, mindist, dists, epsError);
2317
2318 DistanceType dst = dists[idx];
2319 mindist = mindist + cut_dist - dst;
2320 dists[idx] = cut_dist;
2321 if (mindist * epsError <= result_set.worstDist())
2322 {
2323 searchLevel(result_set, vec, otherChild, mindist, dists, epsError);
2324 }
2325 dists[idx] = dst;
2326 }
2327
2328 public:
2334 void saveIndex(std::ostream& stream) { saveIndex(*this, stream); }
2335
2341 void loadIndex(std::istream& stream) { loadIndex(*this, stream); }
2342};
2343
2358template <
2359 typename Distance, class DatasetAdaptor, int32_t DIM = -1,
2360 typename IndexType = uint32_t>
2362{
2363 public:
2364 using ElementType = typename Distance::ElementType;
2365 using DistanceType = typename Distance::DistanceType;
2366
2367 using Offset = typename KDTreeSingleIndexDynamicAdaptor_<
2368 Distance, DatasetAdaptor, DIM>::Offset;
2369 using Size = typename KDTreeSingleIndexDynamicAdaptor_<
2370 Distance, DatasetAdaptor, DIM>::Size;
2371 using Dimension = typename KDTreeSingleIndexDynamicAdaptor_<
2372 Distance, DatasetAdaptor, DIM>::Dimension;
2373
2374 protected:
2375 Size leaf_max_size_;
2376 Size treeCount_;
2377 Size pointCount_;
2378
2382 const DatasetAdaptor& dataset_;
2383
2386 std::vector<int> treeIndex_;
2387 std::unordered_set<int> removedPoints_;
2388
2389 KDTreeSingleIndexAdaptorParams index_params_;
2390
2391 Dimension dim_;
2392
2394 Distance, DatasetAdaptor, DIM, IndexType>;
2395 std::vector<index_container_t> index_;
2396
2397 public:
2400 const std::vector<index_container_t>& getAllIndices() const
2401 {
2402 return index_;
2403 }
2404
2405 private:
2407 int First0Bit(IndexType num)
2408 {
2409 int pos = 0;
2410 while (num & 1)
2411 {
2412 num = num >> 1;
2413 pos++;
2414 }
2415 return pos;
2416 }
2417
2419 void init()
2420 {
2421 using my_kd_tree_t = KDTreeSingleIndexDynamicAdaptor_<
2422 Distance, DatasetAdaptor, DIM, IndexType>;
2423 std::vector<my_kd_tree_t> index(
2424 treeCount_,
2425 my_kd_tree_t(dim_ /*dim*/, dataset_, treeIndex_, index_params_));
2426 index_ = index;
2427 }
2428
2429 public:
2430 Distance distance_;
2431
2448 const int dimensionality, const DatasetAdaptor& inputData,
2449 const KDTreeSingleIndexAdaptorParams& params =
2451 const size_t maximumPointCount = 1000000000U)
2452 : dataset_(inputData), index_params_(params), distance_(inputData)
2453 {
2454 treeCount_ = static_cast<size_t>(std::log2(maximumPointCount)) + 1;
2455 pointCount_ = 0U;
2456 dim_ = dimensionality;
2457 treeIndex_.clear();
2458 if (DIM > 0) dim_ = DIM;
2459 leaf_max_size_ = params.leaf_max_size;
2460 init();
2461 const size_t num_initial_points = dataset_.kdtree_get_point_count();
2462 if (num_initial_points > 0) { addPoints(0, num_initial_points - 1); }
2463 }
2464
2468 Distance, DatasetAdaptor, DIM, IndexType>&) = delete;
2469
2471 void addPoints(IndexType start, IndexType end)
2472 {
2473 const Size count = end - start + 1;
2474 int maxIndex = 0;
2475 treeIndex_.resize(treeIndex_.size() + count);
2476 for (IndexType idx = start; idx <= end; idx++)
2477 {
2478 const int pos = First0Bit(pointCount_);
2479 maxIndex = std::max(pos, maxIndex);
2480 treeIndex_[pointCount_] = pos;
2481
2482 const auto it = removedPoints_.find(idx);
2483 if (it != removedPoints_.end())
2484 {
2485 removedPoints_.erase(it);
2486 treeIndex_[idx] = pos;
2487 }
2488
2489 for (int i = 0; i < pos; i++)
2490 {
2491 for (int j = 0; j < static_cast<int>(index_[i].vAcc_.size());
2492 j++)
2493 {
2494 index_[pos].vAcc_.push_back(index_[i].vAcc_[j]);
2495 if (treeIndex_[index_[i].vAcc_[j]] != -1)
2496 treeIndex_[index_[i].vAcc_[j]] = pos;
2497 }
2498 index_[i].vAcc_.clear();
2499 }
2500 index_[pos].vAcc_.push_back(idx);
2501 pointCount_++;
2502 }
2503
2504 for (int i = 0; i <= maxIndex; ++i)
2505 {
2506 index_[i].freeIndex(index_[i]);
2507 if (!index_[i].vAcc_.empty()) index_[i].buildIndex();
2508 }
2509 }
2510
2512 void removePoint(size_t idx)
2513 {
2514 if (idx >= pointCount_) return;
2515 removedPoints_.insert(idx);
2516 treeIndex_[idx] = -1;
2517 }
2518
2535 template <typename RESULTSET>
2537 RESULTSET& result, const ElementType* vec,
2538 const SearchParameters& searchParams = {}) const
2539 {
2540 for (size_t i = 0; i < treeCount_; i++)
2541 {
2542 index_[i].findNeighbors(result, &vec[0], searchParams);
2543 }
2544 return result.full();
2545 }
2546};
2547
2573template <
2574 class MatrixType, int32_t DIM = -1, class Distance = nanoflann::metric_L2,
2575 bool row_major = true>
2577{
2578 using self_t =
2580 using num_t = typename MatrixType::Scalar;
2581 using IndexType = typename MatrixType::Index;
2582 using metric_t = typename Distance::template traits<
2583 num_t, self_t, IndexType>::distance_t;
2584
2586 metric_t, self_t,
2587 row_major ? MatrixType::ColsAtCompileTime
2588 : MatrixType::RowsAtCompileTime,
2589 IndexType>;
2590
2591 index_t* index_;
2593
2594 using Offset = typename index_t::Offset;
2595 using Size = typename index_t::Size;
2596 using Dimension = typename index_t::Dimension;
2597
2600 const Dimension dimensionality,
2601 const std::reference_wrapper<const MatrixType>& mat,
2602 const int leaf_max_size = 10)
2603 : m_data_matrix(mat)
2604 {
2605 const auto dims = row_major ? mat.get().cols() : mat.get().rows();
2606 if (static_cast<Dimension>(dims) != dimensionality)
2607 throw std::runtime_error(
2608 "Error: 'dimensionality' must match column count in data "
2609 "matrix");
2610 if (DIM > 0 && static_cast<int32_t>(dims) != DIM)
2611 throw std::runtime_error(
2612 "Data set dimensionality does not match the 'DIM' template "
2613 "argument");
2614 index_ = new index_t(
2615 dims, *this /* adaptor */,
2617 }
2618
2619 public:
2622
2623 ~KDTreeEigenMatrixAdaptor() { delete index_; }
2624
2625 const std::reference_wrapper<const MatrixType> m_data_matrix;
2626
2635 void query(
2636 const num_t* query_point, const Size num_closest,
2637 IndexType* out_indices, num_t* out_distances) const
2638 {
2639 nanoflann::KNNResultSet<num_t, IndexType> resultSet(num_closest);
2640 resultSet.init(out_indices, out_distances);
2641 index_->findNeighbors(resultSet, query_point);
2642 }
2643
2647 const self_t& derived() const { return *this; }
2648 self_t& derived() { return *this; }
2649
2650 // Must return the number of data points
2651 Size kdtree_get_point_count() const
2652 {
2653 if (row_major)
2654 return m_data_matrix.get().rows();
2655 else
2656 return m_data_matrix.get().cols();
2657 }
2658
2659 // Returns the dim'th component of the idx'th point in the class:
2660 num_t kdtree_get_pt(const IndexType idx, size_t dim) const
2661 {
2662 if (row_major)
2663 return m_data_matrix.get().coeff(idx, IndexType(dim));
2664 else
2665 return m_data_matrix.get().coeff(IndexType(dim), idx);
2666 }
2667
2668 // Optional bounding-box computation: return false to default to a standard
2669 // bbox computation loop.
2670 // Return true if the BBOX was already computed by the class and returned
2671 // in "bb" so it can be avoided to redo it again. Look at bb.size() to
2672 // find out the expected dimensionality (e.g. 2 or 3 for point clouds)
2673 template <class BBOX>
2674 bool kdtree_get_bbox(BBOX& /*bb*/) const
2675 {
2676 return false;
2677 }
2678
2681}; // end of KDTreeEigenMatrixAdaptor
// end of grouping
2685} // namespace nanoflann
Definition nanoflann.hpp:985
Size usedMemory(Derived &obj)
Definition nanoflann.hpp:1090
NodePtr divideTreeConcurrent(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex)
Definition nanoflann.hpp:1187
void planeSplit(const Derived &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)
Definition nanoflann.hpp:1339
typename array_or_vector< DIM, DistanceType >::type distance_vector_t
Definition nanoflann.hpp:1059
std::vector< IndexType > vAcc_
Definition nanoflann.hpp:1002
Size size(const Derived &obj) const
Definition nanoflann.hpp:1074
void freeIndex(Derived &obj)
Definition nanoflann.hpp:989
void loadIndex(Derived &obj, std::istream &stream)
Definition nanoflann.hpp:1444
typename array_or_vector< DIM, Interval >::type BoundingBox
Definition nanoflann.hpp:1055
BoundingBox root_bbox_
Definition nanoflann.hpp:1062
void saveIndex(const Derived &obj, std::ostream &stream) const
Definition nanoflann.hpp:1429
PooledAllocator pool_
Definition nanoflann.hpp:1071
NodePtr divideTree(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox)
Definition nanoflann.hpp:1118
ElementType dataset_get(const Derived &obj, IndexType element, Dimension component) const
Helper accessor to the dataset points:
Definition nanoflann.hpp:1080
Size veclen(const Derived &obj)
Definition nanoflann.hpp:1077
Definition nanoflann.hpp:1503
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1744
Size rknnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const
Definition nanoflann.hpp:1768
KDTreeSingleIndexAdaptor(const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete
KDTreeSingleIndexAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params, Args &&... args)
Definition nanoflann.hpp:1563
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1723
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:1540
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:1926
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:1536
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances) const
Definition nanoflann.hpp:1694
void init_vind()
Definition nanoflann.hpp:1785
const DatasetAdaptor & dataset_
Definition nanoflann.hpp:1511
void saveIndex(std::ostream &stream) const
Definition nanoflann.hpp:1916
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1657
void buildIndex()
Definition nanoflann.hpp:1613
bool searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:1833
Definition nanoflann.hpp:1975
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2188
KDTreeSingleIndexDynamicAdaptor_(const Dimension dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
Definition nanoflann.hpp:2027
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:2006
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:1980
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2209
KDTreeSingleIndexDynamicAdaptor_(const KDTreeSingleIndexDynamicAdaptor_ &rhs)=default
void buildIndex()
Definition nanoflann.hpp:2078
void saveIndex(std::ostream &stream)
Definition nanoflann.hpp:2334
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:2010
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:2341
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2158
void searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:2259
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2124
KDTreeSingleIndexDynamicAdaptor_ operator=(const KDTreeSingleIndexDynamicAdaptor_ &rhs)
Definition nanoflann.hpp:2059
Definition nanoflann.hpp:2362
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2536
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:2382
void removePoint(size_t idx)
Definition nanoflann.hpp:2512
void addPoints(IndexType start, IndexType end)
Definition nanoflann.hpp:2471
KDTreeSingleIndexDynamicAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams(), const size_t maximumPointCount=1000000000U)
Definition nanoflann.hpp:2447
std::vector< int > treeIndex_
Definition nanoflann.hpp:2386
const std::vector< index_container_t > & getAllIndices() const
Definition nanoflann.hpp:2400
Dimension dim_
Dimensionality of each data point.
Definition nanoflann.hpp:2391
KDTreeSingleIndexDynamicAdaptor(const KDTreeSingleIndexDynamicAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete
Definition nanoflann.hpp:168
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:204
Definition nanoflann.hpp:833
~PooledAllocator()
Definition nanoflann.hpp:869
void free_all()
Definition nanoflann.hpp:872
void * malloc(const size_t req_size)
Definition nanoflann.hpp:888
T * allocate(const size_t count=1)
Definition nanoflann.hpp:939
PooledAllocator()
Definition nanoflann.hpp:864
Definition nanoflann.hpp:247
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: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:328
bool operator()(const PairType &p1, const PairType &p2) const
Definition nanoflann.hpp:331
Definition nanoflann.hpp:1037
Definition nanoflann.hpp:1012
DistanceType divlow
The values used for subdivision.
Definition nanoflann.hpp:1025
Node * child1
Definition nanoflann.hpp:1030
Dimension divfeat
Definition nanoflann.hpp:1023
Offset right
Indices of points in leaf node.
Definition nanoflann.hpp:1019
union nanoflann::KDTreeBaseClass::Node::@0 node_type
Definition nanoflann.hpp:2577
void query(const num_t *query_point, const Size num_closest, IndexType *out_indices, num_t *out_distances) const
Definition nanoflann.hpp:2635
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:2599
KDTreeEigenMatrixAdaptor(const self_t &)=delete
typename index_t::Offset Offset
Definition nanoflann.hpp:2594
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:955
Definition nanoflann.hpp:109
Definition nanoflann.hpp:98
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