57 #include <unordered_set>
61 #define NANOFLANN_VERSION 0x142
64 #if !defined(NOMINMAX) && \
65 (defined(_WIN32) || defined(_WIN32_) || defined(WIN32) || defined(_WIN64))
86 return static_cast<T
>(3.14159265358979323846);
93 template <
typename T,
typename =
int>
104 template <
typename T,
typename =
int>
109 template <
typename T>
118 template <
typename Container>
119 inline typename std::enable_if<has_resize<Container>::value,
void>::type
resize(
120 Container& c,
const size_t nElements)
129 template <
typename Container>
130 inline typename std::enable_if<!has_resize<Container>::value,
void>::type
131 resize(Container& c,
const size_t nElements)
133 if (nElements != c.size())
134 throw std::logic_error(
"Try to change the size of a std::array.");
140 template <
typename Container,
typename T>
141 inline typename std::enable_if<has_assign<Container>::value,
void>::type
assign(
142 Container& c,
const size_t nElements,
const T& value)
144 c.assign(nElements, value);
150 template <
typename Container,
typename T>
151 inline typename std::enable_if<!has_assign<Container>::value,
void>::type
152 assign(Container& c,
const size_t nElements,
const T& value)
154 for (
size_t i = 0; i < nElements; i++) c[i] = value;
160 typename _DistanceType,
typename _IndexType = size_t,
161 typename _CountType =
size_t>
165 using DistanceType = _DistanceType;
166 using IndexType = _IndexType;
167 using CountType = _CountType;
177 : indices(0), dists(0), capacity(capacity_), count(0)
181 inline void init(IndexType* indices_, DistanceType* dists_)
187 dists[capacity - 1] = (std::numeric_limits<DistanceType>::max)();
190 inline CountType size()
const {
return count; }
192 inline bool full()
const {
return count == capacity; }
199 inline bool addPoint(DistanceType dist, IndexType index)
202 for (i = count; i > 0; --i)
204 #ifdef NANOFLANN_FIRST_MATCH
207 if ((dists[i - 1] > dist) ||
208 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
211 if (dists[i - 1] > dist)
216 dists[i] = dists[i - 1];
217 indices[i] = indices[i - 1];
228 if (count < capacity) count++;
234 inline DistanceType worstDist()
const {
return dists[capacity - 1]; }
241 template <
typename PairType>
242 inline bool operator()(
const PairType& p1,
const PairType& p2)
const
244 return p1.second < p2.second;
251 template <
typename _DistanceType,
typename _IndexType =
size_t>
255 using DistanceType = _DistanceType;
256 using IndexType = _IndexType;
259 const DistanceType radius;
261 std::vector<std::pair<IndexType, DistanceType>>& m_indices_dists;
264 DistanceType radius_,
265 std::vector<std::pair<IndexType, DistanceType>>& indices_dists)
266 : radius(radius_), m_indices_dists(indices_dists)
271 inline void init() { clear(); }
272 inline void clear() { m_indices_dists.clear(); }
274 inline size_t size()
const {
return m_indices_dists.size(); }
276 inline bool full()
const {
return true; }
283 inline bool addPoint(DistanceType dist, IndexType index)
286 m_indices_dists.push_back(std::make_pair(index, dist));
290 inline DistanceType worstDist()
const {
return radius; }
298 if (m_indices_dists.empty())
299 throw std::runtime_error(
300 "Cannot invoke RadiusResultSet::worst_item() on "
301 "an empty list of results.");
302 using DistIt =
typename std::vector<
303 std::pair<IndexType, DistanceType>>::const_iterator;
304 DistIt it = std::max_element(
314 template <
typename T>
315 void save_value(std::ostream& stream,
const T& value)
317 stream.write(
reinterpret_cast<const char*
>(&value),
sizeof(T));
320 template <
typename T>
321 void save_value(std::ostream& stream,
const std::vector<T>& value)
323 size_t size = value.size();
324 stream.write(
reinterpret_cast<const char*
>(&size),
sizeof(
size_t));
325 stream.write(
reinterpret_cast<const char*
>(value.data()),
sizeof(T) * size);
328 template <
typename T>
329 void load_value(std::istream& stream, T& value)
331 stream.read(
reinterpret_cast<char*
>(&value),
sizeof(T));
334 template <
typename T>
335 void load_value(std::istream& stream, std::vector<T>& value)
338 stream.read(
reinterpret_cast<char*
>(&size),
sizeof(
size_t));
340 stream.read(
reinterpret_cast<char*
>(value.data()),
sizeof(T) * size);
362 class T,
class DataSource,
typename _DistanceType = T,
363 typename AccessorType = uint32_t>
366 using ElementType = T;
367 using DistanceType = _DistanceType;
369 const DataSource& data_source;
371 L1_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
373 inline DistanceType evalMetric(
374 const T* a,
const AccessorType b_idx,
size_t size,
375 DistanceType worst_dist = -1)
const
377 DistanceType result = DistanceType();
378 const T* last = a + size;
379 const T* lastgroup = last - 3;
383 while (a < lastgroup)
385 const DistanceType diff0 =
386 std::abs(a[0] - data_source.kdtree_get_pt(b_idx, d++));
387 const DistanceType diff1 =
388 std::abs(a[1] - data_source.kdtree_get_pt(b_idx, d++));
389 const DistanceType diff2 =
390 std::abs(a[2] - data_source.kdtree_get_pt(b_idx, d++));
391 const DistanceType diff3 =
392 std::abs(a[3] - data_source.kdtree_get_pt(b_idx, d++));
393 result += diff0 + diff1 + diff2 + diff3;
395 if ((worst_dist > 0) && (result > worst_dist)) {
return result; }
401 result += std::abs(*a++ - data_source.kdtree_get_pt(b_idx, d++));
406 template <
typename U,
typename V>
407 inline DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
409 return std::abs(a - b);
424 class T,
class DataSource,
typename _DistanceType = T,
425 typename AccessorType = uint32_t>
428 using ElementType = T;
429 using DistanceType = _DistanceType;
431 const DataSource& data_source;
433 L2_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
435 inline DistanceType evalMetric(
436 const T* a,
const AccessorType b_idx,
size_t size,
437 DistanceType worst_dist = -1)
const
439 DistanceType result = DistanceType();
440 const T* last = a + size;
441 const T* lastgroup = last - 3;
445 while (a < lastgroup)
447 const DistanceType diff0 =
448 a[0] - data_source.kdtree_get_pt(b_idx, d++);
449 const DistanceType diff1 =
450 a[1] - data_source.kdtree_get_pt(b_idx, d++);
451 const DistanceType diff2 =
452 a[2] - data_source.kdtree_get_pt(b_idx, d++);
453 const DistanceType diff3 =
454 a[3] - data_source.kdtree_get_pt(b_idx, d++);
456 diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
458 if ((worst_dist > 0) && (result > worst_dist)) {
return result; }
464 const DistanceType diff0 =
465 *a++ - data_source.kdtree_get_pt(b_idx, d++);
466 result += diff0 * diff0;
471 template <
typename U,
typename V>
472 inline DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
474 return (a - b) * (a - b);
489 class T,
class DataSource,
typename _DistanceType = T,
490 typename AccessorType = uint32_t>
493 using ElementType = T;
494 using DistanceType = _DistanceType;
496 const DataSource& data_source;
499 : data_source(_data_source)
503 inline DistanceType evalMetric(
504 const T* a,
const AccessorType b_idx,
size_t size)
const
506 DistanceType result = DistanceType();
507 for (
size_t i = 0; i < size; ++i)
509 const DistanceType diff =
510 a[i] - data_source.kdtree_get_pt(b_idx, i);
511 result += diff * diff;
516 template <
typename U,
typename V>
517 inline DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
519 return (a - b) * (a - b);
534 class T,
class DataSource,
typename _DistanceType = T,
535 typename AccessorType = uint32_t>
538 using ElementType = T;
539 using DistanceType = _DistanceType;
541 const DataSource& data_source;
543 SO2_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
545 inline DistanceType evalMetric(
546 const T* a,
const AccessorType b_idx,
size_t size)
const
549 a[size - 1], data_source.kdtree_get_pt(b_idx, size - 1), size - 1);
554 template <
typename U,
typename V>
555 inline DistanceType
accum_dist(
const U a,
const V b,
const size_t)
const
557 DistanceType result = DistanceType();
558 DistanceType PI = pi_const<DistanceType>();
562 else if (result < -PI)
579 class T,
class DataSource,
typename _DistanceType = T,
580 typename AccessorType = uint32_t>
583 using ElementType = T;
584 using DistanceType = _DistanceType;
590 : distance_L2_Simple(_data_source)
594 inline DistanceType evalMetric(
595 const T* a,
const AccessorType b_idx,
size_t size)
const
597 return distance_L2_Simple.evalMetric(a, b_idx, size);
600 template <
typename U,
typename V>
601 inline DistanceType accum_dist(
const U a,
const V b,
const size_t idx)
const
603 return distance_L2_Simple.accum_dist(a, b, idx);
610 template <
class T,
class DataSource,
typename AccessorType = u
int32_t>
619 template <
class T,
class DataSource,
typename AccessorType = u
int32_t>
628 template <
class T,
class DataSource,
typename AccessorType = u
int32_t>
637 template <
class T,
class DataSource,
typename AccessorType = u
int32_t>
646 template <
class T,
class DataSource,
typename AccessorType = u
int32_t>
658 enum class KDTreeSingleIndexAdaptorFlags
661 SkipInitialBuildIndex = 1
664 inline std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type operator&(
665 KDTreeSingleIndexAdaptorFlags lhs, KDTreeSingleIndexAdaptorFlags rhs)
668 typename std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type;
669 return static_cast<underlying
>(lhs) &
static_cast<underlying
>(rhs);
676 size_t _leaf_max_size = 10, KDTreeSingleIndexAdaptorFlags _flags =
677 KDTreeSingleIndexAdaptorFlags::None)
678 : leaf_max_size(_leaf_max_size), flags(_flags)
682 size_t leaf_max_size;
683 KDTreeSingleIndexAdaptorFlags flags;
691 SearchParams(
int checks_IGNORED_ = 32,
float eps_ = 0,
bool sorted_ =
true)
692 : checks(checks_IGNORED_), eps(eps_), sorted(sorted_)
714 template <
typename T>
717 T* mem =
static_cast<T*
>(::malloc(
sizeof(T) * count));
737 const size_t BLOCKSIZE = 8192;
747 using Offset = uint32_t;
748 using Size = uint32_t;
749 using Dimension = int32_t;
780 while (base !=
nullptr)
783 *(
static_cast<void**
>(base));
805 if (size > remaining)
807 wastedMemory += remaining;
810 const Size blocksize =
811 (size +
sizeof(
void*) + (
WORDSIZE - 1) > BLOCKSIZE)
812 ? size +
sizeof(
void*) + (
WORDSIZE - 1)
816 void* m = ::malloc(blocksize);
819 fprintf(stderr,
"Failed to allocate memory.\n");
820 throw std::bad_alloc();
824 static_cast<void**
>(m)[0] = base;
831 remaining = blocksize -
sizeof(
void*) - shift;
832 loc = (
static_cast<char*
>(m) +
sizeof(
void*) + shift);
835 loc =
static_cast<char*
>(loc) + size;
850 template <
typename T>
853 T* mem =
static_cast<T*
>(this->malloc(
sizeof(T) * count));
865 template <
int32_t DIM,
typename T>
868 using container_t = std::array<T, DIM>;
871 template <
typename T>
874 using container_t = std::vector<T>;
893 class Derived,
typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
894 typename AccessorType = uint32_t>
903 obj.root_node =
nullptr;
904 obj.m_size_at_index_build = 0;
907 using ElementType =
typename Distance::ElementType;
908 using DistanceType =
typename Distance::DistanceType;
913 std::vector<AccessorType>
vAcc;
915 using Offset =
typename decltype(vAcc)::size_type;
916 using Size =
typename decltype(vAcc)::size_type;
917 using Dimension = int32_t;
946 ElementType low, high;
951 Size m_leaf_max_size;
966 typename array_or_vector_selector<DIM, DistanceType>::container_t;
982 Size
size(
const Derived& obj)
const {
return obj.m_size; }
985 Size
veclen(
const Derived& obj) {
return DIM > 0 ? DIM : obj.dim; }
989 const Derived& obj, AccessorType element, Dimension component)
const
991 return obj.dataset.kdtree_get_pt(element, component);
1000 return obj.pool.usedMemory + obj.pool.wastedMemory +
1001 obj.dataset.kdtree_get_point_count() *
1002 sizeof(AccessorType);
1006 const Derived& obj, Offset ind, Size count, Dimension element,
1007 ElementType& min_elem, ElementType& max_elem)
1009 min_elem = dataset_get(obj, vAcc[ind], element);
1010 max_elem = min_elem;
1011 for (Offset i = 1; i < count; ++i)
1013 ElementType val = dataset_get(obj, vAcc[ind + i], element);
1014 if (val < min_elem) min_elem = val;
1015 if (val > max_elem) max_elem = val;
1027 Derived& obj,
const Offset left,
const Offset right,
BoundingBox& bbox)
1029 NodePtr node = obj.pool.template allocate<Node>();
1032 if ((right - left) <=
static_cast<Offset
>(obj.m_leaf_max_size))
1034 node->
child1 = node->child2 =
nullptr;
1039 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i)
1041 bbox[i].low = dataset_get(obj, obj.vAcc[left], i);
1042 bbox[i].high = dataset_get(obj, obj.vAcc[left], i);
1044 for (Offset k = left + 1; k < right; ++k)
1046 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i)
1048 if (bbox[i].low > dataset_get(obj, obj.vAcc[k], i))
1049 bbox[i].low = dataset_get(obj, obj.vAcc[k], i);
1050 if (bbox[i].high < dataset_get(obj, obj.vAcc[k], i))
1051 bbox[i].high = dataset_get(obj, obj.vAcc[k], i);
1059 DistanceType cutval;
1060 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1065 left_bbox[cutfeat].high = cutval;
1066 node->
child1 = divideTree(obj, left, left + idx, left_bbox);
1069 right_bbox[cutfeat].low = cutval;
1070 node->child2 = divideTree(obj, left + idx, right, right_bbox);
1072 node->
node_type.sub.divlow = left_bbox[cutfeat].high;
1073 node->
node_type.sub.divhigh = right_bbox[cutfeat].low;
1075 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i)
1077 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1078 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1086 Derived& obj, Offset ind, Size count, Offset& index, Dimension& cutfeat,
1087 DistanceType& cutval,
const BoundingBox& bbox)
1089 const auto EPS =
static_cast<DistanceType
>(0.00001);
1090 ElementType max_span = bbox[0].high - bbox[0].low;
1091 for (Dimension i = 1; i < (DIM > 0 ? DIM : obj.dim); ++i)
1093 ElementType span = bbox[i].high - bbox[i].low;
1094 if (span > max_span) { max_span = span; }
1096 ElementType max_spread = -1;
1098 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i)
1100 ElementType span = bbox[i].high - bbox[i].low;
1101 if (span > (1 - EPS) * max_span)
1103 ElementType min_elem, max_elem;
1104 computeMinMax(obj, ind, count, i, min_elem, max_elem);
1105 ElementType spread = max_elem - min_elem;
1106 if (spread > max_spread)
1109 max_spread = spread;
1114 DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;
1115 ElementType min_elem, max_elem;
1116 computeMinMax(obj, ind, count, cutfeat, min_elem, max_elem);
1118 if (split_val < min_elem)
1120 else if (split_val > max_elem)
1126 planeSplit(obj, ind, count, cutfeat, cutval, lim1, lim2);
1128 if (lim1 > count / 2)
1130 else if (lim2 < count / 2)
1146 Derived& obj, Offset ind,
const Size count, Dimension cutfeat,
1147 DistanceType& cutval, Offset& lim1, Offset& lim2)
1151 Offset right = count - 1;
1154 while (left <= right &&
1155 dataset_get(obj, vAcc[ind + left], cutfeat) < cutval)
1157 while (right && left <= right &&
1158 dataset_get(obj, vAcc[ind + right], cutfeat) >= cutval)
1160 if (left > right || !right)
1162 std::swap(vAcc[ind + left], vAcc[ind + right]);
1173 while (left <= right &&
1174 dataset_get(obj, vAcc[ind + left], cutfeat) <= cutval)
1176 while (right && left <= right &&
1177 dataset_get(obj, vAcc[ind + right], cutfeat) > cutval)
1179 if (left > right || !right)
1181 std::swap(vAcc[ind + left], vAcc[ind + right]);
1188 DistanceType computeInitialDistances(
1189 const Derived& obj,
const ElementType* vec,
1190 distance_vector_t& dists)
const
1193 DistanceType distsq = DistanceType();
1195 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i)
1197 if (vec[i] < obj.root_bbox[i].low)
1200 obj.distance.accum_dist(vec[i], obj.root_bbox[i].low, i);
1203 if (vec[i] > obj.root_bbox[i].high)
1206 obj.distance.accum_dist(vec[i], obj.root_bbox[i].high, i);
1213 void save_tree(Derived& obj, std::ostream& stream, NodePtr tree)
1215 save_value(stream, *tree);
1216 if (tree->child1 !=
nullptr) { save_tree(obj, stream, tree->child1); }
1217 if (tree->child2 !=
nullptr) { save_tree(obj, stream, tree->child2); }
1220 void load_tree(Derived& obj, std::istream& stream, NodePtr& tree)
1222 tree = obj.pool.template allocate<Node>();
1223 load_value(stream, *tree);
1224 if (tree->child1 !=
nullptr) { load_tree(obj, stream, tree->child1); }
1225 if (tree->child2 !=
nullptr) { load_tree(obj, stream, tree->child2); }
1235 save_value(stream, obj.m_size);
1236 save_value(stream, obj.dim);
1237 save_value(stream, obj.root_bbox);
1238 save_value(stream, obj.m_leaf_max_size);
1239 save_value(stream, obj.vAcc);
1240 save_tree(obj, stream, obj.root_node);
1250 load_value(stream, obj.m_size);
1251 load_value(stream, obj.dim);
1252 load_value(stream, obj.root_bbox);
1253 load_value(stream, obj.m_leaf_max_size);
1254 load_value(stream, obj.vAcc);
1255 load_tree(obj, stream, obj.root_node);
1301 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
1302 typename AccessorType = uint32_t>
1305 KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, AccessorType>,
1306 Distance, DatasetAdaptor, DIM, AccessorType>
1312 Distance, DatasetAdaptor, DIM, AccessorType>&) =
delete;
1325 Distance, DatasetAdaptor, DIM, AccessorType>,
1326 Distance, DatasetAdaptor, DIM, AccessorType>;
1328 using Offset =
typename BaseClassRef::Offset;
1329 using Size =
typename BaseClassRef::Size;
1330 using Dimension =
typename BaseClassRef::Dimension;
1332 using ElementType =
typename BaseClassRef::ElementType;
1333 using DistanceType =
typename BaseClassRef::DistanceType;
1335 using Node =
typename BaseClassRef::Node;
1336 using NodePtr = Node*;
1338 using Interval =
typename BaseClassRef::Interval;
1368 template <
class... Args>
1370 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1372 : dataset(inputData),
1373 index_params(params),
1374 distance(inputData, std::forward<Args>(args)...)
1376 init(dimensionality, params);
1380 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1382 : dataset(inputData), index_params(params), distance(inputData)
1384 init(dimensionality, params);
1389 const Dimension dimensionality,
1390 const KDTreeSingleIndexAdaptorParams& params)
1392 BaseClassRef::root_node =
nullptr;
1393 BaseClassRef::m_size = dataset.kdtree_get_point_count();
1394 BaseClassRef::m_size_at_index_build = BaseClassRef::m_size;
1395 BaseClassRef::dim = dimensionality;
1396 if (DIM > 0) BaseClassRef::dim = DIM;
1397 BaseClassRef::m_leaf_max_size = params.leaf_max_size;
1399 if (!(params.flags &
1400 KDTreeSingleIndexAdaptorFlags::SkipInitialBuildIndex))
1412 BaseClassRef::m_size = dataset.kdtree_get_point_count();
1413 BaseClassRef::m_size_at_index_build = BaseClassRef::m_size;
1415 this->freeIndex(*
this);
1416 BaseClassRef::m_size_at_index_build = BaseClassRef::m_size;
1417 if (BaseClassRef::m_size == 0)
return;
1418 computeBoundingBox(BaseClassRef::root_bbox);
1419 BaseClassRef::root_node = this->divideTree(
1420 *
this, 0, BaseClassRef::m_size,
1421 BaseClassRef::root_bbox);
1440 template <
typename RESULTSET>
1442 RESULTSET& result,
const ElementType* vec,
1446 if (this->size(*
this) == 0)
return false;
1447 if (!BaseClassRef::root_node)
1448 throw std::runtime_error(
1449 "[nanoflann] findNeighbors() called before building the "
1451 float epsError = 1 + searchParams.
eps;
1455 auto zero =
static_cast<decltype(result.worstDist())
>(0);
1457 dists, (DIM > 0 ? DIM : BaseClassRef::dim),
1459 DistanceType distsq = this->computeInitialDistances(*
this, vec, dists);
1461 result, vec, BaseClassRef::root_node, distsq, dists,
1464 return result.full();
1477 const ElementType* query_point,
const Size num_closest,
1478 AccessorType* out_indices, DistanceType* out_distances_sq,
1479 const int = 10)
const
1483 resultSet.init(out_indices, out_distances_sq);
1485 return resultSet.size();
1505 const ElementType* query_point,
const DistanceType& radius,
1506 std::vector<std::pair<AccessorType, DistanceType>>& IndicesDists,
1510 radius, IndicesDists);
1512 radiusSearchCustomCallback(query_point, resultSet, searchParams);
1524 template <
class SEARCH_CALLBACK>
1526 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
1529 this->findNeighbors(resultSet, query_point, searchParams);
1530 return resultSet.size();
1541 BaseClassRef::m_size = dataset.kdtree_get_point_count();
1542 if (BaseClassRef::vAcc.size() != BaseClassRef::m_size)
1543 BaseClassRef::vAcc.resize(BaseClassRef::m_size);
1544 for (Size i = 0; i < BaseClassRef::m_size; i++)
1545 BaseClassRef::vAcc[i] = i;
1548 void computeBoundingBox(BoundingBox& bbox)
1550 resize(bbox, (DIM > 0 ? DIM : BaseClassRef::dim));
1551 if (dataset.kdtree_get_bbox(bbox))
1557 const Size N = dataset.kdtree_get_point_count();
1559 throw std::runtime_error(
1560 "[nanoflann] computeBoundingBox() called but "
1561 "no data points found.");
1562 for (Dimension i = 0; i < (DIM > 0 ? DIM : BaseClassRef::dim); ++i)
1564 bbox[i].low = bbox[i].high =
1565 this->dataset_get(*
this, BaseClassRef::vAcc[0], i);
1567 for (Offset k = 1; k < N; ++k)
1569 for (Dimension i = 0; i < (DIM > 0 ? DIM : BaseClassRef::dim);
1572 if (this->dataset_get(*
this, BaseClassRef::vAcc[k], i) <
1575 this->dataset_get(*
this, BaseClassRef::vAcc[k], i);
1576 if (this->dataset_get(*
this, BaseClassRef::vAcc[k], i) >
1579 this->dataset_get(*
this, BaseClassRef::vAcc[k], i);
1591 template <
class RESULTSET>
1593 RESULTSET& result_set,
const ElementType* vec,
const NodePtr node,
1595 const float epsError)
const
1598 if ((node->child1 ==
nullptr) && (node->child2 ==
nullptr))
1602 DistanceType worst_dist = result_set.worstDist();
1603 for (Offset i = node->node_type.lr.left;
1604 i < node->node_type.lr.right; ++i)
1606 const AccessorType accessor =
1607 BaseClassRef::vAcc[i];
1608 DistanceType dist = distance.evalMetric(
1609 vec, accessor, (DIM > 0 ? DIM : BaseClassRef::dim));
1610 if (dist < worst_dist)
1612 if (!result_set.addPoint(dist, BaseClassRef::vAcc[i]))
1624 Dimension idx = node->node_type.sub.divfeat;
1625 ElementType val = vec[idx];
1626 DistanceType diff1 = val - node->node_type.sub.divlow;
1627 DistanceType diff2 = val - node->node_type.sub.divhigh;
1631 DistanceType cut_dist;
1632 if ((diff1 + diff2) < 0)
1634 bestChild = node->child1;
1635 otherChild = node->child2;
1637 distance.accum_dist(val, node->node_type.sub.divhigh, idx);
1641 bestChild = node->child2;
1642 otherChild = node->child1;
1644 distance.accum_dist(val, node->node_type.sub.divlow, idx);
1649 result_set, vec, bestChild, mindistsq, dists, epsError))
1656 DistanceType dst = dists[idx];
1657 mindistsq = mindistsq + cut_dist - dst;
1658 dists[idx] = cut_dist;
1659 if (mindistsq * epsError <= result_set.worstDist())
1662 result_set, vec, otherChild, mindistsq, dists, epsError))
1679 void saveIndex(std::ostream& stream) { this->saveIndex_(*
this, stream); }
1686 void loadIndex(std::istream& stream) { this->loadIndex_(*
this, stream); }
1727 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
1728 typename AccessorType = uint32_t>
1731 KDTreeSingleIndexDynamicAdaptor_<
1732 Distance, DatasetAdaptor, DIM, AccessorType>,
1733 Distance, DatasetAdaptor, DIM, AccessorType>
1743 std::vector<int>& treeIndex;
1749 Distance, DatasetAdaptor, DIM, AccessorType>,
1750 Distance, DatasetAdaptor, DIM, AccessorType>;
1752 using ElementType =
typename BaseClassRef::ElementType;
1753 using DistanceType =
typename BaseClassRef::DistanceType;
1755 using Offset =
typename BaseClassRef::Offset;
1756 using Size =
typename BaseClassRef::Size;
1757 using Dimension =
typename BaseClassRef::Dimension;
1759 using Node =
typename BaseClassRef::Node;
1760 using NodePtr = Node*;
1762 using Interval =
typename BaseClassRef::Interval;
1787 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1788 std::vector<int>& treeIndex_,
1791 : dataset(inputData),
1792 index_params(params),
1793 treeIndex(treeIndex_),
1796 BaseClassRef::root_node =
nullptr;
1797 BaseClassRef::m_size = 0;
1798 BaseClassRef::m_size_at_index_build = 0;
1799 BaseClassRef::dim = dimensionality;
1800 if (DIM > 0) BaseClassRef::dim = DIM;
1801 BaseClassRef::m_leaf_max_size = params.leaf_max_size;
1813 std::swap(BaseClassRef::vAcc, tmp.BaseClassRef::vAcc);
1815 BaseClassRef::m_leaf_max_size, tmp.BaseClassRef::m_leaf_max_size);
1816 std::swap(index_params, tmp.index_params);
1817 std::swap(treeIndex, tmp.treeIndex);
1818 std::swap(BaseClassRef::m_size, tmp.BaseClassRef::m_size);
1820 BaseClassRef::m_size_at_index_build,
1821 tmp.BaseClassRef::m_size_at_index_build);
1822 std::swap(BaseClassRef::root_node, tmp.BaseClassRef::root_node);
1823 std::swap(BaseClassRef::root_bbox, tmp.BaseClassRef::root_bbox);
1824 std::swap(BaseClassRef::pool, tmp.BaseClassRef::pool);
1833 BaseClassRef::m_size = BaseClassRef::vAcc.size();
1834 this->freeIndex(*
this);
1835 BaseClassRef::m_size_at_index_build = BaseClassRef::m_size;
1836 if (BaseClassRef::m_size == 0)
return;
1837 computeBoundingBox(BaseClassRef::root_bbox);
1838 BaseClassRef::root_node = this->divideTree(
1839 *
this, 0, BaseClassRef::m_size,
1840 BaseClassRef::root_bbox);
1859 template <
typename RESULTSET>
1861 RESULTSET& result,
const ElementType* vec,
1865 if (this->size(*
this) == 0)
return false;
1866 if (!BaseClassRef::root_node)
return false;
1867 float epsError = 1 + searchParams.
eps;
1873 dists, (DIM > 0 ? DIM : BaseClassRef::dim),
1874 static_cast<typename distance_vector_t::value_type
>(0));
1875 DistanceType distsq = this->computeInitialDistances(*
this, vec, dists);
1877 result, vec, BaseClassRef::root_node, distsq, dists,
1880 return result.full();
1893 const ElementType* query_point,
const Size num_closest,
1894 AccessorType* out_indices, DistanceType* out_distances_sq,
1895 const int = 10)
const
1899 resultSet.init(out_indices, out_distances_sq);
1901 return resultSet.size();
1921 const ElementType* query_point,
const DistanceType& radius,
1922 std::vector<std::pair<AccessorType, DistanceType>>& IndicesDists,
1926 radius, IndicesDists);
1927 const size_t nFound =
1928 radiusSearchCustomCallback(query_point, resultSet, searchParams);
1940 template <
class SEARCH_CALLBACK>
1942 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
1945 this->findNeighbors(resultSet, query_point, searchParams);
1946 return resultSet.size();
1952 void computeBoundingBox(BoundingBox& bbox)
1954 resize(bbox, (DIM > 0 ? DIM : BaseClassRef::dim));
1956 if (dataset.kdtree_get_bbox(bbox))
1962 const Size N = BaseClassRef::m_size;
1964 throw std::runtime_error(
1965 "[nanoflann] computeBoundingBox() called but "
1966 "no data points found.");
1967 for (Dimension i = 0; i < (DIM > 0 ? DIM : BaseClassRef::dim); ++i)
1969 bbox[i].low = bbox[i].high =
1970 this->dataset_get(*
this, BaseClassRef::vAcc[0], i);
1972 for (Offset k = 1; k < N; ++k)
1974 for (Dimension i = 0; i < (DIM > 0 ? DIM : BaseClassRef::dim);
1977 if (this->dataset_get(*
this, BaseClassRef::vAcc[k], i) <
1980 this->dataset_get(*
this, BaseClassRef::vAcc[k], i);
1981 if (this->dataset_get(*
this, BaseClassRef::vAcc[k], i) >
1984 this->dataset_get(*
this, BaseClassRef::vAcc[k], i);
1994 template <
class RESULTSET>
1996 RESULTSET& result_set,
const ElementType* vec,
const NodePtr node,
1998 const float epsError)
const
2001 if ((node->child1 ==
nullptr) && (node->child2 ==
nullptr))
2005 DistanceType worst_dist = result_set.worstDist();
2006 for (Offset i = node->node_type.lr.left;
2007 i < node->node_type.lr.right; ++i)
2009 const AccessorType index =
2010 BaseClassRef::vAcc[i];
2011 if (treeIndex[index] == -1)
continue;
2012 DistanceType dist = distance.evalMetric(
2013 vec, index, (DIM > 0 ? DIM : BaseClassRef::dim));
2014 if (dist < worst_dist)
2016 if (!result_set.addPoint(
2017 static_cast<typename RESULTSET::DistanceType
>(dist),
2018 static_cast<typename RESULTSET::IndexType
>(
2019 BaseClassRef::vAcc[i])))
2031 Dimension idx = node->node_type.sub.divfeat;
2032 ElementType val = vec[idx];
2033 DistanceType diff1 = val - node->node_type.sub.divlow;
2034 DistanceType diff2 = val - node->node_type.sub.divhigh;
2038 DistanceType cut_dist;
2039 if ((diff1 + diff2) < 0)
2041 bestChild = node->child1;
2042 otherChild = node->child2;
2044 distance.accum_dist(val, node->node_type.sub.divhigh, idx);
2048 bestChild = node->child2;
2049 otherChild = node->child1;
2051 distance.accum_dist(val, node->node_type.sub.divlow, idx);
2055 searchLevel(result_set, vec, bestChild, mindistsq, dists, epsError);
2057 DistanceType dst = dists[idx];
2058 mindistsq = mindistsq + cut_dist - dst;
2059 dists[idx] = cut_dist;
2060 if (mindistsq * epsError <= result_set.worstDist())
2063 result_set, vec, otherChild, mindistsq, dists, epsError);
2074 void saveIndex(std::ostream& stream) { this->saveIndex_(*
this, stream); }
2081 void loadIndex(std::istream& stream) { this->loadIndex_(*
this, stream); }
2099 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
2100 typename AccessorType = uint32_t>
2104 using ElementType =
typename Distance::ElementType;
2105 using DistanceType =
typename Distance::DistanceType;
2108 Distance, DatasetAdaptor, DIM>::Offset;
2110 Distance, DatasetAdaptor, DIM>::Size;
2112 Distance, DatasetAdaptor, DIM>::Dimension;
2115 Size m_leaf_max_size;
2128 std::unordered_set<int> removedPoints;
2135 Distance, DatasetAdaptor, DIM, AccessorType>;
2136 std::vector<index_container_t> index;
2148 int First0Bit(AccessorType num)
2162 using my_kd_tree_t = KDTreeSingleIndexDynamicAdaptor_<
2163 Distance, DatasetAdaptor, DIM, AccessorType>;
2164 std::vector<my_kd_tree_t> index_(
2166 my_kd_tree_t(dim , dataset, treeIndex, index_params));
2189 const int dimensionality,
const DatasetAdaptor& inputData,
2192 const size_t maximumPointCount = 1000000000U)
2193 : dataset(inputData), index_params(params), distance(inputData)
2195 treeCount =
static_cast<size_t>(std::log2(maximumPointCount)) + 1;
2197 dim = dimensionality;
2199 if (DIM > 0) dim = DIM;
2200 m_leaf_max_size = params.leaf_max_size;
2202 const size_t num_initial_points = dataset.kdtree_get_point_count();
2203 if (num_initial_points > 0) { addPoints(0, num_initial_points - 1); }
2209 Distance, DatasetAdaptor, DIM, AccessorType>&) =
delete;
2214 const Size count = end - start + 1;
2216 treeIndex.resize(treeIndex.size() + count);
2217 for (AccessorType idx = start; idx <= end; idx++)
2219 const int pos = First0Bit(pointCount);
2220 maxIndex = std::max(pos, maxIndex);
2221 treeIndex[pointCount] = pos;
2223 const auto it = removedPoints.find(idx);
2224 if (it != removedPoints.end())
2226 removedPoints.erase(it);
2227 treeIndex[idx] = pos;
2230 for (
int i = 0; i < pos; i++)
2232 for (
int j = 0; j < static_cast<int>(index[i].vAcc.size()); j++)
2234 index[pos].vAcc.push_back(index[i].vAcc[j]);
2235 if (treeIndex[index[i].vAcc[j]] != -1)
2236 treeIndex[index[i].vAcc[j]] = pos;
2238 index[i].vAcc.clear();
2240 index[pos].vAcc.push_back(idx);
2244 for (
int i = 0; i <= maxIndex; ++i)
2246 index[i].freeIndex(index[i]);
2247 if (!index[i].vAcc.empty()) index[i].buildIndex();
2254 if (idx >= pointCount)
return;
2255 removedPoints.insert(idx);
2256 treeIndex[idx] = -1;
2272 template <
typename RESULTSET>
2274 RESULTSET& result,
const ElementType* vec,
2277 for (
size_t i = 0; i < treeCount; i++)
2279 index[i].findNeighbors(result, &vec[0], searchParams);
2281 return result.full();
2311 bool row_major =
true>
2316 using num_t =
typename MatrixType::Scalar;
2317 using IndexType =
typename MatrixType::Index;
2318 using metric_t =
typename Distance::template traits<
2319 num_t,
self_t, IndexType>::distance_t;
2323 row_major ? MatrixType::ColsAtCompileTime
2324 : MatrixType::RowsAtCompileTime,
2331 using Size =
typename index_t::Size;
2332 using Dimension =
typename index_t::Dimension;
2336 const Dimension dimensionality,
2337 const std::reference_wrapper<const MatrixType>& mat,
2338 const int leaf_max_size = 10)
2339 : m_data_matrix(mat)
2341 const auto dims = row_major ? mat.get().cols() : mat.get().rows();
2342 if (
static_cast<Dimension
>(dims) != dimensionality)
2343 throw std::runtime_error(
2344 "Error: 'dimensionality' must match column count in data "
2346 if (DIM > 0 &&
static_cast<int32_t
>(dims) != DIM)
2347 throw std::runtime_error(
2348 "Data set dimensionality does not match the 'DIM' template "
2361 const std::reference_wrapper<const MatrixType> m_data_matrix;
2370 const num_t* query_point,
const Size num_closest,
2371 IndexType* out_indices, num_t* out_distances_sq,
2372 const int = 10)
const
2375 resultSet.init(out_indices, out_distances_sq);
2382 const self_t& derived()
const {
return *
this; }
2383 self_t& derived() {
return *
this; }
2386 inline Size kdtree_get_point_count()
const
2389 return m_data_matrix.get().rows();
2391 return m_data_matrix.get().cols();
2395 inline num_t kdtree_get_pt(
const IndexType idx,
size_t dim)
const
2398 return m_data_matrix.get().coeff(idx, IndexType(dim));
2400 return m_data_matrix.get().coeff(IndexType(dim), idx);
2408 template <
class BBOX>
2409 bool kdtree_get_bbox(BBOX& )
const
Definition: nanoflann.hpp:896
Size veclen(const Derived &obj)
Definition: nanoflann.hpp:985
NodePtr divideTree(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox)
Definition: nanoflann.hpp:1026
PooledAllocator pool
Definition: nanoflann.hpp:979
Dimension dim
Dimensionality of each data point.
Definition: nanoflann.hpp:956
Size m_size_at_index_build
Definition: nanoflann.hpp:954
ElementType dataset_get(const Derived &obj, AccessorType element, Dimension component) const
Helper accessor to the dataset points:
Definition: nanoflann.hpp:988
Size size(const Derived &obj) const
Definition: nanoflann.hpp:982
BoundingBox root_bbox
Definition: nanoflann.hpp:970
Size usedMemory(Derived &obj)
Definition: nanoflann.hpp:998
void saveIndex_(Derived &obj, std::ostream &stream)
Definition: nanoflann.hpp:1233
std::vector< AccessorType > vAcc
Definition: nanoflann.hpp:913
void planeSplit(Derived &obj, Offset ind, const Size count, Dimension cutfeat, DistanceType &cutval, Offset &lim1, Offset &lim2)
Definition: nanoflann.hpp:1145
void freeIndex(Derived &obj)
Definition: nanoflann.hpp:900
void loadIndex_(Derived &obj, std::istream &stream)
Definition: nanoflann.hpp:1248
typename array_or_vector_selector< DIM, Interval >::container_t BoundingBox
Definition: nanoflann.hpp:961
Size m_size
Number of current points in the dataset.
Definition: nanoflann.hpp:953
typename array_or_vector_selector< DIM, DistanceType >::container_t distance_vector_t
Definition: nanoflann.hpp:966
Definition: nanoflann.hpp:1307
KDTreeSingleIndexAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms, Args &&... args)
Definition: nanoflann.hpp:1369
void saveIndex(std::ostream &stream)
Definition: nanoflann.hpp:1679
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< std::pair< AccessorType, DistanceType >> &IndicesDists, const SearchParams &searchParams) const
Definition: nanoflann.hpp:1504
void buildIndex()
Definition: nanoflann.hpp:1410
bool searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, distance_vector_t &dists, const float epsError) const
Definition: nanoflann.hpp:1592
KDTreeSingleIndexAdaptor(const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, AccessorType > &)=delete
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParams &searchParams=SearchParams()) const
Definition: nanoflann.hpp:1525
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
Definition: nanoflann.hpp:1441
typename BaseClassRef::distance_vector_t distance_vector_t
Definition: nanoflann.hpp:1346
Size knnSearch(const ElementType *query_point, const Size num_closest, AccessorType *out_indices, DistanceType *out_distances_sq, const int=10) const
Definition: nanoflann.hpp:1476
void init_vind()
Definition: nanoflann.hpp:1538
void loadIndex(std::istream &stream)
Definition: nanoflann.hpp:1686
const DatasetAdaptor & dataset
The source of our data.
Definition: nanoflann.hpp:1317
typename BaseClassRef::BoundingBox BoundingBox
Definition: nanoflann.hpp:1342
Definition: nanoflann.hpp:1734
const DatasetAdaptor & dataset
The source of our data.
Definition: nanoflann.hpp:1739
void searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, distance_vector_t &dists, const float epsError) const
Definition: nanoflann.hpp:1995
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParams &searchParams=SearchParams()) const
Definition: nanoflann.hpp:1941
typename BaseClassRef::distance_vector_t distance_vector_t
Definition: nanoflann.hpp:1769
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< std::pair< AccessorType, DistanceType >> &IndicesDists, const SearchParams &searchParams) const
Definition: nanoflann.hpp:1920
void buildIndex()
Definition: nanoflann.hpp:1831
void loadIndex(std::istream &stream)
Definition: nanoflann.hpp:2081
KDTreeSingleIndexDynamicAdaptor_(const KDTreeSingleIndexDynamicAdaptor_ &rhs)=default
typename BaseClassRef::BoundingBox BoundingBox
Definition: nanoflann.hpp:1765
KDTreeSingleIndexDynamicAdaptor_ operator=(const KDTreeSingleIndexDynamicAdaptor_ &rhs)
Definition: nanoflann.hpp:1809
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
Definition: nanoflann.hpp:1860
KDTreeSingleIndexDynamicAdaptor_(const Dimension dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex_, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams())
Definition: nanoflann.hpp:1786
Size knnSearch(const ElementType *query_point, const Size num_closest, AccessorType *out_indices, DistanceType *out_distances_sq, const int=10) const
Definition: nanoflann.hpp:1892
void saveIndex(std::ostream &stream)
Definition: nanoflann.hpp:2074
Definition: nanoflann.hpp:2102
void removePoint(size_t idx)
Definition: nanoflann.hpp:2252
const DatasetAdaptor & dataset
The source of our data.
Definition: nanoflann.hpp:2122
std::vector< int > treeIndex
Definition: nanoflann.hpp:2125
void addPoints(AccessorType start, AccessorType end)
Definition: nanoflann.hpp:2212
Dimension dim
Dimensionality of each data point.
Definition: nanoflann.hpp:2132
KDTreeSingleIndexDynamicAdaptor(const KDTreeSingleIndexDynamicAdaptor< Distance, DatasetAdaptor, DIM, AccessorType > &)=delete
const std::vector< index_container_t > & getAllIndices() const
Definition: nanoflann.hpp:2141
KDTreeSingleIndexDynamicAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams(), const size_t maximumPointCount=1000000000U)
Definition: nanoflann.hpp:2188
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
Definition: nanoflann.hpp:2273
Definition: nanoflann.hpp:163
bool addPoint(DistanceType dist, IndexType index)
Definition: nanoflann.hpp:199
Definition: nanoflann.hpp:740
T * allocate(const size_t count=1)
Definition: nanoflann.hpp:851
~PooledAllocator()
Definition: nanoflann.hpp:775
void free_all()
Definition: nanoflann.hpp:778
PooledAllocator()
Definition: nanoflann.hpp:770
void * malloc(const size_t req_size)
Definition: nanoflann.hpp:794
Definition: nanoflann.hpp:253
std::pair< IndexType, DistanceType > worst_item() const
Definition: nanoflann.hpp:296
bool addPoint(DistanceType dist, IndexType index)
Definition: nanoflann.hpp:283
const size_t WORDSIZE
Definition: nanoflann.hpp:736
T * allocate(size_t count=1)
Definition: nanoflann.hpp:715
T pi_const()
Definition: nanoflann.hpp:84
std::enable_if< has_assign< Container >::value, void >::type assign(Container &c, const size_t nElements, const T &value)
Definition: nanoflann.hpp:141
std::enable_if< has_resize< Container >::value, void >::type resize(Container &c, const size_t nElements)
Definition: nanoflann.hpp:119
Definition: nanoflann.hpp:239
bool operator()(const PairType &p1, const PairType &p2) const
Definition: nanoflann.hpp:242
Definition: nanoflann.hpp:945
Definition: nanoflann.hpp:922
DistanceType divhigh
The values used for subdivision.
Definition: nanoflann.hpp:935
Dimension divfeat
Dimension used for subdivision.
Definition: nanoflann.hpp:933
Offset right
Indices of points in leaf node.
Definition: nanoflann.hpp:929
union nanoflann::KDTreeBaseClass::Node::@0 node_type
Node * child1
Definition: nanoflann.hpp:939
Definition: nanoflann.hpp:2313
void query(const num_t *query_point, const Size num_closest, IndexType *out_indices, num_t *out_distances_sq, const int=10) const
Definition: nanoflann.hpp:2369
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:2335
KDTreeEigenMatrixAdaptor(const self_t &)=delete
typename index_t::Offset Offset
Definition: nanoflann.hpp:2330
Definition: nanoflann.hpp:674
Definition: nanoflann.hpp:365
Definition: nanoflann.hpp:427
Definition: nanoflann.hpp:492
Definition: nanoflann.hpp:348
Definition: nanoflann.hpp:537
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition: nanoflann.hpp:555
Definition: nanoflann.hpp:582
Definition: nanoflann.hpp:688
bool sorted
distance (default: true)
Definition: nanoflann.hpp:699
SearchParams(int checks_IGNORED_=32, float eps_=0, bool sorted_=true)
Definition: nanoflann.hpp:691
float eps
search for eps-approximate neighbours (default: 0)
Definition: nanoflann.hpp:698
int checks
Definition: nanoflann.hpp:696
Definition: nanoflann.hpp:867
Definition: nanoflann.hpp:106
Definition: nanoflann.hpp:95
Definition: nanoflann.hpp:612
Definition: nanoflann.hpp:609
Definition: nanoflann.hpp:621
Definition: nanoflann.hpp:630
Definition: nanoflann.hpp:627
Definition: nanoflann.hpp:618
Definition: nanoflann.hpp:639
Definition: nanoflann.hpp:636
Definition: nanoflann.hpp:648
Definition: nanoflann.hpp:645