57 #include <unordered_set>
61 #define NANOFLANN_VERSION 0x142
64 #if !defined(NOMINMAX) && \
65 (defined(_WIN32) || defined(_WIN32_) || defined(WIN32) || defined(_WIN64))
82 return static_cast<T
>(3.14159265358979323846);
89 template <
typename T,
typename =
int>
100 template <
typename T,
typename =
int>
105 template <
typename T>
114 template <
typename Container>
115 inline typename std::enable_if<has_resize<Container>::value,
void>::type
resize(
116 Container& c,
const size_t nElements)
125 template <
typename Container>
126 inline typename std::enable_if<!has_resize<Container>::value,
void>::type
127 resize(Container& c,
const size_t nElements)
129 if (nElements != c.size())
130 throw std::logic_error(
"Try to change the size of a std::array.");
136 template <
typename Container,
typename T>
137 inline typename std::enable_if<has_assign<Container>::value,
void>::type
assign(
138 Container& c,
const size_t nElements,
const T& value)
140 c.assign(nElements, value);
146 template <
typename Container,
typename T>
147 inline typename std::enable_if<!has_assign<Container>::value,
void>::type
148 assign(Container& c,
const size_t nElements,
const T& value)
150 for (
size_t i = 0; i < nElements; i++) c[i] = value;
156 typename _DistanceType,
typename _IndexType = size_t,
157 typename _CountType =
size_t>
161 using DistanceType = _DistanceType;
162 using IndexType = _IndexType;
163 using CountType = _CountType;
173 : indices(0), dists(0), capacity(capacity_), count(0)
177 inline void init(IndexType* indices_, DistanceType* dists_)
183 dists[capacity - 1] = (std::numeric_limits<DistanceType>::max)();
186 inline CountType size()
const {
return count; }
188 inline bool full()
const {
return count == capacity; }
195 inline bool addPoint(DistanceType dist, IndexType index)
198 for (i = count; i > 0; --i)
200 #ifdef NANOFLANN_FIRST_MATCH
203 if ((dists[i - 1] > dist) ||
204 ((dist == dists[i - 1]) && (indices[i - 1] > index)))
207 if (dists[i - 1] > dist)
212 dists[i] = dists[i - 1];
213 indices[i] = indices[i - 1];
224 if (count < capacity) count++;
230 inline DistanceType worstDist()
const {
return dists[capacity - 1]; }
237 template <
typename PairType>
238 inline bool operator()(
const PairType& p1,
const PairType& p2)
const
240 return p1.second < p2.second;
247 template <
typename _DistanceType,
typename _IndexType =
size_t>
251 using DistanceType = _DistanceType;
252 using IndexType = _IndexType;
255 const DistanceType radius;
257 std::vector<std::pair<IndexType, DistanceType>>& m_indices_dists;
260 DistanceType radius_,
261 std::vector<std::pair<IndexType, DistanceType>>& indices_dists)
262 : radius(radius_), m_indices_dists(indices_dists)
267 inline void init() { clear(); }
268 inline void clear() { m_indices_dists.clear(); }
270 inline size_t size()
const {
return m_indices_dists.size(); }
272 inline bool full()
const {
return true; }
279 inline bool addPoint(DistanceType dist, IndexType index)
282 m_indices_dists.push_back(std::make_pair(index, dist));
286 inline DistanceType worstDist()
const {
return radius; }
294 if (m_indices_dists.empty())
295 throw std::runtime_error(
296 "Cannot invoke RadiusResultSet::worst_item() on "
297 "an empty list of results.");
298 using DistIt =
typename std::vector<
299 std::pair<IndexType, DistanceType>>::const_iterator;
300 DistIt it = std::max_element(
310 template <
typename T>
311 void save_value(std::ostream& stream,
const T& value)
313 stream.write(
reinterpret_cast<const char*
>(&value),
sizeof(T));
316 template <
typename T>
317 void save_value(std::ostream& stream,
const std::vector<T>& value)
319 size_t size = value.size();
320 stream.write(
reinterpret_cast<const char*
>(&size),
sizeof(
size_t));
321 stream.write(
reinterpret_cast<const char*
>(value.data()),
sizeof(T) * size);
324 template <
typename T>
325 void load_value(std::istream& stream, T& value)
327 stream.read(
reinterpret_cast<char*
>(&value),
sizeof(T));
330 template <
typename T>
331 void load_value(std::istream& stream, std::vector<T>& value)
334 stream.read(
reinterpret_cast<char*
>(&size),
sizeof(
size_t));
336 stream.read(
reinterpret_cast<char*
>(value.data()),
sizeof(T) * size);
358 class T,
class DataSource,
typename _DistanceType = T,
359 typename AccessorType = uint32_t>
362 using ElementType = T;
363 using DistanceType = _DistanceType;
365 const DataSource& data_source;
367 L1_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
369 inline DistanceType evalMetric(
370 const T* a,
const AccessorType b_idx,
size_t size,
371 DistanceType worst_dist = -1)
const
373 DistanceType result = DistanceType();
374 const T* last = a + size;
375 const T* lastgroup = last - 3;
379 while (a < lastgroup)
381 const DistanceType diff0 =
382 std::abs(a[0] - data_source.kdtree_get_pt(b_idx, d++));
383 const DistanceType diff1 =
384 std::abs(a[1] - data_source.kdtree_get_pt(b_idx, d++));
385 const DistanceType diff2 =
386 std::abs(a[2] - data_source.kdtree_get_pt(b_idx, d++));
387 const DistanceType diff3 =
388 std::abs(a[3] - data_source.kdtree_get_pt(b_idx, d++));
389 result += diff0 + diff1 + diff2 + diff3;
391 if ((worst_dist > 0) && (result > worst_dist)) {
return result; }
397 result += std::abs(*a++ - data_source.kdtree_get_pt(b_idx, d++));
402 template <
typename U,
typename V>
403 inline DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
405 return std::abs(a - b);
420 class T,
class DataSource,
typename _DistanceType = T,
421 typename AccessorType = uint32_t>
424 using ElementType = T;
425 using DistanceType = _DistanceType;
427 const DataSource& data_source;
429 L2_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
431 inline DistanceType evalMetric(
432 const T* a,
const AccessorType b_idx,
size_t size,
433 DistanceType worst_dist = -1)
const
435 DistanceType result = DistanceType();
436 const T* last = a + size;
437 const T* lastgroup = last - 3;
441 while (a < lastgroup)
443 const DistanceType diff0 =
444 a[0] - data_source.kdtree_get_pt(b_idx, d++);
445 const DistanceType diff1 =
446 a[1] - data_source.kdtree_get_pt(b_idx, d++);
447 const DistanceType diff2 =
448 a[2] - data_source.kdtree_get_pt(b_idx, d++);
449 const DistanceType diff3 =
450 a[3] - data_source.kdtree_get_pt(b_idx, d++);
452 diff0 * diff0 + diff1 * diff1 + diff2 * diff2 + diff3 * diff3;
454 if ((worst_dist > 0) && (result > worst_dist)) {
return result; }
460 const DistanceType diff0 =
461 *a++ - data_source.kdtree_get_pt(b_idx, d++);
462 result += diff0 * diff0;
467 template <
typename U,
typename V>
468 inline DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
470 return (a - b) * (a - b);
485 class T,
class DataSource,
typename _DistanceType = T,
486 typename AccessorType = uint32_t>
489 using ElementType = T;
490 using DistanceType = _DistanceType;
492 const DataSource& data_source;
495 : data_source(_data_source)
499 inline DistanceType evalMetric(
500 const T* a,
const AccessorType b_idx,
size_t size)
const
502 DistanceType result = DistanceType();
503 for (
size_t i = 0; i < size; ++i)
505 const DistanceType diff =
506 a[i] - data_source.kdtree_get_pt(b_idx, i);
507 result += diff * diff;
512 template <
typename U,
typename V>
513 inline DistanceType accum_dist(
const U a,
const V b,
const size_t)
const
515 return (a - b) * (a - b);
530 class T,
class DataSource,
typename _DistanceType = T,
531 typename AccessorType = uint32_t>
534 using ElementType = T;
535 using DistanceType = _DistanceType;
537 const DataSource& data_source;
539 SO2_Adaptor(
const DataSource& _data_source) : data_source(_data_source) {}
541 inline DistanceType evalMetric(
542 const T* a,
const AccessorType b_idx,
size_t size)
const
545 a[size - 1], data_source.kdtree_get_pt(b_idx, size - 1), size - 1);
550 template <
typename U,
typename V>
551 inline DistanceType
accum_dist(
const U a,
const V b,
const size_t)
const
553 DistanceType result = DistanceType();
554 DistanceType PI = pi_const<DistanceType>();
558 else if (result < -PI)
575 class T,
class DataSource,
typename _DistanceType = T,
576 typename AccessorType = uint32_t>
579 using ElementType = T;
580 using DistanceType = _DistanceType;
586 : distance_L2_Simple(_data_source)
590 inline DistanceType evalMetric(
591 const T* a,
const AccessorType b_idx,
size_t size)
const
593 return distance_L2_Simple.evalMetric(a, b_idx, size);
596 template <
typename U,
typename V>
597 inline DistanceType accum_dist(
const U a,
const V b,
const size_t idx)
const
599 return distance_L2_Simple.accum_dist(a, b, idx);
606 template <
class T,
class DataSource,
typename AccessorType = u
int32_t>
615 template <
class T,
class DataSource,
typename AccessorType = u
int32_t>
624 template <
class T,
class DataSource,
typename AccessorType = u
int32_t>
633 template <
class T,
class DataSource,
typename AccessorType = u
int32_t>
642 template <
class T,
class DataSource,
typename AccessorType = u
int32_t>
654 enum class KDTreeSingleIndexAdaptorFlags
657 SkipInitialBuildIndex = 1
660 inline std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type operator&(
661 KDTreeSingleIndexAdaptorFlags lhs, KDTreeSingleIndexAdaptorFlags rhs)
664 typename std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type;
665 return static_cast<underlying
>(lhs) &
static_cast<underlying
>(rhs);
672 size_t _leaf_max_size = 10, KDTreeSingleIndexAdaptorFlags _flags =
673 KDTreeSingleIndexAdaptorFlags::None)
674 : leaf_max_size(_leaf_max_size), flags(_flags)
678 size_t leaf_max_size;
679 KDTreeSingleIndexAdaptorFlags flags;
687 SearchParams(
int checks_IGNORED_ = 32,
float eps_ = 0,
bool sorted_ =
true)
688 : checks(checks_IGNORED_), eps(eps_), sorted(sorted_)
710 template <
typename T>
713 T* mem =
static_cast<T*
>(::malloc(
sizeof(T) * count));
733 const size_t BLOCKSIZE = 8192;
743 using Offset = uint32_t;
744 using Size = uint32_t;
745 using Dimension = int32_t;
776 while (base !=
nullptr)
779 *(
static_cast<void**
>(base));
801 if (size > remaining)
803 wastedMemory += remaining;
806 const Size blocksize =
807 (size +
sizeof(
void*) + (
WORDSIZE - 1) > BLOCKSIZE)
808 ? size +
sizeof(
void*) + (
WORDSIZE - 1)
812 void* m = ::malloc(blocksize);
815 fprintf(stderr,
"Failed to allocate memory.\n");
816 throw std::bad_alloc();
820 static_cast<void**
>(m)[0] = base;
827 remaining = blocksize -
sizeof(
void*) - shift;
828 loc = (
static_cast<char*
>(m) +
sizeof(
void*) + shift);
831 loc =
static_cast<char*
>(loc) + size;
846 template <
typename T>
849 T* mem =
static_cast<T*
>(this->malloc(
sizeof(T) * count));
861 template <
int32_t DIM,
typename T>
864 using container_t = std::array<T, DIM>;
867 template <
typename T>
870 using container_t = std::vector<T>;
889 class Derived,
typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
890 typename AccessorType = uint32_t>
899 obj.root_node =
nullptr;
900 obj.m_size_at_index_build = 0;
903 using ElementType =
typename Distance::ElementType;
904 using DistanceType =
typename Distance::DistanceType;
909 std::vector<AccessorType>
vAcc;
911 using Offset =
typename decltype(vAcc)::size_type;
912 using Size =
typename decltype(vAcc)::size_type;
913 using Dimension = int32_t;
942 ElementType low, high;
947 Size m_leaf_max_size;
962 typename array_or_vector_selector<DIM, DistanceType>::container_t;
978 Size
size(
const Derived& obj)
const {
return obj.m_size; }
981 Size
veclen(
const Derived& obj) {
return DIM > 0 ? DIM : obj.dim; }
985 const Derived& obj, AccessorType element, Dimension component)
const
987 return obj.dataset.kdtree_get_pt(element, component);
996 return obj.pool.usedMemory + obj.pool.wastedMemory +
997 obj.dataset.kdtree_get_point_count() *
998 sizeof(AccessorType);
1002 const Derived& obj, Offset ind, Size count, Dimension element,
1003 ElementType& min_elem, ElementType& max_elem)
1005 min_elem = dataset_get(obj, vAcc[ind], element);
1006 max_elem = min_elem;
1007 for (Offset i = 1; i < count; ++i)
1009 ElementType val = dataset_get(obj, vAcc[ind + i], element);
1010 if (val < min_elem) min_elem = val;
1011 if (val > max_elem) max_elem = val;
1023 Derived& obj,
const Offset left,
const Offset right,
BoundingBox& bbox)
1025 NodePtr node = obj.pool.template allocate<Node>();
1028 if ((right - left) <=
static_cast<Offset
>(obj.m_leaf_max_size))
1030 node->
child1 = node->child2 =
nullptr;
1035 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i)
1037 bbox[i].low = dataset_get(obj, obj.vAcc[left], i);
1038 bbox[i].high = dataset_get(obj, obj.vAcc[left], i);
1040 for (Offset k = left + 1; k < right; ++k)
1042 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i)
1044 if (bbox[i].low > dataset_get(obj, obj.vAcc[k], i))
1045 bbox[i].low = dataset_get(obj, obj.vAcc[k], i);
1046 if (bbox[i].high < dataset_get(obj, obj.vAcc[k], i))
1047 bbox[i].high = dataset_get(obj, obj.vAcc[k], i);
1055 DistanceType cutval;
1056 middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
1061 left_bbox[cutfeat].high = cutval;
1062 node->
child1 = divideTree(obj, left, left + idx, left_bbox);
1065 right_bbox[cutfeat].low = cutval;
1066 node->child2 = divideTree(obj, left + idx, right, right_bbox);
1068 node->
node_type.sub.divlow = left_bbox[cutfeat].high;
1069 node->
node_type.sub.divhigh = right_bbox[cutfeat].low;
1071 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i)
1073 bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
1074 bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
1082 Derived& obj, Offset ind, Size count, Offset& index, Dimension& cutfeat,
1083 DistanceType& cutval,
const BoundingBox& bbox)
1085 const auto EPS =
static_cast<DistanceType
>(0.00001);
1086 ElementType max_span = bbox[0].high - bbox[0].low;
1087 for (Dimension i = 1; i < (DIM > 0 ? DIM : obj.dim); ++i)
1089 ElementType span = bbox[i].high - bbox[i].low;
1090 if (span > max_span) { max_span = span; }
1092 ElementType max_spread = -1;
1094 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i)
1096 ElementType span = bbox[i].high - bbox[i].low;
1097 if (span > (1 - EPS) * max_span)
1099 ElementType min_elem, max_elem;
1100 computeMinMax(obj, ind, count, i, min_elem, max_elem);
1101 ElementType spread = max_elem - min_elem;
1102 if (spread > max_spread)
1105 max_spread = spread;
1110 DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;
1111 ElementType min_elem, max_elem;
1112 computeMinMax(obj, ind, count, cutfeat, min_elem, max_elem);
1114 if (split_val < min_elem)
1116 else if (split_val > max_elem)
1122 planeSplit(obj, ind, count, cutfeat, cutval, lim1, lim2);
1124 if (lim1 > count / 2)
1126 else if (lim2 < count / 2)
1142 Derived& obj, Offset ind,
const Size count, Dimension cutfeat,
1143 DistanceType& cutval, Offset& lim1, Offset& lim2)
1147 Offset right = count - 1;
1150 while (left <= right &&
1151 dataset_get(obj, vAcc[ind + left], cutfeat) < cutval)
1153 while (right && left <= right &&
1154 dataset_get(obj, vAcc[ind + right], cutfeat) >= cutval)
1156 if (left > right || !right)
1158 std::swap(vAcc[ind + left], vAcc[ind + right]);
1169 while (left <= right &&
1170 dataset_get(obj, vAcc[ind + left], cutfeat) <= cutval)
1172 while (right && left <= right &&
1173 dataset_get(obj, vAcc[ind + right], cutfeat) > cutval)
1175 if (left > right || !right)
1177 std::swap(vAcc[ind + left], vAcc[ind + right]);
1184 DistanceType computeInitialDistances(
1185 const Derived& obj,
const ElementType* vec,
1186 distance_vector_t& dists)
const
1189 DistanceType distsq = DistanceType();
1191 for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim); ++i)
1193 if (vec[i] < obj.root_bbox[i].low)
1196 obj.distance.accum_dist(vec[i], obj.root_bbox[i].low, i);
1199 if (vec[i] > obj.root_bbox[i].high)
1202 obj.distance.accum_dist(vec[i], obj.root_bbox[i].high, i);
1209 void save_tree(Derived& obj, std::ostream& stream, NodePtr tree)
1211 save_value(stream, *tree);
1212 if (tree->child1 !=
nullptr) { save_tree(obj, stream, tree->child1); }
1213 if (tree->child2 !=
nullptr) { save_tree(obj, stream, tree->child2); }
1216 void load_tree(Derived& obj, std::istream& stream, NodePtr& tree)
1218 tree = obj.pool.template allocate<Node>();
1219 load_value(stream, *tree);
1220 if (tree->child1 !=
nullptr) { load_tree(obj, stream, tree->child1); }
1221 if (tree->child2 !=
nullptr) { load_tree(obj, stream, tree->child2); }
1231 save_value(stream, obj.m_size);
1232 save_value(stream, obj.dim);
1233 save_value(stream, obj.root_bbox);
1234 save_value(stream, obj.m_leaf_max_size);
1235 save_value(stream, obj.vAcc);
1236 save_tree(obj, stream, obj.root_node);
1246 load_value(stream, obj.m_size);
1247 load_value(stream, obj.dim);
1248 load_value(stream, obj.root_bbox);
1249 load_value(stream, obj.m_leaf_max_size);
1250 load_value(stream, obj.vAcc);
1251 load_tree(obj, stream, obj.root_node);
1297 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
1298 typename AccessorType = uint32_t>
1301 KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, AccessorType>,
1302 Distance, DatasetAdaptor, DIM, AccessorType>
1308 Distance, DatasetAdaptor, DIM, AccessorType>&) =
delete;
1321 Distance, DatasetAdaptor, DIM, AccessorType>,
1322 Distance, DatasetAdaptor, DIM, AccessorType>;
1324 using Offset =
typename BaseClassRef::Offset;
1325 using Size =
typename BaseClassRef::Size;
1326 using Dimension =
typename BaseClassRef::Dimension;
1328 using ElementType =
typename BaseClassRef::ElementType;
1329 using DistanceType =
typename BaseClassRef::DistanceType;
1331 using Node =
typename BaseClassRef::Node;
1332 using NodePtr = Node*;
1334 using Interval =
typename BaseClassRef::Interval;
1364 template <
class... Args>
1366 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1368 : dataset(inputData),
1369 index_params(params),
1370 distance(inputData, std::forward<Args>(args)...)
1372 init(dimensionality, params);
1376 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1378 : dataset(inputData), index_params(params), distance(inputData)
1380 init(dimensionality, params);
1385 const Dimension dimensionality,
1386 const KDTreeSingleIndexAdaptorParams& params)
1388 BaseClassRef::root_node =
nullptr;
1389 BaseClassRef::m_size = dataset.kdtree_get_point_count();
1390 BaseClassRef::m_size_at_index_build = BaseClassRef::m_size;
1391 BaseClassRef::dim = dimensionality;
1392 if (DIM > 0) BaseClassRef::dim = DIM;
1393 BaseClassRef::m_leaf_max_size = params.leaf_max_size;
1395 if (!(params.flags &
1396 KDTreeSingleIndexAdaptorFlags::SkipInitialBuildIndex))
1408 BaseClassRef::m_size = dataset.kdtree_get_point_count();
1409 BaseClassRef::m_size_at_index_build = BaseClassRef::m_size;
1411 this->freeIndex(*
this);
1412 BaseClassRef::m_size_at_index_build = BaseClassRef::m_size;
1413 if (BaseClassRef::m_size == 0)
return;
1414 computeBoundingBox(BaseClassRef::root_bbox);
1415 BaseClassRef::root_node = this->divideTree(
1416 *
this, 0, BaseClassRef::m_size,
1417 BaseClassRef::root_bbox);
1436 template <
typename RESULTSET>
1438 RESULTSET& result,
const ElementType* vec,
1442 if (this->size(*
this) == 0)
return false;
1443 if (!BaseClassRef::root_node)
1444 throw std::runtime_error(
1445 "[nanoflann] findNeighbors() called before building the "
1447 float epsError = 1 + searchParams.
eps;
1451 auto zero =
static_cast<decltype(result.worstDist())
>(0);
1453 dists, (DIM > 0 ? DIM : BaseClassRef::dim),
1455 DistanceType distsq = this->computeInitialDistances(*
this, vec, dists);
1457 result, vec, BaseClassRef::root_node, distsq, dists,
1460 return result.full();
1473 const ElementType* query_point,
const Size num_closest,
1474 AccessorType* out_indices, DistanceType* out_distances_sq,
1475 const int = 10)
const
1479 resultSet.init(out_indices, out_distances_sq);
1481 return resultSet.size();
1501 const ElementType* query_point,
const DistanceType& radius,
1502 std::vector<std::pair<AccessorType, DistanceType>>& IndicesDists,
1506 radius, IndicesDists);
1508 radiusSearchCustomCallback(query_point, resultSet, searchParams);
1520 template <
class SEARCH_CALLBACK>
1522 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
1525 this->findNeighbors(resultSet, query_point, searchParams);
1526 return resultSet.size();
1537 BaseClassRef::m_size = dataset.kdtree_get_point_count();
1538 if (BaseClassRef::vAcc.size() != BaseClassRef::m_size)
1539 BaseClassRef::vAcc.resize(BaseClassRef::m_size);
1540 for (Size i = 0; i < BaseClassRef::m_size; i++)
1541 BaseClassRef::vAcc[i] = i;
1544 void computeBoundingBox(BoundingBox& bbox)
1546 resize(bbox, (DIM > 0 ? DIM : BaseClassRef::dim));
1547 if (dataset.kdtree_get_bbox(bbox))
1553 const Size N = dataset.kdtree_get_point_count();
1555 throw std::runtime_error(
1556 "[nanoflann] computeBoundingBox() called but "
1557 "no data points found.");
1558 for (Dimension i = 0; i < (DIM > 0 ? DIM : BaseClassRef::dim); ++i)
1560 bbox[i].low = bbox[i].high =
1561 this->dataset_get(*
this, BaseClassRef::vAcc[0], i);
1563 for (Offset k = 1; k < N; ++k)
1565 for (Dimension i = 0; i < (DIM > 0 ? DIM : BaseClassRef::dim);
1568 if (this->dataset_get(*
this, BaseClassRef::vAcc[k], i) <
1571 this->dataset_get(*
this, BaseClassRef::vAcc[k], i);
1572 if (this->dataset_get(*
this, BaseClassRef::vAcc[k], i) >
1575 this->dataset_get(*
this, BaseClassRef::vAcc[k], i);
1587 template <
class RESULTSET>
1589 RESULTSET& result_set,
const ElementType* vec,
const NodePtr node,
1591 const float epsError)
const
1594 if ((node->child1 ==
nullptr) && (node->child2 ==
nullptr))
1598 DistanceType worst_dist = result_set.worstDist();
1599 for (Offset i = node->node_type.lr.left;
1600 i < node->node_type.lr.right; ++i)
1602 const AccessorType accessor =
1603 BaseClassRef::vAcc[i];
1604 DistanceType dist = distance.evalMetric(
1605 vec, accessor, (DIM > 0 ? DIM : BaseClassRef::dim));
1606 if (dist < worst_dist)
1608 if (!result_set.addPoint(dist, BaseClassRef::vAcc[i]))
1620 Dimension idx = node->node_type.sub.divfeat;
1621 ElementType val = vec[idx];
1622 DistanceType diff1 = val - node->node_type.sub.divlow;
1623 DistanceType diff2 = val - node->node_type.sub.divhigh;
1627 DistanceType cut_dist;
1628 if ((diff1 + diff2) < 0)
1630 bestChild = node->child1;
1631 otherChild = node->child2;
1633 distance.accum_dist(val, node->node_type.sub.divhigh, idx);
1637 bestChild = node->child2;
1638 otherChild = node->child1;
1640 distance.accum_dist(val, node->node_type.sub.divlow, idx);
1645 result_set, vec, bestChild, mindistsq, dists, epsError))
1652 DistanceType dst = dists[idx];
1653 mindistsq = mindistsq + cut_dist - dst;
1654 dists[idx] = cut_dist;
1655 if (mindistsq * epsError <= result_set.worstDist())
1658 result_set, vec, otherChild, mindistsq, dists, epsError))
1675 void saveIndex(std::ostream& stream) { this->saveIndex_(*
this, stream); }
1682 void loadIndex(std::istream& stream) { this->loadIndex_(*
this, stream); }
1723 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
1724 typename AccessorType = uint32_t>
1727 KDTreeSingleIndexDynamicAdaptor_<
1728 Distance, DatasetAdaptor, DIM, AccessorType>,
1729 Distance, DatasetAdaptor, DIM, AccessorType>
1739 std::vector<int>& treeIndex;
1745 Distance, DatasetAdaptor, DIM, AccessorType>,
1746 Distance, DatasetAdaptor, DIM, AccessorType>;
1748 using ElementType =
typename BaseClassRef::ElementType;
1749 using DistanceType =
typename BaseClassRef::DistanceType;
1751 using Offset =
typename BaseClassRef::Offset;
1752 using Size =
typename BaseClassRef::Size;
1753 using Dimension =
typename BaseClassRef::Dimension;
1755 using Node =
typename BaseClassRef::Node;
1756 using NodePtr = Node*;
1758 using Interval =
typename BaseClassRef::Interval;
1783 const Dimension dimensionality,
const DatasetAdaptor& inputData,
1784 std::vector<int>& treeIndex_,
1787 : dataset(inputData),
1788 index_params(params),
1789 treeIndex(treeIndex_),
1792 BaseClassRef::root_node =
nullptr;
1793 BaseClassRef::m_size = 0;
1794 BaseClassRef::m_size_at_index_build = 0;
1795 BaseClassRef::dim = dimensionality;
1796 if (DIM > 0) BaseClassRef::dim = DIM;
1797 BaseClassRef::m_leaf_max_size = params.leaf_max_size;
1809 std::swap(BaseClassRef::vAcc, tmp.BaseClassRef::vAcc);
1811 BaseClassRef::m_leaf_max_size, tmp.BaseClassRef::m_leaf_max_size);
1812 std::swap(index_params, tmp.index_params);
1813 std::swap(treeIndex, tmp.treeIndex);
1814 std::swap(BaseClassRef::m_size, tmp.BaseClassRef::m_size);
1816 BaseClassRef::m_size_at_index_build,
1817 tmp.BaseClassRef::m_size_at_index_build);
1818 std::swap(BaseClassRef::root_node, tmp.BaseClassRef::root_node);
1819 std::swap(BaseClassRef::root_bbox, tmp.BaseClassRef::root_bbox);
1820 std::swap(BaseClassRef::pool, tmp.BaseClassRef::pool);
1829 BaseClassRef::m_size = BaseClassRef::vAcc.size();
1830 this->freeIndex(*
this);
1831 BaseClassRef::m_size_at_index_build = BaseClassRef::m_size;
1832 if (BaseClassRef::m_size == 0)
return;
1833 computeBoundingBox(BaseClassRef::root_bbox);
1834 BaseClassRef::root_node = this->divideTree(
1835 *
this, 0, BaseClassRef::m_size,
1836 BaseClassRef::root_bbox);
1855 template <
typename RESULTSET>
1857 RESULTSET& result,
const ElementType* vec,
1861 if (this->size(*
this) == 0)
return false;
1862 if (!BaseClassRef::root_node)
return false;
1863 float epsError = 1 + searchParams.
eps;
1869 dists, (DIM > 0 ? DIM : BaseClassRef::dim),
1870 static_cast<typename distance_vector_t::value_type
>(0));
1871 DistanceType distsq = this->computeInitialDistances(*
this, vec, dists);
1873 result, vec, BaseClassRef::root_node, distsq, dists,
1876 return result.full();
1889 const ElementType* query_point,
const Size num_closest,
1890 AccessorType* out_indices, DistanceType* out_distances_sq,
1891 const int = 10)
const
1895 resultSet.init(out_indices, out_distances_sq);
1897 return resultSet.size();
1917 const ElementType* query_point,
const DistanceType& radius,
1918 std::vector<std::pair<AccessorType, DistanceType>>& IndicesDists,
1922 radius, IndicesDists);
1923 const size_t nFound =
1924 radiusSearchCustomCallback(query_point, resultSet, searchParams);
1936 template <
class SEARCH_CALLBACK>
1938 const ElementType* query_point, SEARCH_CALLBACK& resultSet,
1941 this->findNeighbors(resultSet, query_point, searchParams);
1942 return resultSet.size();
1948 void computeBoundingBox(BoundingBox& bbox)
1950 resize(bbox, (DIM > 0 ? DIM : BaseClassRef::dim));
1952 if (dataset.kdtree_get_bbox(bbox))
1958 const Size N = BaseClassRef::m_size;
1960 throw std::runtime_error(
1961 "[nanoflann] computeBoundingBox() called but "
1962 "no data points found.");
1963 for (Dimension i = 0; i < (DIM > 0 ? DIM : BaseClassRef::dim); ++i)
1965 bbox[i].low = bbox[i].high =
1966 this->dataset_get(*
this, BaseClassRef::vAcc[0], i);
1968 for (Offset k = 1; k < N; ++k)
1970 for (Dimension i = 0; i < (DIM > 0 ? DIM : BaseClassRef::dim);
1973 if (this->dataset_get(*
this, BaseClassRef::vAcc[k], i) <
1976 this->dataset_get(*
this, BaseClassRef::vAcc[k], i);
1977 if (this->dataset_get(*
this, BaseClassRef::vAcc[k], i) >
1980 this->dataset_get(*
this, BaseClassRef::vAcc[k], i);
1990 template <
class RESULTSET>
1992 RESULTSET& result_set,
const ElementType* vec,
const NodePtr node,
1994 const float epsError)
const
1997 if ((node->child1 ==
nullptr) && (node->child2 ==
nullptr))
2001 DistanceType worst_dist = result_set.worstDist();
2002 for (Offset i = node->node_type.lr.left;
2003 i < node->node_type.lr.right; ++i)
2005 const AccessorType index =
2006 BaseClassRef::vAcc[i];
2007 if (treeIndex[index] == -1)
continue;
2008 DistanceType dist = distance.evalMetric(
2009 vec, index, (DIM > 0 ? DIM : BaseClassRef::dim));
2010 if (dist < worst_dist)
2012 if (!result_set.addPoint(
2013 static_cast<typename RESULTSET::DistanceType
>(dist),
2014 static_cast<typename RESULTSET::IndexType
>(
2015 BaseClassRef::vAcc[i])))
2027 Dimension idx = node->node_type.sub.divfeat;
2028 ElementType val = vec[idx];
2029 DistanceType diff1 = val - node->node_type.sub.divlow;
2030 DistanceType diff2 = val - node->node_type.sub.divhigh;
2034 DistanceType cut_dist;
2035 if ((diff1 + diff2) < 0)
2037 bestChild = node->child1;
2038 otherChild = node->child2;
2040 distance.accum_dist(val, node->node_type.sub.divhigh, idx);
2044 bestChild = node->child2;
2045 otherChild = node->child1;
2047 distance.accum_dist(val, node->node_type.sub.divlow, idx);
2051 searchLevel(result_set, vec, bestChild, mindistsq, dists, epsError);
2053 DistanceType dst = dists[idx];
2054 mindistsq = mindistsq + cut_dist - dst;
2055 dists[idx] = cut_dist;
2056 if (mindistsq * epsError <= result_set.worstDist())
2059 result_set, vec, otherChild, mindistsq, dists, epsError);
2070 void saveIndex(std::ostream& stream) { this->saveIndex_(*
this, stream); }
2077 void loadIndex(std::istream& stream) { this->loadIndex_(*
this, stream); }
2095 typename Distance,
class DatasetAdaptor, int32_t DIM = -1,
2096 typename AccessorType = uint32_t>
2100 using ElementType =
typename Distance::ElementType;
2101 using DistanceType =
typename Distance::DistanceType;
2104 Distance, DatasetAdaptor, DIM>::Offset;
2106 Distance, DatasetAdaptor, DIM>::Size;
2108 Distance, DatasetAdaptor, DIM>::Dimension;
2111 Size m_leaf_max_size;
2124 std::unordered_set<int> removedPoints;
2131 Distance, DatasetAdaptor, DIM, AccessorType>;
2132 std::vector<index_container_t> index;
2144 int First0Bit(AccessorType num)
2158 using my_kd_tree_t = KDTreeSingleIndexDynamicAdaptor_<
2159 Distance, DatasetAdaptor, DIM, AccessorType>;
2160 std::vector<my_kd_tree_t> index_(
2162 my_kd_tree_t(dim , dataset, treeIndex, index_params));
2185 const int dimensionality,
const DatasetAdaptor& inputData,
2188 const size_t maximumPointCount = 1000000000U)
2189 : dataset(inputData), index_params(params), distance(inputData)
2191 treeCount =
static_cast<size_t>(std::log2(maximumPointCount)) + 1;
2193 dim = dimensionality;
2195 if (DIM > 0) dim = DIM;
2196 m_leaf_max_size = params.leaf_max_size;
2198 const size_t num_initial_points = dataset.kdtree_get_point_count();
2199 if (num_initial_points > 0) { addPoints(0, num_initial_points - 1); }
2205 Distance, DatasetAdaptor, DIM, AccessorType>&) =
delete;
2210 const Size count = end - start + 1;
2212 treeIndex.resize(treeIndex.size() + count);
2213 for (AccessorType idx = start; idx <= end; idx++)
2215 const int pos = First0Bit(pointCount);
2216 maxIndex = std::max(pos, maxIndex);
2217 treeIndex[pointCount] = pos;
2219 const auto it = removedPoints.find(idx);
2220 if (it != removedPoints.end())
2222 removedPoints.erase(it);
2223 treeIndex[idx] = pos;
2226 for (
int i = 0; i < pos; i++)
2228 for (
int j = 0; j < static_cast<int>(index[i].vAcc.size()); j++)
2230 index[pos].vAcc.push_back(index[i].vAcc[j]);
2231 if (treeIndex[index[i].vAcc[j]] != -1)
2232 treeIndex[index[i].vAcc[j]] = pos;
2234 index[i].vAcc.clear();
2236 index[pos].vAcc.push_back(idx);
2240 for (
int i = 0; i <= maxIndex; ++i)
2242 index[i].freeIndex(index[i]);
2243 if (!index[i].vAcc.empty()) index[i].buildIndex();
2250 if (idx >= pointCount)
return;
2251 removedPoints.insert(idx);
2252 treeIndex[idx] = -1;
2268 template <
typename RESULTSET>
2270 RESULTSET& result,
const ElementType* vec,
2273 for (
size_t i = 0; i < treeCount; i++)
2275 index[i].findNeighbors(result, &vec[0], searchParams);
2277 return result.full();
2307 bool row_major =
true>
2312 using num_t =
typename MatrixType::Scalar;
2313 using IndexType =
typename MatrixType::Index;
2314 using metric_t =
typename Distance::template traits<
2315 num_t,
self_t, IndexType>::distance_t;
2319 row_major ? MatrixType::ColsAtCompileTime
2320 : MatrixType::RowsAtCompileTime,
2327 using Size =
typename index_t::Size;
2328 using Dimension =
typename index_t::Dimension;
2332 const Dimension dimensionality,
2333 const std::reference_wrapper<const MatrixType>& mat,
2334 const int leaf_max_size = 10)
2335 : m_data_matrix(mat)
2337 const auto dims = row_major ? mat.get().cols() : mat.get().rows();
2338 if (
static_cast<Dimension
>(dims) != dimensionality)
2339 throw std::runtime_error(
2340 "Error: 'dimensionality' must match column count in data "
2342 if (DIM > 0 &&
static_cast<int32_t
>(dims) != DIM)
2343 throw std::runtime_error(
2344 "Data set dimensionality does not match the 'DIM' template "
2357 const std::reference_wrapper<const MatrixType> m_data_matrix;
2366 const num_t* query_point,
const Size num_closest,
2367 IndexType* out_indices, num_t* out_distances_sq,
2368 const int = 10)
const
2371 resultSet.init(out_indices, out_distances_sq);
2378 const self_t& derived()
const {
return *
this; }
2379 self_t& derived() {
return *
this; }
2382 inline Size kdtree_get_point_count()
const
2385 return m_data_matrix.get().rows();
2387 return m_data_matrix.get().cols();
2391 inline num_t kdtree_get_pt(
const IndexType idx,
size_t dim)
const
2394 return m_data_matrix.get().coeff(idx, IndexType(dim));
2396 return m_data_matrix.get().coeff(IndexType(dim), idx);
2404 template <
class BBOX>
2405 bool kdtree_get_bbox(BBOX& )
const
Definition: nanoflann.hpp:892
Size veclen(const Derived &obj)
Definition: nanoflann.hpp:981
NodePtr divideTree(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox)
Definition: nanoflann.hpp:1022
PooledAllocator pool
Definition: nanoflann.hpp:975
Dimension dim
Dimensionality of each data point.
Definition: nanoflann.hpp:952
Size m_size_at_index_build
Definition: nanoflann.hpp:950
ElementType dataset_get(const Derived &obj, AccessorType element, Dimension component) const
Helper accessor to the dataset points:
Definition: nanoflann.hpp:984
Size size(const Derived &obj) const
Definition: nanoflann.hpp:978
BoundingBox root_bbox
Definition: nanoflann.hpp:966
Size usedMemory(Derived &obj)
Definition: nanoflann.hpp:994
void saveIndex_(Derived &obj, std::ostream &stream)
Definition: nanoflann.hpp:1229
std::vector< AccessorType > vAcc
Definition: nanoflann.hpp:909
void planeSplit(Derived &obj, Offset ind, const Size count, Dimension cutfeat, DistanceType &cutval, Offset &lim1, Offset &lim2)
Definition: nanoflann.hpp:1141
void freeIndex(Derived &obj)
Definition: nanoflann.hpp:896
void loadIndex_(Derived &obj, std::istream &stream)
Definition: nanoflann.hpp:1244
typename array_or_vector_selector< DIM, Interval >::container_t BoundingBox
Definition: nanoflann.hpp:957
Size m_size
Number of current points in the dataset.
Definition: nanoflann.hpp:949
typename array_or_vector_selector< DIM, DistanceType >::container_t distance_vector_t
Definition: nanoflann.hpp:962
Definition: nanoflann.hpp:1303
KDTreeSingleIndexAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms, Args &&... args)
Definition: nanoflann.hpp:1365
void saveIndex(std::ostream &stream)
Definition: nanoflann.hpp:1675
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< std::pair< AccessorType, DistanceType >> &IndicesDists, const SearchParams &searchParams) const
Definition: nanoflann.hpp:1500
void buildIndex()
Definition: nanoflann.hpp:1406
bool searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, distance_vector_t &dists, const float epsError) const
Definition: nanoflann.hpp:1588
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:1521
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
Definition: nanoflann.hpp:1437
typename BaseClassRef::distance_vector_t distance_vector_t
Definition: nanoflann.hpp:1342
Size knnSearch(const ElementType *query_point, const Size num_closest, AccessorType *out_indices, DistanceType *out_distances_sq, const int=10) const
Definition: nanoflann.hpp:1472
void init_vind()
Definition: nanoflann.hpp:1534
void loadIndex(std::istream &stream)
Definition: nanoflann.hpp:1682
const DatasetAdaptor & dataset
The source of our data.
Definition: nanoflann.hpp:1313
typename BaseClassRef::BoundingBox BoundingBox
Definition: nanoflann.hpp:1338
Definition: nanoflann.hpp:1730
const DatasetAdaptor & dataset
The source of our data.
Definition: nanoflann.hpp:1735
void searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindistsq, distance_vector_t &dists, const float epsError) const
Definition: nanoflann.hpp:1991
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParams &searchParams=SearchParams()) const
Definition: nanoflann.hpp:1937
typename BaseClassRef::distance_vector_t distance_vector_t
Definition: nanoflann.hpp:1765
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< std::pair< AccessorType, DistanceType >> &IndicesDists, const SearchParams &searchParams) const
Definition: nanoflann.hpp:1916
void buildIndex()
Definition: nanoflann.hpp:1827
void loadIndex(std::istream &stream)
Definition: nanoflann.hpp:2077
KDTreeSingleIndexDynamicAdaptor_(const KDTreeSingleIndexDynamicAdaptor_ &rhs)=default
typename BaseClassRef::BoundingBox BoundingBox
Definition: nanoflann.hpp:1761
KDTreeSingleIndexDynamicAdaptor_ operator=(const KDTreeSingleIndexDynamicAdaptor_ &rhs)
Definition: nanoflann.hpp:1805
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
Definition: nanoflann.hpp:1856
KDTreeSingleIndexDynamicAdaptor_(const Dimension dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex_, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams())
Definition: nanoflann.hpp:1782
Size knnSearch(const ElementType *query_point, const Size num_closest, AccessorType *out_indices, DistanceType *out_distances_sq, const int=10) const
Definition: nanoflann.hpp:1888
void saveIndex(std::ostream &stream)
Definition: nanoflann.hpp:2070
Definition: nanoflann.hpp:2098
void removePoint(size_t idx)
Definition: nanoflann.hpp:2248
const DatasetAdaptor & dataset
The source of our data.
Definition: nanoflann.hpp:2118
std::vector< int > treeIndex
Definition: nanoflann.hpp:2121
void addPoints(AccessorType start, AccessorType end)
Definition: nanoflann.hpp:2208
Dimension dim
Dimensionality of each data point.
Definition: nanoflann.hpp:2128
KDTreeSingleIndexDynamicAdaptor(const KDTreeSingleIndexDynamicAdaptor< Distance, DatasetAdaptor, DIM, AccessorType > &)=delete
const std::vector< index_container_t > & getAllIndices() const
Definition: nanoflann.hpp:2137
KDTreeSingleIndexDynamicAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams ¶ms=KDTreeSingleIndexAdaptorParams(), const size_t maximumPointCount=1000000000U)
Definition: nanoflann.hpp:2184
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
Definition: nanoflann.hpp:2269
Definition: nanoflann.hpp:159
bool addPoint(DistanceType dist, IndexType index)
Definition: nanoflann.hpp:195
Definition: nanoflann.hpp:736
T * allocate(const size_t count=1)
Definition: nanoflann.hpp:847
~PooledAllocator()
Definition: nanoflann.hpp:771
void free_all()
Definition: nanoflann.hpp:774
PooledAllocator()
Definition: nanoflann.hpp:766
void * malloc(const size_t req_size)
Definition: nanoflann.hpp:790
Definition: nanoflann.hpp:249
std::pair< IndexType, DistanceType > worst_item() const
Definition: nanoflann.hpp:292
bool addPoint(DistanceType dist, IndexType index)
Definition: nanoflann.hpp:279
const size_t WORDSIZE
Definition: nanoflann.hpp:732
T * allocate(size_t count=1)
Definition: nanoflann.hpp:711
T pi_const()
Definition: nanoflann.hpp:80
std::enable_if< has_assign< Container >::value, void >::type assign(Container &c, const size_t nElements, const T &value)
Definition: nanoflann.hpp:137
std::enable_if< has_resize< Container >::value, void >::type resize(Container &c, const size_t nElements)
Definition: nanoflann.hpp:115
Definition: nanoflann.hpp:235
bool operator()(const PairType &p1, const PairType &p2) const
Definition: nanoflann.hpp:238
Definition: nanoflann.hpp:941
Definition: nanoflann.hpp:918
DistanceType divhigh
The values used for subdivision.
Definition: nanoflann.hpp:931
Dimension divfeat
Dimension used for subdivision.
Definition: nanoflann.hpp:929
Offset right
Indices of points in leaf node.
Definition: nanoflann.hpp:925
union nanoflann::KDTreeBaseClass::Node::@0 node_type
Node * child1
Definition: nanoflann.hpp:935
Definition: nanoflann.hpp:2309
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:2365
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:2331
KDTreeEigenMatrixAdaptor(const self_t &)=delete
typename index_t::Offset Offset
Definition: nanoflann.hpp:2326
Definition: nanoflann.hpp:670
Definition: nanoflann.hpp:361
Definition: nanoflann.hpp:423
Definition: nanoflann.hpp:488
Definition: nanoflann.hpp:344
Definition: nanoflann.hpp:533
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition: nanoflann.hpp:551
Definition: nanoflann.hpp:578
Definition: nanoflann.hpp:684
bool sorted
distance (default: true)
Definition: nanoflann.hpp:695
SearchParams(int checks_IGNORED_=32, float eps_=0, bool sorted_=true)
Definition: nanoflann.hpp:687
float eps
search for eps-approximate neighbours (default: 0)
Definition: nanoflann.hpp:694
int checks
Definition: nanoflann.hpp:692
Definition: nanoflann.hpp:863
Definition: nanoflann.hpp:102
Definition: nanoflann.hpp:91
Definition: nanoflann.hpp:608
Definition: nanoflann.hpp:605
Definition: nanoflann.hpp:617
Definition: nanoflann.hpp:626
Definition: nanoflann.hpp:623
Definition: nanoflann.hpp:614
Definition: nanoflann.hpp:635
Definition: nanoflann.hpp:632
Definition: nanoflann.hpp:644
Definition: nanoflann.hpp:641