mm::KDTree< vec_t > Class Template Reference

#include <KDTree_fwd.hpp>

Detailed Description

template<class vec_t>
class mm::KDTree< vec_t >

Class representing a static k-d tree data structure.

This class is a wrapper around nanoflann library for nearest neighbours. For specific behaviors please refer to nanoflann documentation.

If dynamic insertions and removals are needed, use KDTreeMutable.

Usage example:

    Range<Vec3d> points = {{5, 4, 0}, {4, 2, 1}, {7, 6, 9}, {2, 2, 1}, {8, 0, 5},
                           {5, 7, 0}, {3, 3, 8}, {9, 7, 3}, {2, 2, 6}, {2, 0, 6}};
    KDTree<Vec3d> tree(points);  // Build kd-tree
    Range<double> distances2;  // squares of distances
    Range<int> closest;
    // Get 3 points closest to {4.1, 3, 0.5}
    std::tie(closest, distances2) = tree.query({4.1, 3, 0.5}, 3);
    // closest = [1, 0, 3];
    Vec3d p = tree.get(closest[0]);  // get coordinates of the closest point
    Range<Vec3d> closest_points = tree.get(closest);
    // distances2 = [1.26, 2.06, 5.66];
    std::cout << tree << std::endl;

See also

KDTreeMutable

Definition at line 36 of file KDTree_fwd.hpp.

Public Member Functions
	KDTree (const Range< vec_t > &points)
	Constructor that builds the search tree for the given points. More...
	KDTree ()
	Creates an empty KDTree. The tree may later be filled using KDTree::resetTree. More...
void	reset (const Range< vec_t > &points)
	Grows a new tree with new points. More...
std::pair< Range< int >, Range< scalar_t > >	query (const vec_t &point, int k=1) const
	Find k nearest neighbors to given point. More...
std::pair< Range< int >, Range< scalar_t > >	query (const vec_t &point, const scalar_t &radius_squared) const
	Find neighbors of point in given radius. More...
vec_t	get (int index) const
	Get the coordinates of a point in the tree. More...
Range< vec_t >	get (const Range< int > &indexes) const
	Vectorized version of KDTree::get. More...
int	size () const
	Returns number of points in this tree. More...

Public Types
enum	{ dim = vec_t::dim }
	Store dimension of the space. More...
typedef vec_t	vector_t
	Vector type used. More...
typedef vector_t::scalar_t	scalar_t
	Scalar type used. More...

Friends
template<class V >
std::ostream &	operator<< (std::ostream &os, const KDTree< V > &tree)
	Output basic info about given tree. More...

Private Types
typedef nanoflann::KDTreeSingleIndexAdaptor< nanoflann::L2_Simple_Adaptor< scalar_t, kdtree_internal::PointCloud< vec_t > >, kdtree_internal::PointCloud< vec_t >, dim, int >	kd_tree_t
	k-d tree type. More...

Private Attributes
kdtree_internal::PointCloud< vec_t >	points_
	Points, contained in the tree. More...
kd_tree_t	tree
	Actual tree build over points. More...

Member Enumeration Documentation

anonymous enum

template<class vec_t >

anonymous enum

Store dimension of the space.

Enumerator
dim	Dimensionality of the space.

Definition at line 41 of file KDTree_fwd.hpp.

Constructor & Destructor Documentation

KDTree() [1/2]

template<class vec_t >

mm::KDTree< vec_t >::KDTree ( const Range< vec_t > &  points )

inlineexplicit

Constructor that builds the search tree for the given points.

Parameters

points

A collection of points.

Definition at line 56 of file KDTree_fwd.hpp.

KDTree() [2/2]

template<class vec_t >

mm::KDTree< vec_t >::KDTree ( )

inline

Creates an empty KDTree. The tree may later be filled using KDTree::resetTree.

Definition at line 62 of file KDTree_fwd.hpp.

Member Function Documentation

get() [1/2]

template<class vec_t >

Range<vec_t> mm::KDTree< vec_t >::get ( const Range< int > &  indexes ) const

inline

Vectorized version of KDTree::get.

Definition at line 116 of file KDTree_fwd.hpp.

get() [2/2]

template<class vec_t >

vec_t mm::KDTree< vec_t >::get ( int  index ) const

inline

Get the coordinates of a point in the tree.

Given the index of a point as it appeared in the original list this function returns a its coordinates.

Note

This function is slow as it has to copy the values from its internal containers. It should not be used as a substitute for storing your own values.

Example:

    Range<Vec3d> points = {{5, 4, 0}, {4, 2, 1}, {7, 6, 9}, {2, 2, 1}, {8, 0, 5}};
    KDTree<Vec3d> kd3(points);
    ASSERT_EQ(points.size(), kd3.size());
    for (int i = 0; i < kd3.size(); ++i) {
        EXPECT_EQ(points[i], kd3.get(i));
    }
 
    EXPECT_EQ(points, kd3.get({0, 1, 2, 3, 4}));  // vectorized get
 
    Range<int> idxs = kd3.query({4.1, 3, 0.5}, 1).first;
    ASSERT_EQ(idxs.size(), 1);
    EXPECT_EQ(Vec3d({4, 2, 1}), kd3.get(idxs[0]));

Parameters

index

Index of the point as given in the constructor.

Returns

Vector object with the coordinates of the index-th point.

Definition at line 113 of file KDTree_fwd.hpp.

query() [1/2]

template<class vec_t >

std::pair< Range< int >, Range< typename vec_t::scalar_t > > mm::KDTree< vec_t >::query	(	const vec_t &	point,
		const scalar_t &	radius_squared
	)		const

Find neighbors of point in given radius.

Parameters

point	Find closest points to this point.
radius_squared	Maximum distance (squared) to search.

Returns

A pair of two vectors containing indices of nearest neighbors and squared distances from point to its neighbours.

Definition at line 28 of file KDTree.hpp.

query() [2/2]

template<class vec_t >

std::pair< Range< int >, Range< typename vec_t::scalar_t > > mm::KDTree< vec_t >::query	(	const vec_t &	point,
		int	k = 1
	)		const

Find k nearest neighbors to given point.

This method uses ANN query function.

Parameters

point	Find closest points to this point.
k	How many nearest points to find.

Returns

A pair of two vectors of size k containing indices of nearest neighbors and squared distances from point to its neighbours.

Definition at line 16 of file KDTree.hpp.

reset()

template<class vec_t >

void mm::KDTree< vec_t >::reset ( const Range< vec_t > &  points )

inline

Grows a new tree with new points.

This function deletes the old points and the old tree and builds a new one with the given points.

Parameters

points

A new container of points.

Definition at line 71 of file KDTree_fwd.hpp.

size()

template<class vec_t >

int mm::KDTree< vec_t >::size ( ) const

inline

Returns number of points in this tree.

Definition at line 126 of file KDTree_fwd.hpp.

Friends And Related Function Documentation

operator<<

template<class vec_t >

template<class V >

std::ostream& operator<< ( std::ostream &  os, const KDTree< V > &  tree  )

friend

Output basic info about given tree.

Definition at line 42 of file KDTree.hpp.

Member Data Documentation

points_

template<class vec_t >

kdtree_internal::PointCloud<vec_t> mm::KDTree< vec_t >::points_

private

Points, contained in the tree.

Definition at line 48 of file KDTree_fwd.hpp.

tree

template<class vec_t >

kd_tree_t mm::KDTree< vec_t >::tree

private

Actual tree build over points.

Definition at line 49 of file KDTree_fwd.hpp.

---

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

• include/medusa/bits/spatial_search/KDTree_fwd.hpp
• include/medusa/bits/spatial_search/KDTree.hpp