60#include <unordered_set>
64#define NANOFLANN_VERSION 0x171
67#if !defined(NOMINMAX) && \
68 (defined(_WIN32) || defined(_WIN32_) || defined(WIN32) || defined(_WIN64))
89 return static_cast<T
>(3.14159265358979323846);
96template <
typename T,
typename =
int>
107template <
typename T,
typename =
int>
121template <
typename Container>
122inline typename std::enable_if<has_resize<Container>::value,
void>::type
resize(
123 Container& c,
const size_t nElements)
132template <
typename Container>
133inline typename std::enable_if<!has_resize<Container>::value,
void>::type
134 resize(Container& c,
const size_t nElements)
136 if (nElements != c.size())
137 throw std::logic_error(
"Try to change the size of a std::array.");
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)
147 c.assign(nElements, value);
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)
157 for (
size_t i = 0; i < nElements; i++) c[i] = value;
164 template <
typename PairType>
165 bool operator()(
const PairType& p1,
const PairType& p2)
const
167 return p1.second < p2.second;
179template <
typename IndexType =
size_t,
typename DistanceType =
double>
183 ResultItem(
const IndexType index,
const DistanceType distance)
197 typename _DistanceType,
typename _IndexType = size_t,
198 typename _CountType =
size_t>
202 using DistanceType = _DistanceType;
203 using IndexType = _IndexType;
204 using CountType = _CountType;
214 : indices(
nullptr), dists(
nullptr), capacity(capacity_), count(0)
218 void init(IndexType* indices_, DistanceType* dists_)
225 CountType size()
const {
return count; }
226 bool empty()
const {
return count == 0; }
227 bool full()
const {
return count == capacity; }
237 for (i = count; i > 0; --i)
241#ifdef NANOFLANN_FIRST_MATCH
242 if ((dists[i - 1] > dist) ||
243 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
246 if (dists[i - 1] > dist)
251 dists[i] = dists[i - 1];
252 indices[i] = indices[i - 1];
263 if (count < capacity) count++;
273 return (count < capacity || !count)
274 ? std::numeric_limits<DistanceType>::max()
286 typename _DistanceType,
typename _IndexType = size_t,
287 typename _CountType =
size_t>
291 using DistanceType = _DistanceType;
292 using IndexType = _IndexType;
293 using CountType = _CountType;
300 DistanceType maximumSearchDistanceSquared;
304 CountType capacity_, DistanceType maximumSearchDistanceSquared_)
309 maximumSearchDistanceSquared(maximumSearchDistanceSquared_)
313 void init(IndexType* indices_, DistanceType* dists_)
318 if (capacity) dists[capacity - 1] = maximumSearchDistanceSquared;
321 CountType size()
const {
return count; }
322 bool empty()
const {
return count == 0; }
323 bool full()
const {
return count == capacity; }
333 for (i = count; i > 0; --i)
337#ifdef NANOFLANN_FIRST_MATCH
338 if ((dists[i - 1] > dist) ||
339 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
342 if (dists[i - 1] > dist)
347 dists[i] = dists[i - 1];
348 indices[i] = indices[i - 1];
359 if (count < capacity) count++;
369 return (count < capacity || !count) ? maximumSearchDistanceSquared
382template <
typename _DistanceType,
typename _IndexType =
size_t>
386 using DistanceType = _DistanceType;
387 using IndexType = _IndexType;
390 const DistanceType radius;
392 std::vector<ResultItem<IndexType, DistanceType>>& m_indices_dists;
395 DistanceType radius_,
397 : radius(radius_), m_indices_dists(indices_dists)
402 void init() { clear(); }
403 void clear() { m_indices_dists.clear(); }
405 size_t size()
const {
return m_indices_dists.size(); }
406 size_t empty()
const {
return m_indices_dists.empty(); }
408 bool full()
const {
return true; }
417 if (dist < radius) m_indices_dists.emplace_back(index, dist);
421 DistanceType worstDist()
const {
return radius; }
429 if (m_indices_dists.empty())
430 throw std::runtime_error(
431 "Cannot invoke RadiusResultSet::worst_item() on "
432 "an empty list of results.");
433 auto it = std::max_element(
450void save_value(std::ostream& stream,
const T& value)
452 stream.write(
reinterpret_cast<const char*
>(&value),
sizeof(T));
456void save_value(std::ostream& stream,
const std::vector<T>& value)
458 size_t size = value.size();
459 stream.write(
reinterpret_cast<const char*
>(&size),
sizeof(
size_t));
460 stream.write(
reinterpret_cast<const char*
>(value.data()),
sizeof(T) * size);
464void load_value(std::istream& stream, T& value)
466 stream.read(
reinterpret_cast<char*
>(&value),
sizeof(T));
470void load_value(std::istream& stream, std::vector<T>& value)
473 stream.read(
reinterpret_cast<char*
>(&size),
sizeof(
size_t));
475 stream.read(
reinterpret_cast<char*
>(value.data()),
sizeof(T) * size);
497 class T,
class DataSource,
typename _DistanceType = T,
498 typename IndexType = uint32_t>
501 using ElementType = T;
502 using DistanceType = _DistanceType;
504 const DataSource& data_source;
506 L1_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
508 DistanceType evalMetric(
509 const T* a,
const IndexType b_idx,
size_t size,
510 DistanceType worst_dist = -1)
const
512 DistanceType result = DistanceType();
513 const T* last = a + size;
514 const T* lastgroup = last - 3;
518 while (a < lastgroup)
520 const DistanceType diff0 =
521 std::abs(a[0] - data_source.kdtree_get_pt(b_idx, d++));
522 const DistanceType diff1 =
523 std::abs(a[1] - data_source.kdtree_get_pt(b_idx, d++));
524 const DistanceType diff2 =
525 std::abs(a[2] - data_source.kdtree_get_pt(b_idx, d++));
526 const DistanceType diff3 =
527 std::abs(a[3] - data_source.kdtree_get_pt(b_idx, d++));
528 result += diff0 + diff1 + diff2 + diff3;
530 if ((worst_dist > 0) && (result > worst_dist)) {
return result; }
536 result += std::abs(*a++ - data_source.kdtree_get_pt(b_idx, d++));
541 template <
typename U,
typename V>
542 DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
544 return std::abs(a - b);
559 class T,
class DataSource,
typename _DistanceType = T,
560 typename IndexType = uint32_t>
563 using ElementType = T;
564 using DistanceType = _DistanceType;
566 const DataSource& data_source;
568 L2_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
570 DistanceType evalMetric(
571 const T* a,
const IndexType b_idx,
size_t size,
572 DistanceType worst_dist = -1)
const
574 DistanceType result = DistanceType();
575 const T* last = a + size;
576 const T* lastgroup = last - 3;
580 while (a < lastgroup)
582 const DistanceType diff0 =
583 a[0] - data_source.kdtree_get_pt(b_idx, d++);
584 const DistanceType diff1 =
585 a[1] - data_source.kdtree_get_pt(b_idx, d++);
586 const DistanceType diff2 =
587 a[2] - data_source.kdtree_get_pt(b_idx, d++);
588 const DistanceType diff3 =
589 a[3] - data_source.kdtree_get_pt(b_idx, d++);
591 diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
593 if ((worst_dist > 0) && (result > worst_dist)) {
return result; }
599 const DistanceType diff0 =
600 *a++ - data_source.kdtree_get_pt(b_idx, d++);
601 result += diff0 * diff0;
606 template <
typename U,
typename V>
607 DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
609 return (a - b) * (a - b);
624 class T,
class DataSource,
typename _DistanceType = T,
625 typename IndexType = uint32_t>
628 using ElementType = T;
629 using DistanceType = _DistanceType;
631 const DataSource& data_source;
634 : data_source(_data_source)
638 DistanceType evalMetric(
639 const T* a,
const IndexType b_idx,
size_t size)
const
641 DistanceType result = DistanceType();
642 for (
size_t i = 0; i < size; ++i)
644 const DistanceType diff =
645 a[i] - data_source.kdtree_get_pt(b_idx, i);
646 result += diff * diff;
651 template <
typename U,
typename V>
652 DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
654 return (a - b) * (a - b);
669 class T,
class DataSource,
typename _DistanceType = T,
670 typename IndexType = uint32_t>
673 using ElementType = T;
674 using DistanceType = _DistanceType;
676 const DataSource& data_source;
678 SO2_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
680 DistanceType evalMetric(
681 const T* a,
const IndexType b_idx,
size_t size)
const
684 a[size - 1], data_source.kdtree_get_pt(b_idx, size - 1), size - 1);
689 template <
typename U,
typename V>
690 DistanceType
accum_dist(
const U a,
const V b,
const size_t)
const
692 DistanceType result = DistanceType();
693 DistanceType PI = pi_const<DistanceType>();
697 else if (result < -PI)
714 class T,
class DataSource,
typename _DistanceType = T,
715 typename IndexType = uint32_t>
718 using ElementType = T;
719 using DistanceType = _DistanceType;
725 : distance_L2_Simple(_data_source)
729 DistanceType evalMetric(
730 const T* a,
const IndexType b_idx,
size_t size)
const
732 return distance_L2_Simple.evalMetric(a, b_idx, size);
735 template <
typename U,
typename V>
736 DistanceType accum_dist(
const U a,
const V b,
const size_t idx)
const
738 return distance_L2_Simple.accum_dist(a, b, idx);
745 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
755 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
765 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
774 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
783 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
795enum class KDTreeSingleIndexAdaptorFlags
798 SkipInitialBuildIndex = 1
801inline std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type operator&(
802 KDTreeSingleIndexAdaptorFlags lhs, KDTreeSingleIndexAdaptorFlags rhs)
805 typename std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type;
806 return static_cast<underlying
>(lhs) &
static_cast<underlying
>(rhs);
813 size_t _leaf_max_size = 10,
814 KDTreeSingleIndexAdaptorFlags _flags =
815 KDTreeSingleIndexAdaptorFlags::None,
816 unsigned int _n_thread_build = 1)
817 : leaf_max_size(_leaf_max_size),
819 n_thread_build(_n_thread_build)
823 size_t leaf_max_size;
824 KDTreeSingleIndexAdaptorFlags flags;
825 unsigned int n_thread_build;
832 : eps(eps_), sorted(sorted_)
861 static constexpr size_t WORDSIZE = 16;
862 static constexpr size_t BLOCKSIZE = 8192;
873 void* base_ =
nullptr;
874 void* loc_ =
nullptr;
886 Size wastedMemory = 0;
901 while (base_ !=
nullptr)
904 void* prev = *(
static_cast<void**
>(base_));
921 const Size size = (req_size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
926 if (size > remaining_)
928 wastedMemory += remaining_;
931 const Size blocksize =
932 size > BLOCKSIZE ? size + WORDSIZE : BLOCKSIZE + WORDSIZE;
935 void* m = ::malloc(blocksize);
938 fprintf(stderr,
"Failed to allocate memory.\n");
939 throw std::bad_alloc();
943 static_cast<void**
>(m)[0] = base_;
946 remaining_ = blocksize - WORDSIZE;
947 loc_ =
static_cast<char*
>(m) + WORDSIZE;
950 loc_ =
static_cast<char*
>(loc_) + size;
965 template <
typename T>
968 T* mem =
static_cast<T*
>(this->malloc(
sizeof(T) * count));
980template <
int32_t DIM,
typename T>
983 using type = std::array<T, DIM>;
989 using type = std::vector<T>;
1009 class Derived,
typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
1010 typename index_t = uint32_t>
1018 obj.pool_.free_all();
1019 obj.root_node_ =
nullptr;
1020 obj.size_at_index_build_ = 0;
1023 using ElementType =
typename Distance::ElementType;
1024 using DistanceType =
typename Distance::DistanceType;
1025 using IndexType = index_t;
1032 using Offset =
typename decltype(vAcc_)::size_type;
1033 using Size =
typename decltype(vAcc_)::size_type;
1034 using Dimension = int32_t;
1058 Node *child1 =
nullptr, *child2 =
nullptr;
1066 ElementType low, high;
1071 Size leaf_max_size_ = 0;
1074 Size n_thread_build_ = 1;
1078 Size size_at_index_build_ = 0;
1102 Size
size(
const Derived& obj)
const {
return obj.size_; }
1105 Size
veclen(
const Derived& obj) {
return DIM > 0 ? DIM : obj.dim; }
1109 const Derived& obj, IndexType element, Dimension component)
const
1111 return obj.dataset_.kdtree_get_pt(element, component);
1120 return obj.pool_.usedMemory + obj.pool_.wastedMemory +
1121 obj.dataset_.kdtree_get_point_count() *
1126 const Derived& obj, Offset ind, Size count, Dimension element,
1127 ElementType& min_elem, ElementType& max_elem)
1129 min_elem = dataset_get(obj, vAcc_[ind], element);
1130 max_elem = min_elem;
1131 for (Offset i = 1; i < count; ++i)
1133 ElementType val = dataset_get(obj, vAcc_[ind + i], element);
1134 if (val < min_elem) min_elem = val;
1135 if (val > max_elem) max_elem = val;
1147 Derived& obj,
const Offset left,
const Offset right,
BoundingBox& bbox)
1149 assert(left < obj.dataset_.kdtree_get_point_count());
1151 NodePtr node = obj.pool_.template allocate<Node>();
1152 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1155 if ((right - left) <=
static_cast<Offset
>(obj.leaf_max_size_))
1157 node->
child1 = node->child2 =
nullptr;
1162 for (Dimension i = 0; i < dims; ++i)
1164 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1165 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1167 for (Offset k = left + 1; k < right; ++k)
1169 for (Dimension i = 0; i < dims; ++i)
1171 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1172 if (bbox[i].low > val) bbox[i].low = val;
1173 if (bbox[i].high < val) bbox[i].high = val;
1181 DistanceType cutval;
1182 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1187 left_bbox[cutfeat].high = cutval;
1188 node->
child1 = this->divideTree(obj, left, left + idx, left_bbox);
1191 right_bbox[cutfeat].low = cutval;
1192 node->child2 = this->divideTree(obj, left + idx, right, right_bbox);
1194 node->
node_type.sub.divlow = left_bbox[cutfeat].high;
1195 node->
node_type.sub.divhigh = right_bbox[cutfeat].low;
1197 for (Dimension i = 0; i < dims; ++i)
1199 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1200 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1218 Derived& obj,
const Offset left,
const Offset right,
BoundingBox& bbox,
1219 std::atomic<unsigned int>& thread_count, std::mutex& mutex)
1221 std::unique_lock<std::mutex> lock(mutex);
1222 NodePtr node = obj.pool_.template allocate<Node>();
1225 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1228 if ((right - left) <=
static_cast<Offset
>(obj.leaf_max_size_))
1230 node->
child1 = node->child2 =
nullptr;
1235 for (Dimension i = 0; i < dims; ++i)
1237 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1238 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1240 for (Offset k = left + 1; k < right; ++k)
1242 for (Dimension i = 0; i < dims; ++i)
1244 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1245 if (bbox[i].low > val) bbox[i].low = val;
1246 if (bbox[i].high < val) bbox[i].high = val;
1254 DistanceType cutval;
1255 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1259 std::future<NodePtr> right_future;
1262 right_bbox[cutfeat].low = cutval;
1263 if (++thread_count < n_thread_build_)
1266 right_future = std::async(
1267 std::launch::async, &KDTreeBaseClass::divideTreeConcurrent,
1268 this, std::ref(obj), left + idx, right,
1269 std::ref(right_bbox), std::ref(thread_count),
1272 else { --thread_count; }
1275 left_bbox[cutfeat].high = cutval;
1276 node->
child1 = this->divideTreeConcurrent(
1277 obj, left, left + idx, left_bbox, thread_count, mutex);
1279 if (right_future.valid())
1282 node->child2 = right_future.get();
1287 node->child2 = this->divideTreeConcurrent(
1288 obj, left + idx, right, right_bbox, thread_count, mutex);
1291 node->
node_type.sub.divlow = left_bbox[cutfeat].high;
1292 node->
node_type.sub.divhigh = right_bbox[cutfeat].low;
1294 for (Dimension i = 0; i < dims; ++i)
1296 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1297 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1305 const Derived& obj,
const Offset ind,
const Size count, Offset& index,
1306 Dimension& cutfeat, DistanceType& cutval,
const BoundingBox& bbox)
1308 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1309 const auto EPS =
static_cast<DistanceType
>(0.00001);
1310 ElementType max_span = bbox[0].high - bbox[0].low;
1311 for (Dimension i = 1; i < dims; ++i)
1313 ElementType span = bbox[i].high - bbox[i].low;
1314 if (span > max_span) { max_span = span; }
1316 ElementType max_spread = -1;
1318 ElementType min_elem = 0, max_elem = 0;
1319 for (Dimension i = 0; i < dims; ++i)
1321 ElementType span = bbox[i].high - bbox[i].low;
1322 if (span >= (1 - EPS) * max_span)
1324 ElementType min_elem_, max_elem_;
1325 computeMinMax(obj, ind, count, i, min_elem_, max_elem_);
1326 ElementType spread = max_elem_ - min_elem_;
1327 if (spread > max_spread)
1330 max_spread = spread;
1331 min_elem = min_elem_;
1332 max_elem = max_elem_;
1337 DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;
1339 if (split_val < min_elem)
1341 else if (split_val > max_elem)
1347 planeSplit(obj, ind, count, cutfeat, cutval, lim1, lim2);
1349 if (lim1 > count / 2)
1351 else if (lim2 < count / 2)
1367 const Derived& obj,
const Offset ind,
const Size count,
1368 const Dimension cutfeat,
const DistanceType& cutval, Offset& lim1,
1373 Offset right = count - 1;
1376 while (left <= right &&
1377 dataset_get(obj, vAcc_[ind + left], cutfeat) < cutval)
1379 while (right && left <= right &&
1380 dataset_get(obj, vAcc_[ind + right], cutfeat) >= cutval)
1382 if (left > right || !right)
1384 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1395 while (left <= right &&
1396 dataset_get(obj, vAcc_[ind + left], cutfeat) <= cutval)
1398 while (right && left <= right &&
1399 dataset_get(obj, vAcc_[ind + right], cutfeat) > cutval)
1401 if (left > right || !right)
1403 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1410 DistanceType computeInitialDistances(
1411 const Derived& obj,
const ElementType* vec,
1412 distance_vector_t& dists)
const
1415 DistanceType dist = DistanceType();
1417 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim_); ++i)
1419 if (vec[i] < obj.root_bbox_[i].low)
1422 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].low, i);
1425 if (vec[i] > obj.root_bbox_[i].high)
1428 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].high, i);
1435 static void save_tree(
1436 const Derived& obj, std::ostream& stream,
const NodeConstPtr tree)
1438 save_value(stream, *tree);
1439 if (tree->child1 !=
nullptr) { save_tree(obj, stream, tree->child1); }
1440 if (tree->child2 !=
nullptr) { save_tree(obj, stream, tree->child2); }
1443 static void load_tree(Derived& obj, std::istream& stream, NodePtr& tree)
1445 tree = obj.pool_.template allocate<Node>();
1446 load_value(stream, *tree);
1447 if (tree->child1 !=
nullptr) { load_tree(obj, stream, tree->child1); }
1448 if (tree->child2 !=
nullptr) { load_tree(obj, stream, tree->child2); }
1456 void saveIndex(
const Derived& obj, std::ostream& stream)
const
1458 save_value(stream, obj.size_);
1459 save_value(stream, obj.dim_);
1460 save_value(stream, obj.root_bbox_);
1461 save_value(stream, obj.leaf_max_size_);
1462 save_value(stream, obj.vAcc_);
1463 if (obj.root_node_) save_tree(obj, stream, obj.root_node_);
1473 load_value(stream, obj.size_);
1474 load_value(stream, obj.dim_);
1475 load_value(stream, obj.root_bbox_);
1476 load_value(stream, obj.leaf_max_size_);
1477 load_value(stream, obj.vAcc_);
1478 load_tree(obj, stream, obj.root_node_);
1524 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
1525 typename index_t = uint32_t>
1528 KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, index_t>,
1529 Distance, DatasetAdaptor, DIM, index_t>
1535 Distance, DatasetAdaptor, DIM, index_t>&) =
delete;
1546 Distance, DatasetAdaptor, DIM, index_t>,
1547 Distance, DatasetAdaptor, DIM, index_t>;
1549 using Offset =
typename Base::Offset;
1550 using Size =
typename Base::Size;
1551 using Dimension =
typename Base::Dimension;
1553 using ElementType =
typename Base::ElementType;
1554 using DistanceType =
typename Base::DistanceType;
1555 using IndexType =
typename Base::IndexType;
1557 using Node =
typename Base::Node;
1558 using NodePtr = Node*;
1560 using Interval =
typename Base::Interval;
1590 template <
class... Args>
1592 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1594 : dataset_(inputData),
1595 indexParams(params),
1596 distance_(inputData, std::forward<Args>(args)...)
1598 init(dimensionality, params);
1602 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1604 : dataset_(inputData), indexParams(params), distance_(inputData)
1606 init(dimensionality, params);
1611 const Dimension dimensionality,
1612 const KDTreeSingleIndexAdaptorParams& params)
1614 Base::size_ = dataset_.kdtree_get_point_count();
1615 Base::size_at_index_build_ = Base::size_;
1616 Base::dim_ = dimensionality;
1617 if (DIM > 0) Base::dim_ = DIM;
1618 Base::leaf_max_size_ = params.leaf_max_size;
1619 if (params.n_thread_build > 0)
1621 Base::n_thread_build_ = params.n_thread_build;
1625 Base::n_thread_build_ =
1626 std::max(std::thread::hardware_concurrency(), 1u);
1629 if (!(params.flags &
1630 KDTreeSingleIndexAdaptorFlags::SkipInitialBuildIndex))
1643 Base::size_ = dataset_.kdtree_get_point_count();
1644 Base::size_at_index_build_ = Base::size_;
1646 this->freeIndex(*
this);
1647 Base::size_at_index_build_ = Base::size_;
1648 if (Base::size_ == 0)
return;
1649 computeBoundingBox(Base::root_bbox_);
1651 if (Base::n_thread_build_ == 1)
1654 this->divideTree(*
this, 0, Base::size_, Base::root_bbox_);
1658#ifndef NANOFLANN_NO_THREADS
1659 std::atomic<unsigned int> thread_count(0u);
1661 Base::root_node_ = this->divideTreeConcurrent(
1662 *
this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
1664 throw std::runtime_error(
"Multithreading is disabled");
1688 template <
typename RESULTSET>
1690 RESULTSET& result,
const ElementType* vec,
1694 if (this->size(*
this) == 0)
return false;
1695 if (!Base::root_node_)
1696 throw std::runtime_error(
1697 "[nanoflann] findNeighbors() called before building the "
1699 float epsError = 1 + searchParams.eps;
1702 distance_vector_t dists;
1704 auto zero =
static_cast<typename RESULTSET::DistanceType
>(0);
1705 assign(dists, (DIM > 0 ? DIM : Base::dim_), zero);
1706 DistanceType dist = this->computeInitialDistances(*
this, vec, dists);
1707 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
1709 if (searchParams.sorted) result.sort();
1711 return result.full();
1730 const ElementType* query_point,
const Size num_closest,
1731 IndexType* out_indices, DistanceType* out_distances)
const
1734 resultSet.init(out_indices, out_distances);
1735 findNeighbors(resultSet, query_point);
1736 return resultSet.size();
1759 const ElementType* query_point,
const DistanceType& radius,
1764 radius, IndicesDists);
1766 radiusSearchCustomCallback(query_point, resultSet, searchParams);
1775 template <
class SEARCH_CALLBACK>
1777 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
1780 findNeighbors(resultSet, query_point, searchParams);
1781 return resultSet.size();
1801 const ElementType* query_point,
const Size num_closest,
1802 IndexType* out_indices, DistanceType* out_distances,
1803 const DistanceType& radius)
const
1806 num_closest, radius);
1807 resultSet.init(out_indices, out_distances);
1808 findNeighbors(resultSet, query_point);
1809 return resultSet.size();
1820 Base::size_ = dataset_.kdtree_get_point_count();
1821 if (Base::vAcc_.size() != Base::size_) Base::vAcc_.resize(Base::size_);
1822 for (IndexType i = 0; i < static_cast<IndexType>(Base::size_); i++)
1826 void computeBoundingBox(BoundingBox& bbox)
1828 const auto dims = (DIM > 0 ? DIM : Base::dim_);
1830 if (dataset_.kdtree_get_bbox(bbox))
1836 const Size N = dataset_.kdtree_get_point_count();
1838 throw std::runtime_error(
1839 "[nanoflann] computeBoundingBox() called but "
1840 "no data points found.");
1841 for (Dimension i = 0; i < dims; ++i)
1843 bbox[i].low = bbox[i].high =
1844 this->dataset_get(*
this, Base::vAcc_[0], i);
1846 for (Offset k = 1; k < N; ++k)
1848 for (Dimension i = 0; i < dims; ++i)
1851 this->dataset_get(*
this, Base::vAcc_[k], i);
1852 if (val < bbox[i].low) bbox[i].low = val;
1853 if (val > bbox[i].high) bbox[i].high = val;
1865 template <
class RESULTSET>
1867 RESULTSET& result_set,
const ElementType* vec,
const NodePtr node,
1869 const float epsError)
const
1872 if ((node->child1 ==
nullptr) && (node->child2 ==
nullptr))
1874 DistanceType worst_dist = result_set.worstDist();
1875 for (Offset i = node->node_type.lr.left;
1876 i < node->node_type.lr.right; ++i)
1878 const IndexType accessor = Base::vAcc_[i];
1879 DistanceType dist = distance_.evalMetric(
1880 vec, accessor, (DIM > 0 ? DIM : Base::dim_));
1881 if (dist < worst_dist)
1883 if (!result_set.addPoint(dist, Base::vAcc_[i]))
1895 Dimension idx = node->node_type.sub.divfeat;
1896 ElementType val = vec[idx];
1897 DistanceType diff1 = val - node->node_type.sub.divlow;
1898 DistanceType diff2 = val - node->node_type.sub.divhigh;
1902 DistanceType cut_dist;
1903 if ((diff1 + diff2) < 0)
1905 bestChild = node->child1;
1906 otherChild = node->child2;
1908 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
1912 bestChild = node->child2;
1913 otherChild = node->child1;
1915 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
1919 if (!searchLevel(result_set, vec, bestChild, mindist, dists, epsError))
1926 DistanceType dst = dists[idx];
1927 mindist = mindist + cut_dist - dst;
1928 dists[idx] = cut_dist;
1929 if (mindist * epsError <= result_set.worstDist())
1932 result_set, vec, otherChild, mindist, dists, epsError))
1951 Base::saveIndex(*
this, stream);
1959 void loadIndex(std::istream& stream) { Base::loadIndex(*
this, stream); }
2001 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
2002 typename IndexType = uint32_t>
2005 KDTreeSingleIndexDynamicAdaptor_<
2006 Distance, DatasetAdaptor, DIM, IndexType>,
2007 Distance, DatasetAdaptor, DIM, IndexType>
2017 std::vector<int>& treeIndex_;
2023 Distance, DatasetAdaptor, DIM, IndexType>,
2024 Distance, DatasetAdaptor, DIM, IndexType>;
2026 using ElementType =
typename Base::ElementType;
2027 using DistanceType =
typename Base::DistanceType;
2029 using Offset =
typename Base::Offset;
2030 using Size =
typename Base::Size;
2031 using Dimension =
typename Base::Dimension;
2033 using Node =
typename Base::Node;
2034 using NodePtr = Node*;
2036 using Interval =
typename Base::Interval;
2061 const Dimension dimensionality,
const DatasetAdaptor& inputData,
2062 std::vector<int>& treeIndex,
2065 : dataset_(inputData),
2066 index_params_(params),
2067 treeIndex_(treeIndex),
2068 distance_(inputData)
2071 Base::size_at_index_build_ = 0;
2072 for (
auto& v : Base::root_bbox_) v = {};
2073 Base::dim_ = dimensionality;
2074 if (DIM > 0) Base::dim_ = DIM;
2075 Base::leaf_max_size_ = params.leaf_max_size;
2076 if (params.n_thread_build > 0)
2078 Base::n_thread_build_ = params.n_thread_build;
2082 Base::n_thread_build_ =
2083 std::max(std::thread::hardware_concurrency(), 1u);
2096 std::swap(Base::vAcc_, tmp.Base::vAcc_);
2097 std::swap(Base::leaf_max_size_, tmp.Base::leaf_max_size_);
2098 std::swap(index_params_, tmp.index_params_);
2099 std::swap(treeIndex_, tmp.treeIndex_);
2100 std::swap(Base::size_, tmp.Base::size_);
2101 std::swap(Base::size_at_index_build_, tmp.Base::size_at_index_build_);
2102 std::swap(Base::root_node_, tmp.Base::root_node_);
2103 std::swap(Base::root_bbox_, tmp.Base::root_bbox_);
2104 std::swap(Base::pool_, tmp.Base::pool_);
2113 Base::size_ = Base::vAcc_.size();
2114 this->freeIndex(*
this);
2115 Base::size_at_index_build_ = Base::size_;
2116 if (Base::size_ == 0)
return;
2117 computeBoundingBox(Base::root_bbox_);
2119 if (Base::n_thread_build_ == 1)
2122 this->divideTree(*
this, 0, Base::size_, Base::root_bbox_);
2126#ifndef NANOFLANN_NO_THREADS
2127 std::atomic<unsigned int> thread_count(0u);
2129 Base::root_node_ = this->divideTreeConcurrent(
2130 *
this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
2132 throw std::runtime_error(
"Multithreading is disabled");
2160 template <
typename RESULTSET>
2162 RESULTSET& result,
const ElementType* vec,
2166 if (this->size(*
this) == 0)
return false;
2167 if (!Base::root_node_)
return false;
2168 float epsError = 1 + searchParams.eps;
2171 distance_vector_t dists;
2174 dists, (DIM > 0 ? DIM : Base::dim_),
2175 static_cast<typename distance_vector_t::value_type
>(0));
2176 DistanceType dist = this->computeInitialDistances(*
this, vec, dists);
2177 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
2178 return result.full();
2196 const ElementType* query_point,
const Size num_closest,
2197 IndexType* out_indices, DistanceType* out_distances,
2201 resultSet.init(out_indices, out_distances);
2202 findNeighbors(resultSet, query_point, searchParams);
2203 return resultSet.size();
2226 const ElementType* query_point,
const DistanceType& radius,
2231 radius, IndicesDists);
2232 const size_t nFound =
2233 radiusSearchCustomCallback(query_point, resultSet, searchParams);
2242 template <
class SEARCH_CALLBACK>
2244 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
2247 findNeighbors(resultSet, query_point, searchParams);
2248 return resultSet.size();
2254 void computeBoundingBox(BoundingBox& bbox)
2256 const auto dims = (DIM > 0 ? DIM : Base::dim_);
2259 if (dataset_.kdtree_get_bbox(bbox))
2265 const Size N = Base::size_;
2267 throw std::runtime_error(
2268 "[nanoflann] computeBoundingBox() called but "
2269 "no data points found.");
2270 for (Dimension i = 0; i < dims; ++i)
2272 bbox[i].low = bbox[i].high =
2273 this->dataset_get(*
this, Base::vAcc_[0], i);
2275 for (Offset k = 1; k < N; ++k)
2277 for (Dimension i = 0; i < dims; ++i)
2280 this->dataset_get(*
this, Base::vAcc_[k], i);
2281 if (val < bbox[i].low) bbox[i].low = val;
2282 if (val > bbox[i].high) bbox[i].high = val;
2292 template <
class RESULTSET>
2294 RESULTSET& result_set,
const ElementType* vec,
const NodePtr node,
2296 const float epsError)
const
2299 if ((node->child1 ==
nullptr) && (node->child2 ==
nullptr))
2301 DistanceType worst_dist = result_set.worstDist();
2302 for (Offset i = node->node_type.lr.left;
2303 i < node->node_type.lr.right; ++i)
2305 const IndexType index = Base::vAcc_[i];
2306 if (treeIndex_[index] == -1)
continue;
2307 DistanceType dist = distance_.evalMetric(
2308 vec, index, (DIM > 0 ? DIM : Base::dim_));
2309 if (dist < worst_dist)
2311 if (!result_set.addPoint(
2312 static_cast<typename RESULTSET::DistanceType
>(dist),
2313 static_cast<typename RESULTSET::IndexType
>(
2326 Dimension idx = node->node_type.sub.divfeat;
2327 ElementType val = vec[idx];
2328 DistanceType diff1 = val - node->node_type.sub.divlow;
2329 DistanceType diff2 = val - node->node_type.sub.divhigh;
2333 DistanceType cut_dist;
2334 if ((diff1 + diff2) < 0)
2336 bestChild = node->child1;
2337 otherChild = node->child2;
2339 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
2343 bestChild = node->child2;
2344 otherChild = node->child1;
2346 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
2350 searchLevel(result_set, vec, bestChild, mindist, dists, epsError);
2352 DistanceType dst = dists[idx];
2353 mindist = mindist + cut_dist - dst;
2354 dists[idx] = cut_dist;
2355 if (mindist * epsError <= result_set.worstDist())
2357 searchLevel(result_set, vec, otherChild, mindist, dists, epsError);
2393 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
2394 typename IndexType = uint32_t>
2398 using ElementType =
typename Distance::ElementType;
2399 using DistanceType =
typename Distance::DistanceType;
2402 Distance, DatasetAdaptor, DIM>::Offset;
2404 Distance, DatasetAdaptor, DIM>::Size;
2406 Distance, DatasetAdaptor, DIM>::Dimension;
2409 Size leaf_max_size_;
2421 std::unordered_set<int> removedPoints_;
2428 Distance, DatasetAdaptor, DIM, IndexType>;
2429 std::vector<index_container_t> index_;
2441 int First0Bit(IndexType num)
2455 using my_kd_tree_t = KDTreeSingleIndexDynamicAdaptor_<
2456 Distance, DatasetAdaptor, DIM, IndexType>;
2457 std::vector<my_kd_tree_t> index(
2459 my_kd_tree_t(dim_ , dataset_, treeIndex_, index_params_));
2482 const int dimensionality,
const DatasetAdaptor& inputData,
2485 const size_t maximumPointCount = 1000000000U)
2486 : dataset_(inputData), index_params_(params), distance_(inputData)
2488 treeCount_ =
static_cast<size_t>(std::log2(maximumPointCount)) + 1;
2490 dim_ = dimensionality;
2492 if (DIM > 0) dim_ = DIM;
2493 leaf_max_size_ = params.leaf_max_size;
2495 const size_t num_initial_points = dataset_.kdtree_get_point_count();
2496 if (num_initial_points > 0) { addPoints(0, num_initial_points - 1); }
2502 Distance, DatasetAdaptor, DIM, IndexType>&) =
delete;
2507 const Size count = end - start + 1;
2509 treeIndex_.resize(treeIndex_.size() + count);
2510 for (IndexType idx = start; idx <= end; idx++)
2512 const int pos = First0Bit(pointCount_);
2513 maxIndex = std::max(pos, maxIndex);
2514 treeIndex_[pointCount_] = pos;
2516 const auto it = removedPoints_.find(idx);
2517 if (it != removedPoints_.end())
2519 removedPoints_.erase(it);
2520 treeIndex_[idx] = pos;
2523 for (
int i = 0; i < pos; i++)
2525 for (
int j = 0; j < static_cast<int>(index_[i].vAcc_.size());
2528 index_[pos].vAcc_.push_back(index_[i].vAcc_[j]);
2529 if (treeIndex_[index_[i].vAcc_[j]] != -1)
2530 treeIndex_[index_[i].vAcc_[j]] = pos;
2532 index_[i].vAcc_.clear();
2534 index_[pos].vAcc_.push_back(idx);
2538 for (
int i = 0; i <= maxIndex; ++i)
2540 index_[i].freeIndex(index_[i]);
2541 if (!index_[i].vAcc_.empty()) index_[i].buildIndex();
2548 if (idx >= pointCount_)
return;
2549 removedPoints_.insert(idx);
2550 treeIndex_[idx] = -1;
2569 template <
typename RESULTSET>
2571 RESULTSET& result,
const ElementType* vec,
2574 for (
size_t i = 0; i < treeCount_; i++)
2576 index_[i].findNeighbors(result, &vec[0], searchParams);
2578 return result.full();
2609 bool row_major =
true>
2614 using num_t =
typename MatrixType::Scalar;
2615 using IndexType =
typename MatrixType::Index;
2616 using metric_t =
typename Distance::template traits<
2617 num_t,
self_t, IndexType>::distance_t;
2621 row_major ? MatrixType::ColsAtCompileTime
2622 : MatrixType::RowsAtCompileTime,
2629 using Size =
typename index_t::Size;
2630 using Dimension =
typename index_t::Dimension;
2634 const Dimension dimensionality,
2635 const std::reference_wrapper<const MatrixType>& mat,
2636 const int leaf_max_size = 10,
const unsigned int n_thread_build = 1)
2637 : m_data_matrix(mat)
2639 const auto dims = row_major ? mat.get().cols() : mat.get().rows();
2640 if (
static_cast<Dimension
>(dims) != dimensionality)
2641 throw std::runtime_error(
2642 "Error: 'dimensionality' must match column count in data "
2644 if (DIM > 0 &&
static_cast<int32_t
>(dims) != DIM)
2645 throw std::runtime_error(
2646 "Data set dimensionality does not match the 'DIM' template "
2651 leaf_max_size, nanoflann::KDTreeSingleIndexAdaptorFlags::None,
2661 const std::reference_wrapper<const MatrixType> m_data_matrix;
2672 const num_t* query_point,
const Size num_closest,
2673 IndexType* out_indices, num_t* out_distances)
const
2676 resultSet.init(out_indices, out_distances);
2683 const self_t& derived()
const {
return *
this; }
2684 self_t& derived() {
return *
this; }
2687 Size kdtree_get_point_count()
const
2690 return m_data_matrix.get().rows();
2692 return m_data_matrix.get().cols();
2696 num_t kdtree_get_pt(
const IndexType idx,
size_t dim)
const
2699 return m_data_matrix.get().coeff(idx, IndexType(dim));
2701 return m_data_matrix.get().coeff(IndexType(dim), idx);
2709 template <
class BBOX>
2710 bool kdtree_get_bbox(BBOX& )
const
Definition nanoflann.hpp:1012
void freeIndex(Derived &obj)
Definition nanoflann.hpp:1016
BoundingBox root_bbox_
Definition nanoflann.hpp:1090
Size veclen(const Derived &obj)
Definition nanoflann.hpp:1105
void saveIndex(const Derived &obj, std::ostream &stream) const
Definition nanoflann.hpp:1456
Size usedMemory(Derived &obj)
Definition nanoflann.hpp:1118
typename array_or_vector< DIM, DistanceType >::type distance_vector_t
Definition nanoflann.hpp:1087
void planeSplit(const Derived &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)
Definition nanoflann.hpp:1366
NodePtr divideTree(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox)
Definition nanoflann.hpp:1146
std::vector< IndexType > vAcc_
Definition nanoflann.hpp:1030
Size size(const Derived &obj) const
Definition nanoflann.hpp:1102
NodePtr divideTreeConcurrent(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex)
Definition nanoflann.hpp:1217
void loadIndex(Derived &obj, std::istream &stream)
Definition nanoflann.hpp:1471
PooledAllocator pool_
Definition nanoflann.hpp:1099
ElementType dataset_get(const Derived &obj, IndexType element, Dimension component) const
Helper accessor to the dataset points:
Definition nanoflann.hpp:1108
typename array_or_vector< DIM, Interval >::type BoundingBox
Definition nanoflann.hpp:1083
Definition nanoflann.hpp:1530
bool searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:1866
void saveIndex(std::ostream &stream) const
Definition nanoflann.hpp:1949
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1758
void init_vind()
Definition nanoflann.hpp:1817
void buildIndex()
Definition nanoflann.hpp:1641
const DatasetAdaptor & dataset_
Definition nanoflann.hpp:1538
KDTreeSingleIndexAdaptor(const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t > &)=delete
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1689
Size rknnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const
Definition nanoflann.hpp:1800
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1776
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:1568
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:1959
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:1564
KDTreeSingleIndexAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms, Args &&... args)
Definition nanoflann.hpp:1591
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances) const
Definition nanoflann.hpp:1729
Definition nanoflann.hpp:2008
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2225
KDTreeSingleIndexDynamicAdaptor_(const Dimension dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams())
Definition nanoflann.hpp:2060
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:2039
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:2013
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2243
KDTreeSingleIndexDynamicAdaptor_(const KDTreeSingleIndexDynamicAdaptor_ &rhs)=default
void buildIndex()
Definition nanoflann.hpp:2111
void saveIndex(std::ostream &stream)
Definition nanoflann.hpp:2368
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:2043
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:2375
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2195
void searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:2293
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2161
KDTreeSingleIndexDynamicAdaptor_ operator=(const KDTreeSingleIndexDynamicAdaptor_ &rhs)
Definition nanoflann.hpp:2092
Definition nanoflann.hpp:2396
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2570
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:2416
void removePoint(size_t idx)
Definition nanoflann.hpp:2546
void addPoints(IndexType start, IndexType end)
Definition nanoflann.hpp:2505
KDTreeSingleIndexDynamicAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams(), const size_t maximumPointCount=1000000000U)
Definition nanoflann.hpp:2481
std::vector< int > treeIndex_
Definition nanoflann.hpp:2420
const std::vector< index_container_t > & getAllIndices() const
Definition nanoflann.hpp:2434
Dimension dim_
Dimensionality of each data point.
Definition nanoflann.hpp:2425
KDTreeSingleIndexDynamicAdaptor(const KDTreeSingleIndexDynamicAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete
Definition nanoflann.hpp:200
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:234
DistanceType worstDist() const
Definition nanoflann.hpp:271
Definition nanoflann.hpp:860
~PooledAllocator()
Definition nanoflann.hpp:896
void free_all()
Definition nanoflann.hpp:899
void * malloc(const size_t req_size)
Definition nanoflann.hpp:915
T * allocate(const size_t count=1)
Definition nanoflann.hpp:966
PooledAllocator()
Definition nanoflann.hpp:891
Definition nanoflann.hpp:289
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:330
DistanceType worstDist() const
Definition nanoflann.hpp:367
Definition nanoflann.hpp:384
ResultItem< IndexType, DistanceType > worst_item() const
Definition nanoflann.hpp:427
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:415
std::enable_if< has_assign< Container >::value, void >::type assign(Container &c, const size_t nElements, const T &value)
Definition nanoflann.hpp:144
T pi_const()
Definition nanoflann.hpp:87
std::enable_if< has_resize< Container >::value, void >::type resize(Container &c, const size_t nElements)
Definition nanoflann.hpp:122
Definition nanoflann.hpp:162
bool operator()(const PairType &p1, const PairType &p2) const
Definition nanoflann.hpp:165
Definition nanoflann.hpp:1065
Definition nanoflann.hpp:1040
DistanceType divlow
The values used for subdivision.
Definition nanoflann.hpp:1053
Offset right
Indices of points in leaf node.
Definition nanoflann.hpp:1047
union nanoflann::KDTreeBaseClass::Node::@0 node_type
Dimension divfeat
Definition nanoflann.hpp:1051
Node * child1
Definition nanoflann.hpp:1058
Definition nanoflann.hpp:2611
void query(const num_t *query_point, const Size num_closest, IndexType *out_indices, num_t *out_distances) const
Definition nanoflann.hpp:2671
KDTreeEigenMatrixAdaptor(const self_t &)=delete
typename index_t::Offset Offset
Definition nanoflann.hpp:2628
KDTreeEigenMatrixAdaptor(const Dimension dimensionality, const std::reference_wrapper< const MatrixType > &mat, const int leaf_max_size=10, const unsigned int n_thread_build=1)
Constructor: takes a const ref to the matrix object with the data points.
Definition nanoflann.hpp:2633
Definition nanoflann.hpp:811
Definition nanoflann.hpp:500
Definition nanoflann.hpp:562
Definition nanoflann.hpp:627
Definition nanoflann.hpp:483
Definition nanoflann.hpp:181
DistanceType second
Distance from sample to query point.
Definition nanoflann.hpp:189
IndexType first
Index of the sample in the dataset.
Definition nanoflann.hpp:188
Definition nanoflann.hpp:672
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition nanoflann.hpp:690
Definition nanoflann.hpp:717
Definition nanoflann.hpp:830
bool sorted
distance (default: true)
Definition nanoflann.hpp:837
float eps
search for eps-approximate neighbours (default: 0)
Definition nanoflann.hpp:836
Definition nanoflann.hpp:982
Definition nanoflann.hpp:109
Definition nanoflann.hpp:98
Definition nanoflann.hpp:747
Definition nanoflann.hpp:744
Definition nanoflann.hpp:757
Definition nanoflann.hpp:767
Definition nanoflann.hpp:764
Definition nanoflann.hpp:754
Definition nanoflann.hpp:776
Definition nanoflann.hpp:773
Definition nanoflann.hpp:785
Definition nanoflann.hpp:782