Loading...
Searching...
No Matches
nanoflann.hpp
/***********************************************************************
* Software License Agreement (BSD License)
*
* Copyright 2008-2009 Marius Muja (mariusm@cs.ubc.ca). All rights reserved.
* Copyright 2008-2009 David G. Lowe (lowe@cs.ubc.ca). All rights reserved.
* Copyright 2011-2025 Jose Luis Blanco (joseluisblancoc@gmail.com).
* All rights reserved.
*
* THE BSD LICENSE
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
* are met:
*
* 1. Redistributions of source code must retain the above copyright
* notice, this list of conditions and the following disclaimer.
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
*
* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*************************************************************************/
#pragma once
#include <algorithm>
#include <array>
#include <atomic>
#include <cassert>
#include <cmath> // for abs()
#include <cstdint>
#include <cstdlib> // for abs()
#include <functional> // std::reference_wrapper
#include <future>
#include <istream>
#include <limits> // std::numeric_limits
#include <ostream>
#include <stack>
#include <stdexcept>
#include <unordered_set>
#include <vector>
#define NANOFLANN_VERSION 0x190
// Avoid conflicting declaration of min/max macros in Windows headers
#if !defined(NOMINMAX) && (defined(_WIN32) || defined(_WIN32_) || defined(WIN32) || defined(_WIN64))
#define NOMINMAX
#ifdef max
#undef max
#undef min
#endif
#endif
// Avoid conflicts with X11 headers
#ifdef None
#undef None
#endif
// Handle restricted pointers
#if defined(__GNUC__) || defined(__clang__)
#define NANOFLANN_RESTRICT __restrict__
#elif defined(_MSC_VER)
#define NANOFLANN_RESTRICT __restrict
#else
#define NANOFLANN_RESTRICT
#endif
// Memory alignment of KD-tree nodes:
#ifndef NANOFLANN_NODE_ALIGNMENT
#define NANOFLANN_NODE_ALIGNMENT 16
#endif
namespace nanoflann
{
template <typename T>
constexpr T pi_const()
{
return static_cast<T>(3.14159265358979323846);
}
template <typename T, typename = int>
struct has_resize : std::false_type
{
};
template <typename T>
struct has_resize<T, decltype((void)std::declval<T>().resize(1), 0)> : std::true_type
{
};
template <typename T, typename = int>
struct has_assign : std::false_type
{
};
template <typename T>
struct has_assign<T, decltype((void)std::declval<T>().assign(1, 0), 0)> : std::true_type
{
};
template <typename Container>
inline typename std::enable_if<has_resize<Container>::value, void>::type resize(
Container& c, const size_t nElements)
{
c.resize(nElements);
}
template <typename Container>
inline typename std::enable_if<!has_resize<Container>::value, void>::type resize(
Container& c, const size_t nElements)
{
if (nElements != c.size()) throw std::logic_error("Attempt to resize a fixed size container.");
}
template <typename Container, typename T>
inline typename std::enable_if<has_assign<Container>::value, void>::type assign(
Container& c, const size_t nElements, const T& value)
{
c.assign(nElements, value);
}
template <typename Container, typename T>
inline typename std::enable_if<!has_assign<Container>::value, void>::type assign(
Container& c, const size_t nElements, const T& value)
{
for (size_t i = 0; i < nElements; i++) c[i] = value;
}
struct IndexDist_Sorter
{
template <typename PairType>
bool operator()(const PairType& p1, const PairType& p2) const
{
return p1.second < p2.second;
}
};
template <typename IndexType = size_t, typename DistanceType = double>
struct ResultItem
{
ResultItem() = default;
ResultItem(const IndexType index, const DistanceType distance) : first(index), second(distance)
{
}
IndexType first;
DistanceType second;
};
template <typename _DistanceType, typename _IndexType = size_t, typename _CountType = size_t>
class KNNResultSet
{
public:
using DistanceType = _DistanceType;
using IndexType = _IndexType;
using CountType = _CountType;
private:
IndexType* indices;
DistanceType* dists;
CountType capacity;
CountType count;
public:
explicit KNNResultSet(CountType capacity_)
: indices(nullptr), dists(nullptr), capacity(capacity_), count(0)
{
}
void init(IndexType* indices_, DistanceType* dists_)
{
indices = indices_;
dists = dists_;
count = 0;
}
CountType size() const noexcept { return count; }
bool empty() const noexcept { return count == 0; }
bool full() const noexcept { return count == capacity; }
bool addPoint(DistanceType dist, IndexType index)
{
CountType i;
for (i = count; i > 0; --i)
{
#ifdef NANOFLANN_FIRST_MATCH
if ((dists[i - 1] > dist) || ((dist == dists[i - 1]) && (indices[i - 1] > index)))
{
#else
if (dists[i - 1] > dist)
{
#endif
if (i < capacity)
{
dists[i] = dists[i - 1];
indices[i] = indices[i - 1];
}
}
else
break;
}
if (i < capacity)
{
dists[i] = dist;
indices[i] = index;
}
if (count < capacity) count++;
// tell caller that the search shall continue
return true;
}
DistanceType worstDist() const noexcept
{
return (count < capacity || !count) ? std::numeric_limits<DistanceType>::max()
: dists[count - 1];
}
void sort()
{
// already sorted
}
};
template <typename _DistanceType, typename _IndexType = size_t, typename _CountType = size_t>
class RKNNResultSet
{
public:
using DistanceType = _DistanceType;
using IndexType = _IndexType;
using CountType = _CountType;
private:
IndexType* indices;
DistanceType* dists;
CountType capacity;
CountType count;
DistanceType maximumSearchDistanceSquared;
public:
explicit RKNNResultSet(CountType capacity_, DistanceType maximumSearchDistanceSquared_)
: indices(nullptr),
dists(nullptr),
capacity(capacity_),
count(0),
maximumSearchDistanceSquared(maximumSearchDistanceSquared_)
{
}
void init(IndexType* indices_, DistanceType* dists_)
{
indices = indices_;
dists = dists_;
count = 0;
if (capacity) dists[capacity - 1] = maximumSearchDistanceSquared;
}
CountType size() const noexcept { return count; }
bool empty() const noexcept { return count == 0; }
bool full() const noexcept { return count == capacity; }
bool addPoint(DistanceType dist, IndexType index)
{
CountType i;
for (i = count; i > 0; --i)
{
#ifdef NANOFLANN_FIRST_MATCH
if ((dists[i - 1] > dist) || ((dist == dists[i - 1]) && (indices[i - 1] > index)))
{
#else
if (dists[i - 1] > dist)
{
#endif
if (i < capacity)
{
dists[i] = dists[i - 1];
indices[i] = indices[i - 1];
}
}
else
break;
}
if (i < capacity)
{
dists[i] = dist;
indices[i] = index;
}
if (count < capacity) count++;
// tell caller that the search shall continue
return true;
}
DistanceType worstDist() const noexcept
{
return (count < capacity || !count) ? maximumSearchDistanceSquared : dists[count - 1];
}
void sort()
{
// already sorted
}
};
template <typename _DistanceType, typename _IndexType = size_t>
class RadiusResultSet
{
public:
using DistanceType = _DistanceType;
using IndexType = _IndexType;
public:
const DistanceType radius;
std::vector<ResultItem<IndexType, DistanceType>>& m_indices_dists;
explicit RadiusResultSet(
DistanceType radius_, std::vector<ResultItem<IndexType, DistanceType>>& indices_dists)
: radius(radius_), m_indices_dists(indices_dists)
{
init();
}
void init() { clear(); }
void clear() { m_indices_dists.clear(); }
size_t size() const noexcept { return m_indices_dists.size(); }
bool empty() const noexcept { return m_indices_dists.empty(); }
bool full() const noexcept { return true; }
bool addPoint(DistanceType dist, IndexType index)
{
if (dist < radius) m_indices_dists.emplace_back(index, dist);
return true;
}
DistanceType worstDist() const noexcept { return radius; }
ResultItem<IndexType, DistanceType> worst_item() const
{
if (m_indices_dists.empty())
throw std::runtime_error(
"Cannot invoke RadiusResultSet::worst_item() on "
"an empty list of results.");
auto it =
std::max_element(m_indices_dists.begin(), m_indices_dists.end(), IndexDist_Sorter());
return *it;
}
void sort() { std::sort(m_indices_dists.begin(), m_indices_dists.end(), IndexDist_Sorter()); }
};
template <typename T>
void save_value(std::ostream& stream, const T& value)
{
stream.write(reinterpret_cast<const char*>(&value), sizeof(T));
}
template <typename T>
void save_value(std::ostream& stream, const std::vector<T>& value)
{
size_t size = value.size();
stream.write(reinterpret_cast<const char*>(&size), sizeof(size_t));
stream.write(reinterpret_cast<const char*>(value.data()), sizeof(T) * size);
}
template <typename T>
void load_value(std::istream& stream, T& value)
{
stream.read(reinterpret_cast<char*>(&value), sizeof(T));
}
template <typename T>
void load_value(std::istream& stream, std::vector<T>& value)
{
size_t size;
stream.read(reinterpret_cast<char*>(&size), sizeof(size_t));
value.resize(size);
stream.read(reinterpret_cast<char*>(value.data()), sizeof(T) * size);
}
struct Metric
{
};
template <class T, class DataSource, typename _DistanceType = T, typename IndexType = size_t>
struct L1_Adaptor
{
using ElementType = T;
using DistanceType = _DistanceType;
const DataSource& data_source;
L1_Adaptor(const DataSource& _data_source) : data_source(_data_source) {}
inline DistanceType evalMetric(
const T* NANOFLANN_RESTRICT a, const IndexType b_idx, size_t size,
DistanceType worst_dist = -1) const
{
DistanceType result = DistanceType();
const size_t multof4 = (size >> 2) << 2; // largest multiple of 4, i.e. 1 << 2
size_t d;
/* Process 4 items with each loop for efficiency. */
if (worst_dist <= 0)
{
/* No checks with worst_dist. */
for (d = 0; d < multof4; d += 4)
{
const DistanceType diff0 =
std::abs(a[d + 0] - data_source.kdtree_get_pt(b_idx, d + 0));
const DistanceType diff1 =
std::abs(a[d + 1] - data_source.kdtree_get_pt(b_idx, d + 1));
const DistanceType diff2 =
std::abs(a[d + 2] - data_source.kdtree_get_pt(b_idx, d + 2));
const DistanceType diff3 =
std::abs(a[d + 3] - data_source.kdtree_get_pt(b_idx, d + 3));
/* Parentheses break dependency chain: */
result += (diff0 + diff1) + (diff2 + diff3);
}
}
else
{
/* Check with worst_dist. */
for (d = 0; d < multof4; d += 4)
{
const DistanceType diff0 =
std::abs(a[d + 0] - data_source.kdtree_get_pt(b_idx, d + 0));
const DistanceType diff1 =
std::abs(a[d + 1] - data_source.kdtree_get_pt(b_idx, d + 1));
const DistanceType diff2 =
std::abs(a[d + 2] - data_source.kdtree_get_pt(b_idx, d + 2));
const DistanceType diff3 =
std::abs(a[d + 3] - data_source.kdtree_get_pt(b_idx, d + 3));
/* Parentheses break dependency chain: */
result += (diff0 + diff1) + (diff2 + diff3);
if (result > worst_dist)
{
return result;
}
}
}
/* Process last 0-3 components. Unrolled loop with fall-through switch.
*/
switch (size - multof4)
{
case 3:
result += std::abs(a[d + 2] - data_source.kdtree_get_pt(b_idx, d + 2));
case 2:
result += std::abs(a[d + 1] - data_source.kdtree_get_pt(b_idx, d + 1));
case 1:
result += std::abs(a[d + 0] - data_source.kdtree_get_pt(b_idx, d + 0));
case 0:
break;
}
return result;
}
template <typename U, typename V>
inline DistanceType accum_dist(const U a, const V b, const size_t) const
{
return std::abs(a - b);
}
};
template <class T, class DataSource, typename _DistanceType = T, typename IndexType = size_t>
struct L2_Adaptor
{
using ElementType = T;
using DistanceType = _DistanceType;
const DataSource& data_source;
L2_Adaptor(const DataSource& _data_source) : data_source(_data_source) {}
inline DistanceType evalMetric(
const T* NANOFLANN_RESTRICT a, const IndexType b_idx, size_t size,
DistanceType worst_dist = -1) const
{
DistanceType result = DistanceType();
const size_t multof4 = (size >> 2) << 2; // largest multiple of 4, i.e. 1 << 2
size_t d;
/* Process 4 items with each loop for efficiency. */
if (worst_dist <= 0)
{
/* No checks with worst_dist. */
for (d = 0; d < multof4; d += 4)
{
const DistanceType diff0 = a[d + 0] - data_source.kdtree_get_pt(b_idx, d + 0);
const DistanceType diff1 = a[d + 1] - data_source.kdtree_get_pt(b_idx, d + 1);
const DistanceType diff2 = a[d + 2] - data_source.kdtree_get_pt(b_idx, d + 2);
const DistanceType diff3 = a[d + 3] - data_source.kdtree_get_pt(b_idx, d + 3);
/* Parentheses break dependency chain: */
result += (diff0 * diff0 + diff1 * diff1) + (diff2 * diff2 + diff3 * diff3);
}
}
else
{
/* Check with worst_dist. */
for (d = 0; d < multof4; d += 4)
{
const DistanceType diff0 = a[d + 0] - data_source.kdtree_get_pt(b_idx, d + 0);
const DistanceType diff1 = a[d + 1] - data_source.kdtree_get_pt(b_idx, d + 1);
const DistanceType diff2 = a[d + 2] - data_source.kdtree_get_pt(b_idx, d + 2);
const DistanceType diff3 = a[d + 3] - data_source.kdtree_get_pt(b_idx, d + 3);
/* Parentheses break dependency chain: */
result += (diff0 * diff0 + diff1 * diff1) + (diff2 * diff2 + diff3 * diff3);
if (result > worst_dist)
{
return result;
}
}
}
/* Process last 0-3 components. Unrolled loop with fall-through switch.
*/
DistanceType diff;
switch (size - multof4)
{
case 3:
diff = a[d + 2] - data_source.kdtree_get_pt(b_idx, d + 2);
result += diff * diff;
case 2:
diff = a[d + 1] - data_source.kdtree_get_pt(b_idx, d + 1);
result += diff * diff;
case 1:
diff = a[d + 0] - data_source.kdtree_get_pt(b_idx, d + 0);
result += diff * diff;
case 0:
break;
}
return result;
}
template <typename U, typename V>
inline DistanceType accum_dist(const U a, const V b, const size_t) const
{
auto diff = a - b;
return diff * diff;
}
};
template <class T, class DataSource, typename _DistanceType = T, typename IndexType = size_t>
struct L2_Simple_Adaptor
{
using ElementType = T;
using DistanceType = _DistanceType;
const DataSource& data_source;
L2_Simple_Adaptor(const DataSource& _data_source) : data_source(_data_source) {}
inline DistanceType evalMetric(const T* a, const IndexType b_idx, size_t size) const
{
DistanceType result = DistanceType();
for (size_t i = 0; i < size; ++i)
{
const DistanceType diff = a[i] - data_source.kdtree_get_pt(b_idx, i);
result += diff * diff;
}
return result;
}
template <typename U, typename V>
inline DistanceType accum_dist(const U a, const V b, const size_t) const
{
auto diff = a - b;
return diff * diff;
}
};
template <class T, class DataSource, typename _DistanceType = T, typename IndexType = size_t>
struct SO2_Adaptor
{
using ElementType = T;
using DistanceType = _DistanceType;
const DataSource& data_source;
SO2_Adaptor(const DataSource& _data_source) : data_source(_data_source) {}
inline DistanceType evalMetric(const T* a, const IndexType b_idx, size_t size) const
{
return accum_dist(a[size - 1], data_source.kdtree_get_pt(b_idx, size - 1), size - 1);
}
template <typename U, typename V>
inline DistanceType accum_dist(const U a, const V b, const size_t) const
{
DistanceType result = DistanceType();
DistanceType PI = pi_const<DistanceType>();
result = b - a;
if (result > PI)
result -= 2 * PI;
else if (result < -PI)
result += 2 * PI;
return result;
}
};
template <class T, class DataSource, typename _DistanceType = T, typename IndexType = size_t>
struct SO3_Adaptor
{
using ElementType = T;
using DistanceType = _DistanceType;
L2_Simple_Adaptor<T, DataSource, DistanceType, IndexType> distance_L2_Simple;
SO3_Adaptor(const DataSource& _data_source) : distance_L2_Simple(_data_source) {}
inline DistanceType evalMetric(const T* a, const IndexType b_idx, size_t size) const
{
return distance_L2_Simple.evalMetric(a, b_idx, size);
}
template <typename U, typename V>
inline DistanceType accum_dist(const U a, const V b, const size_t idx) const
{
return distance_L2_Simple.accum_dist(a, b, idx);
}
};
struct metric_L1 : public Metric
{
template <class T, class DataSource, typename IndexType = size_t>
struct traits
{
using distance_t = L1_Adaptor<T, DataSource, T, IndexType>;
};
};
struct metric_L2 : public Metric
{
template <class T, class DataSource, typename IndexType = size_t>
struct traits
{
using distance_t = L2_Adaptor<T, DataSource, T, IndexType>;
};
};
struct metric_L2_Simple : public Metric
{
template <class T, class DataSource, typename IndexType = size_t>
struct traits
{
using distance_t = L2_Simple_Adaptor<T, DataSource, T, IndexType>;
};
};
struct metric_SO2 : public Metric
{
template <class T, class DataSource, typename IndexType = size_t>
struct traits
{
using distance_t = SO2_Adaptor<T, DataSource, T, IndexType>;
};
};
struct metric_SO3 : public Metric
{
template <class T, class DataSource, typename IndexType = size_t>
struct traits
{
using distance_t = SO3_Adaptor<T, DataSource, T, IndexType>;
};
};
enum class KDTreeSingleIndexAdaptorFlags
{
None = 0,
SkipInitialBuildIndex = 1
};
inline std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type operator&(
KDTreeSingleIndexAdaptorFlags lhs, KDTreeSingleIndexAdaptorFlags rhs)
{
using underlying = typename std::underlying_type<KDTreeSingleIndexAdaptorFlags>::type;
return static_cast<underlying>(lhs) & static_cast<underlying>(rhs);
}
struct KDTreeSingleIndexAdaptorParams
{
KDTreeSingleIndexAdaptorParams(
size_t _leaf_max_size = 10,
KDTreeSingleIndexAdaptorFlags _flags = KDTreeSingleIndexAdaptorFlags::None,
unsigned int _n_thread_build = 1)
: leaf_max_size(_leaf_max_size), flags(_flags), n_thread_build(_n_thread_build)
{
}
size_t leaf_max_size;
KDTreeSingleIndexAdaptorFlags flags;
unsigned int n_thread_build;
};
struct SearchParameters
{
SearchParameters(float eps_ = 0, bool sorted_ = true) : eps(eps_), sorted(sorted_) {}
float eps;
bool sorted;
};
class PooledAllocator
{
static constexpr size_t WORDSIZE = 16; // WORDSIZE must >= 8
static constexpr size_t BLOCKSIZE = 8192;
/* We maintain memory alignment to word boundaries by requiring that all
allocations be in multiples of the machine wordsize. */
/* Size of machine word in bytes. Must be power of 2. */
/* Minimum number of bytes requested at a time from the system. Must be
* multiple of WORDSIZE. */
using Size = size_t;
Size remaining_ = 0;
void* base_ = nullptr;
void* loc_ = nullptr;
void internal_init()
{
remaining_ = 0;
base_ = nullptr;
usedMemory = 0;
wastedMemory = 0;
}
public:
Size usedMemory = 0;
Size wastedMemory = 0;
PooledAllocator() { internal_init(); }
~PooledAllocator() { free_all(); }
void free_all()
{
while (base_ != nullptr)
{
// Get pointer to prev block
void* prev = *(static_cast<void**>(base_));
::free(base_);
base_ = prev;
}
internal_init();
}
void* malloc(const size_t req_size)
{
/* Round size up to a multiple of wordsize. The following expression
only works for WORDSIZE that is a power of 2, by masking last bits
of incremented size to zero.
*/
const Size size = (req_size + (WORDSIZE - 1)) & ~(WORDSIZE - 1);
/* Check whether a new block must be allocated. Note that the first
word of a block is reserved for a pointer to the previous block.
*/
if (size > remaining_)
{
wastedMemory += remaining_;
/* Allocate new storage. */
const Size blocksize = size > BLOCKSIZE ? size + WORDSIZE : BLOCKSIZE + WORDSIZE;
// use the standard C malloc to allocate memory
void* m = ::malloc(blocksize);
if (!m)
{
throw std::bad_alloc();
}
/* Fill first word of new block with pointer to previous block. */
static_cast<void**>(m)[0] = base_;
base_ = m;
remaining_ = blocksize - WORDSIZE;
loc_ = static_cast<char*>(m) + WORDSIZE;
}
void* rloc = loc_;
loc_ = static_cast<char*>(loc_) + size;
remaining_ -= size;
usedMemory += size;
return rloc;
}
template <typename T>
T* allocate(const size_t count = 1)
{
T* mem = static_cast<T*>(this->malloc(sizeof(T) * count));
return mem;
}
};
template <int32_t DIM, typename T>
struct array_or_vector
{
using type = std::array<T, DIM>;
};
template <typename T>
struct array_or_vector<-1, T>
{
using type = std::vector<T>;
};
template <
class Derived, typename Distance, class DatasetAdaptor, int32_t DIM = -1,
typename index_t = uint32_t>
class KDTreeBaseClass
{
public:
void freeIndex(Derived& obj)
{
obj.pool_.free_all();
obj.root_node_ = nullptr;
obj.size_at_index_build_ = 0;
}
using ElementType = typename Distance::ElementType;
using DistanceType = typename Distance::DistanceType;
using IndexType = index_t;
std::vector<IndexType> vAcc_;
using Offset = typename decltype(vAcc_)::size_type;
using Size = typename decltype(vAcc_)::size_type;
using Dimension = int32_t;
/*-------------------------------------------------------------------
* Internal Data Structures
*
* "Node" below can be declared with alignas(N) to improve
* cache friendliness and SIMD load/store performance.
*
* The optimal N depends on the underlying hardware:
* + Intel x86-64: 16 for SSE, 32 for AVX/AVX2 and 64 for AVX-512
* + NVIDIA Jetson: 16 for ARM + NEON and CUDA float4/
* To avoid unnecessary padding, the smallest alignment
* compatible with a platform's vector width should be chosen.
* ------------------------------------------------------------------*/
struct alignas(NANOFLANN_NODE_ALIGNMENT) Node
{
union
{
struct leaf
{
Offset left, right;
} lr;
struct nonleaf
{
Dimension divfeat;
DistanceType divlow, divhigh;
} sub;
} node_type;
Node *child1 = nullptr, *child2 = nullptr;
};
using NodePtr = Node*;
using NodeConstPtr = const Node*;
struct Interval
{
ElementType low, high;
};
NodePtr root_node_ = nullptr;
Size leaf_max_size_ = 0;
Size n_thread_build_ = 1;
Size size_ = 0;
Size size_at_index_build_ = 0;
Dimension dim_ = 0;
using BoundingBox = typename array_or_vector<DIM, Interval>::type;
using distance_vector_t = typename array_or_vector<DIM, DistanceType>::type;
BoundingBox root_bbox_;
PooledAllocator pool_;
Size size(const Derived& obj) const { return obj.size_; }
Size veclen(const Derived& obj) const { return DIM > 0 ? DIM : obj.dim_; }
ElementType dataset_get(const Derived& obj, IndexType element, Dimension component) const
{
return obj.dataset_.kdtree_get_pt(element, component);
}
Size usedMemory(const Derived& obj) const
{
return obj.pool_.usedMemory + obj.pool_.wastedMemory +
obj.dataset_.kdtree_get_point_count() *
sizeof(IndexType); // pool memory and vind array memory
}
void computeMinMax(
const Derived& obj, Offset ind, Size count, Dimension element, ElementType& min_elem,
ElementType& max_elem) const
{
min_elem = dataset_get(obj, vAcc_[ind], element);
max_elem = min_elem;
for (Offset i = 1; i < count; ++i)
{
ElementType val = dataset_get(obj, vAcc_[ind + i], element);
if (val < min_elem) min_elem = val;
if (val > max_elem) max_elem = val;
}
}
NodePtr divideTree(Derived& obj, const Offset left, const Offset right, BoundingBox& bbox)
{
assert(left < obj.dataset_.kdtree_get_point_count());
NodePtr node = obj.pool_.template allocate<Node>(); // allocate memory
const auto dims = (DIM > 0 ? DIM : obj.dim_);
/* If too few exemplars remain, then make this a leaf node. */
if ((right - left) <= static_cast<Offset>(obj.leaf_max_size_))
{
node->child1 = node->child2 = nullptr; /* Mark as leaf node. */
node->node_type.lr.left = left;
node->node_type.lr.right = right;
// compute bounding-box of leaf points
for (Dimension i = 0; i < dims; ++i)
{
bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
}
for (Offset k = left + 1; k < right; ++k)
{
for (Dimension i = 0; i < dims; ++i)
{
const auto val = dataset_get(obj, obj.vAcc_[k], i);
if (bbox[i].low > val) bbox[i].low = val;
if (bbox[i].high < val) bbox[i].high = val;
}
}
}
else
{
/* Determine the index, dimension and value for split plane */
Offset idx;
Dimension cutfeat;
DistanceType cutval;
middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
node->node_type.sub.divfeat = cutfeat;
/* Recurse on left */
BoundingBox left_bbox(bbox);
left_bbox[cutfeat].high = cutval;
node->child1 = this->divideTree(obj, left, left + idx, left_bbox);
/* Recurse on right */
BoundingBox right_bbox(bbox);
right_bbox[cutfeat].low = cutval;
node->child2 = this->divideTree(obj, left + idx, right, right_bbox);
node->node_type.sub.divlow = left_bbox[cutfeat].high;
node->node_type.sub.divhigh = right_bbox[cutfeat].low;
for (Dimension i = 0; i < dims; ++i)
{
bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
}
}
return node;
}
NodePtr divideTreeConcurrent(
Derived& obj, const Offset left, const Offset right, BoundingBox& bbox,
std::atomic<unsigned int>& thread_count, std::mutex& mutex)
{
std::unique_lock<std::mutex> lock(mutex);
NodePtr node = obj.pool_.template allocate<Node>(); // allocate memory
lock.unlock();
const auto dims = (DIM > 0 ? DIM : obj.dim_);
/* If too few exemplars remain, then make this a leaf node. */
if ((right - left) <= static_cast<Offset>(obj.leaf_max_size_))
{
node->child1 = node->child2 = nullptr; /* Mark as leaf node. */
node->node_type.lr.left = left;
node->node_type.lr.right = right;
// compute bounding-box of leaf points
for (Dimension i = 0; i < dims; ++i)
{
bbox[i].low = dataset_get(obj, obj.vAcc_[left], i);
bbox[i].high = dataset_get(obj, obj.vAcc_[left], i);
}
for (Offset k = left + 1; k < right; ++k)
{
for (Dimension i = 0; i < dims; ++i)
{
const auto val = dataset_get(obj, obj.vAcc_[k], i);
if (bbox[i].low > val) bbox[i].low = val;
if (bbox[i].high < val) bbox[i].high = val;
}
}
}
else
{
/* Determine the index, dimension and value for split plane */
Offset idx;
Dimension cutfeat;
DistanceType cutval;
middleSplit_(obj, left, right - left, idx, cutfeat, cutval, bbox);
node->node_type.sub.divfeat = cutfeat;
std::future<NodePtr> right_future;
/* Recurse on right concurrently, if possible */
BoundingBox right_bbox(bbox);
right_bbox[cutfeat].low = cutval;
if (++thread_count < n_thread_build_)
{
/* Concurrent thread for right recursion */
right_future = std::async(
std::launch::async, &KDTreeBaseClass::divideTreeConcurrent, this, std::ref(obj),
left + idx, right, std::ref(right_bbox), std::ref(thread_count),
std::ref(mutex));
}
else
{
--thread_count;
}
/* Recurse on left in this thread */
BoundingBox left_bbox(bbox);
left_bbox[cutfeat].high = cutval;
node->child1 =
this->divideTreeConcurrent(obj, left, left + idx, left_bbox, thread_count, mutex);
if (right_future.valid())
{
/* Block and wait for concurrent right from above */
node->child2 = right_future.get();
--thread_count;
}
else
{
/* Otherwise, recurse on right in this thread */
node->child2 = this->divideTreeConcurrent(
obj, left + idx, right, right_bbox, thread_count, mutex);
}
node->node_type.sub.divlow = left_bbox[cutfeat].high;
node->node_type.sub.divhigh = right_bbox[cutfeat].low;
for (Dimension i = 0; i < dims; ++i)
{
bbox[i].low = std::min(left_bbox[i].low, right_bbox[i].low);
bbox[i].high = std::max(left_bbox[i].high, right_bbox[i].high);
}
}
return node;
}
void middleSplit_(
const Derived& obj, const Offset ind, const Size count, Offset& index, Dimension& cutfeat,
DistanceType& cutval, const BoundingBox& bbox)
{
const auto dims = (DIM > 0 ? DIM : obj.dim_);
const auto EPS = static_cast<DistanceType>(0.00001);
// Pre-compute max_span once
ElementType max_span = bbox[0].high - bbox[0].low;
for (Dimension i = 1; i < dims; ++i)
{
ElementType span = bbox[i].high - bbox[i].low;
if (span > max_span) max_span = span;
}
// Single-pass min/max computation for candidate dimensions
cutfeat = 0;
ElementType max_spread = -1;
ElementType min_elem = 0, max_elem = 0;
// Only check dimensions within (1-EPS) of max_span
std::vector<Dimension> candidates;
candidates.reserve(dims);
for (Dimension i = 0; i < dims; ++i)
{
if (bbox[i].high - bbox[i].low >= (1 - EPS) * max_span)
{
candidates.push_back(i);
}
}
// Vectorized min/max for candidates
for (Dimension dim : candidates)
{
ElementType local_min = dataset_get(obj, vAcc_[ind], dim);
ElementType local_max = local_min;
// Unrolled loop for better performance
constexpr size_t UNROLL = 4;
Offset k = 1;
for (; k + UNROLL <= count; k += UNROLL)
{
ElementType v0 = dataset_get(obj, vAcc_[ind + k], dim);
ElementType v1 = dataset_get(obj, vAcc_[ind + k + 1], dim);
ElementType v2 = dataset_get(obj, vAcc_[ind + k + 2], dim);
ElementType v3 = dataset_get(obj, vAcc_[ind + k + 3], dim);
local_min = std::min({local_min, v0, v1, v2, v3});
local_max = std::max({local_max, v0, v1, v2, v3});
}
// Handle remainder
for (; k < count; ++k)
{
ElementType val = dataset_get(obj, vAcc_[ind + k], dim);
local_min = std::min(local_min, val);
local_max = std::max(local_max, val);
}
ElementType spread = local_max - local_min;
if (spread > max_spread)
{
cutfeat = dim;
max_spread = spread;
min_elem = local_min;
max_elem = local_max;
}
}
// Median-of-three for better balance
DistanceType split_val = (bbox[cutfeat].low + bbox[cutfeat].high) / 2;
if (split_val < min_elem) split_val = min_elem;
if (split_val > max_elem) split_val = max_elem;
cutval = split_val;
// Optimized partitioning
Offset lim1, lim2;
planeSplit(obj, ind, count, cutfeat, cutval, lim1, lim2);
index = (lim1 > count / 2) ? lim1 : (lim2 < count / 2) ? lim2 : count / 2;
}
void planeSplit(
const Derived& obj, const Offset ind, const Size count, const Dimension cutfeat,
const DistanceType& cutval, Offset& lim1, Offset& lim2)
{
// Dutch National Flag algorithm for three-way partitioning
Offset left = 0;
Offset mid = 0;
Offset right = count - 1;
while (mid <= right)
{
ElementType val = dataset_get(obj, vAcc_[ind + mid], cutfeat);
if (val < cutval)
{
std::swap(vAcc_[ind + left], vAcc_[ind + mid]);
left++;
mid++;
}
else if (val > cutval)
{
std::swap(vAcc_[ind + mid], vAcc_[ind + right]);
right--;
}
else
{
mid++;
}
}
lim1 = left;
lim2 = mid;
}
DistanceType computeInitialDistances(
const Derived& obj, const ElementType* vec, distance_vector_t& dists) const
{
assert(vec);
DistanceType dist = DistanceType();
for (Dimension i = 0; i < (DIM > 0 ? DIM : obj.dim_); ++i)
{
if (vec[i] < obj.root_bbox_[i].low)
{
dists[i] = obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].low, i);
dist += dists[i];
}
if (vec[i] > obj.root_bbox_[i].high)
{
dists[i] = obj.distance_.accum_dist(vec[i], obj.root_bbox_[i].high, i);
dist += dists[i];
}
}
return dist;
}
static void save_tree(const Derived& obj, std::ostream& stream, const NodeConstPtr tree)
{
save_value(stream, *tree);
if (tree->child1 != nullptr)
{
save_tree(obj, stream, tree->child1);
}
if (tree->child2 != nullptr)
{
save_tree(obj, stream, tree->child2);
}
}
static void load_tree(Derived& obj, std::istream& stream, NodePtr& tree)
{
tree = obj.pool_.template allocate<Node>();
load_value(stream, *tree);
if (tree->child1 != nullptr)
{
load_tree(obj, stream, tree->child1);
}
if (tree->child2 != nullptr)
{
load_tree(obj, stream, tree->child2);
}
}
void saveIndex(const Derived& obj, std::ostream& stream) const
{
save_value(stream, obj.size_);
save_value(stream, obj.dim_);
save_value(stream, obj.root_bbox_);
save_value(stream, obj.leaf_max_size_);
save_value(stream, obj.vAcc_);
if (obj.root_node_) save_tree(obj, stream, obj.root_node_);
}
void loadIndex(Derived& obj, std::istream& stream)
{
load_value(stream, obj.size_);
load_value(stream, obj.dim_);
load_value(stream, obj.root_bbox_);
load_value(stream, obj.leaf_max_size_);
load_value(stream, obj.vAcc_);
load_tree(obj, stream, obj.root_node_);
}
};
template <typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
class KDTreeSingleIndexAdaptor
: public KDTreeBaseClass<
KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, index_t>, Distance,
DatasetAdaptor, DIM, index_t>
{
public:
explicit KDTreeSingleIndexAdaptor(
const KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, index_t>&) = delete;
const DatasetAdaptor& dataset_;
const KDTreeSingleIndexAdaptorParams indexParams;
Distance distance_;
using Base = typename nanoflann::KDTreeBaseClass<
nanoflann::KDTreeSingleIndexAdaptor<Distance, DatasetAdaptor, DIM, index_t>, Distance,
DatasetAdaptor, DIM, index_t>;
using Offset = typename Base::Offset;
using Size = typename Base::Size;
using Dimension = typename Base::Dimension;
using ElementType = typename Base::ElementType;
using DistanceType = typename Base::DistanceType;
using IndexType = typename Base::IndexType;
using Node = typename Base::Node;
using NodePtr = Node*;
using Interval = typename Base::Interval;
using BoundingBox = typename Base::BoundingBox;
using distance_vector_t = typename Base::distance_vector_t;
template <class... Args>
explicit KDTreeSingleIndexAdaptor(
const Dimension dimensionality, const DatasetAdaptor& inputData,
const KDTreeSingleIndexAdaptorParams& params, Args&&... args)
: dataset_(inputData),
indexParams(params),
distance_(inputData, std::forward<Args>(args)...)
{
init(dimensionality, params);
}
explicit KDTreeSingleIndexAdaptor(
const Dimension dimensionality, const DatasetAdaptor& inputData,
const KDTreeSingleIndexAdaptorParams& params = {})
: dataset_(inputData), indexParams(params), distance_(inputData)
{
init(dimensionality, params);
}
private:
void init(const Dimension dimensionality, const KDTreeSingleIndexAdaptorParams& params)
{
Base::size_ = dataset_.kdtree_get_point_count();
Base::size_at_index_build_ = Base::size_;
Base::dim_ = dimensionality;
if (DIM > 0) Base::dim_ = DIM;
Base::leaf_max_size_ = params.leaf_max_size;
if (params.n_thread_build > 0)
{
Base::n_thread_build_ = params.n_thread_build;
}
else
{
Base::n_thread_build_ = std::max(std::thread::hardware_concurrency(), 1u);
}
if (!(params.flags & KDTreeSingleIndexAdaptorFlags::SkipInitialBuildIndex))
{
// Build KD-tree:
buildIndex();
}
}
public:
void buildIndex()
{
Base::size_ = dataset_.kdtree_get_point_count();
Base::size_at_index_build_ = Base::size_;
init_vind();
this->freeIndex(*this);
Base::size_at_index_build_ = Base::size_;
if (Base::size_ == 0) return;
computeBoundingBox(Base::root_bbox_);
// construct the tree
if (Base::n_thread_build_ == 1)
{
Base::root_node_ = this->divideTree(*this, 0, Base::size_, Base::root_bbox_);
}
else
{
#ifndef NANOFLANN_NO_THREADS
std::atomic<unsigned int> thread_count(0u);
std::mutex mutex;
Base::root_node_ = this->divideTreeConcurrent(
*this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
#else /* NANOFLANN_NO_THREADS */
throw std::runtime_error("Multithreading is disabled");
#endif /* NANOFLANN_NO_THREADS */
}
}
template <typename RESULTSET>
bool findNeighbors(
RESULTSET& result, const ElementType* vec, const SearchParameters& searchParams = {}) const
{
assert(vec);
if (this->size(*this) == 0) return false;
if (!Base::root_node_)
throw std::runtime_error(
"[nanoflann] findNeighbors() called before building the "
"index.");
float epsError = 1 + searchParams.eps;
// fixed or variable-sized container (depending on DIM)
distance_vector_t dists;
// Fill it with zeros.
auto zero = static_cast<typename RESULTSET::DistanceType>(0);
assign(dists, (DIM > 0 ? DIM : Base::dim_), zero);
DistanceType dist = this->computeInitialDistances(*this, vec, dists);
searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
if (searchParams.sorted) result.sort();
return result.full();
}
template <typename RESULTSET>
Size findWithinBox(RESULTSET& result, const BoundingBox& bbox) const
{
if (this->size(*this) == 0) return 0;
if (!Base::root_node_)
throw std::runtime_error(
"[nanoflann] findWithinBox() called before building the "
"index.");
std::stack<NodePtr> stack;
stack.push(Base::root_node_);
while (!stack.empty())
{
const NodePtr node = stack.top();
stack.pop();
// If this is a leaf node, then do check and return.
if (!node->child1) // (if one node is nullptr, both are)
{
for (Offset i = node->node_type.lr.left; i < node->node_type.lr.right; ++i)
{
if (contains(bbox, Base::vAcc_[i]))
{
if (!result.addPoint(0, Base::vAcc_[i]))
{
// the resultset doesn't want to receive any more
// points, we're done searching!
return result.size();
}
}
}
}
else
{
const int idx = node->node_type.sub.divfeat;
const auto low_bound = node->node_type.sub.divlow;
const auto high_bound = node->node_type.sub.divhigh;
if (bbox[idx].low <= low_bound) stack.push(node->child1);
if (bbox[idx].high >= high_bound) stack.push(node->child2);
}
}
return result.size();
}
Size knnSearch(
const ElementType* query_point, const Size num_closest, IndexType* out_indices,
DistanceType* out_distances) const
{
nanoflann::KNNResultSet<DistanceType, IndexType> resultSet(num_closest);
resultSet.init(out_indices, out_distances);
findNeighbors(resultSet, query_point);
return resultSet.size();
}
Size radiusSearch(
const ElementType* query_point, const DistanceType& radius,
std::vector<ResultItem<IndexType, DistanceType>>& IndicesDists,
const SearchParameters& searchParams = {}) const
{
RadiusResultSet<DistanceType, IndexType> resultSet(radius, IndicesDists);
const Size nFound = radiusSearchCustomCallback(query_point, resultSet, searchParams);
return nFound;
}
template <class SEARCH_CALLBACK>
Size radiusSearchCustomCallback(
const ElementType* query_point, SEARCH_CALLBACK& resultSet,
const SearchParameters& searchParams = {}) const
{
findNeighbors(resultSet, query_point, searchParams);
return resultSet.size();
}
Size rknnSearch(
const ElementType* query_point, const Size num_closest, IndexType* out_indices,
DistanceType* out_distances, const DistanceType& radius) const
{
nanoflann::RKNNResultSet<DistanceType, IndexType> resultSet(num_closest, radius);
resultSet.init(out_indices, out_distances);
findNeighbors(resultSet, query_point);
return resultSet.size();
}
public:
void init_vind()
{
// Create a permutable array of indices to the input vectors.
Base::size_ = dataset_.kdtree_get_point_count();
if (Base::vAcc_.size() != Base::size_) Base::vAcc_.resize(Base::size_);
for (IndexType i = 0; i < static_cast<IndexType>(Base::size_); i++) Base::vAcc_[i] = i;
}
void computeBoundingBox(BoundingBox& bbox)
{
const auto dims = (DIM > 0 ? DIM : Base::dim_);
resize(bbox, dims);
if (dataset_.kdtree_get_bbox(bbox))
{
// Done! It was implemented in derived class
}
else
{
const Size N = dataset_.kdtree_get_point_count();
if (!N)
throw std::runtime_error(
"[nanoflann] computeBoundingBox() called but "
"no data points found.");
for (Dimension i = 0; i < dims; ++i)
{
bbox[i].low = bbox[i].high = this->dataset_get(*this, Base::vAcc_[0], i);
}
for (Offset k = 1; k < N; ++k)
{
for (Dimension i = 0; i < dims; ++i)
{
const auto val = this->dataset_get(*this, Base::vAcc_[k], i);
if (val < bbox[i].low) bbox[i].low = val;
if (val > bbox[i].high) bbox[i].high = val;
}
}
}
}
bool contains(const BoundingBox& bbox, IndexType idx) const
{
const auto dims = (DIM > 0 ? DIM : Base::dim_);
for (Dimension i = 0; i < dims; ++i)
{
const auto point = this->dataset_.kdtree_get_pt(idx, i);
if (point < bbox[i].low || point > bbox[i].high) return false;
}
return true;
}
template <class RESULTSET>
bool searchLevel(
RESULTSET& result_set, const ElementType* vec, const NodePtr node, DistanceType mindist,
distance_vector_t& dists, const float epsError) const
{
// If this is a leaf node, then do check and return.
if (!node->child1) // (if one node is nullptr, both are)
{
for (Offset i = node->node_type.lr.left; i < node->node_type.lr.right; ++i)
{
const IndexType accessor = Base::vAcc_[i]; // reorder... : i;
DistanceType dist =
distance_.evalMetric(vec, accessor, (DIM > 0 ? DIM : Base::dim_));
if (dist < result_set.worstDist())
{
if (!result_set.addPoint(dist, Base::vAcc_[i]))
{
// the resultset doesn't want to receive any more
// points, we're done searching!
return false;
}
}
}
return true;
}
/* Which child branch should be taken first? */
Dimension idx = node->node_type.sub.divfeat;
ElementType val = vec[idx];
DistanceType diff1 = val - node->node_type.sub.divlow;
DistanceType diff2 = val - node->node_type.sub.divhigh;
NodePtr bestChild;
NodePtr otherChild;
DistanceType cut_dist;
if ((diff1 + diff2) < 0)
{
bestChild = node->child1;
otherChild = node->child2;
cut_dist = distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
}
else
{
bestChild = node->child2;
otherChild = node->child1;
cut_dist = distance_.accum_dist(val, node->node_type.sub.divlow, idx);
}
/* Call recursively to search next level down. */
if (!searchLevel(result_set, vec, bestChild, mindist, dists, epsError))
{
// the resultset doesn't want to receive any more points, we're done
// searching!
return false;
}
DistanceType dst = dists[idx];
mindist = mindist + cut_dist - dst;
dists[idx] = cut_dist;
if (mindist * epsError <= result_set.worstDist())
{
if (!searchLevel(result_set, vec, otherChild, mindist, dists, epsError))
{
// the resultset doesn't want to receive any more points, we're
// done searching!
return false;
}
}
dists[idx] = dst;
return true;
}
public:
void saveIndex(std::ostream& stream) const { Base::saveIndex(*this, stream); }
void loadIndex(std::istream& stream) { Base::loadIndex(*this, stream); }
}; // class KDTree
template <typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>
class KDTreeSingleIndexDynamicAdaptor_
: public KDTreeBaseClass<
KDTreeSingleIndexDynamicAdaptor_<Distance, DatasetAdaptor, DIM, IndexType>, Distance,
DatasetAdaptor, DIM, IndexType>
{
public:
const DatasetAdaptor& dataset_;
KDTreeSingleIndexAdaptorParams index_params_;
std::vector<int>& treeIndex_;
Distance distance_;
using Base = typename nanoflann::KDTreeBaseClass<
nanoflann::KDTreeSingleIndexDynamicAdaptor_<Distance, DatasetAdaptor, DIM, IndexType>,
Distance, DatasetAdaptor, DIM, IndexType>;
using ElementType = typename Base::ElementType;
using DistanceType = typename Base::DistanceType;
using Offset = typename Base::Offset;
using Size = typename Base::Size;
using Dimension = typename Base::Dimension;
using Node = typename Base::Node;
using NodePtr = Node*;
using Interval = typename Base::Interval;
using BoundingBox = typename Base::BoundingBox;
using distance_vector_t = typename Base::distance_vector_t;
KDTreeSingleIndexDynamicAdaptor_(
const Dimension dimensionality, const DatasetAdaptor& inputData,
std::vector<int>& treeIndex,
const KDTreeSingleIndexAdaptorParams& params = KDTreeSingleIndexAdaptorParams())
: dataset_(inputData), index_params_(params), treeIndex_(treeIndex), distance_(inputData)
{
Base::size_ = 0;
Base::size_at_index_build_ = 0;
for (auto& v : Base::root_bbox_) v = {};
Base::dim_ = dimensionality;
if (DIM > 0) Base::dim_ = DIM;
Base::leaf_max_size_ = params.leaf_max_size;
if (params.n_thread_build > 0)
{
Base::n_thread_build_ = params.n_thread_build;
}
else
{
Base::n_thread_build_ = std::max(std::thread::hardware_concurrency(), 1u);
}
}
KDTreeSingleIndexDynamicAdaptor_(const KDTreeSingleIndexDynamicAdaptor_& rhs) = default;
KDTreeSingleIndexDynamicAdaptor_ operator=(const KDTreeSingleIndexDynamicAdaptor_& rhs)
{
KDTreeSingleIndexDynamicAdaptor_ tmp(rhs);
std::swap(Base::vAcc_, tmp.Base::vAcc_);
std::swap(Base::leaf_max_size_, tmp.Base::leaf_max_size_);
std::swap(index_params_, tmp.index_params_);
std::swap(treeIndex_, tmp.treeIndex_);
std::swap(Base::size_, tmp.Base::size_);
std::swap(Base::size_at_index_build_, tmp.Base::size_at_index_build_);
std::swap(Base::root_node_, tmp.Base::root_node_);
std::swap(Base::root_bbox_, tmp.Base::root_bbox_);
std::swap(Base::pool_, tmp.Base::pool_);
return *this;
}
void buildIndex()
{
Base::size_ = Base::vAcc_.size();
this->freeIndex(*this);
Base::size_at_index_build_ = Base::size_;
if (Base::size_ == 0) return;
computeBoundingBox(Base::root_bbox_);
// construct the tree
if (Base::n_thread_build_ == 1)
{
Base::root_node_ = this->divideTree(*this, 0, Base::size_, Base::root_bbox_);
}
else
{
#ifndef NANOFLANN_NO_THREADS
std::atomic<unsigned int> thread_count(0u);
std::mutex mutex;
Base::root_node_ = this->divideTreeConcurrent(
*this, 0, Base::size_, Base::root_bbox_, thread_count, mutex);
#else /* NANOFLANN_NO_THREADS */
throw std::runtime_error("Multithreading is disabled");
#endif /* NANOFLANN_NO_THREADS */
}
}
template <typename RESULTSET>
bool findNeighbors(
RESULTSET& result, const ElementType* vec, const SearchParameters& searchParams = {}) const
{
assert(vec);
if (this->size(*this) == 0) return false;
if (!Base::root_node_) return false;
float epsError = 1 + searchParams.eps;
// fixed or variable-sized container (depending on DIM)
distance_vector_t dists;
// Fill it with zeros.
assign(
dists, (DIM > 0 ? DIM : Base::dim_),
static_cast<typename distance_vector_t::value_type>(0));
DistanceType dist = this->computeInitialDistances(*this, vec, dists);
searchLevel(result, vec, Base::root_node_, dist, dists, epsError);
if (searchParams.sorted) result.sort();
return result.full();
}
Size knnSearch(
const ElementType* query_point, const Size num_closest, IndexType* out_indices,
DistanceType* out_distances, const SearchParameters& searchParams = {}) const
{
nanoflann::KNNResultSet<DistanceType, IndexType> resultSet(num_closest);
resultSet.init(out_indices, out_distances);
findNeighbors(resultSet, query_point, searchParams);
return resultSet.size();
}
Size radiusSearch(
const ElementType* query_point, const DistanceType& radius,
std::vector<ResultItem<IndexType, DistanceType>>& IndicesDists,
const SearchParameters& searchParams = {}) const
{
RadiusResultSet<DistanceType, IndexType> resultSet(radius, IndicesDists);
const size_t nFound = radiusSearchCustomCallback(query_point, resultSet, searchParams);
return nFound;
}
template <class SEARCH_CALLBACK>
Size radiusSearchCustomCallback(
const ElementType* query_point, SEARCH_CALLBACK& resultSet,
const SearchParameters& searchParams = {}) const
{
findNeighbors(resultSet, query_point, searchParams);
return resultSet.size();
}
public:
void computeBoundingBox(BoundingBox& bbox)
{
const auto dims = (DIM > 0 ? DIM : Base::dim_);
resize(bbox, dims);
if (dataset_.kdtree_get_bbox(bbox))
{
// Done! It was implemented in derived class
}
else
{
const Size N = Base::size_;
if (!N)
throw std::runtime_error(
"[nanoflann] computeBoundingBox() called but "
"no data points found.");
for (Dimension i = 0; i < dims; ++i)
{
bbox[i].low = bbox[i].high = this->dataset_get(*this, Base::vAcc_[0], i);
}
for (Offset k = 1; k < N; ++k)
{
for (Dimension i = 0; i < dims; ++i)
{
const auto val = this->dataset_get(*this, Base::vAcc_[k], i);
if (val < bbox[i].low) bbox[i].low = val;
if (val > bbox[i].high) bbox[i].high = val;
}
}
}
}
template <class RESULTSET>
void searchLevel(
RESULTSET& result_set, const ElementType* vec, const NodePtr node, DistanceType mindist,
distance_vector_t& dists, const float epsError) const
{
// If this is a leaf node, then do check and return.
if (!node->child1) // (if one node is nullptr, both are)
{
for (Offset i = node->node_type.lr.left; i < node->node_type.lr.right; ++i)
{
const IndexType index = Base::vAcc_[i]; // reorder... : i;
if (treeIndex_[index] == -1) continue;
DistanceType dist = distance_.evalMetric(vec, index, (DIM > 0 ? DIM : Base::dim_));
if (dist < result_set.worstDist())
{
if (!result_set.addPoint(
static_cast<typename RESULTSET::DistanceType>(dist),
static_cast<typename RESULTSET::IndexType>(Base::vAcc_[i])))
{
// the resultset doesn't want to receive any more
// points, we're done searching!
return; // false;
}
}
}
return;
}
/* Which child branch should be taken first? */
Dimension idx = node->node_type.sub.divfeat;
ElementType val = vec[idx];
DistanceType diff1 = val - node->node_type.sub.divlow;
DistanceType diff2 = val - node->node_type.sub.divhigh;
NodePtr bestChild;
NodePtr otherChild;
DistanceType cut_dist;
if ((diff1 + diff2) < 0)
{
bestChild = node->child1;
otherChild = node->child2;
cut_dist = distance_.accum_dist(val, node->node_type.sub.divhigh, idx);
}
else
{
bestChild = node->child2;
otherChild = node->child1;
cut_dist = distance_.accum_dist(val, node->node_type.sub.divlow, idx);
}
/* Call recursively to search next level down. */
searchLevel(result_set, vec, bestChild, mindist, dists, epsError);
DistanceType dst = dists[idx];
mindist = mindist + cut_dist - dst;
dists[idx] = cut_dist;
if (mindist * epsError <= result_set.worstDist())
{
searchLevel(result_set, vec, otherChild, mindist, dists, epsError);
}
dists[idx] = dst;
}
public:
void saveIndex(std::ostream& stream) { saveIndex(*this, stream); }
void loadIndex(std::istream& stream) { loadIndex(*this, stream); }
};
template <typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename IndexType = uint32_t>
class KDTreeSingleIndexDynamicAdaptor
{
public:
using ElementType = typename Distance::ElementType;
using DistanceType = typename Distance::DistanceType;
using Offset = typename KDTreeSingleIndexDynamicAdaptor_<Distance, DatasetAdaptor, DIM>::Offset;
using Size = typename KDTreeSingleIndexDynamicAdaptor_<Distance, DatasetAdaptor, DIM>::Size;
using Dimension =
typename KDTreeSingleIndexDynamicAdaptor_<Distance, DatasetAdaptor, DIM>::Dimension;
protected:
Size leaf_max_size_;
Size treeCount_;
Size pointCount_;
const DatasetAdaptor& dataset_;
std::vector<int> treeIndex_;
std::unordered_set<int> removedPoints_;
KDTreeSingleIndexAdaptorParams index_params_;
Dimension dim_;
using index_container_t =
KDTreeSingleIndexDynamicAdaptor_<Distance, DatasetAdaptor, DIM, IndexType>;
std::vector<index_container_t> index_;
public:
const std::vector<index_container_t>& getAllIndices() const { return index_; }
private:
int First0Bit(IndexType num)
{
int pos = 0;
while (num & 1)
{
num = num >> 1;
pos++;
}
return pos;
}
void init()
{
using my_kd_tree_t =
KDTreeSingleIndexDynamicAdaptor_<Distance, DatasetAdaptor, DIM, IndexType>;
std::vector<my_kd_tree_t> index(
treeCount_, my_kd_tree_t(dim_ /*dim*/, dataset_, treeIndex_, index_params_));
index_ = index;
}
public:
Distance distance_;
explicit KDTreeSingleIndexDynamicAdaptor(
const int dimensionality, const DatasetAdaptor& inputData,
const KDTreeSingleIndexAdaptorParams& params = KDTreeSingleIndexAdaptorParams(),
const size_t maximumPointCount = 1000000000U)
: dataset_(inputData), index_params_(params), distance_(inputData)
{
treeCount_ = static_cast<size_t>(std::log2(maximumPointCount)) + 1;
pointCount_ = 0U;
dim_ = dimensionality;
treeIndex_.clear();
if (DIM > 0) dim_ = DIM;
leaf_max_size_ = params.leaf_max_size;
init();
const size_t num_initial_points = dataset_.kdtree_get_point_count();
if (num_initial_points > 0)
{
addPoints(0, num_initial_points - 1);
}
}
explicit KDTreeSingleIndexDynamicAdaptor(
const KDTreeSingleIndexDynamicAdaptor<Distance, DatasetAdaptor, DIM, IndexType>&) = delete;
void addPoints(IndexType start, IndexType end)
{
const Size count = end - start + 1;
int maxIndex = 0;
treeIndex_.resize(treeIndex_.size() + count);
for (IndexType idx = start; idx <= end; idx++)
{
const int pos = First0Bit(pointCount_);
maxIndex = std::max(pos, maxIndex);
treeIndex_[pointCount_] = pos;
const auto it = removedPoints_.find(idx);
if (it != removedPoints_.end())
{
removedPoints_.erase(it);
treeIndex_[idx] = pos;
}
for (int i = 0; i < pos; i++)
{
for (int j = 0; j < static_cast<int>(index_[i].vAcc_.size()); j++)
{
index_[pos].vAcc_.push_back(index_[i].vAcc_[j]);
if (treeIndex_[index_[i].vAcc_[j]] != -1) treeIndex_[index_[i].vAcc_[j]] = pos;
}
index_[i].vAcc_.clear();
}
index_[pos].vAcc_.push_back(idx);
pointCount_++;
}
for (int i = 0; i <= maxIndex; ++i)
{
index_[i].freeIndex(index_[i]);
if (!index_[i].vAcc_.empty()) index_[i].buildIndex();
}
}
void removePoint(size_t idx)
{
if (idx >= pointCount_) return;
removedPoints_.insert(idx);
treeIndex_[idx] = -1;
}
template <typename RESULTSET>
bool findNeighbors(
RESULTSET& result, const ElementType* vec, const SearchParameters& searchParams = {}) const
{
for (size_t i = 0; i < treeCount_; i++)
{
index_[i].findNeighbors(result, &vec[0], searchParams);
}
return result.full();
}
};
template <
class MatrixType, int32_t DIM = -1, class Distance = nanoflann::metric_L2,
bool row_major = true>
struct KDTreeEigenMatrixAdaptor
{
using self_t = KDTreeEigenMatrixAdaptor<MatrixType, DIM, Distance, row_major>;
using num_t = typename MatrixType::Scalar;
using IndexType = typename MatrixType::Index;
using metric_t = typename Distance::template traits<num_t, self_t, IndexType>::distance_t;
using index_t = KDTreeSingleIndexAdaptor<
metric_t, self_t, row_major ? MatrixType::ColsAtCompileTime : MatrixType::RowsAtCompileTime,
IndexType>;
index_t* index_;
using Offset = typename index_t::Offset;
using Size = typename index_t::Size;
using Dimension = typename index_t::Dimension;
explicit KDTreeEigenMatrixAdaptor(
const Dimension dimensionality, const std::reference_wrapper<const MatrixType>& mat,
const int leaf_max_size = 10, const unsigned int n_thread_build = 1)
: m_data_matrix(mat)
{
const auto dims = row_major ? mat.get().cols() : mat.get().rows();
if (static_cast<Dimension>(dims) != dimensionality)
throw std::runtime_error(
"Error: 'dimensionality' must match column count in data "
"matrix");
if (DIM > 0 && static_cast<int32_t>(dims) != DIM)
throw std::runtime_error(
"Data set dimensionality does not match the 'DIM' template "
"argument");
index_ = new index_t(
dims, *this /* adaptor */,
nanoflann::KDTreeSingleIndexAdaptorParams(
leaf_max_size, nanoflann::KDTreeSingleIndexAdaptorFlags::None, n_thread_build));
}
public:
KDTreeEigenMatrixAdaptor(const self_t&) = delete;
~KDTreeEigenMatrixAdaptor() { delete index_; }
const std::reference_wrapper<const MatrixType> m_data_matrix;
void query(
const num_t* query_point, const Size num_closest, IndexType* out_indices,
num_t* out_distances) const
{
nanoflann::KNNResultSet<num_t, IndexType> resultSet(num_closest);
resultSet.init(out_indices, out_distances);
index_->findNeighbors(resultSet, query_point);
}
inline const self_t& derived() const noexcept { return *this; }
inline self_t& derived() noexcept { return *this; }
// Must return the number of data points
inline Size kdtree_get_point_count() const
{
if (row_major)
return m_data_matrix.get().rows();
else
return m_data_matrix.get().cols();
}
// Returns the dim'th component of the idx'th point in the class:
inline num_t kdtree_get_pt(const IndexType idx, size_t dim) const
{
if (row_major)
return m_data_matrix.get().coeff(idx, IndexType(dim));
else
return m_data_matrix.get().coeff(IndexType(dim), idx);
}
// Optional bounding-box computation: return false to default to a standard
// bbox computation loop.
// Return true if the BBOX was already computed by the class and returned
// in "bb" so it can be avoided to redo it again. Look at bb.size() to
// find out the expected dimensionality (e.g. 2 or 3 for point clouds)
template <class BBOX>
inline bool kdtree_get_bbox(BBOX& /*bb*/) const
{
return false;
}
}; // end of KDTreeEigenMatrixAdaptor
// end of grouping
} // namespace nanoflann
#undef NANOFLANN_RESTRICT
nanoflann::KDTreeBaseClass
Definition nanoflann.hpp:1037
nanoflann::KDTreeBaseClass::freeIndex
void freeIndex(Derived &obj)
Definition nanoflann.hpp:1041
nanoflann::KDTreeBaseClass::veclen
Size veclen(const Derived &obj) const
Definition nanoflann.hpp:1139
nanoflann::KDTreeBaseClass::computeMinMax
void computeMinMax(const Derived &obj, Offset ind, Size count, Dimension element, ElementType &min_elem, ElementType &max_elem) const
Definition nanoflann.hpp:1161
nanoflann::KDTreeBaseClass::root_bbox_
BoundingBox root_bbox_
Definition nanoflann.hpp:1124
nanoflann::KDTreeBaseClass::saveIndex
void saveIndex(const Derived &obj, std::ostream &stream) const
Definition nanoflann.hpp:1537
nanoflann::KDTreeBaseClass::dim_
Dimension dim_
Dimensionality of each data point.
Definition nanoflann.hpp:1113
nanoflann::KDTreeBaseClass::distance_vector_t
typename array_or_vector< DIM, DistanceType >::type distance_vector_t
Definition nanoflann.hpp:1121
nanoflann::KDTreeBaseClass::planeSplit
void planeSplit(const Derived &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)
Definition nanoflann.hpp:1449
nanoflann::KDTreeBaseClass::n_thread_build_
Size n_thread_build_
Number of thread for concurrent tree build.
Definition nanoflann.hpp:1108
nanoflann::KDTreeBaseClass::divideTree
NodePtr divideTree(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox)
Definition nanoflann.hpp:1184
nanoflann::KDTreeBaseClass::vAcc_
std::vector< IndexType > vAcc_
Definition nanoflann.hpp:1055
nanoflann::KDTreeBaseClass::size
Size size(const Derived &obj) const
Definition nanoflann.hpp:1136
nanoflann::KDTreeBaseClass::size_at_index_build_
Size size_at_index_build_
Number of points in the dataset when the index was built.
Definition nanoflann.hpp:1112
nanoflann::KDTreeBaseClass::divideTreeConcurrent
NodePtr divideTreeConcurrent(Derived &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex)
Definition nanoflann.hpp:1259
nanoflann::KDTreeBaseClass::size_
Size size_
Number of current points in the dataset.
Definition nanoflann.hpp:1110
nanoflann::KDTreeBaseClass::usedMemory
Size usedMemory(const Derived &obj) const
Definition nanoflann.hpp:1151
nanoflann::KDTreeBaseClass::loadIndex
void loadIndex(Derived &obj, std::istream &stream)
Definition nanoflann.hpp:1552
nanoflann::KDTreeBaseClass::pool_
PooledAllocator pool_
Definition nanoflann.hpp:1133
nanoflann::KDTreeBaseClass::dataset_get
ElementType dataset_get(const Derived &obj, IndexType element, Dimension component) const
Helper accessor to the dataset points:
Definition nanoflann.hpp:1142
nanoflann::KDTreeBaseClass::BoundingBox
typename array_or_vector< DIM, Interval >::type BoundingBox
Definition nanoflann.hpp:1117
nanoflann::KDTreeSingleIndexAdaptor
Definition nanoflann.hpp:1609
nanoflann::KDTreeSingleIndexAdaptor::searchLevel
bool searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:2003
nanoflann::KDTreeSingleIndexAdaptor::saveIndex
void saveIndex(std::ostream &stream) const
Definition nanoflann.hpp:2080
nanoflann::KDTreeSingleIndexAdaptor::findWithinBox
Size findWithinBox(RESULTSET &result, const BoundingBox &bbox) const
Definition nanoflann.hpp:1801
nanoflann::KDTreeSingleIndexAdaptor::radiusSearch
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1891
nanoflann::KDTreeSingleIndexAdaptor< metric_t, self_t, row_major ? MatrixType::ColsAtCompileTime :MatrixType::RowsAtCompileTime, IndexType >::init_vind
void init_vind()
Definition nanoflann.hpp:1946
nanoflann::KDTreeSingleIndexAdaptor::buildIndex
void buildIndex()
Definition nanoflann.hpp:1714
nanoflann::KDTreeSingleIndexAdaptor< metric_t, self_t, row_major ? MatrixType::ColsAtCompileTime :MatrixType::RowsAtCompileTime, IndexType >::dataset_
const self_t & dataset_
Definition nanoflann.hpp:1616
nanoflann::KDTreeSingleIndexAdaptor::KDTreeSingleIndexAdaptor
KDTreeSingleIndexAdaptor(const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t > &)=delete
nanoflann::KDTreeSingleIndexAdaptor::findNeighbors
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1761
nanoflann::KDTreeSingleIndexAdaptor::rknnSearch
Size rknnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const
Definition nanoflann.hpp:1931
nanoflann::KDTreeSingleIndexAdaptor::radiusSearchCustomCallback
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:1907
nanoflann::KDTreeSingleIndexAdaptor::distance_vector_t
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:1645
nanoflann::KDTreeSingleIndexAdaptor::loadIndex
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:2087
nanoflann::KDTreeSingleIndexAdaptor::BoundingBox
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:1641
nanoflann::KDTreeSingleIndexAdaptor::KDTreeSingleIndexAdaptor
KDTreeSingleIndexAdaptor(const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params, Args &&... args)
Definition nanoflann.hpp:1668
nanoflann::KDTreeSingleIndexAdaptor::knnSearch
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances) const
Definition nanoflann.hpp:1862
nanoflann::KDTreeSingleIndexDynamicAdaptor_
Definition nanoflann.hpp:2133
nanoflann::KDTreeSingleIndexDynamicAdaptor_::radiusSearch
Size radiusSearch(const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2342
nanoflann::KDTreeSingleIndexDynamicAdaptor_::KDTreeSingleIndexDynamicAdaptor_
KDTreeSingleIndexDynamicAdaptor_(const Dimension dimensionality, const DatasetAdaptor &inputData, std::vector< int > &treeIndex, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
Definition nanoflann.hpp:2184
nanoflann::KDTreeSingleIndexDynamicAdaptor_::BoundingBox
typename Base::BoundingBox BoundingBox
Definition nanoflann.hpp:2163
nanoflann::KDTreeSingleIndexDynamicAdaptor_< Distance, DatasetAdaptor, DIM, IndexType >::dataset_
const DatasetAdaptor & dataset_
Definition nanoflann.hpp:2138
nanoflann::KDTreeSingleIndexDynamicAdaptor_::radiusSearchCustomCallback
Size radiusSearchCustomCallback(const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2358
nanoflann::KDTreeSingleIndexDynamicAdaptor_::KDTreeSingleIndexDynamicAdaptor_
KDTreeSingleIndexDynamicAdaptor_(const KDTreeSingleIndexDynamicAdaptor_ &rhs)=default
nanoflann::KDTreeSingleIndexDynamicAdaptor_::buildIndex
void buildIndex()
Definition nanoflann.hpp:2228
nanoflann::KDTreeSingleIndexDynamicAdaptor_::saveIndex
void saveIndex(std::ostream &stream)
Definition nanoflann.hpp:2474
nanoflann::KDTreeSingleIndexDynamicAdaptor_::distance_vector_t
typename Base::distance_vector_t distance_vector_t
Definition nanoflann.hpp:2167
nanoflann::KDTreeSingleIndexDynamicAdaptor_::loadIndex
void loadIndex(std::istream &stream)
Definition nanoflann.hpp:2481
nanoflann::KDTreeSingleIndexDynamicAdaptor_::knnSearch
Size knnSearch(const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2313
nanoflann::KDTreeSingleIndexDynamicAdaptor_::searchLevel
void searchLevel(RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
Definition nanoflann.hpp:2406
nanoflann::KDTreeSingleIndexDynamicAdaptor_::findNeighbors
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2277
nanoflann::KDTreeSingleIndexDynamicAdaptor_::operator=
KDTreeSingleIndexDynamicAdaptor_ operator=(const KDTreeSingleIndexDynamicAdaptor_ &rhs)
Definition nanoflann.hpp:2210
nanoflann::KDTreeSingleIndexDynamicAdaptor::findNeighbors
bool findNeighbors(RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
Definition nanoflann.hpp:2667
nanoflann::KDTreeSingleIndexDynamicAdaptor::dataset_
const DatasetAdaptor & dataset_
The source of our data.
Definition nanoflann.hpp:2518
nanoflann::KDTreeSingleIndexDynamicAdaptor::removePoint
void removePoint(size_t idx)
Definition nanoflann.hpp:2643
nanoflann::KDTreeSingleIndexDynamicAdaptor::addPoints
void addPoints(IndexType start, IndexType end)
Definition nanoflann.hpp:2604
nanoflann::KDTreeSingleIndexDynamicAdaptor::KDTreeSingleIndexDynamicAdaptor
KDTreeSingleIndexDynamicAdaptor(const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams(), const size_t maximumPointCount=1000000000U)
Definition nanoflann.hpp:2579
nanoflann::KDTreeSingleIndexDynamicAdaptor::treeIndex_
std::vector< int > treeIndex_
Definition nanoflann.hpp:2522
nanoflann::KDTreeSingleIndexDynamicAdaptor::getAllIndices
const std::vector< index_container_t > & getAllIndices() const
Definition nanoflann.hpp:2536
nanoflann::KDTreeSingleIndexDynamicAdaptor::dim_
Dimension dim_
Dimensionality of each data point.
Definition nanoflann.hpp:2527
nanoflann::KDTreeSingleIndexDynamicAdaptor::KDTreeSingleIndexDynamicAdaptor
KDTreeSingleIndexDynamicAdaptor(const KDTreeSingleIndexDynamicAdaptor< Distance, DatasetAdaptor, DIM, IndexType > &)=delete
nanoflann::KNNResultSet
Definition nanoflann.hpp:214
nanoflann::KNNResultSet::addPoint
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:248
nanoflann::KNNResultSet::worstDist
DistanceType worstDist() const noexcept
Returns the worst distance among found solutions if the search result is full, or the maximum possibl...
Definition nanoflann.hpp:284
nanoflann::PooledAllocator
Definition nanoflann.hpp:887
nanoflann::PooledAllocator::~PooledAllocator
~PooledAllocator()
Definition nanoflann.hpp:923
nanoflann::PooledAllocator::free_all
void free_all()
Definition nanoflann.hpp:926
nanoflann::PooledAllocator::malloc
void * malloc(const size_t req_size)
Definition nanoflann.hpp:942
nanoflann::PooledAllocator::allocate
T * allocate(const size_t count=1)
Definition nanoflann.hpp:991
nanoflann::PooledAllocator::PooledAllocator
PooledAllocator()
Definition nanoflann.hpp:918
nanoflann::RKNNResultSet
Definition nanoflann.hpp:299
nanoflann::RKNNResultSet::addPoint
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:339
nanoflann::RKNNResultSet::worstDist
DistanceType worstDist() const noexcept
Returns the worst distance among found solutions if the search result is full, or the maximum possibl...
Definition nanoflann.hpp:375
nanoflann::RadiusResultSet
Definition nanoflann.hpp:391
nanoflann::RadiusResultSet::worst_item
ResultItem< IndexType, DistanceType > worst_item() const
Definition nanoflann.hpp:432
nanoflann::RadiusResultSet::addPoint
bool addPoint(DistanceType dist, IndexType index)
Definition nanoflann.hpp:420
nanoflann::assign
std::enable_if< has_assign< Container >::value, void >::type assign(Container &c, const size_t nElements, const T &value)
Definition nanoflann.hpp:161
nanoflann::resize
std::enable_if< has_resize< Container >::value, void >::type resize(Container &c, const size_t nElements)
Definition nanoflann.hpp:140
nanoflann::pi_const
constexpr T pi_const()
Definition nanoflann.hpp:107
nanoflann::IndexDist_Sorter
Definition nanoflann.hpp:179
nanoflann::IndexDist_Sorter::operator()
bool operator()(const PairType &p1, const PairType &p2) const
Definition nanoflann.hpp:182
nanoflann::KDTreeBaseClass::Interval
Definition nanoflann.hpp:1099
nanoflann::KDTreeBaseClass::Node
Definition nanoflann.hpp:1074
nanoflann::KDTreeBaseClass::Node::right
Offset right
Indices of points in leaf node.
Definition nanoflann.hpp:1081
nanoflann::KDTreeBaseClass::Node::divfeat
Dimension divfeat
Dimension used for subdivision. The values used for subdivision.
Definition nanoflann.hpp:1085
nanoflann::KDTreeBaseClass::Node::child1
Node * child1
Definition nanoflann.hpp:1092
nanoflann::KDTreeBaseClass::Node::node_type
union nanoflann::KDTreeBaseClass::Node::@327270127162340211203002370327206303122355110302 node_type
nanoflann::KDTreeEigenMatrixAdaptor::query
void query(const num_t *query_point, const Size num_closest, IndexType *out_indices, num_t *out_distances) const
Definition nanoflann.hpp:2761
nanoflann::KDTreeEigenMatrixAdaptor::KDTreeEigenMatrixAdaptor
KDTreeEigenMatrixAdaptor(const self_t &)=delete
nanoflann::KDTreeEigenMatrixAdaptor< MatrixType, DIM, Distance, row_major >::Offset
typename index_t::Offset Offset
Definition nanoflann.hpp:2720
nanoflann::KDTreeEigenMatrixAdaptor::KDTreeEigenMatrixAdaptor
KDTreeEigenMatrixAdaptor(const Dimension dimensionality, const std::reference_wrapper< const MatrixType > &mat, const int leaf_max_size=10, const unsigned int n_thread_build=1)
Constructor: takes a const ref to the matrix object with the data points.
Definition nanoflann.hpp:2725
nanoflann::KDTreeSingleIndexAdaptorParams
Definition nanoflann.hpp:844
nanoflann::L1_Adaptor
Definition nanoflann.hpp:499
nanoflann::L2_Adaptor
Definition nanoflann.hpp:589
nanoflann::L2_Simple_Adaptor
Definition nanoflann.hpp:676
nanoflann::Metric
Definition nanoflann.hpp:484
nanoflann::ResultItem
Definition nanoflann.hpp:198
nanoflann::ResultItem::second
DistanceType second
Distance from sample to query point.
Definition nanoflann.hpp:205
nanoflann::ResultItem::first
IndexType first
Index of the sample in the dataset.
Definition nanoflann.hpp:204
nanoflann::SO2_Adaptor
Definition nanoflann.hpp:715
nanoflann::SO2_Adaptor::accum_dist
DistanceType accum_dist(const U a, const V b, const size_t) const
Definition nanoflann.hpp:731
nanoflann::SO3_Adaptor
Definition nanoflann.hpp:756
nanoflann::SearchParameters
Definition nanoflann.hpp:860
nanoflann::SearchParameters::sorted
bool sorted
only for radius search, require neighbours sorted by distance (default: true)
Definition nanoflann.hpp:864
nanoflann::SearchParameters::eps
float eps
search for eps-approximate neighbours (default: 0)
Definition nanoflann.hpp:863
nanoflann::array_or_vector
Definition nanoflann.hpp:1007
nanoflann::has_assign
Definition nanoflann.hpp:128
nanoflann::has_resize
Definition nanoflann.hpp:118
nanoflann::metric_L1::traits
Definition nanoflann.hpp:781
nanoflann::metric_L1
Definition nanoflann.hpp:778
nanoflann::metric_L2::traits
Definition nanoflann.hpp:791
nanoflann::metric_L2_Simple::traits
Definition nanoflann.hpp:801
nanoflann::metric_L2_Simple
Definition nanoflann.hpp:798
nanoflann::metric_L2
Definition nanoflann.hpp:788
nanoflann::metric_SO2::traits
Definition nanoflann.hpp:810
nanoflann::metric_SO2
Definition nanoflann.hpp:807
nanoflann::metric_SO3::traits
Definition nanoflann.hpp:819
nanoflann::metric_SO3
Definition nanoflann.hpp:816