60#include <unordered_set>
64#define NANOFLANN_VERSION 0x155
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;
165 template <
typename PairType>
166 bool operator()(
const PairType& p1,
const PairType& p2)
const
168 return p1.second < p2.second;
180template <
typename IndexType =
size_t,
typename DistanceType =
double>
184 ResultItem(
const IndexType index,
const DistanceType distance)
198 typename _DistanceType,
typename _IndexType = size_t,
199 typename _CountType =
size_t>
203 using DistanceType = _DistanceType;
204 using IndexType = _IndexType;
205 using CountType = _CountType;
215 : indices(
nullptr), dists(
nullptr), capacity(capacity_), count(0)
219 void init(IndexType* indices_, DistanceType* dists_)
225 dists[capacity - 1] = (std::numeric_limits<DistanceType>::max)();
228 CountType size()
const {
return count; }
229 bool empty()
const {
return count == 0; }
230 bool full()
const {
return count == capacity; }
240 for (i = count; i > 0; --i)
244#ifdef NANOFLANN_FIRST_MATCH
245 if ((dists[i - 1] > dist) ||
246 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
249 if (dists[i - 1] > dist)
254 dists[i] = dists[i - 1];
255 indices[i] = indices[i - 1];
266 if (count < capacity) count++;
272 DistanceType worstDist()
const {
return dists[capacity - 1]; }
282 typename _DistanceType,
typename _IndexType = size_t,
283 typename _CountType =
size_t>
287 using DistanceType = _DistanceType;
288 using IndexType = _IndexType;
289 using CountType = _CountType;
296 DistanceType maximumSearchDistanceSquared;
300 CountType capacity_, DistanceType maximumSearchDistanceSquared_)
305 maximumSearchDistanceSquared(maximumSearchDistanceSquared_)
309 void init(IndexType* indices_, DistanceType* dists_)
314 if (capacity) dists[capacity - 1] = maximumSearchDistanceSquared;
317 CountType size()
const {
return count; }
318 bool empty()
const {
return count == 0; }
319 bool full()
const {
return count == capacity; }
329 for (i = count; i > 0; --i)
333#ifdef NANOFLANN_FIRST_MATCH
334 if ((dists[i - 1] > dist) ||
335 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
338 if (dists[i - 1] > dist)
343 dists[i] = dists[i - 1];
344 indices[i] = indices[i - 1];
355 if (count < capacity) count++;
361 DistanceType worstDist()
const {
return dists[capacity - 1]; }
372template <
typename _DistanceType,
typename _IndexType =
size_t>
376 using DistanceType = _DistanceType;
377 using IndexType = _IndexType;
380 const DistanceType radius;
382 std::vector<ResultItem<IndexType, DistanceType>>& m_indices_dists;
385 DistanceType radius_,
387 : radius(radius_), m_indices_dists(indices_dists)
392 void init() { clear(); }
393 void clear() { m_indices_dists.clear(); }
395 size_t size()
const {
return m_indices_dists.size(); }
396 size_t empty()
const {
return m_indices_dists.empty(); }
398 bool full()
const {
return true; }
407 if (dist < radius) m_indices_dists.emplace_back(index, dist);
411 DistanceType worstDist()
const {
return radius; }
419 if (m_indices_dists.empty())
420 throw std::runtime_error(
421 "Cannot invoke RadiusResultSet::worst_item() on "
422 "an empty list of results.");
423 auto it = std::max_element(
440void save_value(std::ostream& stream,
const T& value)
442 stream.write(
reinterpret_cast<const char*
>(&value),
sizeof(T));
446void save_value(std::ostream& stream,
const std::vector<T>& value)
448 size_t size = value.size();
449 stream.write(
reinterpret_cast<const char*
>(&size),
sizeof(
size_t));
450 stream.write(
reinterpret_cast<const char*
>(value.data()),
sizeof(T) * size);
454void load_value(std::istream& stream, T& value)
456 stream.read(
reinterpret_cast<char*
>(&value),
sizeof(T));
460void load_value(std::istream& stream, std::vector<T>& value)
463 stream.read(
reinterpret_cast<char*
>(&size),
sizeof(
size_t));
465 stream.read(
reinterpret_cast<char*
>(value.data()),
sizeof(T) * size);
487 class T,
class DataSource,
typename _DistanceType = T,
488 typename IndexType = uint32_t>
491 using ElementType = T;
492 using DistanceType = _DistanceType;
494 const DataSource& data_source;
496 L1_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
498 DistanceType evalMetric(
499 const T* a,
const IndexType b_idx,
size_t size,
500 DistanceType worst_dist = -1)
const
502 DistanceType result = DistanceType();
503 const T* last = a + size;
504 const T* lastgroup = last - 3;
508 while (a < lastgroup)
510 const DistanceType diff0 =
511 std::abs(a[0] - data_source.kdtree_get_pt(b_idx, d++));
512 const DistanceType diff1 =
513 std::abs(a[1] - data_source.kdtree_get_pt(b_idx, d++));
514 const DistanceType diff2 =
515 std::abs(a[2] - data_source.kdtree_get_pt(b_idx, d++));
516 const DistanceType diff3 =
517 std::abs(a[3] - data_source.kdtree_get_pt(b_idx, d++));
518 result += diff0 + diff1 + diff2 + diff3;
520 if ((worst_dist > 0) && (result > worst_dist)) {
return result; }
526 result += std::abs(*a++ - data_source.kdtree_get_pt(b_idx, d++));
531 template <
typename U,
typename V>
532 DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
534 return std::abs(a - b);
549 class T,
class DataSource,
typename _DistanceType = T,
550 typename IndexType = uint32_t>
553 using ElementType = T;
554 using DistanceType = _DistanceType;
556 const DataSource& data_source;
558 L2_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
560 DistanceType evalMetric(
561 const T* a,
const IndexType b_idx,
size_t size,
562 DistanceType worst_dist = -1)
const
564 DistanceType result = DistanceType();
565 const T* last = a + size;
566 const T* lastgroup = last - 3;
570 while (a < lastgroup)
572 const DistanceType diff0 =
573 a[0] - data_source.kdtree_get_pt(b_idx, d++);
574 const DistanceType diff1 =
575 a[1] - data_source.kdtree_get_pt(b_idx, d++);
576 const DistanceType diff2 =
577 a[2] - data_source.kdtree_get_pt(b_idx, d++);
578 const DistanceType diff3 =
579 a[3] - data_source.kdtree_get_pt(b_idx, d++);
581 diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
583 if ((worst_dist > 0) && (result > worst_dist)) {
return result; }
589 const DistanceType diff0 =
590 *a++ - data_source.kdtree_get_pt(b_idx, d++);
591 result += diff0 * diff0;
596 template <
typename U,
typename V>
597 DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
599 return (a - b) * (a - b);
614 class T,
class DataSource,
typename _DistanceType = T,
615 typename IndexType = uint32_t>
618 using ElementType = T;
619 using DistanceType = _DistanceType;
621 const DataSource& data_source;
624 : data_source(_data_source)
628 DistanceType evalMetric(
629 const T* a,
const IndexType b_idx,
size_t size)
const
631 DistanceType result = DistanceType();
632 for (
size_t i = 0; i < size; ++i)
634 const DistanceType diff =
635 a[i] - data_source.kdtree_get_pt(b_idx, i);
636 result += diff * diff;
641 template <
typename U,
typename V>
642 DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
644 return (a - b) * (a - b);
659 class T,
class DataSource,
typename _DistanceType = T,
660 typename IndexType = uint32_t>
663 using ElementType = T;
664 using DistanceType = _DistanceType;
666 const DataSource& data_source;
668 SO2_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
670 DistanceType evalMetric(
671 const T* a,
const IndexType b_idx,
size_t size)
const
674 a[size - 1], data_source.kdtree_get_pt(b_idx, size - 1), size - 1);
679 template <
typename U,
typename V>
680 DistanceType
accum_dist(
const U a,
const V b,
const size_t)
const
682 DistanceType result = DistanceType();
683 DistanceType PI = pi_const<DistanceType>();
687 else if (result < -PI)
704 class T,
class DataSource,
typename _DistanceType = T,
705 typename IndexType = uint32_t>
708 using ElementType = T;
709 using DistanceType = _DistanceType;
715 : distance_L2_Simple(_data_source)
719 DistanceType evalMetric(
720 const T* a,
const IndexType b_idx,
size_t size)
const
722 return distance_L2_Simple.evalMetric(a, b_idx, size);
725 template <
typename U,
typename V>
726 DistanceType accum_dist(
const U a,
const V b,
const size_t idx)
const
728 return distance_L2_Simple.accum_dist(a, b, idx);
735 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
745 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
755 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
764 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
773 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
785enum class KDTreeSingleIndexAdaptorFlags
788 SkipInitialBuildIndex = 1
791inline std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type operator&(
792 KDTreeSingleIndexAdaptorFlags lhs, KDTreeSingleIndexAdaptorFlags rhs)
795 typename std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type;
796 return static_cast<underlying
>(lhs) &
static_cast<underlying
>(rhs);
803 size_t _leaf_max_size = 10,
804 KDTreeSingleIndexAdaptorFlags _flags =
805 KDTreeSingleIndexAdaptorFlags::None,
806 unsigned int _n_thread_build = 1)
807 : leaf_max_size(_leaf_max_size),
809 n_thread_build(_n_thread_build)
813 size_t leaf_max_size;
814 KDTreeSingleIndexAdaptorFlags flags;
815 unsigned int n_thread_build;
822 : eps(eps_), sorted(sorted_)
851 static constexpr size_t WORDSIZE = 16;
852 static constexpr size_t BLOCKSIZE = 8192;
863 void* base_ =
nullptr;
864 void* loc_ =
nullptr;
876 Size wastedMemory = 0;
891 while (base_ !=
nullptr)
894 void* prev = *(
static_cast<void**
>(base_));
911 const Size size = (req_size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
916 if (size > remaining_)
918 wastedMemory += remaining_;
921 const Size blocksize =
922 size > BLOCKSIZE ? size + WORDSIZE : BLOCKSIZE + WORDSIZE;
925 void* m = ::malloc(blocksize);
928 fprintf(stderr,
"Failed to allocate memory.\n");
929 throw std::bad_alloc();
933 static_cast<void**
>(m)[0] = base_;
936 remaining_ = blocksize - WORDSIZE;
937 loc_ =
static_cast<char*
>(m) + WORDSIZE;
940 loc_ =
static_cast<char*
>(loc_) + size;
955 template <
typename T>
958 T* mem =
static_cast<T*
>(this->malloc(
sizeof(T) * count));
970template <
int32_t DIM,
typename T>
973 using type = std::array<T, DIM>;
979 using type = std::vector<T>;
999 class Derived,
typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
1000 typename index_t = uint32_t>
1008 obj.pool_.free_all();
1009 obj.root_node_ =
nullptr;
1010 obj.size_at_index_build_ = 0;
1013 using ElementType =
typename Distance::ElementType;
1014 using DistanceType =
typename Distance::DistanceType;
1015 using IndexType = index_t;
1022 using Offset =
typename decltype(vAcc_)::size_type;
1023 using Size =
typename decltype(vAcc_)::size_type;
1024 using Dimension = int32_t;
1048 Node *child1 =
nullptr, *child2 =
nullptr;
1056 ElementType low, high;
1061 Size leaf_max_size_ = 0;
1064 Size n_thread_build_ = 1;
1068 Size size_at_index_build_ = 0;
1092 Size
size(
const Derived& obj)
const {
return obj.size_; }
1095 Size
veclen(
const Derived& obj) {
return DIM > 0 ? DIM : obj.dim; }
1099 const Derived& obj, IndexType element, Dimension component)
const
1101 return obj.dataset_.kdtree_get_pt(element, component);
1110 return obj.pool_.usedMemory + obj.pool_.wastedMemory +
1111 obj.dataset_.kdtree_get_point_count() *
1116 const Derived& obj, Offset ind, Size count, Dimension element,
1117 ElementType& min_elem, ElementType& max_elem)
1119 min_elem = dataset_get(obj, vAcc_[ind], element);
1120 max_elem = min_elem;
1121 for (Offset i = 1; i < count; ++i)
1123 ElementType val = dataset_get(obj, vAcc_[ind + i], element);
1124 if (val < min_elem) min_elem = val;
1125 if (val > max_elem) max_elem = val;
1137 Derived& obj,
const Offset left,
const Offset right,
BoundingBox& bbox)
1139 NodePtr node = obj.pool_.template allocate<Node>();
1140 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1143 if ((right - left) <=
static_cast<Offset
>(obj.leaf_max_size_))
1145 node->
child1 = node->child2 =
nullptr;
1150 for (Dimension i = 0; i < dims; ++i)
1152 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1153 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1155 for (Offset k = left + 1; k < right; ++k)
1157 for (Dimension i = 0; i < dims; ++i)
1159 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1160 if (bbox[i].low > val) bbox[i].low = val;
1161 if (bbox[i].high < val) bbox[i].high = val;
1169 DistanceType cutval;
1170 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1175 left_bbox[cutfeat].high = cutval;
1176 node->
child1 = this->divideTree(obj, left, left + idx, left_bbox);
1179 right_bbox[cutfeat].low = cutval;
1180 node->child2 = this->divideTree(obj, left + idx, right, right_bbox);
1182 node->
node_type.sub.divlow = left_bbox[cutfeat].high;
1183 node->
node_type.sub.divhigh = right_bbox[cutfeat].low;
1185 for (Dimension i = 0; i < dims; ++i)
1187 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1188 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1206 Derived& obj,
const Offset left,
const Offset right,
BoundingBox& bbox,
1207 std::atomic<unsigned int>& thread_count, std::mutex& mutex)
1209 std::unique_lock<std::mutex> lock(mutex);
1210 NodePtr node = obj.pool_.template allocate<Node>();
1213 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1216 if ((right - left) <=
static_cast<Offset
>(obj.leaf_max_size_))
1218 node->
child1 = node->child2 =
nullptr;
1223 for (Dimension i = 0; i < dims; ++i)
1225 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1226 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1228 for (Offset k = left + 1; k < right; ++k)
1230 for (Dimension i = 0; i < dims; ++i)
1232 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1233 if (bbox[i].low > val) bbox[i].low = val;
1234 if (bbox[i].high < val) bbox[i].high = val;
1242 DistanceType cutval;
1243 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1247 std::future<NodePtr> right_future;
1250 right_bbox[cutfeat].low = cutval;
1251 if (++thread_count < n_thread_build_)
1254 right_future = std::async(
1255 std::launch::async, &KDTreeBaseClass::divideTreeConcurrent,
1256 this, std::ref(obj), left + idx, right,
1257 std::ref(right_bbox), std::ref(thread_count),
1260 else { --thread_count; }
1263 left_bbox[cutfeat].high = cutval;
1264 node->
child1 = this->divideTreeConcurrent(
1265 obj, left, left + idx, left_bbox, thread_count, mutex);
1267 if (right_future.valid())
1270 node->child2 = right_future.get();
1275 node->child2 = this->divideTreeConcurrent(
1276 obj, left + idx, right, right_bbox, thread_count, mutex);
1279 node->
node_type.sub.divlow = left_bbox[cutfeat].high;
1280 node->
node_type.sub.divhigh = right_bbox[cutfeat].low;
1282 for (Dimension i = 0; i < dims; ++i)
1284 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1285 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1293 const Derived& obj,
const Offset ind,
const Size count, Offset& index,
1294 Dimension& cutfeat, DistanceType& cutval,
const BoundingBox& bbox)
1296 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1297 const auto EPS =
static_cast<DistanceType
>(0.00001);
1298 ElementType max_span = bbox[0].high - bbox[0].low;
1299 for (Dimension i = 1; i < dims; ++i)
1301 ElementType span = bbox[i].high - bbox[i].low;
1302 if (span > max_span) { max_span = span; }
1304 ElementType max_spread = -1;
1306 ElementType min_elem = 0, max_elem = 0;
1307 for (Dimension i = 0; i < dims; ++i)
1309 ElementType span = bbox[i].high - bbox[i].low;
1310 if (span > (1 - EPS) * max_span)
1312 ElementType min_elem_, max_elem_;
1313 computeMinMax(obj, ind, count, i, min_elem_, max_elem_);
1314 ElementType spread = max_elem_ - min_elem_;
1315 if (spread > max_spread)
1318 max_spread = spread;
1319 min_elem = min_elem_;
1320 max_elem = max_elem_;
1325 DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;
1327 if (split_val < min_elem)
1329 else if (split_val > max_elem)
1335 planeSplit(obj, ind, count, cutfeat, cutval, lim1, lim2);
1337 if (lim1 > count / 2)
1339 else if (lim2 < count / 2)
1355 const Derived& obj,
const Offset ind,
const Size count,
1356 const Dimension cutfeat,
const DistanceType& cutval, Offset& lim1,
1361 Offset right = count - 1;
1364 while (left <= right &&
1365 dataset_get(obj, vAcc_[ind + left], cutfeat) < cutval)
1367 while (right && left <= right &&
1368 dataset_get(obj, vAcc_[ind + right], cutfeat) >= cutval)
1370 if (left > right || !right)
1372 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1383 while (left <= right &&
1384 dataset_get(obj, vAcc_[ind + left], cutfeat) <= cutval)
1386 while (right && left <= right &&
1387 dataset_get(obj, vAcc_[ind + right], cutfeat) > cutval)
1389 if (left > right || !right)
1391 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1398 DistanceType computeInitialDistances(
1399 const Derived& obj,
const ElementType* vec,
1400 distance_vector_t& dists)
const
1403 DistanceType dist = DistanceType();
1405 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim_); ++i)
1407 if (vec[i] < obj.root_bbox_[i].low)
1410 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].low, i);
1413 if (vec[i] > obj.root_bbox_[i].high)
1416 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].high, i);
1423 static void save_tree(
1424 const Derived& obj, std::ostream& stream,
const NodeConstPtr tree)
1426 save_value(stream, *tree);
1427 if (tree->child1 !=
nullptr) { save_tree(obj, stream, tree->child1); }
1428 if (tree->child2 !=
nullptr) { save_tree(obj, stream, tree->child2); }
1431 static void load_tree(Derived& obj, std::istream& stream, NodePtr& tree)
1433 tree = obj.pool_.template allocate<Node>();
1434 load_value(stream, *tree);
1435 if (tree->child1 !=
nullptr) { load_tree(obj, stream, tree->child1); }
1436 if (tree->child2 !=
nullptr) { load_tree(obj, stream, tree->child2); }
1444 void saveIndex(
const Derived& obj, std::ostream& stream)
const
1446 save_value(stream, obj.size_);
1447 save_value(stream, obj.dim_);
1448 save_value(stream, obj.root_bbox_);
1449 save_value(stream, obj.leaf_max_size_);
1450 save_value(stream, obj.vAcc_);
1451 if (obj.root_node_) save_tree(obj, stream, obj.root_node_);
1461 load_value(stream, obj.size_);
1462 load_value(stream, obj.dim_);
1463 load_value(stream, obj.root_bbox_);
1464 load_value(stream, obj.leaf_max_size_);
1465 load_value(stream, obj.vAcc_);
1466 load_tree(obj, stream, obj.root_node_);
1512 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
1513 typename index_t = uint32_t>
1516 KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, index_t>,
1517 Distance, DatasetAdaptor, DIM, index_t>
1523 Distance, DatasetAdaptor, DIM, index_t>&) =
delete;
1534 Distance, DatasetAdaptor, DIM, index_t>,
1535 Distance, DatasetAdaptor, DIM, index_t>;
1537 using Offset =
typename Base::Offset;
1538 using Size =
typename Base::Size;
1539 using Dimension =
typename Base::Dimension;
1541 using ElementType =
typename Base::ElementType;
1542 using DistanceType =
typename Base::DistanceType;
1543 using IndexType =
typename Base::IndexType;
1545 using Node =
typename Base::Node;
1546 using NodePtr = Node*;
1548 using Interval =
typename Base::Interval;
1578 template <
class... Args>
1580 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1582 : dataset_(inputData),
1583 indexParams(params),
1584 distance_(inputData, std::forward<Args>(args)...)
1586 init(dimensionality, params);
1590 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1592 : dataset_(inputData), indexParams(params), distance_(inputData)
1594 init(dimensionality, params);
1599 const Dimension dimensionality,
1600 const KDTreeSingleIndexAdaptorParams& params)
1602 Base::size_ = dataset_.kdtree_get_point_count();
1603 Base::size_at_index_build_ = Base::size_;
1604 Base::dim_ = dimensionality;
1605 if (DIM > 0) Base::dim_ = DIM;
1606 Base::leaf_max_size_ = params.leaf_max_size;
1607 if (params.n_thread_build > 0)
1609 Base::n_thread_build_ = params.n_thread_build;
1613 Base::n_thread_build_ =
1614 std::max(std::thread::hardware_concurrency(), 1u);
1617 if (!(params.flags &
1618 KDTreeSingleIndexAdaptorFlags::SkipInitialBuildIndex))
1631 Base::size_ = dataset_.kdtree_get_point_count();
1632 Base::size_at_index_build_ = Base::size_;
1634 this->freeIndex(*
this);
1635 Base::size_at_index_build_ = Base::size_;
1636 if (Base::size_ == 0)
return;
1637 computeBoundingBox(Base::root_bbox_);
1639 if (Base::n_thread_build_ == 1)
1642 this->divideTree(*
this, 0, Base::size_, Base::root_bbox_);
1646#ifndef NANOFLANN_NO_THREADS
1647 std::atomic<unsigned int> thread_count(0u);
1649 Base::root_node_ = this->divideTreeConcurrent(
1650 *
this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
1652 throw std::runtime_error(
"Multithreading is disabled");
1676 template <
typename RESULTSET>
1678 RESULTSET& result,
const ElementType* vec,
1682 if (this->size(*
this) == 0)
return false;
1683 if (!Base::root_node_)
1684 throw std::runtime_error(
1685 "[nanoflann] findNeighbors() called before building the "
1687 float epsError = 1 + searchParams.eps;
1690 distance_vector_t dists;
1692 auto zero =
static_cast<decltype(result.worstDist())
>(0);
1693 assign(dists, (DIM > 0 ? DIM : Base::dim_), zero);
1694 DistanceType dist = this->computeInitialDistances(*
this, vec, dists);
1695 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
1697 if (searchParams.sorted) result.sort();
1699 return result.full();
1718 const ElementType* query_point,
const Size num_closest,
1719 IndexType* out_indices, DistanceType* out_distances)
const
1722 resultSet.init(out_indices, out_distances);
1723 findNeighbors(resultSet, query_point);
1724 return resultSet.size();
1747 const ElementType* query_point,
const DistanceType& radius,
1752 radius, IndicesDists);
1754 radiusSearchCustomCallback(query_point, resultSet, searchParams);
1763 template <
class SEARCH_CALLBACK>
1765 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
1768 findNeighbors(resultSet, query_point, searchParams);
1769 return resultSet.size();
1789 const ElementType* query_point,
const Size num_closest,
1790 IndexType* out_indices, DistanceType* out_distances,
1791 const DistanceType& radius)
const
1794 num_closest, radius);
1795 resultSet.init(out_indices, out_distances);
1796 findNeighbors(resultSet, query_point);
1797 return resultSet.size();
1808 Base::size_ = dataset_.kdtree_get_point_count();
1809 if (Base::vAcc_.size() != Base::size_) Base::vAcc_.resize(Base::size_);
1810 for (Size i = 0; i < Base::size_; i++) Base::vAcc_[i] = i;
1813 void computeBoundingBox(BoundingBox& bbox)
1815 const auto dims = (DIM > 0 ? DIM : Base::dim_);
1817 if (dataset_.kdtree_get_bbox(bbox))
1823 const Size N = dataset_.kdtree_get_point_count();
1825 throw std::runtime_error(
1826 "[nanoflann] computeBoundingBox() called but "
1827 "no data points found.");
1828 for (Dimension i = 0; i < dims; ++i)
1830 bbox[i].low = bbox[i].high =
1831 this->dataset_get(*
this, Base::vAcc_[0], i);
1833 for (Offset k = 1; k < N; ++k)
1835 for (Dimension i = 0; i < dims; ++i)
1838 this->dataset_get(*
this, Base::vAcc_[k], i);
1839 if (val < bbox[i].low) bbox[i].low = val;
1840 if (val > bbox[i].high) bbox[i].high = val;
1852 template <
class RESULTSET>
1854 RESULTSET& result_set,
const ElementType* vec,
const NodePtr node,
1856 const float epsError)
const
1859 if ((node->child1 ==
nullptr) && (node->child2 ==
nullptr))
1861 DistanceType worst_dist = result_set.worstDist();
1862 for (Offset i = node->node_type.lr.left;
1863 i < node->node_type.lr.right; ++i)
1865 const IndexType accessor = Base::vAcc_[i];
1866 DistanceType dist = distance_.evalMetric(
1867 vec, accessor, (DIM > 0 ? DIM : Base::dim_));
1868 if (dist < worst_dist)
1870 if (!result_set.addPoint(dist, Base::vAcc_[i]))
1882 Dimension idx = node->node_type.sub.divfeat;
1883 ElementType val = vec[idx];
1884 DistanceType diff1 = val - node->node_type.sub.divlow;
1885 DistanceType diff2 = val - node->node_type.sub.divhigh;
1889 DistanceType cut_dist;
1890 if ((diff1 + diff2) < 0)
1892 bestChild = node->child1;
1893 otherChild = node->child2;
1895 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
1899 bestChild = node->child2;
1900 otherChild = node->child1;
1902 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
1906 if (!searchLevel(result_set, vec, bestChild, mindist, dists, epsError))
1913 DistanceType dst = dists[idx];
1914 mindist = mindist + cut_dist - dst;
1915 dists[idx] = cut_dist;
1916 if (mindist * epsError <= result_set.worstDist())
1919 result_set, vec, otherChild, mindist, dists, epsError))
1938 Base::saveIndex(*
this, stream);
1946 void loadIndex(std::istream& stream) { Base::loadIndex(*
this, stream); }
1988 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
1989 typename IndexType = uint32_t>
1992 KDTreeSingleIndexDynamicAdaptor_<
1993 Distance, DatasetAdaptor, DIM, IndexType>,
1994 Distance, DatasetAdaptor, DIM, IndexType>
2004 std::vector<int>& treeIndex_;
2010 Distance, DatasetAdaptor, DIM, IndexType>,
2011 Distance, DatasetAdaptor, DIM, IndexType>;
2013 using ElementType =
typename Base::ElementType;
2014 using DistanceType =
typename Base::DistanceType;
2016 using Offset =
typename Base::Offset;
2017 using Size =
typename Base::Size;
2018 using Dimension =
typename Base::Dimension;
2020 using Node =
typename Base::Node;
2021 using NodePtr = Node*;
2023 using Interval =
typename Base::Interval;
2048 const Dimension dimensionality,
const DatasetAdaptor& inputData,
2049 std::vector<int>& treeIndex,
2052 : dataset_(inputData),
2053 index_params_(params),
2054 treeIndex_(treeIndex),
2055 distance_(inputData)
2058 Base::size_at_index_build_ = 0;
2059 for (
auto& v : Base::root_bbox_) v = {};
2060 Base::dim_ = dimensionality;
2061 if (DIM > 0) Base::dim_ = DIM;
2062 Base::leaf_max_size_ = params.leaf_max_size;
2063 if (params.n_thread_build > 0)
2065 Base::n_thread_build_ = params.n_thread_build;
2069 Base::n_thread_build_ =
2070 std::max(std::thread::hardware_concurrency(), 1u);
2083 std::swap(Base::vAcc_, tmp.Base::vAcc_);
2084 std::swap(Base::leaf_max_size_, tmp.Base::leaf_max_size_);
2085 std::swap(index_params_, tmp.index_params_);
2086 std::swap(treeIndex_, tmp.treeIndex_);
2087 std::swap(Base::size_, tmp.Base::size_);
2088 std::swap(Base::size_at_index_build_, tmp.Base::size_at_index_build_);
2089 std::swap(Base::root_node_, tmp.Base::root_node_);
2090 std::swap(Base::root_bbox_, tmp.Base::root_bbox_);
2091 std::swap(Base::pool_, tmp.Base::pool_);
2100 Base::size_ = Base::vAcc_.size();
2101 this->freeIndex(*
this);
2102 Base::size_at_index_build_ = Base::size_;
2103 if (Base::size_ == 0)
return;
2104 computeBoundingBox(Base::root_bbox_);
2106 if (Base::n_thread_build_ == 1)
2109 this->divideTree(*
this, 0, Base::size_, Base::root_bbox_);
2113#ifndef NANOFLANN_NO_THREADS
2114 std::atomic<unsigned int> thread_count(0u);
2116 Base::root_node_ = this->divideTreeConcurrent(
2117 *
this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
2119 throw std::runtime_error(
"Multithreading is disabled");
2147 template <
typename RESULTSET>
2149 RESULTSET& result,
const ElementType* vec,
2153 if (this->size(*
this) == 0)
return false;
2154 if (!Base::root_node_)
return false;
2155 float epsError = 1 + searchParams.eps;
2158 distance_vector_t dists;
2161 dists, (DIM > 0 ? DIM : Base::dim_),
2162 static_cast<typename distance_vector_t::value_type>(0));
2163 DistanceType dist = this->computeInitialDistances(*
this, vec, dists);
2164 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
2165 return result.full();
2183 const ElementType* query_point,
const Size num_closest,
2184 IndexType* out_indices, DistanceType* out_distances,
2188 resultSet.init(out_indices, out_distances);
2189 findNeighbors(resultSet, query_point, searchParams);
2190 return resultSet.size();
2213 const ElementType* query_point,
const DistanceType& radius,
2218 radius, IndicesDists);
2219 const size_t nFound =
2220 radiusSearchCustomCallback(query_point, resultSet, searchParams);
2229 template <
class SEARCH_CALLBACK>
2231 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
2234 findNeighbors(resultSet, query_point, searchParams);
2235 return resultSet.size();
2241 void computeBoundingBox(BoundingBox& bbox)
2243 const auto dims = (DIM > 0 ? DIM : Base::dim_);
2246 if (dataset_.kdtree_get_bbox(bbox))
2252 const Size N = Base::size_;
2254 throw std::runtime_error(
2255 "[nanoflann] computeBoundingBox() called but "
2256 "no data points found.");
2257 for (Dimension i = 0; i < dims; ++i)
2259 bbox[i].low = bbox[i].high =
2260 this->dataset_get(*
this, Base::vAcc_[0], i);
2262 for (Offset k = 1; k < N; ++k)
2264 for (Dimension i = 0; i < dims; ++i)
2267 this->dataset_get(*
this, Base::vAcc_[k], i);
2268 if (val < bbox[i].low) bbox[i].low = val;
2269 if (val > bbox[i].high) bbox[i].high = val;
2279 template <
class RESULTSET>
2281 RESULTSET& result_set,
const ElementType* vec,
const NodePtr node,
2283 const float epsError)
const
2286 if ((node->child1 ==
nullptr) && (node->child2 ==
nullptr))
2288 DistanceType worst_dist = result_set.worstDist();
2289 for (Offset i = node->node_type.lr.left;
2290 i < node->node_type.lr.right; ++i)
2292 const IndexType index = Base::vAcc_[i];
2293 if (treeIndex_[index] == -1)
continue;
2294 DistanceType dist = distance_.evalMetric(
2295 vec, index, (DIM > 0 ? DIM : Base::dim_));
2296 if (dist < worst_dist)
2298 if (!result_set.addPoint(
2299 static_cast<typename RESULTSET::DistanceType
>(dist),
2300 static_cast<typename RESULTSET::IndexType
>(
2313 Dimension idx = node->node_type.sub.divfeat;
2314 ElementType val = vec[idx];
2315 DistanceType diff1 = val - node->node_type.sub.divlow;
2316 DistanceType diff2 = val - node->node_type.sub.divhigh;
2320 DistanceType cut_dist;
2321 if ((diff1 + diff2) < 0)
2323 bestChild = node->child1;
2324 otherChild = node->child2;
2326 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
2330 bestChild = node->child2;
2331 otherChild = node->child1;
2333 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
2337 searchLevel(result_set, vec, bestChild, mindist, dists, epsError);
2339 DistanceType dst = dists[idx];
2340 mindist = mindist + cut_dist - dst;
2341 dists[idx] = cut_dist;
2342 if (mindist * epsError <= result_set.worstDist())
2344 searchLevel(result_set, vec, otherChild, mindist, dists, epsError);
2380 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
2381 typename IndexType = uint32_t>
2385 using ElementType =
typename Distance::ElementType;
2386 using DistanceType =
typename Distance::DistanceType;
2389 Distance, DatasetAdaptor, DIM>::Offset;
2391 Distance, DatasetAdaptor, DIM>::Size;
2393 Distance, DatasetAdaptor, DIM>::Dimension;
2396 Size leaf_max_size_;
2408 std::unordered_set<int> removedPoints_;
2415 Distance, DatasetAdaptor, DIM, IndexType>;
2416 std::vector<index_container_t> index_;
2428 int First0Bit(IndexType num)
2442 using my_kd_tree_t = KDTreeSingleIndexDynamicAdaptor_<
2443 Distance, DatasetAdaptor, DIM, IndexType>;
2444 std::vector<my_kd_tree_t> index(
2446 my_kd_tree_t(dim_ , dataset_, treeIndex_, index_params_));
2469 const int dimensionality,
const DatasetAdaptor& inputData,
2472 const size_t maximumPointCount = 1000000000U)
2473 : dataset_(inputData), index_params_(params), distance_(inputData)
2475 treeCount_ =
static_cast<size_t>(std::log2(maximumPointCount)) + 1;
2477 dim_ = dimensionality;
2479 if (DIM > 0) dim_ = DIM;
2480 leaf_max_size_ = params.leaf_max_size;
2482 const size_t num_initial_points = dataset_.kdtree_get_point_count();
2483 if (num_initial_points > 0) { addPoints(0, num_initial_points - 1); }
2489 Distance, DatasetAdaptor, DIM, IndexType>&) =
delete;
2494 const Size count = end - start + 1;
2496 treeIndex_.resize(treeIndex_.size() + count);
2497 for (IndexType idx = start; idx <= end; idx++)
2499 const int pos = First0Bit(pointCount_);
2500 maxIndex = std::max(pos, maxIndex);
2501 treeIndex_[pointCount_] = pos;
2503 const auto it = removedPoints_.find(idx);
2504 if (it != removedPoints_.end())
2506 removedPoints_.erase(it);
2507 treeIndex_[idx] = pos;
2510 for (
int i = 0; i < pos; i++)
2512 for (
int j = 0; j < static_cast<int>(index_[i].vAcc_.size());
2515 index_[pos].vAcc_.push_back(index_[i].vAcc_[j]);
2516 if (treeIndex_[index_[i].vAcc_[j]] != -1)
2517 treeIndex_[index_[i].vAcc_[j]] = pos;
2519 index_[i].vAcc_.clear();
2521 index_[pos].vAcc_.push_back(idx);
2525 for (
int i = 0; i <= maxIndex; ++i)
2527 index_[i].freeIndex(index_[i]);
2528 if (!index_[i].vAcc_.empty()) index_[i].buildIndex();
2535 if (idx >= pointCount_)
return;
2536 removedPoints_.insert(idx);
2537 treeIndex_[idx] = -1;
2556 template <
typename RESULTSET>
2558 RESULTSET& result,
const ElementType* vec,
2561 for (
size_t i = 0; i < treeCount_; i++)
2563 index_[i].findNeighbors(result, &vec[0], searchParams);
2565 return result.full();
2596 bool row_major =
true>
2601 using num_t =
typename MatrixType::Scalar;
2602 using IndexType =
typename MatrixType::Index;
2603 using metric_t =
typename Distance::template traits<
2604 num_t,
self_t, IndexType>::distance_t;
2608 row_major ? MatrixType::ColsAtCompileTime
2609 : MatrixType::RowsAtCompileTime,
2616 using Size =
typename index_t::Size;
2617 using Dimension =
typename index_t::Dimension;
2621 const Dimension dimensionality,
2622 const std::reference_wrapper<const MatrixType>& mat,
2623 const int leaf_max_size = 10)
2624 : m_data_matrix(mat)
2626 const auto dims = row_major ? mat.get().cols() : mat.get().rows();
2627 if (
static_cast<Dimension
>(dims) != dimensionality)
2628 throw std::runtime_error(
2629 "Error: 'dimensionality' must match column count in data "
2631 if (DIM > 0 &&
static_cast<int32_t
>(dims) != DIM)
2632 throw std::runtime_error(
2633 "Data set dimensionality does not match the 'DIM' template "
2646 const std::reference_wrapper<const MatrixType> m_data_matrix;
2657 const num_t* query_point,
const Size num_closest,
2658 IndexType* out_indices, num_t* out_distances)
const
2661 resultSet.init(out_indices, out_distances);
2668 const self_t& derived()
const {
return *
this; }
2669 self_t& derived() {
return *
this; }
2672 Size kdtree_get_point_count()
const
2675 return m_data_matrix.get().rows();
2677 return m_data_matrix.get().cols();
2681 num_t kdtree_get_pt(
const IndexType idx,
size_t dim)
const
2684 return m_data_matrix.get().coeff(idx, IndexType(dim));
2686 return m_data_matrix.get().coeff(IndexType(dim), idx);
2694 template <
class BBOX>
2695 bool kdtree_get_bbox(BBOX& )
const
// end of grouping
Definition nanoflann.hpp:1002
void freeIndex(Derived &obj)
Definition nanoflann.hpp:1006
BoundingBox root_bbox_
Definition nanoflann.hpp:1080
Size veclen(const Derived &obj)
Definition nanoflann.hpp:1095
void saveIndex(const Derived &obj, std::ostream &stream) const
Definition nanoflann.hpp:1444
Size usedMemory(Derived &obj)
Definition nanoflann.hpp:1108
typename array_or_vector< DIM, DistanceType >::type distance_vector_t
Definition nanoflann.hpp:1077
void planeSplit(const Derived &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)
Definition nanoflann.hpp:1354
NodePtr divideTree(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox)
Definition nanoflann.hpp:1136
std::vector< IndexType > vAcc_
Definition nanoflann.hpp:1020
Size size(const Derived &obj) const
Definition nanoflann.hpp:1092
NodePtr divideTreeConcurrent(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex)
Definition nanoflann.hpp:1205
void loadIndex(Derived &obj, std::istream &stream)
Definition nanoflann.hpp:1459
PooledAllocator pool_
Definition nanoflann.hpp:1089
ElementType dataset_get(const Derived &obj, IndexType element, Dimension component) const
Helper accessor to the dataset points:
Definition nanoflann.hpp:1098
typename array_or_vector< DIM, Interval >::type BoundingBox
Definition nanoflann.hpp:1073
Definition nanoflann.hpp:1518
bool searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:1853
void saveIndex(std::ostream &stream) const
Definition nanoflann.hpp:1936
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1746
void init_vind()
Definition nanoflann.hpp:1805
void buildIndex()
Definition nanoflann.hpp:1629
const DatasetAdaptor & dataset_
Definition nanoflann.hpp:1526
KDTreeSingleIndexAdaptor(const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t > &)=delete
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1677
Size rknnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const
Definition nanoflann.hpp:1788
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1764
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:1556
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:1946
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:1552
KDTreeSingleIndexAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms, Args &&... args)
Definition nanoflann.hpp:1579
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances) const
Definition nanoflann.hpp:1717
Definition nanoflann.hpp:1995
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2212
KDTreeSingleIndexDynamicAdaptor_(const Dimension dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams())
Definition nanoflann.hpp:2047
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:2026
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:2000
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2230
KDTreeSingleIndexDynamicAdaptor_(const KDTreeSingleIndexDynamicAdaptor_ &rhs)=default
void buildIndex()
Definition nanoflann.hpp:2098
void saveIndex(std::ostream &stream)
Definition nanoflann.hpp:2355
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:2030
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:2362
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2182
void searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:2280
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2148
KDTreeSingleIndexDynamicAdaptor_ operator=(const KDTreeSingleIndexDynamicAdaptor_ &rhs)
Definition nanoflann.hpp:2079
Definition nanoflann.hpp:2383
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2557
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:2403
void removePoint(size_t idx)
Definition nanoflann.hpp:2533
void addPoints(IndexType start, IndexType end)
Definition nanoflann.hpp:2492
KDTreeSingleIndexDynamicAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams(), const size_t maximumPointCount=1000000000U)
Definition nanoflann.hpp:2468
std::vector< int > treeIndex_
Definition nanoflann.hpp:2407
const std::vector< index_container_t > & getAllIndices() const
Definition nanoflann.hpp:2421
Dimension dim_
Dimensionality of each data point.
Definition nanoflann.hpp:2412
KDTreeSingleIndexDynamicAdaptor(const KDTreeSingleIndexDynamicAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete
Definition nanoflann.hpp:201
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:237
Definition nanoflann.hpp:850
~PooledAllocator()
Definition nanoflann.hpp:886
void free_all()
Definition nanoflann.hpp:889
void * malloc(const size_t req_size)
Definition nanoflann.hpp:905
T * allocate(const size_t count=1)
Definition nanoflann.hpp:956
PooledAllocator()
Definition nanoflann.hpp:881
Definition nanoflann.hpp:285
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:326
Definition nanoflann.hpp:374
ResultItem< IndexType, DistanceType > worst_item() const
Definition nanoflann.hpp:417
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:405
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:163
bool operator()(const PairType &p1, const PairType &p2) const
Definition nanoflann.hpp:166
Definition nanoflann.hpp:1055
Definition nanoflann.hpp:1030
DistanceType divlow
The values used for subdivision.
Definition nanoflann.hpp:1043
Offset right
Indices of points in leaf node.
Definition nanoflann.hpp:1037
union nanoflann::KDTreeBaseClass::Node::@0 node_type
Dimension divfeat
Definition nanoflann.hpp:1041
Node * child1
Definition nanoflann.hpp:1048
Definition nanoflann.hpp:2598
void query(const num_t *query_point, const Size num_closest, IndexType *out_indices, num_t *out_distances) const
Definition nanoflann.hpp:2656
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:2620
KDTreeEigenMatrixAdaptor(const self_t &)=delete
typename index_t::Offset Offset
Definition nanoflann.hpp:2615
Definition nanoflann.hpp:801
Definition nanoflann.hpp:490
Definition nanoflann.hpp:552
Definition nanoflann.hpp:617
Definition nanoflann.hpp:473
Definition nanoflann.hpp:182
DistanceType second
Distance from sample to query point.
Definition nanoflann.hpp:190
IndexType first
Index of the sample in the dataset.
Definition nanoflann.hpp:189
Definition nanoflann.hpp:662
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition nanoflann.hpp:680
Definition nanoflann.hpp:707
Definition nanoflann.hpp:820
bool sorted
distance (default: true)
Definition nanoflann.hpp:827
float eps
search for eps-approximate neighbours (default: 0)
Definition nanoflann.hpp:826
Definition nanoflann.hpp:972
Definition nanoflann.hpp:109
Definition nanoflann.hpp:98
Definition nanoflann.hpp:737
Definition nanoflann.hpp:734
Definition nanoflann.hpp:747
Definition nanoflann.hpp:757
Definition nanoflann.hpp:754
Definition nanoflann.hpp:744
Definition nanoflann.hpp:766
Definition nanoflann.hpp:763
Definition nanoflann.hpp:775
Definition nanoflann.hpp:772