59#include <unordered_set>
63#define NANOFLANN_VERSION 0x150
66#if !defined(NOMINMAX) && \
67 (defined(_WIN32) || defined(_WIN32_) || defined(WIN32) || defined(_WIN64))
88 return static_cast<T
>(3.14159265358979323846);
95template <
typename T,
typename =
int>
106template <
typename T,
typename =
int>
120template <
typename Container>
121inline typename std::enable_if<has_resize<Container>::value,
void>::type
resize(
122 Container& c,
const size_t nElements)
131template <
typename Container>
132inline typename std::enable_if<!has_resize<Container>::value,
void>::type
133 resize(Container& c,
const size_t nElements)
135 if (nElements != c.size())
136 throw std::logic_error(
"Try to change the size of a std::array.");
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)
146 c.assign(nElements, value);
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)
156 for (
size_t i = 0; i < nElements; i++) c[i] = value;
162 typename _DistanceType,
typename _IndexType = size_t,
163 typename _CountType =
size_t>
167 using DistanceType = _DistanceType;
168 using IndexType = _IndexType;
169 using CountType = _CountType;
179 : indices(
nullptr), dists(
nullptr), capacity(capacity_), count(0)
183 void init(IndexType* indices_, DistanceType* dists_)
189 dists[capacity - 1] = (std::numeric_limits<DistanceType>::max)();
192 CountType size()
const {
return count; }
194 bool full()
const {
return count == capacity; }
204 for (i = count; i > 0; --i)
208#ifdef NANOFLANN_FIRST_MATCH
209 if ((dists[i - 1] > dist) ||
210 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
213 if (dists[i - 1] > dist)
218 dists[i] = dists[i - 1];
219 indices[i] = indices[i - 1];
230 if (count < capacity) count++;
236 DistanceType worstDist()
const {
return dists[capacity - 1]; }
243 template <
typename PairType>
244 bool operator()(
const PairType& p1,
const PairType& p2)
const
246 return p1.second < p2.second;
258template <
typename IndexType =
size_t,
typename DistanceType =
double>
262 ResultItem(
const IndexType index,
const DistanceType distance)
263 : first(index), second(distance)
274template <
typename _DistanceType,
typename _IndexType =
size_t>
278 using DistanceType = _DistanceType;
279 using IndexType = _IndexType;
282 const DistanceType radius;
284 std::vector<ResultItem<IndexType, DistanceType>>& m_indices_dists;
287 DistanceType radius_,
289 : radius(radius_), m_indices_dists(indices_dists)
294 void init() { clear(); }
295 void clear() { m_indices_dists.clear(); }
297 size_t size()
const {
return m_indices_dists.size(); }
298 size_t empty()
const {
return m_indices_dists.empty(); }
300 bool full()
const {
return true; }
309 if (dist < radius) m_indices_dists.emplace_back(index, dist);
313 DistanceType worstDist()
const {
return radius; }
321 if (m_indices_dists.empty())
322 throw std::runtime_error(
323 "Cannot invoke RadiusResultSet::worst_item() on "
324 "an empty list of results.");
325 auto it = std::max_element(
336void save_value(std::ostream& stream,
const T& value)
338 stream.write(
reinterpret_cast<const char*
>(&value),
sizeof(T));
342void save_value(std::ostream& stream,
const std::vector<T>& value)
344 size_t size = value.size();
345 stream.write(
reinterpret_cast<const char*
>(&size),
sizeof(
size_t));
346 stream.write(
reinterpret_cast<const char*
>(value.data()),
sizeof(T) * size);
350void load_value(std::istream& stream, T& value)
352 stream.read(
reinterpret_cast<char*
>(&value),
sizeof(T));
356void load_value(std::istream& stream, std::vector<T>& value)
359 stream.read(
reinterpret_cast<char*
>(&size),
sizeof(
size_t));
361 stream.read(
reinterpret_cast<char*
>(value.data()),
sizeof(T) * size);
383 class T,
class DataSource,
typename _DistanceType = T,
384 typename IndexType = uint32_t>
387 using ElementType = T;
388 using DistanceType = _DistanceType;
390 const DataSource& data_source;
392 L1_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
394 DistanceType evalMetric(
395 const T* a,
const IndexType b_idx,
size_t size,
396 DistanceType worst_dist = -1)
const
398 DistanceType result = DistanceType();
399 const T* last = a + size;
400 const T* lastgroup = last - 3;
404 while (a < lastgroup)
406 const DistanceType diff0 =
407 std::abs(a[0] - data_source.kdtree_get_pt(b_idx, d++));
408 const DistanceType diff1 =
409 std::abs(a[1] - data_source.kdtree_get_pt(b_idx, d++));
410 const DistanceType diff2 =
411 std::abs(a[2] - data_source.kdtree_get_pt(b_idx, d++));
412 const DistanceType diff3 =
413 std::abs(a[3] - data_source.kdtree_get_pt(b_idx, d++));
414 result += diff0 + diff1 + diff2 + diff3;
416 if ((worst_dist > 0) && (result > worst_dist)) {
return result; }
422 result += std::abs(*a++ - data_source.kdtree_get_pt(b_idx, d++));
427 template <
typename U,
typename V>
428 DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
430 return std::abs(a - b);
445 class T,
class DataSource,
typename _DistanceType = T,
446 typename IndexType = uint32_t>
449 using ElementType = T;
450 using DistanceType = _DistanceType;
452 const DataSource& data_source;
454 L2_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
456 DistanceType evalMetric(
457 const T* a,
const IndexType b_idx,
size_t size,
458 DistanceType worst_dist = -1)
const
460 DistanceType result = DistanceType();
461 const T* last = a + size;
462 const T* lastgroup = last - 3;
466 while (a < lastgroup)
468 const DistanceType diff0 =
469 a[0] - data_source.kdtree_get_pt(b_idx, d++);
470 const DistanceType diff1 =
471 a[1] - data_source.kdtree_get_pt(b_idx, d++);
472 const DistanceType diff2 =
473 a[2] - data_source.kdtree_get_pt(b_idx, d++);
474 const DistanceType diff3 =
475 a[3] - data_source.kdtree_get_pt(b_idx, d++);
477 diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
479 if ((worst_dist > 0) && (result > worst_dist)) {
return result; }
485 const DistanceType diff0 =
486 *a++ - data_source.kdtree_get_pt(b_idx, d++);
487 result += diff0 * diff0;
492 template <
typename U,
typename V>
493 DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
495 return (a - b) * (a - b);
510 class T,
class DataSource,
typename _DistanceType = T,
511 typename IndexType = uint32_t>
514 using ElementType = T;
515 using DistanceType = _DistanceType;
517 const DataSource& data_source;
520 : data_source(_data_source)
524 DistanceType evalMetric(
525 const T* a,
const IndexType b_idx,
size_t size)
const
527 DistanceType result = DistanceType();
528 for (
size_t i = 0; i < size; ++i)
530 const DistanceType diff =
531 a[i] - data_source.kdtree_get_pt(b_idx, i);
532 result += diff * diff;
537 template <
typename U,
typename V>
538 DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
540 return (a - b) * (a - b);
555 class T,
class DataSource,
typename _DistanceType = T,
556 typename IndexType = uint32_t>
559 using ElementType = T;
560 using DistanceType = _DistanceType;
562 const DataSource& data_source;
564 SO2_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
566 DistanceType evalMetric(
567 const T* a,
const IndexType b_idx,
size_t size)
const
570 a[size - 1], data_source.kdtree_get_pt(b_idx, size - 1), size - 1);
575 template <
typename U,
typename V>
576 DistanceType
accum_dist(
const U a,
const V b,
const size_t)
const
578 DistanceType result = DistanceType();
579 DistanceType PI = pi_const<DistanceType>();
583 else if (result < -PI)
600 class T,
class DataSource,
typename _DistanceType = T,
601 typename IndexType = uint32_t>
604 using ElementType = T;
605 using DistanceType = _DistanceType;
611 : distance_L2_Simple(_data_source)
615 DistanceType evalMetric(
616 const T* a,
const IndexType b_idx,
size_t size)
const
618 return distance_L2_Simple.evalMetric(a, b_idx, size);
621 template <
typename U,
typename V>
622 DistanceType accum_dist(
const U a,
const V b,
const size_t idx)
const
624 return distance_L2_Simple.accum_dist(a, b, idx);
631 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
641 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
651 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
660 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
669 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
681enum class KDTreeSingleIndexAdaptorFlags
684 SkipInitialBuildIndex = 1
687inline std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type operator&(
688 KDTreeSingleIndexAdaptorFlags lhs, KDTreeSingleIndexAdaptorFlags rhs)
691 typename std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type;
692 return static_cast<underlying
>(lhs) &
static_cast<underlying
>(rhs);
699 size_t _leaf_max_size = 10,
700 KDTreeSingleIndexAdaptorFlags _flags =
701 KDTreeSingleIndexAdaptorFlags::None,
702 unsigned int _n_thread_build = 1)
703 : leaf_max_size(_leaf_max_size),
705 n_thread_build(_n_thread_build)
709 size_t leaf_max_size;
710 KDTreeSingleIndexAdaptorFlags flags;
711 unsigned int n_thread_build;
718 : eps(eps_), sorted(sorted_)
747 static constexpr size_t WORDSIZE = 16;
748 static constexpr size_t BLOCKSIZE = 8192;
756 using Offset = uint32_t;
757 using Size = uint32_t;
758 using Dimension = int32_t;
761 void* base_ =
nullptr;
762 void* loc_ =
nullptr;
774 Size wastedMemory = 0;
789 while (base_ !=
nullptr)
792 void* prev = *(
static_cast<void**
>(base_));
809 const Size size = (req_size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
814 if (size > remaining_)
816 wastedMemory += remaining_;
819 const Size blocksize =
820 (size +
sizeof(
void*) + (WORDSIZE - 1) > BLOCKSIZE)
821 ? size +
sizeof(
void*) + (WORDSIZE - 1)
825 void* m = ::malloc(blocksize);
828 fprintf(stderr,
"Failed to allocate memory.\n");
829 throw std::bad_alloc();
833 static_cast<void**
>(m)[0] = base_;
840 remaining_ = blocksize -
sizeof(
void*) - shift;
841 loc_ = (
static_cast<char*
>(m) +
sizeof(
void*) + shift);
844 loc_ =
static_cast<char*
>(loc_) + size;
859 template <
typename T>
862 T* mem =
static_cast<T*
>(this->malloc(
sizeof(T) * count));
874template <
int32_t DIM,
typename T>
877 using type = std::array<T, DIM>;
883 using type = std::vector<T>;
903 class Derived,
typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
904 typename IndexType = uint32_t>
912 obj.pool_.free_all();
913 obj.root_node_ =
nullptr;
914 obj.size_at_index_build_ = 0;
917 using ElementType =
typename Distance::ElementType;
918 using DistanceType =
typename Distance::DistanceType;
925 using Offset =
typename decltype(vAcc_)::size_type;
926 using Size =
typename decltype(vAcc_)::size_type;
927 using Dimension = int32_t;
951 Node *child1 =
nullptr, *child2 =
nullptr;
959 ElementType low, high;
964 Size leaf_max_size_ = 0;
967 Size n_thread_build_ = 1;
971 Size size_at_index_build_ = 0;
995 Size
size(
const Derived& obj)
const {
return obj.size_; }
998 Size
veclen(
const Derived& obj) {
return DIM > 0 ? DIM : obj.dim; }
1002 const Derived& obj, IndexType element, Dimension component)
const
1004 return obj.dataset_.kdtree_get_pt(element, component);
1013 return obj.pool_.usedMemory + obj.pool_.wastedMemory +
1014 obj.dataset_.kdtree_get_point_count() *
1019 const Derived& obj, Offset ind, Size count, Dimension element,
1020 ElementType& min_elem, ElementType& max_elem)
1022 min_elem = dataset_get(obj, vAcc_[ind], element);
1023 max_elem = min_elem;
1024 for (Offset i = 1; i < count; ++i)
1026 ElementType val = dataset_get(obj, vAcc_[ind + i], element);
1027 if (val < min_elem) min_elem = val;
1028 if (val > max_elem) max_elem = val;
1040 Derived& obj,
const Offset left,
const Offset right,
BoundingBox& bbox)
1042 NodePtr node = obj.pool_.template allocate<Node>();
1043 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1046 if ((right - left) <=
static_cast<Offset
>(obj.leaf_max_size_))
1048 node->
child1 = node->child2 =
nullptr;
1053 for (Dimension i = 0; i < dims; ++i)
1055 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1056 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1058 for (Offset k = left + 1; k < right; ++k)
1060 for (Dimension i = 0; i < dims; ++i)
1062 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1063 if (bbox[i].low > val) bbox[i].low = val;
1064 if (bbox[i].high < val) bbox[i].high = val;
1072 DistanceType cutval;
1073 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1078 left_bbox[cutfeat].high = cutval;
1079 node->
child1 = this->divideTree(obj, left, left + idx, left_bbox);
1082 right_bbox[cutfeat].low = cutval;
1083 node->child2 = this->divideTree(obj, left + idx, right, right_bbox);
1085 node->
node_type.sub.divlow = left_bbox[cutfeat].high;
1086 node->
node_type.sub.divhigh = right_bbox[cutfeat].low;
1088 for (Dimension i = 0; i < dims; ++i)
1090 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1091 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1109 Derived& obj,
const Offset left,
const Offset right,
BoundingBox& bbox,
1110 std::atomic<unsigned int>& thread_count, std::mutex& mutex)
1112 std::unique_lock<std::mutex> lock(mutex);
1113 NodePtr node = obj.pool_.template allocate<Node>();
1116 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1119 if ((right - left) <=
static_cast<Offset
>(obj.leaf_max_size_))
1121 node->
child1 = node->child2 =
nullptr;
1126 for (Dimension i = 0; i < dims; ++i)
1128 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1129 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1131 for (Offset k = left + 1; k < right; ++k)
1133 for (Dimension i = 0; i < dims; ++i)
1135 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1136 if (bbox[i].low > val) bbox[i].low = val;
1137 if (bbox[i].high < val) bbox[i].high = val;
1145 DistanceType cutval;
1146 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1150 std::future<NodePtr> left_future, right_future;
1153 left_bbox[cutfeat].high = cutval;
1154 if (++thread_count < n_thread_build_)
1156 left_future = std::async(
1158 this, std::ref(obj), left, left + idx, std::ref(left_bbox),
1159 std::ref(thread_count), std::ref(mutex));
1164 node->
child1 = this->divideTreeConcurrent(
1165 obj, left, left + idx, left_bbox, thread_count, mutex);
1169 right_bbox[cutfeat].low = cutval;
1170 if (++thread_count < n_thread_build_)
1172 right_future = std::async(
1174 this, std::ref(obj), left + idx, right,
1175 std::ref(right_bbox), std::ref(thread_count),
1181 node->child2 = this->divideTreeConcurrent(
1182 obj, left + idx, right, right_bbox, thread_count, mutex);
1185 if (left_future.valid())
1187 node->
child1 = left_future.get();
1190 if (right_future.valid())
1192 node->child2 = right_future.get();
1196 node->
node_type.sub.divlow = left_bbox[cutfeat].high;
1197 node->
node_type.sub.divhigh = right_bbox[cutfeat].low;
1199 for (Dimension i = 0; i < dims; ++i)
1201 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1202 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1210 const Derived& obj,
const Offset ind,
const Size count, Offset& index,
1211 Dimension& cutfeat, DistanceType& cutval,
const BoundingBox& bbox)
1213 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1214 const auto EPS =
static_cast<DistanceType
>(0.00001);
1215 ElementType max_span = bbox[0].high - bbox[0].low;
1216 for (Dimension i = 1; i < dims; ++i)
1218 ElementType span = bbox[i].high - bbox[i].low;
1219 if (span > max_span) { max_span = span; }
1221 ElementType max_spread = -1;
1223 for (Dimension i = 0; i < dims; ++i)
1225 ElementType span = bbox[i].high - bbox[i].low;
1226 if (span > (1 - EPS) * max_span)
1228 ElementType min_elem, max_elem;
1229 computeMinMax(obj, ind, count, i, min_elem, max_elem);
1230 ElementType spread = max_elem - min_elem;
1231 if (spread > max_spread)
1234 max_spread = spread;
1239 DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;
1240 ElementType min_elem, max_elem;
1241 computeMinMax(obj, ind, count, cutfeat, min_elem, max_elem);
1243 if (split_val < min_elem)
1245 else if (split_val > max_elem)
1251 planeSplit(obj, ind, count, cutfeat, cutval, lim1, lim2);
1253 if (lim1 > count / 2)
1255 else if (lim2 < count / 2)
1271 const Derived& obj,
const Offset ind,
const Size count,
1272 const Dimension cutfeat,
const DistanceType& cutval, Offset& lim1,
1277 Offset right = count - 1;
1280 while (left <= right &&
1281 dataset_get(obj, vAcc_[ind + left], cutfeat) < cutval)
1283 while (right && left <= right &&
1284 dataset_get(obj, vAcc_[ind + right], cutfeat) >= cutval)
1286 if (left > right || !right)
1288 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1299 while (left <= right &&
1300 dataset_get(obj, vAcc_[ind + left], cutfeat) <= cutval)
1302 while (right && left <= right &&
1303 dataset_get(obj, vAcc_[ind + right], cutfeat) > cutval)
1305 if (left > right || !right)
1307 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1314 DistanceType computeInitialDistances(
1315 const Derived& obj,
const ElementType* vec,
1316 distance_vector_t& dists)
const
1319 DistanceType dist = DistanceType();
1321 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim_); ++i)
1323 if (vec[i] < obj.root_bbox_[i].low)
1326 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].low, i);
1329 if (vec[i] > obj.root_bbox_[i].high)
1332 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].high, i);
1339 static void save_tree(
1340 const Derived& obj, std::ostream& stream,
const NodeConstPtr tree)
1342 save_value(stream, *tree);
1343 if (tree->child1 !=
nullptr) { save_tree(obj, stream, tree->child1); }
1344 if (tree->child2 !=
nullptr) { save_tree(obj, stream, tree->child2); }
1347 static void load_tree(Derived& obj, std::istream& stream, NodePtr& tree)
1349 tree = obj.pool_.template allocate<Node>();
1350 load_value(stream, *tree);
1351 if (tree->child1 !=
nullptr) { load_tree(obj, stream, tree->child1); }
1352 if (tree->child2 !=
nullptr) { load_tree(obj, stream, tree->child2); }
1360 void saveIndex(
const Derived& obj, std::ostream& stream)
const
1362 save_value(stream, obj.size_);
1363 save_value(stream, obj.dim_);
1364 save_value(stream, obj.root_bbox_);
1365 save_value(stream, obj.leaf_max_size_);
1366 save_value(stream, obj.vAcc_);
1367 if (obj.root_node_) save_tree(obj, stream, obj.root_node_);
1377 load_value(stream, obj.size_);
1378 load_value(stream, obj.dim_);
1379 load_value(stream, obj.root_bbox_);
1380 load_value(stream, obj.leaf_max_size_);
1381 load_value(stream, obj.vAcc_);
1382 load_tree(obj, stream, obj.root_node_);
1428 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
1429 typename IndexType = uint32_t>
1432 KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, IndexType>,
1433 Distance, DatasetAdaptor, DIM, IndexType>
1439 Distance, DatasetAdaptor, DIM, IndexType>&) =
delete;
1450 Distance, DatasetAdaptor, DIM, IndexType>,
1451 Distance, DatasetAdaptor, DIM, IndexType>;
1453 using Offset =
typename Base::Offset;
1454 using Size =
typename Base::Size;
1455 using Dimension =
typename Base::Dimension;
1457 using ElementType =
typename Base::ElementType;
1458 using DistanceType =
typename Base::DistanceType;
1460 using Node =
typename Base::Node;
1461 using NodePtr = Node*;
1463 using Interval =
typename Base::Interval;
1493 template <
class... Args>
1495 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1497 : dataset_(inputData),
1498 indexParams(params),
1499 distance_(inputData, std::forward<Args>(args)...)
1501 init(dimensionality, params);
1505 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1507 : dataset_(inputData), indexParams(params), distance_(inputData)
1509 init(dimensionality, params);
1514 const Dimension dimensionality,
1515 const KDTreeSingleIndexAdaptorParams& params)
1517 Base::size_ = dataset_.kdtree_get_point_count();
1518 Base::size_at_index_build_ = Base::size_;
1519 Base::dim_ = dimensionality;
1520 if (DIM > 0) Base::dim_ = DIM;
1521 Base::leaf_max_size_ = params.leaf_max_size;
1522 if (params.n_thread_build > 0)
1524 Base::n_thread_build_ = params.n_thread_build;
1528 Base::n_thread_build_ =
1529 std::max(std::thread::hardware_concurrency(), 1u);
1532 if (!(params.flags &
1533 KDTreeSingleIndexAdaptorFlags::SkipInitialBuildIndex))
1546 Base::size_ = dataset_.kdtree_get_point_count();
1547 Base::size_at_index_build_ = Base::size_;
1549 this->freeIndex(*
this);
1550 Base::size_at_index_build_ = Base::size_;
1551 if (Base::size_ == 0)
return;
1552 computeBoundingBox(Base::root_bbox_);
1554 if (Base::n_thread_build_ == 1)
1557 this->divideTree(*
this, 0, Base::size_, Base::root_bbox_);
1561 std::atomic<unsigned int> thread_count(0u);
1563 Base::root_node_ = this->divideTreeConcurrent(
1564 *
this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
1587 template <
typename RESULTSET>
1589 RESULTSET& result,
const ElementType* vec,
1593 if (this->size(*
this) == 0)
return false;
1594 if (!Base::root_node_)
1595 throw std::runtime_error(
1596 "[nanoflann] findNeighbors() called before building the "
1598 float epsError = 1 + searchParams.eps;
1601 distance_vector_t dists;
1603 auto zero =
static_cast<decltype(result.worstDist())
>(0);
1604 assign(dists, (DIM > 0 ? DIM : Base::dim_), zero);
1605 DistanceType dist = this->computeInitialDistances(*
this, vec, dists);
1606 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
1607 return result.full();
1626 const ElementType* query_point,
const Size num_closest,
1627 IndexType* out_indices, DistanceType* out_distances)
const
1630 resultSet.init(out_indices, out_distances);
1631 findNeighbors(resultSet, query_point);
1632 return resultSet.size();
1655 const ElementType* query_point,
const DistanceType& radius,
1660 radius, IndicesDists);
1662 radiusSearchCustomCallback(query_point, resultSet, searchParams);
1663 if (searchParams.sorted)
1674 template <
class SEARCH_CALLBACK>
1676 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
1679 findNeighbors(resultSet, query_point, searchParams);
1680 return resultSet.size();
1691 Base::size_ = dataset_.kdtree_get_point_count();
1692 if (Base::vAcc_.size() != Base::size_) Base::vAcc_.resize(Base::size_);
1693 for (Size i = 0; i < Base::size_; i++) Base::vAcc_[i] = i;
1696 void computeBoundingBox(BoundingBox& bbox)
1698 const auto dims = (DIM > 0 ? DIM : Base::dim_);
1700 if (dataset_.kdtree_get_bbox(bbox))
1706 const Size N = dataset_.kdtree_get_point_count();
1708 throw std::runtime_error(
1709 "[nanoflann] computeBoundingBox() called but "
1710 "no data points found.");
1711 for (Dimension i = 0; i < dims; ++i)
1713 bbox[i].low = bbox[i].high =
1714 this->dataset_get(*
this, Base::vAcc_[0], i);
1716 for (Offset k = 1; k < N; ++k)
1718 for (Dimension i = 0; i < dims; ++i)
1721 this->dataset_get(*
this, Base::vAcc_[k], i);
1722 if (val < bbox[i].low) bbox[i].low = val;
1723 if (val > bbox[i].high) bbox[i].high = val;
1735 template <
class RESULTSET>
1737 RESULTSET& result_set,
const ElementType* vec,
const NodePtr node,
1739 const float epsError)
const
1742 if ((node->child1 ==
nullptr) && (node->child2 ==
nullptr))
1744 DistanceType worst_dist = result_set.worstDist();
1745 for (Offset i = node->node_type.lr.left;
1746 i < node->node_type.lr.right; ++i)
1748 const IndexType accessor = Base::vAcc_[i];
1749 DistanceType dist = distance_.evalMetric(
1750 vec, accessor, (DIM > 0 ? DIM : Base::dim_));
1751 if (dist < worst_dist)
1753 if (!result_set.addPoint(dist, Base::vAcc_[i]))
1765 Dimension idx = node->node_type.sub.divfeat;
1766 ElementType val = vec[idx];
1767 DistanceType diff1 = val - node->node_type.sub.divlow;
1768 DistanceType diff2 = val - node->node_type.sub.divhigh;
1772 DistanceType cut_dist;
1773 if ((diff1 + diff2) < 0)
1775 bestChild = node->child1;
1776 otherChild = node->child2;
1778 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
1782 bestChild = node->child2;
1783 otherChild = node->child1;
1785 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
1789 if (!searchLevel(result_set, vec, bestChild, mindist, dists, epsError))
1796 DistanceType dst = dists[idx];
1797 mindist = mindist + cut_dist - dst;
1798 dists[idx] = cut_dist;
1799 if (mindist * epsError <= result_set.worstDist())
1802 result_set, vec, otherChild, mindist, dists, epsError))
1821 Base::saveIndex(*
this, stream);
1829 void loadIndex(std::istream& stream) { Base::loadIndex(*
this, stream); }
1871 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
1872 typename IndexType = uint32_t>
1875 KDTreeSingleIndexDynamicAdaptor_<
1876 Distance, DatasetAdaptor, DIM, IndexType>,
1877 Distance, DatasetAdaptor, DIM, IndexType>
1887 std::vector<int>& treeIndex_;
1893 Distance, DatasetAdaptor, DIM, IndexType>,
1894 Distance, DatasetAdaptor, DIM, IndexType>;
1896 using ElementType =
typename Base::ElementType;
1897 using DistanceType =
typename Base::DistanceType;
1899 using Offset =
typename Base::Offset;
1900 using Size =
typename Base::Size;
1901 using Dimension =
typename Base::Dimension;
1903 using Node =
typename Base::Node;
1904 using NodePtr = Node*;
1906 using Interval =
typename Base::Interval;
1931 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1932 std::vector<int>& treeIndex,
1935 : dataset_(inputData),
1936 index_params_(params),
1937 treeIndex_(treeIndex),
1938 distance_(inputData)
1941 Base::size_at_index_build_ = 0;
1942 for (
auto& v : Base::root_bbox_) v = {};
1943 Base::dim_ = dimensionality;
1944 if (DIM > 0) Base::dim_ = DIM;
1945 Base::leaf_max_size_ = params.leaf_max_size;
1946 if (params.n_thread_build > 0)
1948 Base::n_thread_build_ = params.n_thread_build;
1952 Base::n_thread_build_ =
1953 std::max(std::thread::hardware_concurrency(), 1u);
1966 std::swap(Base::vAcc_, tmp.Base::vAcc_);
1967 std::swap(Base::leaf_max_size_, tmp.Base::leaf_max_size_);
1968 std::swap(index_params_, tmp.index_params_);
1969 std::swap(treeIndex_, tmp.treeIndex_);
1970 std::swap(Base::size_, tmp.Base::size_);
1971 std::swap(Base::size_at_index_build_, tmp.Base::size_at_index_build_);
1972 std::swap(Base::root_node_, tmp.Base::root_node_);
1973 std::swap(Base::root_bbox_, tmp.Base::root_bbox_);
1974 std::swap(Base::pool_, tmp.Base::pool_);
1983 Base::size_ = Base::vAcc_.size();
1984 this->freeIndex(*
this);
1985 Base::size_at_index_build_ = Base::size_;
1986 if (Base::size_ == 0)
return;
1987 computeBoundingBox(Base::root_bbox_);
1989 if (Base::n_thread_build_ == 1)
1992 this->divideTree(*
this, 0, Base::size_, Base::root_bbox_);
1996 std::atomic<unsigned int> thread_count(0u);
1998 Base::root_node_ = this->divideTreeConcurrent(
1999 *
this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
2026 template <
typename RESULTSET>
2028 RESULTSET& result,
const ElementType* vec,
2032 if (this->size(*
this) == 0)
return false;
2033 if (!Base::root_node_)
return false;
2034 float epsError = 1 + searchParams.eps;
2037 distance_vector_t dists;
2040 dists, (DIM > 0 ? DIM : Base::dim_),
2041 static_cast<typename distance_vector_t::value_type
>(0));
2042 DistanceType dist = this->computeInitialDistances(*
this, vec, dists);
2043 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
2044 return result.full();
2062 const ElementType* query_point,
const Size num_closest,
2063 IndexType* out_indices, DistanceType* out_distances)
const
2066 resultSet.init(out_indices, out_distances);
2067 findNeighbors(resultSet, query_point);
2068 return resultSet.size();
2091 const ElementType* query_point,
const DistanceType& radius,
2096 radius, IndicesDists);
2097 const size_t nFound =
2098 radiusSearchCustomCallback(query_point, resultSet, searchParams);
2099 if (searchParams.sorted)
2110 template <
class SEARCH_CALLBACK>
2112 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
2115 findNeighbors(resultSet, query_point, searchParams);
2116 return resultSet.size();
2122 void computeBoundingBox(BoundingBox& bbox)
2124 const auto dims = (DIM > 0 ? DIM : Base::dim_);
2127 if (dataset_.kdtree_get_bbox(bbox))
2133 const Size N = Base::size_;
2135 throw std::runtime_error(
2136 "[nanoflann] computeBoundingBox() called but "
2137 "no data points found.");
2138 for (Dimension i = 0; i < dims; ++i)
2140 bbox[i].low = bbox[i].high =
2141 this->dataset_get(*
this, Base::vAcc_[0], i);
2143 for (Offset k = 1; k < N; ++k)
2145 for (Dimension i = 0; i < dims; ++i)
2148 this->dataset_get(*
this, Base::vAcc_[k], i);
2149 if (val < bbox[i].low) bbox[i].low = val;
2150 if (val > bbox[i].high) bbox[i].high = val;
2160 template <
class RESULTSET>
2162 RESULTSET& result_set,
const ElementType* vec,
const NodePtr node,
2164 const float epsError)
const
2167 if ((node->child1 ==
nullptr) && (node->child2 ==
nullptr))
2169 DistanceType worst_dist = result_set.worstDist();
2170 for (Offset i = node->node_type.lr.left;
2171 i < node->node_type.lr.right; ++i)
2173 const IndexType index = Base::vAcc_[i];
2174 if (treeIndex_[index] == -1)
continue;
2175 DistanceType dist = distance_.evalMetric(
2176 vec, index, (DIM > 0 ? DIM : Base::dim_));
2177 if (dist < worst_dist)
2179 if (!result_set.addPoint(
2180 static_cast<typename RESULTSET::DistanceType
>(dist),
2181 static_cast<typename RESULTSET::IndexType
>(
2194 Dimension idx = node->node_type.sub.divfeat;
2195 ElementType val = vec[idx];
2196 DistanceType diff1 = val - node->node_type.sub.divlow;
2197 DistanceType diff2 = val - node->node_type.sub.divhigh;
2201 DistanceType cut_dist;
2202 if ((diff1 + diff2) < 0)
2204 bestChild = node->child1;
2205 otherChild = node->child2;
2207 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
2211 bestChild = node->child2;
2212 otherChild = node->child1;
2214 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
2218 searchLevel(result_set, vec, bestChild, mindist, dists, epsError);
2220 DistanceType dst = dists[idx];
2221 mindist = mindist + cut_dist - dst;
2222 dists[idx] = cut_dist;
2223 if (mindist * epsError <= result_set.worstDist())
2225 searchLevel(result_set, vec, otherChild, mindist, dists, epsError);
2261 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
2262 typename IndexType = uint32_t>
2266 using ElementType =
typename Distance::ElementType;
2267 using DistanceType =
typename Distance::DistanceType;
2270 Distance, DatasetAdaptor, DIM>::Offset;
2272 Distance, DatasetAdaptor, DIM>::Size;
2274 Distance, DatasetAdaptor, DIM>::Dimension;
2277 Size leaf_max_size_;
2289 std::unordered_set<int> removedPoints_;
2296 Distance, DatasetAdaptor, DIM, IndexType>;
2297 std::vector<index_container_t> index_;
2309 int First0Bit(IndexType num)
2323 using my_kd_tree_t = KDTreeSingleIndexDynamicAdaptor_<
2324 Distance, DatasetAdaptor, DIM, IndexType>;
2325 std::vector<my_kd_tree_t> index(
2327 my_kd_tree_t(dim_ , dataset_, treeIndex_, index_params_));
2350 const int dimensionality,
const DatasetAdaptor& inputData,
2353 const size_t maximumPointCount = 1000000000U)
2354 : dataset_(inputData), index_params_(params), distance_(inputData)
2356 treeCount_ =
static_cast<size_t>(std::log2(maximumPointCount)) + 1;
2358 dim_ = dimensionality;
2360 if (DIM > 0) dim_ = DIM;
2361 leaf_max_size_ = params.leaf_max_size;
2363 const size_t num_initial_points = dataset_.kdtree_get_point_count();
2364 if (num_initial_points > 0) { addPoints(0, num_initial_points - 1); }
2370 Distance, DatasetAdaptor, DIM, IndexType>&) =
delete;
2375 const Size count = end - start + 1;
2377 treeIndex_.resize(treeIndex_.size() + count);
2378 for (IndexType idx = start; idx <= end; idx++)
2380 const int pos = First0Bit(pointCount_);
2381 maxIndex = std::max(pos, maxIndex);
2382 treeIndex_[pointCount_] = pos;
2384 const auto it = removedPoints_.find(idx);
2385 if (it != removedPoints_.end())
2387 removedPoints_.erase(it);
2388 treeIndex_[idx] = pos;
2391 for (
int i = 0; i < pos; i++)
2393 for (
int j = 0; j < static_cast<int>(index_[i].vAcc_.size());
2396 index_[pos].vAcc_.push_back(index_[i].vAcc_[j]);
2397 if (treeIndex_[index_[i].vAcc_[j]] != -1)
2398 treeIndex_[index_[i].vAcc_[j]] = pos;
2400 index_[i].vAcc_.clear();
2402 index_[pos].vAcc_.push_back(idx);
2406 for (
int i = 0; i <= maxIndex; ++i)
2408 index_[i].freeIndex(index_[i]);
2409 if (!index_[i].vAcc_.empty()) index_[i].buildIndex();
2416 if (idx >= pointCount_)
return;
2417 removedPoints_.insert(idx);
2418 treeIndex_[idx] = -1;
2437 template <
typename RESULTSET>
2439 RESULTSET& result,
const ElementType* vec,
2442 for (
size_t i = 0; i < treeCount_; i++)
2444 index_[i].findNeighbors(result, &vec[0], searchParams);
2446 return result.full();
2477 bool row_major =
true>
2482 using num_t =
typename MatrixType::Scalar;
2483 using IndexType =
typename MatrixType::Index;
2484 using metric_t =
typename Distance::template traits<
2485 num_t,
self_t, IndexType>::distance_t;
2489 row_major ? MatrixType::ColsAtCompileTime
2490 : MatrixType::RowsAtCompileTime,
2497 using Size =
typename index_t::Size;
2498 using Dimension =
typename index_t::Dimension;
2502 const Dimension dimensionality,
2503 const std::reference_wrapper<const MatrixType>& mat,
2504 const int leaf_max_size = 10)
2505 : m_data_matrix(mat)
2507 const auto dims = row_major ? mat.get().cols() : mat.get().rows();
2508 if (
static_cast<Dimension
>(dims) != dimensionality)
2509 throw std::runtime_error(
2510 "Error: 'dimensionality' must match column count in data "
2512 if (DIM > 0 &&
static_cast<int32_t
>(dims) != DIM)
2513 throw std::runtime_error(
2514 "Data set dimensionality does not match the 'DIM' template "
2527 const std::reference_wrapper<const MatrixType> m_data_matrix;
2538 const num_t* query_point,
const Size num_closest,
2539 IndexType* out_indices, num_t* out_distances)
const
2542 resultSet.init(out_indices, out_distances);
2549 const self_t& derived()
const {
return *
this; }
2550 self_t& derived() {
return *
this; }
2553 Size kdtree_get_point_count()
const
2556 return m_data_matrix.get().rows();
2558 return m_data_matrix.get().cols();
2562 num_t kdtree_get_pt(
const IndexType idx,
size_t dim)
const
2565 return m_data_matrix.get().coeff(idx, IndexType(dim));
2567 return m_data_matrix.get().coeff(IndexType(dim), idx);
2575 template <
class BBOX>
2576 bool kdtree_get_bbox(BBOX& )
const
Definition: nanoflann.hpp:906
Size usedMemory(Derived &obj)
Definition: nanoflann.hpp:1011
NodePtr divideTreeConcurrent(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex)
Definition: nanoflann.hpp:1108
void planeSplit(const Derived &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)
Definition: nanoflann.hpp:1270
typename array_or_vector< DIM, DistanceType >::type distance_vector_t
Definition: nanoflann.hpp:980
std::vector< IndexType > vAcc_
Definition: nanoflann.hpp:923
Size size(const Derived &obj) const
Definition: nanoflann.hpp:995
void freeIndex(Derived &obj)
Definition: nanoflann.hpp:910
void loadIndex(Derived &obj, std::istream &stream)
Definition: nanoflann.hpp:1375
typename array_or_vector< DIM, Interval >::type BoundingBox
Definition: nanoflann.hpp:976
BoundingBox root_bbox_
Definition: nanoflann.hpp:983
void saveIndex(const Derived &obj, std::ostream &stream) const
Definition: nanoflann.hpp:1360
PooledAllocator pool_
Definition: nanoflann.hpp:992
NodePtr divideTree(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox)
Definition: nanoflann.hpp:1039
ElementType dataset_get(const Derived &obj, IndexType element, Dimension component) const
Helper accessor to the dataset points:
Definition: nanoflann.hpp:1001
Size veclen(const Derived &obj)
Definition: nanoflann.hpp:998
Definition: nanoflann.hpp:1434
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition: nanoflann.hpp:1675
KDTreeSingleIndexAdaptor(const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete
KDTreeSingleIndexAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms, Args &&... args)
Definition: nanoflann.hpp:1494
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition: nanoflann.hpp:1654
typename Base::distance_vector_t distance_vector_t
Definition: nanoflann.hpp:1471
void loadIndex(std::istream &stream)
Definition: nanoflann.hpp:1829
typename Base::BoundingBox BoundingBox
Definition: nanoflann.hpp:1467
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances) const
Definition: nanoflann.hpp:1625
void init_vind()
Definition: nanoflann.hpp:1688
const DatasetAdaptor & dataset_
Definition: nanoflann.hpp:1442
void saveIndex(std::ostream &stream) const
Definition: nanoflann.hpp:1819
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition: nanoflann.hpp:1588
void buildIndex()
Definition: nanoflann.hpp:1544
bool searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition: nanoflann.hpp:1736
Definition: nanoflann.hpp:1878
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition: nanoflann.hpp:2090
KDTreeSingleIndexDynamicAdaptor_(const Dimension dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams())
Definition: nanoflann.hpp:1930
typename Base::BoundingBox BoundingBox
Definition: nanoflann.hpp:1909
const DatasetAdaptor & dataset_
The source of our data.
Definition: nanoflann.hpp:1883
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition: nanoflann.hpp:2111
KDTreeSingleIndexDynamicAdaptor_(const KDTreeSingleIndexDynamicAdaptor_ &rhs)=default
void buildIndex()
Definition: nanoflann.hpp:1981
void saveIndex(std::ostream &stream)
Definition: nanoflann.hpp:2236
typename Base::distance_vector_t distance_vector_t
Definition: nanoflann.hpp:1913
void loadIndex(std::istream &stream)
Definition: nanoflann.hpp:2243
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances) const
Definition: nanoflann.hpp:2061
void searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition: nanoflann.hpp:2161
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition: nanoflann.hpp:2027
KDTreeSingleIndexDynamicAdaptor_ operator=(const KDTreeSingleIndexDynamicAdaptor_ &rhs)
Definition: nanoflann.hpp:1962
Definition: nanoflann.hpp:2264
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition: nanoflann.hpp:2438
const DatasetAdaptor & dataset_
The source of our data.
Definition: nanoflann.hpp:2284
void removePoint(size_t idx)
Definition: nanoflann.hpp:2414
void addPoints(IndexType start, IndexType end)
Definition: nanoflann.hpp:2373
KDTreeSingleIndexDynamicAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams(), const size_t maximumPointCount=1000000000U)
Definition: nanoflann.hpp:2349
std::vector< int > treeIndex_
Definition: nanoflann.hpp:2288
const std::vector< index_container_t > & getAllIndices() const
Definition: nanoflann.hpp:2302
Dimension dim_
Dimensionality of each data point.
Definition: nanoflann.hpp:2293
KDTreeSingleIndexDynamicAdaptor(const KDTreeSingleIndexDynamicAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete
Definition: nanoflann.hpp:165
bool addPoint(DistanceType dist, IndexType index)
Definition: nanoflann.hpp:201
Definition: nanoflann.hpp:746
~PooledAllocator()
Definition: nanoflann.hpp:784
void free_all()
Definition: nanoflann.hpp:787
void * malloc(const size_t req_size)
Definition: nanoflann.hpp:803
T * allocate(const size_t count=1)
Definition: nanoflann.hpp:860
PooledAllocator()
Definition: nanoflann.hpp:779
Definition: nanoflann.hpp:276
ResultItem< IndexType, DistanceType > worst_item() const
Definition: nanoflann.hpp:319
bool addPoint(DistanceType dist, IndexType index)
Definition: nanoflann.hpp:307
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:241
bool operator()(const PairType &p1, const PairType &p2) const
Definition: nanoflann.hpp:244
Definition: nanoflann.hpp:958
Definition: nanoflann.hpp:933
DistanceType divlow
The values used for subdivision.
Definition: nanoflann.hpp:946
Node * child1
Definition: nanoflann.hpp:951
Dimension divfeat
Definition: nanoflann.hpp:944
Offset right
Indices of points in leaf node.
Definition: nanoflann.hpp:940
union nanoflann::KDTreeBaseClass::Node::@0 node_type
Definition: nanoflann.hpp:2479
void query(const num_t *query_point, const Size num_closest, IndexType *out_indices, num_t *out_distances) const
Definition: nanoflann.hpp:2537
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:2501
KDTreeEigenMatrixAdaptor(const self_t &)=delete
typename index_t::Offset Offset
Definition: nanoflann.hpp:2496
Definition: nanoflann.hpp:697
Definition: nanoflann.hpp:386
Definition: nanoflann.hpp:448
Definition: nanoflann.hpp:513
Definition: nanoflann.hpp:369
Definition: nanoflann.hpp:260
DistanceType second
Distance from sample to query point.
Definition: nanoflann.hpp:268
IndexType first
Index of the sample in the dataset.
Definition: nanoflann.hpp:267
Definition: nanoflann.hpp:558
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition: nanoflann.hpp:576
Definition: nanoflann.hpp:603
Definition: nanoflann.hpp:716
bool sorted
distance (default: true)
Definition: nanoflann.hpp:723
float eps
search for eps-approximate neighbours (default: 0)
Definition: nanoflann.hpp:722
Definition: nanoflann.hpp:876
Definition: nanoflann.hpp:108
Definition: nanoflann.hpp:97
Definition: nanoflann.hpp:633
Definition: nanoflann.hpp:630
Definition: nanoflann.hpp:643
Definition: nanoflann.hpp:653
Definition: nanoflann.hpp:650
Definition: nanoflann.hpp:640
Definition: nanoflann.hpp:662
Definition: nanoflann.hpp:659
Definition: nanoflann.hpp:671
Definition: nanoflann.hpp:668