60#include <unordered_set>
64#define NANOFLANN_VERSION 0x154
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 typename _DistanceType,
typename _IndexType = size_t,
166 typename _CountType =
size_t>
170 using DistanceType = _DistanceType;
171 using IndexType = _IndexType;
172 using CountType = _CountType;
182 : indices(
nullptr), dists(
nullptr), capacity(capacity_), count(0)
186 void init(IndexType* indices_, DistanceType* dists_)
192 dists[capacity - 1] = (std::numeric_limits<DistanceType>::max)();
195 CountType size()
const {
return count; }
196 bool empty()
const {
return count == 0; }
197 bool full()
const {
return count == capacity; }
207 for (i = count; i > 0; --i)
211#ifdef NANOFLANN_FIRST_MATCH
212 if ((dists[i - 1] > dist) ||
213 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
216 if (dists[i - 1] > dist)
221 dists[i] = dists[i - 1];
222 indices[i] = indices[i - 1];
233 if (count < capacity) count++;
239 DistanceType worstDist()
const {
return dists[capacity - 1]; }
244 typename _DistanceType,
typename _IndexType = size_t,
245 typename _CountType =
size_t>
249 using DistanceType = _DistanceType;
250 using IndexType = _IndexType;
251 using CountType = _CountType;
258 DistanceType maximumSearchDistanceSquared;
262 CountType capacity_, DistanceType maximumSearchDistanceSquared_)
267 maximumSearchDistanceSquared(maximumSearchDistanceSquared_)
271 void init(IndexType* indices_, DistanceType* dists_)
276 if (capacity) dists[capacity - 1] = maximumSearchDistanceSquared;
279 CountType size()
const {
return count; }
280 bool empty()
const {
return count == 0; }
281 bool full()
const {
return count == capacity; }
291 for (i = count; i > 0; --i)
295#ifdef NANOFLANN_FIRST_MATCH
296 if ((dists[i - 1] > dist) ||
297 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
300 if (dists[i - 1] > dist)
305 dists[i] = dists[i - 1];
306 indices[i] = indices[i - 1];
317 if (count < capacity) count++;
323 DistanceType worstDist()
const {
return dists[capacity - 1]; }
330 template <
typename PairType>
331 bool operator()(
const PairType& p1,
const PairType& p2)
const
333 return p1.second < p2.second;
345template <
typename IndexType =
size_t,
typename DistanceType =
double>
349 ResultItem(
const IndexType index,
const DistanceType distance)
350 : first(index), second(distance)
361template <
typename _DistanceType,
typename _IndexType =
size_t>
365 using DistanceType = _DistanceType;
366 using IndexType = _IndexType;
369 const DistanceType radius;
371 std::vector<ResultItem<IndexType, DistanceType>>& m_indices_dists;
374 DistanceType radius_,
376 : radius(radius_), m_indices_dists(indices_dists)
381 void init() { clear(); }
382 void clear() { m_indices_dists.clear(); }
384 size_t size()
const {
return m_indices_dists.size(); }
385 size_t empty()
const {
return m_indices_dists.empty(); }
387 bool full()
const {
return true; }
396 if (dist < radius) m_indices_dists.emplace_back(index, dist);
400 DistanceType worstDist()
const {
return radius; }
408 if (m_indices_dists.empty())
409 throw std::runtime_error(
410 "Cannot invoke RadiusResultSet::worst_item() on "
411 "an empty list of results.");
412 auto it = std::max_element(
423void save_value(std::ostream& stream,
const T& value)
425 stream.write(
reinterpret_cast<const char*
>(&value),
sizeof(T));
429void save_value(std::ostream& stream,
const std::vector<T>& value)
431 size_t size = value.size();
432 stream.write(
reinterpret_cast<const char*
>(&size),
sizeof(
size_t));
433 stream.write(
reinterpret_cast<const char*
>(value.data()),
sizeof(T) * size);
437void load_value(std::istream& stream, T& value)
439 stream.read(
reinterpret_cast<char*
>(&value),
sizeof(T));
443void load_value(std::istream& stream, std::vector<T>& value)
446 stream.read(
reinterpret_cast<char*
>(&size),
sizeof(
size_t));
448 stream.read(
reinterpret_cast<char*
>(value.data()),
sizeof(T) * size);
470 class T,
class DataSource,
typename _DistanceType = T,
471 typename IndexType = uint32_t>
474 using ElementType = T;
475 using DistanceType = _DistanceType;
477 const DataSource& data_source;
479 L1_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
481 DistanceType evalMetric(
482 const T* a,
const IndexType b_idx,
size_t size,
483 DistanceType worst_dist = -1)
const
485 DistanceType result = DistanceType();
486 const T* last = a + size;
487 const T* lastgroup = last - 3;
491 while (a < lastgroup)
493 const DistanceType diff0 =
494 std::abs(a[0] - data_source.kdtree_get_pt(b_idx, d++));
495 const DistanceType diff1 =
496 std::abs(a[1] - data_source.kdtree_get_pt(b_idx, d++));
497 const DistanceType diff2 =
498 std::abs(a[2] - data_source.kdtree_get_pt(b_idx, d++));
499 const DistanceType diff3 =
500 std::abs(a[3] - data_source.kdtree_get_pt(b_idx, d++));
501 result += diff0 + diff1 + diff2 + diff3;
503 if ((worst_dist > 0) && (result > worst_dist)) {
return result; }
509 result += std::abs(*a++ - data_source.kdtree_get_pt(b_idx, d++));
514 template <
typename U,
typename V>
515 DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
517 return std::abs(a - b);
532 class T,
class DataSource,
typename _DistanceType = T,
533 typename IndexType = uint32_t>
536 using ElementType = T;
537 using DistanceType = _DistanceType;
539 const DataSource& data_source;
541 L2_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
543 DistanceType evalMetric(
544 const T* a,
const IndexType b_idx,
size_t size,
545 DistanceType worst_dist = -1)
const
547 DistanceType result = DistanceType();
548 const T* last = a + size;
549 const T* lastgroup = last - 3;
553 while (a < lastgroup)
555 const DistanceType diff0 =
556 a[0] - data_source.kdtree_get_pt(b_idx, d++);
557 const DistanceType diff1 =
558 a[1] - data_source.kdtree_get_pt(b_idx, d++);
559 const DistanceType diff2 =
560 a[2] - data_source.kdtree_get_pt(b_idx, d++);
561 const DistanceType diff3 =
562 a[3] - data_source.kdtree_get_pt(b_idx, d++);
564 diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
566 if ((worst_dist > 0) && (result > worst_dist)) {
return result; }
572 const DistanceType diff0 =
573 *a++ - data_source.kdtree_get_pt(b_idx, d++);
574 result += diff0 * diff0;
579 template <
typename U,
typename V>
580 DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
582 return (a - b) * (a - b);
597 class T,
class DataSource,
typename _DistanceType = T,
598 typename IndexType = uint32_t>
601 using ElementType = T;
602 using DistanceType = _DistanceType;
604 const DataSource& data_source;
607 : data_source(_data_source)
611 DistanceType evalMetric(
612 const T* a,
const IndexType b_idx,
size_t size)
const
614 DistanceType result = DistanceType();
615 for (
size_t i = 0; i < size; ++i)
617 const DistanceType diff =
618 a[i] - data_source.kdtree_get_pt(b_idx, i);
619 result += diff * diff;
624 template <
typename U,
typename V>
625 DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
627 return (a - b) * (a - b);
642 class T,
class DataSource,
typename _DistanceType = T,
643 typename IndexType = uint32_t>
646 using ElementType = T;
647 using DistanceType = _DistanceType;
649 const DataSource& data_source;
651 SO2_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
653 DistanceType evalMetric(
654 const T* a,
const IndexType b_idx,
size_t size)
const
657 a[size - 1], data_source.kdtree_get_pt(b_idx, size - 1), size - 1);
662 template <
typename U,
typename V>
663 DistanceType
accum_dist(
const U a,
const V b,
const size_t)
const
665 DistanceType result = DistanceType();
666 DistanceType PI = pi_const<DistanceType>();
670 else if (result < -PI)
687 class T,
class DataSource,
typename _DistanceType = T,
688 typename IndexType = uint32_t>
691 using ElementType = T;
692 using DistanceType = _DistanceType;
698 : distance_L2_Simple(_data_source)
702 DistanceType evalMetric(
703 const T* a,
const IndexType b_idx,
size_t size)
const
705 return distance_L2_Simple.evalMetric(a, b_idx, size);
708 template <
typename U,
typename V>
709 DistanceType accum_dist(
const U a,
const V b,
const size_t idx)
const
711 return distance_L2_Simple.accum_dist(a, b, idx);
718 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
728 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
738 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
747 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
756 template <
class T,
class DataSource,
typename IndexType = u
int32_t>
768enum class KDTreeSingleIndexAdaptorFlags
771 SkipInitialBuildIndex = 1
774inline std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type operator&(
775 KDTreeSingleIndexAdaptorFlags lhs, KDTreeSingleIndexAdaptorFlags rhs)
778 typename std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type;
779 return static_cast<underlying
>(lhs) &
static_cast<underlying
>(rhs);
786 size_t _leaf_max_size = 10,
787 KDTreeSingleIndexAdaptorFlags _flags =
788 KDTreeSingleIndexAdaptorFlags::None,
789 unsigned int _n_thread_build = 1)
790 : leaf_max_size(_leaf_max_size),
792 n_thread_build(_n_thread_build)
796 size_t leaf_max_size;
797 KDTreeSingleIndexAdaptorFlags flags;
798 unsigned int n_thread_build;
805 : eps(eps_), sorted(sorted_)
834 static constexpr size_t WORDSIZE = 16;
835 static constexpr size_t BLOCKSIZE = 8192;
846 void* base_ =
nullptr;
847 void* loc_ =
nullptr;
859 Size wastedMemory = 0;
874 while (base_ !=
nullptr)
877 void* prev = *(
static_cast<void**
>(base_));
894 const Size size = (req_size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
899 if (size > remaining_)
901 wastedMemory += remaining_;
904 const Size blocksize =
905 size > BLOCKSIZE ? size + WORDSIZE : BLOCKSIZE + WORDSIZE;
908 void* m = ::malloc(blocksize);
911 fprintf(stderr,
"Failed to allocate memory.\n");
912 throw std::bad_alloc();
916 static_cast<void**
>(m)[0] = base_;
919 remaining_ = blocksize - WORDSIZE;
920 loc_ =
static_cast<char*
>(m) + WORDSIZE;
923 loc_ =
static_cast<char*
>(loc_) + size;
938 template <
typename T>
941 T* mem =
static_cast<T*
>(this->malloc(
sizeof(T) * count));
953template <
int32_t DIM,
typename T>
956 using type = std::array<T, DIM>;
962 using type = std::vector<T>;
982 class Derived,
typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
983 typename IndexType = uint32_t>
991 obj.pool_.free_all();
992 obj.root_node_ =
nullptr;
993 obj.size_at_index_build_ = 0;
996 using ElementType =
typename Distance::ElementType;
997 using DistanceType =
typename Distance::DistanceType;
1004 using Offset =
typename decltype(vAcc_)::size_type;
1005 using Size =
typename decltype(vAcc_)::size_type;
1006 using Dimension = int32_t;
1030 Node *child1 =
nullptr, *child2 =
nullptr;
1038 ElementType low, high;
1043 Size leaf_max_size_ = 0;
1046 Size n_thread_build_ = 1;
1050 Size size_at_index_build_ = 0;
1074 Size
size(
const Derived& obj)
const {
return obj.size_; }
1077 Size
veclen(
const Derived& obj) {
return DIM > 0 ? DIM : obj.dim; }
1081 const Derived& obj, IndexType element, Dimension component)
const
1083 return obj.dataset_.kdtree_get_pt(element, component);
1092 return obj.pool_.usedMemory + obj.pool_.wastedMemory +
1093 obj.dataset_.kdtree_get_point_count() *
1098 const Derived& obj, Offset ind, Size count, Dimension element,
1099 ElementType& min_elem, ElementType& max_elem)
1101 min_elem = dataset_get(obj, vAcc_[ind], element);
1102 max_elem = min_elem;
1103 for (Offset i = 1; i < count; ++i)
1105 ElementType val = dataset_get(obj, vAcc_[ind + i], element);
1106 if (val < min_elem) min_elem = val;
1107 if (val > max_elem) max_elem = val;
1119 Derived& obj,
const Offset left,
const Offset right,
BoundingBox& bbox)
1121 NodePtr node = obj.pool_.template allocate<Node>();
1122 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1125 if ((right - left) <=
static_cast<Offset
>(obj.leaf_max_size_))
1127 node->
child1 = node->child2 =
nullptr;
1132 for (Dimension i = 0; i < dims; ++i)
1134 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1135 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1137 for (Offset k = left + 1; k < right; ++k)
1139 for (Dimension i = 0; i < dims; ++i)
1141 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1142 if (bbox[i].low > val) bbox[i].low = val;
1143 if (bbox[i].high < val) bbox[i].high = val;
1151 DistanceType cutval;
1152 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1157 left_bbox[cutfeat].high = cutval;
1158 node->
child1 = this->divideTree(obj, left, left + idx, left_bbox);
1161 right_bbox[cutfeat].low = cutval;
1162 node->child2 = this->divideTree(obj, left + idx, right, right_bbox);
1164 node->
node_type.sub.divlow = left_bbox[cutfeat].high;
1165 node->
node_type.sub.divhigh = right_bbox[cutfeat].low;
1167 for (Dimension i = 0; i < dims; ++i)
1169 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1170 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1188 Derived& obj,
const Offset left,
const Offset right,
BoundingBox& bbox,
1189 std::atomic<unsigned int>& thread_count, std::mutex& mutex)
1191 std::unique_lock<std::mutex> lock(mutex);
1192 NodePtr node = obj.pool_.template allocate<Node>();
1195 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1198 if ((right - left) <=
static_cast<Offset
>(obj.leaf_max_size_))
1200 node->
child1 = node->child2 =
nullptr;
1205 for (Dimension i = 0; i < dims; ++i)
1207 bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
1208 bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
1210 for (Offset k = left + 1; k < right; ++k)
1212 for (Dimension i = 0; i < dims; ++i)
1214 const auto val = dataset_get(obj, obj.vAcc_[k], i);
1215 if (bbox[i].low > val) bbox[i].low = val;
1216 if (bbox[i].high < val) bbox[i].high = val;
1224 DistanceType cutval;
1225 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1229 std::future<NodePtr> left_future, right_future;
1232 left_bbox[cutfeat].high = cutval;
1233 if (++thread_count < n_thread_build_)
1235 left_future = std::async(
1236 std::launch::async, &KDTreeBaseClass::divideTreeConcurrent,
1237 this, std::ref(obj), left, left + idx, std::ref(left_bbox),
1238 std::ref(thread_count), std::ref(mutex));
1243 node->
child1 = this->divideTreeConcurrent(
1244 obj, left, left + idx, left_bbox, thread_count, mutex);
1248 right_bbox[cutfeat].low = cutval;
1249 if (++thread_count < n_thread_build_)
1251 right_future = std::async(
1252 std::launch::async, &KDTreeBaseClass::divideTreeConcurrent,
1253 this, std::ref(obj), left + idx, right,
1254 std::ref(right_bbox), std::ref(thread_count),
1260 node->child2 = this->divideTreeConcurrent(
1261 obj, left + idx, right, right_bbox, thread_count, mutex);
1264 if (left_future.valid())
1266 node->
child1 = left_future.get();
1269 if (right_future.valid())
1271 node->child2 = right_future.get();
1275 node->
node_type.sub.divlow = left_bbox[cutfeat].high;
1276 node->
node_type.sub.divhigh = right_bbox[cutfeat].low;
1278 for (Dimension i = 0; i < dims; ++i)
1280 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1281 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1289 const Derived& obj,
const Offset ind,
const Size count, Offset& index,
1290 Dimension& cutfeat, DistanceType& cutval,
const BoundingBox& bbox)
1292 const auto dims = (DIM > 0 ? DIM : obj.dim_);
1293 const auto EPS =
static_cast<DistanceType
>(0.00001);
1294 ElementType max_span = bbox[0].high - bbox[0].low;
1295 for (Dimension i = 1; i < dims; ++i)
1297 ElementType span = bbox[i].high - bbox[i].low;
1298 if (span > max_span) { max_span = span; }
1300 ElementType max_spread = -1;
1302 ElementType min_elem = 0, max_elem = 0;
1303 for (Dimension i = 0; i < dims; ++i)
1305 ElementType span = bbox[i].high - bbox[i].low;
1306 if (span > (1 - EPS) * max_span)
1308 ElementType min_elem_, max_elem_;
1309 computeMinMax(obj, ind, count, i, min_elem_, max_elem_);
1310 ElementType spread = max_elem_ - min_elem_;
1311 if (spread > max_spread)
1314 max_spread = spread;
1315 min_elem = min_elem_;
1316 max_elem = max_elem_;
1321 DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;
1323 if (split_val < min_elem)
1325 else if (split_val > max_elem)
1331 planeSplit(obj, ind, count, cutfeat, cutval, lim1, lim2);
1333 if (lim1 > count / 2)
1335 else if (lim2 < count / 2)
1351 const Derived& obj,
const Offset ind,
const Size count,
1352 const Dimension cutfeat,
const DistanceType& cutval, Offset& lim1,
1357 Offset right = count - 1;
1360 while (left <= right &&
1361 dataset_get(obj, vAcc_[ind + left], cutfeat) < cutval)
1363 while (right && left <= right &&
1364 dataset_get(obj, vAcc_[ind + right], cutfeat) >= cutval)
1366 if (left > right || !right)
1368 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1379 while (left <= right &&
1380 dataset_get(obj, vAcc_[ind + left], cutfeat) <= cutval)
1382 while (right && left <= right &&
1383 dataset_get(obj, vAcc_[ind + right], cutfeat) > cutval)
1385 if (left > right || !right)
1387 std::swap(vAcc_[ind + left], vAcc_[ind + right]);
1394 DistanceType computeInitialDistances(
1395 const Derived& obj,
const ElementType* vec,
1396 distance_vector_t& dists)
const
1399 DistanceType dist = DistanceType();
1401 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim_); ++i)
1403 if (vec[i] < obj.root_bbox_[i].low)
1406 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].low, i);
1409 if (vec[i] > obj.root_bbox_[i].high)
1412 obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].high, i);
1419 static void save_tree(
1420 const Derived& obj, std::ostream& stream,
const NodeConstPtr tree)
1422 save_value(stream, *tree);
1423 if (tree->child1 !=
nullptr) { save_tree(obj, stream, tree->child1); }
1424 if (tree->child2 !=
nullptr) { save_tree(obj, stream, tree->child2); }
1427 static void load_tree(Derived& obj, std::istream& stream, NodePtr& tree)
1429 tree = obj.pool_.template allocate<Node>();
1430 load_value(stream, *tree);
1431 if (tree->child1 !=
nullptr) { load_tree(obj, stream, tree->child1); }
1432 if (tree->child2 !=
nullptr) { load_tree(obj, stream, tree->child2); }
1440 void saveIndex(
const Derived& obj, std::ostream& stream)
const
1442 save_value(stream, obj.size_);
1443 save_value(stream, obj.dim_);
1444 save_value(stream, obj.root_bbox_);
1445 save_value(stream, obj.leaf_max_size_);
1446 save_value(stream, obj.vAcc_);
1447 if (obj.root_node_) save_tree(obj, stream, obj.root_node_);
1457 load_value(stream, obj.size_);
1458 load_value(stream, obj.dim_);
1459 load_value(stream, obj.root_bbox_);
1460 load_value(stream, obj.leaf_max_size_);
1461 load_value(stream, obj.vAcc_);
1462 load_tree(obj, stream, obj.root_node_);
1508 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
1509 typename IndexType = uint32_t>
1512 KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, IndexType>,
1513 Distance, DatasetAdaptor, DIM, IndexType>
1519 Distance, DatasetAdaptor, DIM, IndexType>&) =
delete;
1530 Distance, DatasetAdaptor, DIM, IndexType>,
1531 Distance, DatasetAdaptor, DIM, IndexType>;
1533 using Offset =
typename Base::Offset;
1534 using Size =
typename Base::Size;
1535 using Dimension =
typename Base::Dimension;
1537 using ElementType =
typename Base::ElementType;
1538 using DistanceType =
typename Base::DistanceType;
1540 using Node =
typename Base::Node;
1541 using NodePtr = Node*;
1543 using Interval =
typename Base::Interval;
1573 template <
class... Args>
1575 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1577 : dataset_(inputData),
1578 indexParams(params),
1579 distance_(inputData, std::forward<Args>(args)...)
1581 init(dimensionality, params);
1585 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1587 : dataset_(inputData), indexParams(params), distance_(inputData)
1589 init(dimensionality, params);
1594 const Dimension dimensionality,
1595 const KDTreeSingleIndexAdaptorParams& params)
1597 Base::size_ = dataset_.kdtree_get_point_count();
1598 Base::size_at_index_build_ = Base::size_;
1599 Base::dim_ = dimensionality;
1600 if (DIM > 0) Base::dim_ = DIM;
1601 Base::leaf_max_size_ = params.leaf_max_size;
1602 if (params.n_thread_build > 0)
1604 Base::n_thread_build_ = params.n_thread_build;
1608 Base::n_thread_build_ =
1609 std::max(std::thread::hardware_concurrency(), 1u);
1612 if (!(params.flags &
1613 KDTreeSingleIndexAdaptorFlags::SkipInitialBuildIndex))
1626 Base::size_ = dataset_.kdtree_get_point_count();
1627 Base::size_at_index_build_ = Base::size_;
1629 this->freeIndex(*
this);
1630 Base::size_at_index_build_ = Base::size_;
1631 if (Base::size_ == 0)
return;
1632 computeBoundingBox(Base::root_bbox_);
1634 if (Base::n_thread_build_ == 1)
1637 this->divideTree(*
this, 0, Base::size_, Base::root_bbox_);
1641 std::atomic<unsigned int> thread_count(0u);
1643 Base::root_node_ = this->divideTreeConcurrent(
1644 *
this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
1667 template <
typename RESULTSET>
1669 RESULTSET& result,
const ElementType* vec,
1673 if (this->size(*
this) == 0)
return false;
1674 if (!Base::root_node_)
1675 throw std::runtime_error(
1676 "[nanoflann] findNeighbors() called before building the "
1678 float epsError = 1 + searchParams.eps;
1681 distance_vector_t dists;
1683 auto zero =
static_cast<decltype(result.worstDist())
>(0);
1684 assign(dists, (DIM > 0 ? DIM : Base::dim_), zero);
1685 DistanceType dist = this->computeInitialDistances(*
this, vec, dists);
1686 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
1687 return result.full();
1706 const ElementType* query_point,
const Size num_closest,
1707 IndexType* out_indices, DistanceType* out_distances)
const
1710 resultSet.init(out_indices, out_distances);
1711 findNeighbors(resultSet, query_point);
1712 return resultSet.size();
1735 const ElementType* query_point,
const DistanceType& radius,
1740 radius, IndicesDists);
1742 radiusSearchCustomCallback(query_point, resultSet, searchParams);
1743 if (searchParams.sorted)
1754 template <
class SEARCH_CALLBACK>
1756 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
1759 findNeighbors(resultSet, query_point, searchParams);
1760 return resultSet.size();
1780 const ElementType* query_point,
const Size num_closest,
1781 IndexType* out_indices, DistanceType* out_distances,
1782 const DistanceType& radius)
const
1785 num_closest, radius);
1786 resultSet.init(out_indices, out_distances);
1787 findNeighbors(resultSet, query_point);
1788 return resultSet.size();
1799 Base::size_ = dataset_.kdtree_get_point_count();
1800 if (Base::vAcc_.size() != Base::size_) Base::vAcc_.resize(Base::size_);
1801 for (Size i = 0; i < Base::size_; i++) Base::vAcc_[i] = i;
1804 void computeBoundingBox(BoundingBox& bbox)
1806 const auto dims = (DIM > 0 ? DIM : Base::dim_);
1808 if (dataset_.kdtree_get_bbox(bbox))
1814 const Size N = dataset_.kdtree_get_point_count();
1816 throw std::runtime_error(
1817 "[nanoflann] computeBoundingBox() called but "
1818 "no data points found.");
1819 for (Dimension i = 0; i < dims; ++i)
1821 bbox[i].low = bbox[i].high =
1822 this->dataset_get(*
this, Base::vAcc_[0], i);
1824 for (Offset k = 1; k < N; ++k)
1826 for (Dimension i = 0; i < dims; ++i)
1829 this->dataset_get(*
this, Base::vAcc_[k], i);
1830 if (val < bbox[i].low) bbox[i].low = val;
1831 if (val > bbox[i].high) bbox[i].high = val;
1843 template <
class RESULTSET>
1845 RESULTSET& result_set,
const ElementType* vec,
const NodePtr node,
1847 const float epsError)
const
1850 if ((node->child1 ==
nullptr) && (node->child2 ==
nullptr))
1852 DistanceType worst_dist = result_set.worstDist();
1853 for (Offset i = node->node_type.lr.left;
1854 i < node->node_type.lr.right; ++i)
1856 const IndexType accessor = Base::vAcc_[i];
1857 DistanceType dist = distance_.evalMetric(
1858 vec, accessor, (DIM > 0 ? DIM : Base::dim_));
1859 if (dist < worst_dist)
1861 if (!result_set.addPoint(dist, Base::vAcc_[i]))
1873 Dimension idx = node->node_type.sub.divfeat;
1874 ElementType val = vec[idx];
1875 DistanceType diff1 = val - node->node_type.sub.divlow;
1876 DistanceType diff2 = val - node->node_type.sub.divhigh;
1880 DistanceType cut_dist;
1881 if ((diff1 + diff2) < 0)
1883 bestChild = node->child1;
1884 otherChild = node->child2;
1886 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
1890 bestChild = node->child2;
1891 otherChild = node->child1;
1893 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
1897 if (!searchLevel(result_set, vec, bestChild, mindist, dists, epsError))
1904 DistanceType dst = dists[idx];
1905 mindist = mindist + cut_dist - dst;
1906 dists[idx] = cut_dist;
1907 if (mindist * epsError <= result_set.worstDist())
1910 result_set, vec, otherChild, mindist, dists, epsError))
1929 Base::saveIndex(*
this, stream);
1937 void loadIndex(std::istream& stream) { Base::loadIndex(*
this, stream); }
1979 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
1980 typename IndexType = uint32_t>
1983 KDTreeSingleIndexDynamicAdaptor_<
1984 Distance, DatasetAdaptor, DIM, IndexType>,
1985 Distance, DatasetAdaptor, DIM, IndexType>
1995 std::vector<int>& treeIndex_;
2001 Distance, DatasetAdaptor, DIM, IndexType>,
2002 Distance, DatasetAdaptor, DIM, IndexType>;
2004 using ElementType =
typename Base::ElementType;
2005 using DistanceType =
typename Base::DistanceType;
2007 using Offset =
typename Base::Offset;
2008 using Size =
typename Base::Size;
2009 using Dimension =
typename Base::Dimension;
2011 using Node =
typename Base::Node;
2012 using NodePtr = Node*;
2014 using Interval =
typename Base::Interval;
2039 const Dimension dimensionality,
const DatasetAdaptor& inputData,
2040 std::vector<int>& treeIndex,
2043 : dataset_(inputData),
2044 index_params_(params),
2045 treeIndex_(treeIndex),
2046 distance_(inputData)
2049 Base::size_at_index_build_ = 0;
2050 for (
auto& v : Base::root_bbox_) v = {};
2051 Base::dim_ = dimensionality;
2052 if (DIM > 0) Base::dim_ = DIM;
2053 Base::leaf_max_size_ = params.leaf_max_size;
2054 if (params.n_thread_build > 0)
2056 Base::n_thread_build_ = params.n_thread_build;
2060 Base::n_thread_build_ =
2061 std::max(std::thread::hardware_concurrency(), 1u);
2074 std::swap(Base::vAcc_, tmp.Base::vAcc_);
2075 std::swap(Base::leaf_max_size_, tmp.Base::leaf_max_size_);
2076 std::swap(index_params_, tmp.index_params_);
2077 std::swap(treeIndex_, tmp.treeIndex_);
2078 std::swap(Base::size_, tmp.Base::size_);
2079 std::swap(Base::size_at_index_build_, tmp.Base::size_at_index_build_);
2080 std::swap(Base::root_node_, tmp.Base::root_node_);
2081 std::swap(Base::root_bbox_, tmp.Base::root_bbox_);
2082 std::swap(Base::pool_, tmp.Base::pool_);
2091 Base::size_ = Base::vAcc_.size();
2092 this->freeIndex(*
this);
2093 Base::size_at_index_build_ = Base::size_;
2094 if (Base::size_ == 0)
return;
2095 computeBoundingBox(Base::root_bbox_);
2097 if (Base::n_thread_build_ == 1)
2100 this->divideTree(*
this, 0, Base::size_, Base::root_bbox_);
2104 std::atomic<unsigned int> thread_count(0u);
2106 Base::root_node_ = this->divideTreeConcurrent(
2107 *
this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
2134 template <
typename RESULTSET>
2136 RESULTSET& result,
const ElementType* vec,
2140 if (this->size(*
this) == 0)
return false;
2141 if (!Base::root_node_)
return false;
2142 float epsError = 1 + searchParams.eps;
2145 distance_vector_t dists;
2148 dists, (DIM > 0 ? DIM : Base::dim_),
2149 static_cast<typename distance_vector_t::value_type>(0));
2150 DistanceType dist = this->computeInitialDistances(*
this, vec, dists);
2151 searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
2152 return result.full();
2170 const ElementType* query_point,
const Size num_closest,
2171 IndexType* out_indices, DistanceType* out_distances,
2175 resultSet.init(out_indices, out_distances);
2176 findNeighbors(resultSet, query_point, searchParams);
2177 return resultSet.size();
2200 const ElementType* query_point,
const DistanceType& radius,
2205 radius, IndicesDists);
2206 const size_t nFound =
2207 radiusSearchCustomCallback(query_point, resultSet, searchParams);
2208 if (searchParams.sorted)
2219 template <
class SEARCH_CALLBACK>
2221 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
2224 findNeighbors(resultSet, query_point, searchParams);
2225 return resultSet.size();
2231 void computeBoundingBox(BoundingBox& bbox)
2233 const auto dims = (DIM > 0 ? DIM : Base::dim_);
2236 if (dataset_.kdtree_get_bbox(bbox))
2242 const Size N = Base::size_;
2244 throw std::runtime_error(
2245 "[nanoflann] computeBoundingBox() called but "
2246 "no data points found.");
2247 for (Dimension i = 0; i < dims; ++i)
2249 bbox[i].low = bbox[i].high =
2250 this->dataset_get(*
this, Base::vAcc_[0], i);
2252 for (Offset k = 1; k < N; ++k)
2254 for (Dimension i = 0; i < dims; ++i)
2257 this->dataset_get(*
this, Base::vAcc_[k], i);
2258 if (val < bbox[i].low) bbox[i].low = val;
2259 if (val > bbox[i].high) bbox[i].high = val;
2269 template <
class RESULTSET>
2271 RESULTSET& result_set,
const ElementType* vec,
const NodePtr node,
2273 const float epsError)
const
2276 if ((node->child1 ==
nullptr) && (node->child2 ==
nullptr))
2278 DistanceType worst_dist = result_set.worstDist();
2279 for (Offset i = node->node_type.lr.left;
2280 i < node->node_type.lr.right; ++i)
2282 const IndexType index = Base::vAcc_[i];
2283 if (treeIndex_[index] == -1)
continue;
2284 DistanceType dist = distance_.evalMetric(
2285 vec, index, (DIM > 0 ? DIM : Base::dim_));
2286 if (dist < worst_dist)
2288 if (!result_set.addPoint(
2289 static_cast<typename RESULTSET::DistanceType
>(dist),
2290 static_cast<typename RESULTSET::IndexType
>(
2303 Dimension idx = node->node_type.sub.divfeat;
2304 ElementType val = vec[idx];
2305 DistanceType diff1 = val - node->node_type.sub.divlow;
2306 DistanceType diff2 = val - node->node_type.sub.divhigh;
2310 DistanceType cut_dist;
2311 if ((diff1 + diff2) < 0)
2313 bestChild = node->child1;
2314 otherChild = node->child2;
2316 distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
2320 bestChild = node->child2;
2321 otherChild = node->child1;
2323 distance_.accum_dist(val, node->node_type.sub.divlow, idx);
2327 searchLevel(result_set, vec, bestChild, mindist, dists, epsError);
2329 DistanceType dst = dists[idx];
2330 mindist = mindist + cut_dist - dst;
2331 dists[idx] = cut_dist;
2332 if (mindist * epsError <= result_set.worstDist())
2334 searchLevel(result_set, vec, otherChild, mindist, dists, epsError);
2370 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
2371 typename IndexType = uint32_t>
2375 using ElementType =
typename Distance::ElementType;
2376 using DistanceType =
typename Distance::DistanceType;
2379 Distance, DatasetAdaptor, DIM>::Offset;
2381 Distance, DatasetAdaptor, DIM>::Size;
2383 Distance, DatasetAdaptor, DIM>::Dimension;
2386 Size leaf_max_size_;
2398 std::unordered_set<int> removedPoints_;
2405 Distance, DatasetAdaptor, DIM, IndexType>;
2406 std::vector<index_container_t> index_;
2418 int First0Bit(IndexType num)
2432 using my_kd_tree_t = KDTreeSingleIndexDynamicAdaptor_<
2433 Distance, DatasetAdaptor, DIM, IndexType>;
2434 std::vector<my_kd_tree_t> index(
2436 my_kd_tree_t(dim_ , dataset_, treeIndex_, index_params_));
2459 const int dimensionality,
const DatasetAdaptor& inputData,
2462 const size_t maximumPointCount = 1000000000U)
2463 : dataset_(inputData), index_params_(params), distance_(inputData)
2465 treeCount_ =
static_cast<size_t>(std::log2(maximumPointCount)) + 1;
2467 dim_ = dimensionality;
2469 if (DIM > 0) dim_ = DIM;
2470 leaf_max_size_ = params.leaf_max_size;
2472 const size_t num_initial_points = dataset_.kdtree_get_point_count();
2473 if (num_initial_points > 0) { addPoints(0, num_initial_points - 1); }
2479 Distance, DatasetAdaptor, DIM, IndexType>&) =
delete;
2484 const Size count = end - start + 1;
2486 treeIndex_.resize(treeIndex_.size() + count);
2487 for (IndexType idx = start; idx <= end; idx++)
2489 const int pos = First0Bit(pointCount_);
2490 maxIndex = std::max(pos, maxIndex);
2491 treeIndex_[pointCount_] = pos;
2493 const auto it = removedPoints_.find(idx);
2494 if (it != removedPoints_.end())
2496 removedPoints_.erase(it);
2497 treeIndex_[idx] = pos;
2500 for (
int i = 0; i < pos; i++)
2502 for (
int j = 0; j < static_cast<int>(index_[i].vAcc_.size());
2505 index_[pos].vAcc_.push_back(index_[i].vAcc_[j]);
2506 if (treeIndex_[index_[i].vAcc_[j]] != -1)
2507 treeIndex_[index_[i].vAcc_[j]] = pos;
2509 index_[i].vAcc_.clear();
2511 index_[pos].vAcc_.push_back(idx);
2515 for (
int i = 0; i <= maxIndex; ++i)
2517 index_[i].freeIndex(index_[i]);
2518 if (!index_[i].vAcc_.empty()) index_[i].buildIndex();
2525 if (idx >= pointCount_)
return;
2526 removedPoints_.insert(idx);
2527 treeIndex_[idx] = -1;
2546 template <
typename RESULTSET>
2548 RESULTSET& result,
const ElementType* vec,
2551 for (
size_t i = 0; i < treeCount_; i++)
2553 index_[i].findNeighbors(result, &vec[0], searchParams);
2555 return result.full();
2586 bool row_major =
true>
2591 using num_t =
typename MatrixType::Scalar;
2592 using IndexType =
typename MatrixType::Index;
2593 using metric_t =
typename Distance::template traits<
2594 num_t,
self_t, IndexType>::distance_t;
2598 row_major ? MatrixType::ColsAtCompileTime
2599 : MatrixType::RowsAtCompileTime,
2606 using Size =
typename index_t::Size;
2607 using Dimension =
typename index_t::Dimension;
2611 const Dimension dimensionality,
2612 const std::reference_wrapper<const MatrixType>& mat,
2613 const int leaf_max_size = 10)
2614 : m_data_matrix(mat)
2616 const auto dims = row_major ? mat.get().cols() : mat.get().rows();
2617 if (
static_cast<Dimension
>(dims) != dimensionality)
2618 throw std::runtime_error(
2619 "Error: 'dimensionality' must match column count in data "
2621 if (DIM > 0 &&
static_cast<int32_t
>(dims) != DIM)
2622 throw std::runtime_error(
2623 "Data set dimensionality does not match the 'DIM' template "
2636 const std::reference_wrapper<const MatrixType> m_data_matrix;
2647 const num_t* query_point,
const Size num_closest,
2648 IndexType* out_indices, num_t* out_distances)
const
2651 resultSet.init(out_indices, out_distances);
2658 const self_t& derived()
const {
return *
this; }
2659 self_t& derived() {
return *
this; }
2662 Size kdtree_get_point_count()
const
2665 return m_data_matrix.get().rows();
2667 return m_data_matrix.get().cols();
2671 num_t kdtree_get_pt(
const IndexType idx,
size_t dim)
const
2674 return m_data_matrix.get().coeff(idx, IndexType(dim));
2676 return m_data_matrix.get().coeff(IndexType(dim), idx);
2684 template <
class BBOX>
2685 bool kdtree_get_bbox(BBOX& )
const
// end of grouping
Definition nanoflann.hpp:985
Size usedMemory(Derived &obj)
Definition nanoflann.hpp:1090
NodePtr divideTreeConcurrent(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex)
Definition nanoflann.hpp:1187
void planeSplit(const Derived &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)
Definition nanoflann.hpp:1350
typename array_or_vector< DIM, DistanceType >::type distance_vector_t
Definition nanoflann.hpp:1059
std::vector< IndexType > vAcc_
Definition nanoflann.hpp:1002
Size size(const Derived &obj) const
Definition nanoflann.hpp:1074
void freeIndex(Derived &obj)
Definition nanoflann.hpp:989
void loadIndex(Derived &obj, std::istream &stream)
Definition nanoflann.hpp:1455
typename array_or_vector< DIM, Interval >::type BoundingBox
Definition nanoflann.hpp:1055
BoundingBox root_bbox_
Definition nanoflann.hpp:1062
void saveIndex(const Derived &obj, std::ostream &stream) const
Definition nanoflann.hpp:1440
PooledAllocator pool_
Definition nanoflann.hpp:1071
NodePtr divideTree(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox)
Definition nanoflann.hpp:1118
ElementType dataset_get(const Derived &obj, IndexType element, Dimension component) const
Helper accessor to the dataset points:
Definition nanoflann.hpp:1080
Size veclen(const Derived &obj)
Definition nanoflann.hpp:1077
Definition nanoflann.hpp:1514
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1755
Size rknnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const
Definition nanoflann.hpp:1779
KDTreeSingleIndexAdaptor(const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete
KDTreeSingleIndexAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms, Args &&... args)
Definition nanoflann.hpp:1574
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1734
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:1551
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:1937
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:1547
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances) const
Definition nanoflann.hpp:1705
void init_vind()
Definition nanoflann.hpp:1796
const DatasetAdaptor & dataset_
Definition nanoflann.hpp:1522
void saveIndex(std::ostream &stream) const
Definition nanoflann.hpp:1927
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1668
void buildIndex()
Definition nanoflann.hpp:1624
bool searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:1844
Definition nanoflann.hpp:1986
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2199
KDTreeSingleIndexDynamicAdaptor_(const Dimension dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams())
Definition nanoflann.hpp:2038
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:2017
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:1991
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2220
KDTreeSingleIndexDynamicAdaptor_(const KDTreeSingleIndexDynamicAdaptor_ &rhs)=default
void buildIndex()
Definition nanoflann.hpp:2089
void saveIndex(std::ostream &stream)
Definition nanoflann.hpp:2345
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:2021
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:2352
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2169
void searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:2270
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2135
KDTreeSingleIndexDynamicAdaptor_ operator=(const KDTreeSingleIndexDynamicAdaptor_ &rhs)
Definition nanoflann.hpp:2070
Definition nanoflann.hpp:2373
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2547
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:2393
void removePoint(size_t idx)
Definition nanoflann.hpp:2523
void addPoints(IndexType start, IndexType end)
Definition nanoflann.hpp:2482
KDTreeSingleIndexDynamicAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams(), const size_t maximumPointCount=1000000000U)
Definition nanoflann.hpp:2458
std::vector< int > treeIndex_
Definition nanoflann.hpp:2397
const std::vector< index_container_t > & getAllIndices() const
Definition nanoflann.hpp:2411
Dimension dim_
Dimensionality of each data point.
Definition nanoflann.hpp:2402
KDTreeSingleIndexDynamicAdaptor(const KDTreeSingleIndexDynamicAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete
Definition nanoflann.hpp:168
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:204
Definition nanoflann.hpp:833
~PooledAllocator()
Definition nanoflann.hpp:869
void free_all()
Definition nanoflann.hpp:872
void * malloc(const size_t req_size)
Definition nanoflann.hpp:888
T * allocate(const size_t count=1)
Definition nanoflann.hpp:939
PooledAllocator()
Definition nanoflann.hpp:864
Definition nanoflann.hpp:247
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:288
Definition nanoflann.hpp:363
ResultItem< IndexType, DistanceType > worst_item() const
Definition nanoflann.hpp:406
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:394
std::enable_if< has_assign< Container >::value, void >::type assign(Container &c, const size_t nElements, const T &value)
Definition nanoflann.hpp:144
T pi_const()
Definition nanoflann.hpp:87
std::enable_if< has_resize< Container >::value, void >::type resize(Container &c, const size_t nElements)
Definition nanoflann.hpp:122
Definition nanoflann.hpp:328
bool operator()(const PairType &p1, const PairType &p2) const
Definition nanoflann.hpp:331
Definition nanoflann.hpp:1037
Definition nanoflann.hpp:1012
DistanceType divlow
The values used for subdivision.
Definition nanoflann.hpp:1025
Node * child1
Definition nanoflann.hpp:1030
Dimension divfeat
Definition nanoflann.hpp:1023
Offset right
Indices of points in leaf node.
Definition nanoflann.hpp:1019
union nanoflann::KDTreeBaseClass::Node::@0 node_type
Definition nanoflann.hpp:2588
void query(const num_t *query_point, const Size num_closest, IndexType *out_indices, num_t *out_distances) const
Definition nanoflann.hpp:2646
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:2610
KDTreeEigenMatrixAdaptor(const self_t &)=delete
typename index_t::Offset Offset
Definition nanoflann.hpp:2605
Definition nanoflann.hpp:784
Definition nanoflann.hpp:473
Definition nanoflann.hpp:535
Definition nanoflann.hpp:600
Definition nanoflann.hpp:456
Definition nanoflann.hpp:347
DistanceType second
Distance from sample to query point.
Definition nanoflann.hpp:355
IndexType first
Index of the sample in the dataset.
Definition nanoflann.hpp:354
Definition nanoflann.hpp:645
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition nanoflann.hpp:663
Definition nanoflann.hpp:690
Definition nanoflann.hpp:803
bool sorted
distance (default: true)
Definition nanoflann.hpp:810
float eps
search for eps-approximate neighbours (default: 0)
Definition nanoflann.hpp:809
Definition nanoflann.hpp:955
Definition nanoflann.hpp:109
Definition nanoflann.hpp:98
Definition nanoflann.hpp:720
Definition nanoflann.hpp:717
Definition nanoflann.hpp:730
Definition nanoflann.hpp:740
Definition nanoflann.hpp:737
Definition nanoflann.hpp:727
Definition nanoflann.hpp:749
Definition nanoflann.hpp:746
Definition nanoflann.hpp:758
Definition nanoflann.hpp:755