kd-tree index More...

#include <nanoflann.hpp>

Inheritance diagram for nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >:

Collaboration diagram for nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >:

Classes
struct	BranchStruct
	This record represents a branch point when finding neighbors in the tree. More...

struct	Interval

struct	Node

Public Types
typedef Distance::ElementType	ElementType

typedef Distance::DistanceType	DistanceType

Public Member Functions
	KDTreeSingleIndexAdaptor (const int dimensionality, const DatasetAdaptor &inputData, const KDTreeSingleIndexAdaptorParams &params=KDTreeSingleIndexAdaptorParams())
	KDTree constructor.

void	init ()

	~KDTreeSingleIndexAdaptor ()
	Standard destructor.

void	freeIndex ()
	Frees the previously-built index.

void	buildIndex ()
	Builds the index.

size_t	size () const
	Returns size of index.

size_t	veclen () const
	Returns the length of an index feature.

size_t	usedMemory () const
	Computes the inde memory usage Returns: memory used by the index.

void	saveIndex (FILE *stream)
	Stores the index in a binary file.

void	loadIndex (FILE *stream)
	Loads a previous index from a binary file.

Query methods
template<typename RESULTSET >
void	findNeighbors (RESULTSET &result, const ElementType *vec, const SearchParams &searchParams) const
	Find set of nearest neighbors to vec[0:dim-1].

void	knnSearch (const ElementType query_point, const size_t num_closest, IndexType out_indices, DistanceType *out_distances_sq, const int=10) const
	Find the "num_closest" nearest neighbors to the query_point[0:dim-1].

size_t	radiusSearch (const ElementType *query_point, const DistanceType radius, std::vector< std::pair< IndexType, DistanceType > > &IndicesDists, const SearchParams &searchParams) const
	Find all the neighbors to query_point[0:dim-1] within a maximum radius.

size_t	radiusSearch (const ElementType *query_point, const DistanceType radius, std::list< IndexType > &IndicesDists, const SearchParams &searchParams) const

Public Attributes
Distance	distance

Protected Types
typedef Node *	NodePtr

typedef array_or_vector_selector< DIM, Interval >::container_t	BoundingBox
	Define "BoundingBox" as a fixed-size or variable-size container depending on "DIM".

typedef array_or_vector_selector< DIM, DistanceType >::container_t	distance_vector_t
	Define "distance_vector_t" as a fixed-size or variable-size container depending on "DIM".

typedef BranchStruct< NodePtr, DistanceType >	BranchSt

typedef BranchSt *	Branch

Protected Attributes
std::vector< IndexType >	vind
	Array of indices to vectors in the dataset.

size_t	m_leaf_max_size

const DatasetAdaptor &	dataset
	The dataset used by this index.

const KDTreeSingleIndexAdaptorParams	index_params

size_t	m_size

int	dim
	Dimensionality of each data point.

NodePtr	root_node
	Array of k-d trees used to find neighbours.

BoundingBox	root_bbox

PooledAllocator	pool
	Pooled memory allocator.

Detailed Description

template<typename Distance, class DatasetAdaptor, int DIM = -1, typename IndexType = size_t>
class nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >

kd-tree 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 points
inline size_t kdtree_get_point_count() const { ... }
 
// [Only if using the metric_L2_Simple type] Must return the Euclidean (L2) distance between the vector "p1[0:size-1]" and the data point with index "idx_p2" stored in the class:
inline DistanceType kdtree_distance(const T *p1, const size_t idx_p2,size_t size) const { ... }
 
// Must return the dim'th component of the idx'th point in the class:
inline T kdtree_get_pt(const size_t idx, int 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

DatasetAdaptor	The user-provided adaptor (see comments above).
Distance	The distance metric to use: nanoflann::metric_L1, nanoflann::metric_L2, nanoflann::metric_L2_Simple, etc.
IndexType	Will be typically size_t or int

Definition at line 869 of file nanoflann.hpp.

Member Typedef Documentation

◆ BoundingBox

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

typedef array_or_vector_selector<DIM,Interval>::container_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::BoundingBox

protected

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

Definition at line 928 of file nanoflann.hpp.

◆ Branch

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

typedef BranchSt* nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::Branch

protected

Definition at line 959 of file nanoflann.hpp.

◆ BranchSt

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

typedef BranchStruct<NodePtr, DistanceType> nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::BranchSt

protected

Definition at line 958 of file nanoflann.hpp.

◆ distance_vector_t

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

typedef array_or_vector_selector<DIM,DistanceType>::container_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::distance_vector_t

protected

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

Definition at line 931 of file nanoflann.hpp.

◆ DistanceType

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

typedef Distance::DistanceType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::DistanceType

Definition at line 876 of file nanoflann.hpp.

◆ ElementType

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

typedef Distance::ElementType nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::ElementType

Definition at line 875 of file nanoflann.hpp.

◆ NodePtr

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

typedef Node* nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::NodePtr

protected

Definition at line 921 of file nanoflann.hpp.

Constructor & Destructor Documentation

◆ KDTreeSingleIndexAdaptor()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::KDTreeSingleIndexAdaptor	(	const int	dimensionality,
		const DatasetAdaptor &	inputData,
		const KDTreeSingleIndexAdaptorParams &	params = KDTreeSingleIndexAdaptorParams() )

inline

KDTree constructor.

Params: inputData = dataset with the input features params = parameters passed to the kdtree algorithm (see http://code.google.com/p/nanoflann/ for help choosing the parameters)

Definition at line 983 of file nanoflann.hpp.

      : m_leaf_max_size(0),
        dataset(inputData),
        index_params(params),
        m_size(0),
        dim(dimensionality),
        root_node(NULL),
        distance(inputData) {
    m_size = 0;
    if (DIM > 0)
      dim = DIM;
    else {
      if (params.dim > 0)
        dim = params.dim;
    }
    m_leaf_max_size = params.leaf_max_size;
  }

◆ ~KDTreeSingleIndexAdaptor()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::~KDTreeSingleIndexAdaptor ( )

inline

Standard destructor.

Definition at line 1014 of file nanoflann.hpp.

1014 {

1015 }

Member Function Documentation

◆ buildIndex()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::buildIndex ( )

inline

Builds the index.

Definition at line 1026 of file nanoflann.hpp.

                    {
    init_vind();
    freeIndex();
    if (m_size == 0)
      return;
    computeBoundingBox(root_bbox);
    root_node = divideTree(0, m_size, root_bbox);   // construct the tree
  }

Here is the caller graph for this function:

◆ findNeighbors()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

template<typename RESULTSET >

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::findNeighbors	(	RESULTSET &	result,
		const ElementType *	vec,
		const SearchParams &	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

RESULTSET Should be any ResultSet<DistanceType>

See also: knnSearch, radiusSearch

Definition at line 1073 of file nanoflann.hpp.

                                                             {
    assert(vec);
    if (!root_node)
      throw std::runtime_error(
          "[nanoflann] findNeighbors() called before building the index or no data points.");
    float epsError = 1 + searchParams.eps;
 
    distance_vector_t dists;  // fixed or variable-sized container (depending on DIM)
    dists.assign((DIM > 0 ? DIM : dim), 0);  // Fill it with zeros.
    DistanceType distsq = computeInitialDistances(vec, dists);
    searchLevel(result, vec, root_node, distsq, dists, epsError);  // "count_leaf" parameter removed since was neither used nor returned to the user.
  }

References nanoflann::CArray< T, N >::assign(), and nanoflann::SearchParams::eps.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ freeIndex()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::freeIndex ( )

inline

Frees the previously-built index.

Automatically called within buildIndex().

Definition at line 1018 of file nanoflann.hpp.

                   {
    pool.free_all();
    root_node = NULL;
  }

◆ init()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::init ( )

inline

Definition at line 1004 of file nanoflann.hpp.

              {
    m_size = dataset.kdtree_get_point_count();
 
    // Create a permutable array of indices to the input vectors.
    init_vind();
  }

Here is the caller graph for this function:

◆ knnSearch()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::knnSearch	(	const ElementType *	query_point,
		const size_t	num_closest,
		IndexType *	out_indices,
		DistanceType *	out_distances_sq,
		const int	= 10 ) const

inline

Find the "num_closest" nearest neighbors to the query_point[0:dim-1].

Their indices are stored inside the result object.

See also: radiusSearch, findNeighbors

Note: nChecks_IGNORED is ignored but kept for compatibility with the original FLANN interface.

Definition at line 1093 of file nanoflann.hpp.

                                               {
    nanoflann::KNNResultSet<DistanceType, IndexType> resultSet(num_closest);
    resultSet.init(out_indices, out_distances_sq);
    this->findNeighbors(resultSet, query_point, nanoflann::SearchParams());
  }

References nanoflann::KNNResultSet< DistanceType, IndexType, CountType >::init().

Here is the call graph for this function:

◆ loadIndex()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::loadIndex ( FILE * 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 1507 of file nanoflann.hpp.

                               {
    load_value(stream, m_size);
    load_value(stream, dim);
    load_value(stream, root_bbox);
    load_value(stream, m_leaf_max_size);
    load_value(stream, vind);
    load_tree(stream, root_node);
  }

References nanoflann::load_value().

Here is the call graph for this function:

◆ radiusSearch() [1/2]

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::radiusSearch	(	const ElementType *	query_point,
		const DistanceType	radius,
		std::list< IndexType > &	IndicesDists,
		const SearchParams &	searchParams ) const

inline

Definition at line 1127 of file nanoflann.hpp.

                                                              {
    RadiusResultList<DistanceType, IndexType> resultList(radius, IndicesDists);
    this->findNeighbors(resultList, query_point, searchParams);
 
    if (searchParams.sorted)
      IndicesDists.sort();
 
    return resultList.size();
  }

References nanoflann::RadiusResultList< DistanceType, IndexType >::size(), and nanoflann::SearchParams::sorted.

Here is the call graph for this function:

◆ radiusSearch() [2/2]

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::radiusSearch	(	const ElementType *	query_point,
		const DistanceType	radius,
		std::vector< std::pair< IndexType, DistanceType > > &	IndicesDists,
		const SearchParams &	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

Returns: The number of points within the given radius (i.e. indices.size() or dists.size() )

Definition at line 1114 of file nanoflann.hpp.

                                              {
    RadiusResultSet<DistanceType, IndexType> resultSet(radius, IndicesDists);
    this->findNeighbors(resultSet, query_point, searchParams);
 
    if (searchParams.sorted)
      std::sort(IndicesDists.begin(), IndicesDists.end(), IndexDist_Sorter());
 
    return resultSet.size();
  }

References nanoflann::RadiusResultSet< DistanceType, IndexType >::size(), and nanoflann::SearchParams::sorted.

Here is the call graph for this function:

Here is the caller graph for this function:

◆ saveIndex()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

void nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::saveIndex ( FILE * stream )

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 1494 of file nanoflann.hpp.

                               {
    save_value(stream, m_size);
    save_value(stream, dim);
    save_value(stream, root_bbox);
    save_value(stream, m_leaf_max_size);
    save_value(stream, vind);
    save_tree(stream, root_node);
  }

References nanoflann::save_value().

Here is the call graph for this function:

◆ size()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::size ( ) const

inline

Returns size of index.

Definition at line 1038 of file nanoflann.hpp.

                      {
    return m_size;
  }

◆ usedMemory()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::usedMemory ( ) const

inline

Computes the inde memory usage Returns: memory used by the index.

Definition at line 1053 of file nanoflann.hpp.

                            {
    return pool.usedMemory + pool.wastedMemory
        + dataset.kdtree_get_point_count() * sizeof(IndexType);  // pool memory and vind array memory
  }

◆ veclen()

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::veclen ( ) const

inline

Returns the length of an index feature.

Definition at line 1045 of file nanoflann.hpp.

                        {
    return static_cast<size_t>(DIM > 0 ? DIM : dim);
  }

Member Data Documentation

◆ dataset

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

const DatasetAdaptor& nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::dataset

protected

The dataset used by this index.

The source of our data

Definition at line 889 of file nanoflann.hpp.

◆ dim

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

int nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::dim

protected

Dimensionality of each data point.

Definition at line 894 of file nanoflann.hpp.

◆ distance

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

Distance nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::distance

Definition at line 974 of file nanoflann.hpp.

◆ index_params

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

const KDTreeSingleIndexAdaptorParams nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::index_params

protected

Definition at line 891 of file nanoflann.hpp.

◆ m_leaf_max_size

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::m_leaf_max_size

protected

Definition at line 884 of file nanoflann.hpp.

◆ m_size

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

size_t nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::m_size

protected

Definition at line 893 of file nanoflann.hpp.

◆ pool

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

PooledAllocator nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::pool

protected

Pooled memory allocator.

Using a pooled memory allocator is more efficient than allocating memory directly when there is a large number small of memory allocations.

Definition at line 970 of file nanoflann.hpp.

◆ root_bbox

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

BoundingBox nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::root_bbox

protected

Definition at line 961 of file nanoflann.hpp.

◆ root_node

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

NodePtr nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::root_node

protected

Array of k-d trees used to find neighbours.

Definition at line 957 of file nanoflann.hpp.

◆ vind

template<typename Distance , class DatasetAdaptor , int DIM = -1, typename IndexType = size_t>

std::vector<IndexType> nanoflann::KDTreeSingleIndexAdaptor< Distance, DatasetAdaptor, DIM, IndexType >::vind

protected

Array of indices to vectors in the dataset.

Definition at line 882 of file nanoflann.hpp.

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

src/particles/subgrid3DLegacyFramework/contactDetection/nanoflann.hpp

Classes

Public Types

Public Member Functions

Public Attributes

Protected Types

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ BoundingBox

◆ Branch

◆ BranchSt

◆ distance_vector_t

◆ DistanceType

◆ ElementType

◆ NodePtr

Constructor & Destructor Documentation

◆ KDTreeSingleIndexAdaptor()

◆ ~KDTreeSingleIndexAdaptor()

Member Function Documentation

◆ buildIndex()

◆ findNeighbors()

◆ freeIndex()

◆ init()

◆ knnSearch()

◆ loadIndex()

◆ radiusSearch() [1/2]

◆ radiusSearch() [2/2]

◆ saveIndex()

◆ size()

◆ usedMemory()

◆ veclen()

Member Data Documentation

◆ dataset

◆ dim

◆ distance

◆ index_params

◆ m_leaf_max_size

◆ m_size

◆ pool

◆ root_bbox

◆ root_node

◆ vind