CoastalME (Coastal Modelling Environment)
Simulates the long-term behaviour of complex coastlines
Loading...
Searching...
No Matches
nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t > Class Template Reference

#include <nanoflann.hpp>

Inherits nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >.

Public Types

using Base
 
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
 
- Public Types inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
using ElementType
 
using DistanceType
 
using IndexType
 
using Offset
 
using Size
 
using Dimension
 
using NodePtr
 
using NodeConstPtr
 
using BoundingBox
 
using distance_vector_t
 

Public Member Functions

 KDTreeSingleIndexAdaptor (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t > &)=delete
 
template<class... Args>
 KDTreeSingleIndexAdaptor (const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params, Args &&... args)
 
 KDTreeSingleIndexAdaptor (const Dimension dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params={})
 
void buildIndex ()
 
void init_vind ()
 
void computeBoundingBox (BoundingBox &bbox)
 
template<class RESULTSET>
bool searchLevel (RESULTSET &result_set, const ElementType *vec, const NodePtr node, DistanceType mindist, distance_vector_t &dists, const float epsError) const
 
void saveIndex (std::ostream &stream) const
 
void loadIndex (std::istream &stream)
 
Query methods
template<typename RESULTSET>
bool findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParameters &searchParams={}) const
 
Size knnSearch (const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances) const
 
Size radiusSearch (const ElementType *query_point, const DistanceType &radius, std::vector< ResultItem< IndexType, DistanceType > > &IndicesDists, const SearchParameters &searchParams={}) const
 
template<class SEARCH_CALLBACK>
Size radiusSearchCustomCallback (const ElementType *query_point, SEARCH_CALLBACK &resultSet, const SearchParameters &searchParams={}) const
 
Size rknnSearch (const ElementType *query_point, const Size num_closest, IndexType *out_indices, DistanceType *out_distances, const DistanceType &radius) const
 
- Public Member Functions inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
void freeIndex (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj)
 
Size size (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj) const
 
Size veclen (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj) const
 
ElementType dataset_get (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, IndexType element, Dimension component) const
 Helper accessor to the dataset points:
 
Size usedMemory (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj) const
 
void computeMinMax (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, Offset ind, Size count, Dimension element, ElementType &min_elem, ElementType &max_elem) const
 
NodePtr divideTree (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset left, const Offset right, BoundingBox &bbox)
 
NodePtr divideTreeConcurrent (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset left, const Offset right, BoundingBox &bbox, std::atomic< unsigned int > &thread_count, std::mutex &mutex)
 
void middleSplit_ (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset ind, const Size count, Offset &index, Dimension &cutfeat, DistanceType &cutval, const BoundingBox &bbox)
 
void planeSplit (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const Offset ind, const Size count, const Dimension cutfeat, const DistanceType &cutval, Offset &lim1, Offset &lim2)
 
DistanceType computeInitialDistances (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, const ElementType *vec, distance_vector_t &dists) const
 
void saveIndex (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::ostream &stream) const
 
void loadIndex (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::istream &stream)
 

Data Fields

const DatasetAdaptor & dataset_
 
const KDTreeSingleIndexAdaptorParams indexParams
 
Distance distance_
 
- Data Fields inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
std::vector< IndexTypevAcc_
 
NodePtr root_node_
 
Size leaf_max_size_
 
Size n_thread_build_
 Number of thread for concurrent tree build.
 
Size size_
 Number of current points in the dataset.
 
Size size_at_index_build_
 Number of points in the dataset when the index was built.
 
Dimension dim_
 Dimensionality of each data point.
 
BoundingBox root_bbox_
 
PooledAllocator pool_
 

Private Member Functions

void init (const Dimension dimensionality, const KDTreeSingleIndexAdaptorParams &params)
 

Additional Inherited Members

- Static Public Member Functions inherited from nanoflann::KDTreeBaseClass< KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t >, Distance, DatasetAdaptor, -1, uint32_t >
static void save_tree (const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::ostream &stream, const NodeConstPtr tree)
 
static void load_tree (KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, -1, uint32_t > &obj, std::istream &stream, NodePtr &tree)
 

Detailed Description

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
class nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >

kd-tree static index

Contains the k-d trees and other information for indexing a set of points for nearest-neighbor matching.

The class "DatasetAdaptor" must provide the following interface (can be non-virtual, inlined methods):

// Must return the number of data poins
size_t kdtree_get_point_count() const { ... }
// Must return the dim'th component of the idx'th point in the class:
T kdtree_get_pt(const size_t idx, const size_t dim) const { ... }
// 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> bool kdtree_get_bbox(BBOX &bb) const
{
bb[0].low = ...; bb[0].high = ...; // 0th dimension limits
bb[1].low = ...; bb[1].high = ...; // 1st dimension limits
...
return true;
}
Template Parameters
DatasetAdaptorThe user-provided adaptor, which must be ensured to have a lifetime equal or longer than the instance of this class.
DistanceThe distance metric to use: nanoflann::metric_L1, nanoflann::metric_L2, nanoflann::metric_L2_Simple, etc.
DIMDimensionality of data points (e.g. 3 for 3D points)
IndexTypeWill be typically size_t or int

Definition at line 1545 of file nanoflann.hpp.

Member Typedef Documentation

◆ Base

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::Base
Initial value:
Distance, DatasetAdaptor, DIM, index_t>,
Distance, DatasetAdaptor, DIM, index_t>

Definition at line 1563 of file nanoflann.hpp.

◆ BoundingBox

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::BoundingBox = typename Base::BoundingBox

Define "BoundingBox" as a fixed-size or variable-size container depending on "DIM"

Definition at line 1583 of file nanoflann.hpp.

◆ Dimension

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::Dimension = typename Base::Dimension

Definition at line 1570 of file nanoflann.hpp.

◆ distance_vector_t

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::distance_vector_t = typename Base::distance_vector_t

Define "distance_vector_t" as a fixed-size or variable-size container depending on "DIM"

Definition at line 1587 of file nanoflann.hpp.

◆ DistanceType

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::DistanceType = typename Base::DistanceType

Definition at line 1573 of file nanoflann.hpp.

◆ ElementType

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::ElementType = typename Base::ElementType

Definition at line 1572 of file nanoflann.hpp.

◆ IndexType

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::IndexType = typename Base::IndexType

Definition at line 1574 of file nanoflann.hpp.

◆ Interval

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::Interval = typename Base::Interval

Definition at line 1579 of file nanoflann.hpp.

◆ Node

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::Node = typename Base::Node

Definition at line 1576 of file nanoflann.hpp.

◆ NodePtr

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::NodePtr = Node*

Definition at line 1577 of file nanoflann.hpp.

◆ Offset

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::Offset = typename Base::Offset

Definition at line 1568 of file nanoflann.hpp.

◆ Size

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
using nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::Size = typename Base::Size

Definition at line 1569 of file nanoflann.hpp.

Constructor & Destructor Documentation

◆ KDTreeSingleIndexAdaptor() [1/3]

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::KDTreeSingleIndexAdaptor ( const KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t > & )
explicitdelete

Deleted copy constructor

◆ KDTreeSingleIndexAdaptor() [2/3]

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
template<class... Args>
nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::KDTreeSingleIndexAdaptor ( const Dimension dimensionality,
const DatasetAdaptor & inputData,
const KDTreeSingleIndexAdaptorParams & params,
Args &&... args )
inlineexplicit

KDTree constructor

Refer to docs in README.md or online in https://github.com/jlblancoc/nanoflann

The KD-Tree point dimension (the length of each point in the datase, e.g. 3 for 3D points) is determined by means of:

  • The DIM template parameter if >0 (highest priority)
  • Otherwise, the dimensionality parameter of this constructor.
Parameters
inputDataDataset with the input features. Its lifetime must be equal or longer than that of the instance of this class.
paramsBasically, the maximum leaf node size

Note that there is a variable number of optional additional parameters which will be forwarded to the metric class constructor. Refer to example examples/pointcloud_custom_metric.cpp for a use case.

Definition at line 1610 of file nanoflann.hpp.

◆ KDTreeSingleIndexAdaptor() [3/3]

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::KDTreeSingleIndexAdaptor ( const Dimension dimensionality,
const DatasetAdaptor & inputData,
const KDTreeSingleIndexAdaptorParams & params = {} )
inlineexplicit

Definition at line 1620 of file nanoflann.hpp.

Member Function Documentation

◆ buildIndex()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::buildIndex ( )
inline

Builds the index

Definition at line 1660 of file nanoflann.hpp.

◆ computeBoundingBox()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::computeBoundingBox ( BoundingBox & bbox)
inline

Definition at line 1845 of file nanoflann.hpp.

◆ findNeighbors()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
template<typename RESULTSET>
bool nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::findNeighbors ( RESULTSET & result,
const ElementType * vec,
const SearchParameters & searchParams = {} ) const
inline

Find set of nearest neighbors to vec[0:dim-1]. Their indices are stored inside the result object.

Params: result = the result object in which the indices of the nearest-neighbors are stored vec = the vector for which to search the nearest neighbors

Template Parameters
RESULTSETShould be any ResultSet<DistanceType>
Returns
True if the requested neighbors could be found.
See also
knnSearch, radiusSearch
Note
If L2 norms are used, all returned distances are actually squared distances.

Definition at line 1708 of file nanoflann.hpp.

◆ init()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::init ( const Dimension dimensionality,
const KDTreeSingleIndexAdaptorParams & params )
inlineprivate

Definition at line 1629 of file nanoflann.hpp.

◆ init_vind()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::init_vind ( )
inline

Make sure the auxiliary list vind has the same size than the current dataset, and re-generate if size has changed.

Definition at line 1836 of file nanoflann.hpp.

◆ knnSearch()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
Size nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::knnSearch ( const ElementType * query_point,
const Size num_closest,
IndexType * out_indices,
DistanceType * out_distances ) const
inline

Find the "num_closest" nearest neighbors to the query_point[0:dim-1]. Their indices and distances are stored in the provided pointers to array/vector.

See also
radiusSearch, findNeighbors
Returns
Number N of valid points in the result set.
Note
If L2 norms are used, all returned distances are actually squared distances.
Only the first N entries in out_indices and out_distances will be valid. Return is less than num_closest only if the number of elements in the tree is less than num_closest.

Definition at line 1748 of file nanoflann.hpp.

◆ loadIndex()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::loadIndex ( std::istream & stream)
inline

Loads a previous index from a binary file. IMPORTANT NOTE: The set of data points is NOT stored in the file, so the index object must be constructed associated to the same source of data points used while building the index. See the example: examples/saveload_example.cpp

See also
loadIndex

Definition at line 1978 of file nanoflann.hpp.

◆ radiusSearch()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
Size nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::radiusSearch ( const ElementType * query_point,
const DistanceType & radius,
std::vector< ResultItem< IndexType, DistanceType > > & IndicesDists,
const SearchParameters & searchParams = {} ) const
inline

Find all the neighbors to query_point[0:dim-1] within a maximum radius. The output is given as a vector of pairs, of which the first element is a point index and the second the corresponding distance. Previous contents of IndicesDists are cleared.

If searchParams.sorted==true, the output list is sorted by ascending distances.

For a better performance, it is advisable to do a .reserve() on the vector if you have any wild guess about the number of expected matches.

See also
knnSearch, findNeighbors, radiusSearchCustomCallback
Returns
The number of points within the given radius (i.e. indices.size() or dists.size() )
Note
If L2 norms are used, search radius and all returned distances are actually squared distances.

Definition at line 1777 of file nanoflann.hpp.

◆ radiusSearchCustomCallback()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
template<class SEARCH_CALLBACK>
Size nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::radiusSearchCustomCallback ( const ElementType * query_point,
SEARCH_CALLBACK & resultSet,
const SearchParameters & searchParams = {} ) const
inline

Just like radiusSearch() but with a custom callback class for each point found in the radius of the query. See the source of RadiusResultSet<> as a start point for your own classes.

See also
radiusSearch

Definition at line 1795 of file nanoflann.hpp.

◆ rknnSearch()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
Size nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::rknnSearch ( const ElementType * query_point,
const Size num_closest,
IndexType * out_indices,
DistanceType * out_distances,
const DistanceType & radius ) const
inline

Find the first N neighbors to query_point[0:dim-1] within a maximum radius. The output is given as a vector of pairs, of which the first element is a point index and the second the corresponding distance. Previous contents of IndicesDists are cleared.

See also
radiusSearch, findNeighbors
Returns
Number N of valid points in the result set.
Note
If L2 norms are used, all returned distances are actually squared distances.
Only the first N entries in out_indices and out_distances will be valid. Return is less than num_closest only if the number of elements in the tree is less than num_closest.

Definition at line 1819 of file nanoflann.hpp.

◆ saveIndex()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::saveIndex ( std::ostream & stream) const
inline

Stores the index in a binary file. IMPORTANT NOTE: The set of data points is NOT stored in the file, so when loading the index object it must be constructed associated to the same source of data points used while building it. See the example: examples/saveload_example.cpp

See also
loadIndex

Definition at line 1968 of file nanoflann.hpp.

◆ searchLevel()

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
template<class RESULTSET>
bool nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::searchLevel ( RESULTSET & result_set,
const ElementType * vec,
const NodePtr node,
DistanceType mindist,
distance_vector_t & dists,
const float epsError ) const
inline

Performs an exact search in the tree starting from a node.

Template Parameters
RESULTSETShould be any ResultSet<DistanceType>
Returns
true if the search should be continued, false if the results are sufficient

Definition at line 1885 of file nanoflann.hpp.

Field Documentation

◆ dataset_

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
const DatasetAdaptor& nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::dataset_

The data source used by this index

Definition at line 1557 of file nanoflann.hpp.

◆ distance_

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
Distance nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::distance_

Definition at line 1561 of file nanoflann.hpp.

◆ indexParams

template<typename Distance, class DatasetAdaptor, int32_t DIM = -1, typename index_t = uint32_t>
const KDTreeSingleIndexAdaptorParams nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, index_t >::indexParams

Definition at line 1559 of file nanoflann.hpp.


The documentation for this class was generated from the following file: