sofa::helper::kdTree< Coord > Class Template Reference

#include <kdTree.h>

Detailed Description

template<class Coord>
class sofa::helper::kdTree< Coord >

This class implements classical kd tree for nearest neighbors search

• the tree is rebuild from points by calling build(p)
• N nearest points from point x (in terms of euclidean distance) are retrieved with getNClosest(distance/index_List , x , N)
• Caching may be used to speed up retrieval: if dx< (d(n)-d(0))/2, then the closest point is in the n-1 cached points (updateCachedDistances is used to update the n-1 distances) see for instance: [zhang92] report and [simon96] thesis for more details

Author

Benjamin Gilles

Classes
struct	TREENODE

Protected Attributes
type::vector< TREENODE >	tree
unsigned int	firstNode

Public Member Functions
bool	isEmpty () const
void	build (const VecCoord &positions)
	update tree (to be used whenever positions have changed) More...
void	build (const VecCoord &positions, const type::vector< unsigned int > &ROI)
	update tree based on positions subset (to be used whenever points p have changed) More...
void	getNClosest (distanceSet &cl, const Coord &x, const VecCoord &positions, const unsigned int n) const
	get an ordered set of n distance/index pairs between positions and x More...
unsigned int	getClosest (const Coord &x, const VecCoord &positions) const
	get the index of the closest point between positions and x More...
bool	getNClosestCached (distanceSet &cl, distanceToPoint &cacheThresh_max, distanceToPoint &cacheThresh_min, Coord &previous_x, const Coord &x, const VecCoord &positions, const unsigned int n) const
	use distance caching to accelerate closest point computation when positions are fixed (see simon96 thesis) More...

Protected Member Functions
void	print (const unsigned int index)
unsigned int	build (UIlist &list, unsigned char direction, const VecCoord &positions)
void	closest (distanceSet &cl, const Coord &x, const unsigned int &currentnode, const VecCoord &positions, unsigned N) const
void	closest (distanceToPoint &cl, const Coord &x, const unsigned int &currentnode, const VecCoord &positions) const

Friends
To be Data-zable
std::ostream &	operator<< (std::ostream &os, const kdTree< Coord > &)
std::istream &	operator>> (std::istream &is, kdTree< Coord > &)

Attribute details

firstNode

template<class Coord >

unsigned int sofa::helper::kdTree< Coord >::firstNode

protected

tree

template<class Coord >

type::vector< TREENODE > sofa::helper::kdTree< Coord >::tree

protected

Function details

build() [1/3]

template<class Coord >

void sofa::helper::kdTree< Coord >::build

(

const VecCoord &

positions

)

update tree (to be used whenever positions have changed)

build() [2/3]

template<class Coord >

void sofa::helper::kdTree< Coord >::build	(	const VecCoord &	positions,
		const type::vector< unsigned int > &	ROI
	)

update tree based on positions subset (to be used whenever points p have changed)

build() [3/3]

template<class Coord >

unsigned int sofa::helper::kdTree< Coord >::build ( UIlist &  list, unsigned char  direction, const VecCoord &  positions  )

protected

closest() [1/2]

template<class Coord >

void sofa::helper::kdTree< Coord >::closest ( distanceSet &  cl, const Coord &  x, const unsigned int &  currentnode, const VecCoord &  positions, unsigned  N  ) const

protected

closest() [2/2]

template<class Coord >

void sofa::helper::kdTree< Coord >::closest ( distanceToPoint &  cl, const Coord &  x, const unsigned int &  currentnode, const VecCoord &  positions  ) const

protected

getClosest()

template<class Coord >

unsigned int sofa::helper::kdTree< Coord >::getClosest	(	const Coord &	x,
		const VecCoord &	positions
	)		const

get the index of the closest point between positions and x

getNClosest()

template<class Coord >

void sofa::helper::kdTree< Coord >::getNClosest	(	distanceSet &	cl,
		const Coord &	x,
		const VecCoord &	positions,
		const unsigned int	n
	)		const

get an ordered set of n distance/index pairs between positions and x

getNClosestCached()

template<class Coord >

bool sofa::helper::kdTree< Coord >::getNClosestCached	(	distanceSet &	cl,
		distanceToPoint &	cacheThresh_max,
		distanceToPoint &	cacheThresh_min,
		Coord &	previous_x,
		const Coord &	x,
		const VecCoord &	positions,
		const unsigned int	n
	)		const

use distance caching to accelerate closest point computation when positions are fixed (see simon96 thesis)

isEmpty()

template<class Coord >

bool sofa::helper::kdTree< Coord >::isEmpty ( ) const

inline

print()

template<class Coord >

void sofa::helper::kdTree< Coord >::print ( const unsigned int  index )

protected

Enum details

anonymous enum

template<class Coord >

anonymous enum

Enumerator
dim

Related details

operator<<

template<class Coord >

std::ostream& operator<< ( std::ostream &  os, const kdTree< Coord > &    )

friend

operator>>

template<class Coord >

std::istream& operator>> ( std::istream &  is, kdTree< Coord > &    )

friend