#include <KDTreeMutable_fwd.hpp>

Detailed Description

template<class vec_t>
class mm::KDTreeMutable< vec_t >

A k-d tree data structure that supports dynamic insertions and lazy-removal.

This class is a wrapper around nanoflann k-d tree implementation. For specific behavior please refer to nanoflann docs.

If dynamic structure is not needed, a faster static KDTree structure can be used.

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}};
    KDTreeMutable<Vec3d> tree(points);  //  Build kd-tree
    Range<double> distances;
    Range<int> closest;
    //  Get 3 points closest to {4.1, 3, 0.5}
    std::tie(closest, distances) = tree.query({4.1, 3, 0.5}, 3);
    //  Insertion and removal
    Vec3d new_point = {2, 30, 45};
    tree.insert(new_point);
    tree.remove(2);  // remove by index (assigned at insertion)
    std::cout << tree << std::endl;

See also: KDTree, KDGrid, GeneralFill, FindSupport

Definition at line 18 of file HalfLinksRefine_fwd.hpp.

Public Member Functions
	KDTreeMutable (const Range< vec_t > &points)
	Constructor that builds the search tree for the given points. More...

	KDTreeMutable ()
	Creates an empty k-d tree. More...

void	reset (const Range< vec_t > &points)
	Grows a new tree with new points. More...

void	insert (const vec_t &point)
	Insert a point into the tree. More...

void	insert (const Range< vec_t > &points)
	Inserts a sequence of points. More...

bool	existsPointInSphere (const vec_t &p, scalar_t r)
	Check if any point exists in sphere centered at `p` with radius `r`. More...

void	remove (int index)
	Removes a point with given index from the tree. More...

int	size () const
	Returns number of points in the tree. More...

std::pair< mm::Range< int >, mm::Range< double > >	query (const vec_t &point, int k=1)
	Find `k` nearest neighbors to given point. 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 KDTreeMutable< V > &tree)
	Output basic info about given tree. More...

Private Types
typedef nanoflann::KDTreeSingleIndexDynamicAdaptor< nanoflann::L2_Simple_Adaptor< scalar_t, kdtree_internal::PointCloud< vec_t > >, kdtree_internal::PointCloud< vec_t >, dim >	kd_tree_t
	Tree type. More...

Private Attributes
kdtree_internal::PointCloud< vec_t >	points_
	Points, contained in the tree. More...

int	size_
	Number of points 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 KDTreeMutable_fwd.hpp.

Constructor & Destructor Documentation

◆ KDTreeMutable() [1/2]

template<class vec_t >

mm::KDTreeMutable< vec_t >::KDTreeMutable ( 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 58 of file KDTreeMutable_fwd.hpp.

◆ KDTreeMutable() [2/2]

template<class vec_t >

mm::KDTreeMutable< vec_t >::KDTreeMutable ( )

inline

Creates an empty k-d tree.

Definition at line 63 of file KDTreeMutable_fwd.hpp.

Member Function Documentation

◆ existsPointInSphere()

template<class vec_t >

bool mm::KDTreeMutable< vec_t >::existsPointInSphere	(	const vec_t &	p,
		scalar_t	r
	)

inline

Check if any point exists in sphere centered at p with radius r.

Definition at line 88 of file KDTreeMutable_fwd.hpp.

◆ insert() [1/2]

template<class vec_t >

void mm::KDTreeMutable< vec_t >::insert ( const Range< vec_t > & points )

Inserts a sequence of points.

Definition at line 33 of file KDTreeMutable.hpp.

◆ insert() [2/2]

template<class vec_t >

void mm::KDTreeMutable< vec_t >::insert ( const vec_t & point )

Insert a point into the tree.

Parameters

point Point to be inserted into the tree.

Definition at line 24 of file KDTreeMutable.hpp.

◆ query()

template<class vec_t >

std::pair< mm::Range< int >, mm::Range< double > > mm::KDTreeMutable< vec_t >::query	(	const vec_t &	point,
		int	k = `1`
	)

Find k nearest neighbors to given point.

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 to said neighbors.

Exceptions

Assertion fails if there are not enough points in the tree.

Definition at line 45 of file KDTreeMutable.hpp.

◆ remove()

template<class vec_t >

void mm::KDTreeMutable< vec_t >::remove ( int index )

inline

Removes a point with given index from the tree.

The indexes of the points are given sequentially at insertion and do not change. The removal is lazy and point still takes up memory.

Definition at line 98 of file KDTreeMutable_fwd.hpp.

◆ reset()

template<class vec_t >

void mm::KDTreeMutable< 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 73 of file KDTreeMutable_fwd.hpp.

◆ size()

template<class vec_t >

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

inline

Returns number of points in the tree.

Definition at line 103 of file KDTreeMutable_fwd.hpp.

Friends And Related Function Documentation

◆ operator<<

template<class vec_t >

template<class V >

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

friend

Output basic info about given tree.

Definition at line 17 of file KDTreeMutable.hpp.

Member Data Documentation

◆ points_

template<class vec_t >

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

private

Points, contained in the tree.

Definition at line 49 of file KDTreeMutable_fwd.hpp.

◆ size_

template<class vec_t >

int mm::KDTreeMutable< vec_t >::size_

private

Number of points in the tree.

Definition at line 50 of file KDTreeMutable_fwd.hpp.

◆ tree

template<class vec_t >

kd_tree_t mm::KDTreeMutable< vec_t >::tree

private

Actual tree build over points.

Definition at line 51 of file KDTreeMutable_fwd.hpp.

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

include/medusa/bits/domains/HalfLinksRefine_fwd.hpp
include/medusa/bits/spatial_search/KDTreeMutable_fwd.hpp
include/medusa/bits/spatial_search/KDTreeMutable.hpp

Detailed Description

template<class vec_t> class mm::KDTreeMutable< vec_t >

Public Member Functions

Public Types

Friends

Private Types

Private Attributes

Member Enumeration Documentation

◆ anonymous enum

Constructor & Destructor Documentation

◆ KDTreeMutable() [1/2]

◆ KDTreeMutable() [2/2]

Member Function Documentation

◆ existsPointInSphere()

◆ insert() [1/2]

◆ insert() [2/2]

◆ query()

◆ remove()

◆ reset()

◆ size()

Friends And Related Function Documentation

◆ operator<<

Member Data Documentation

◆ points_

◆ size_

◆ tree

template<class vec_t>
class mm::KDTreeMutable< vec_t >