KDTree< KEY, DIM > Class Template Reference

a space partitioning structure for organizing points in k-dimensional space. Used for searches involving multi.dimensional search keys, including nearest neighbor and range search. More...

#include <KDTree.hpp>

Classes
struct	KDNode
	a struct for the node in the tree More...
struct	KDResult

Public Member Functions
	KDTree (rw::core::Ptr< rw::math::Metric< KEY >> metric)
	Constructor. More...
virtual	~KDTree ()
	destructor
rw::core::Ptr< rw::math::Metric< KEY > >	getMetric ()
size_t	getDimensions () const
	gets the number of dimensions that this KDTree supports More...
void	addNode (const KEY &key, boost::any val)
	adds a key value pair to the KDTree. More...
KDNode *	search (const KEY &nnkey)
	finds the KDNode with key equal to nnkey More...
KDNode &	nnSearch (const KEY &nnkey)
	finds the KDNode with the key closest too nnkey More...
void	nnSearchElipse (const KEY &nnkey, const KEY &radi, std::list< const KDNode * > &nodes)
	finds all neighbors in the hyperelipse with radius radi and center in nnkey. More...
void	nnSearchElipseRect (const KEY &nnkey, const KEY &radi, std::list< const KDNode * > &nodes)
	finds all neighbors in the hyperelipse with radius radi and center in nnkey. More...
void	nnSearchRect (const KEY &low, const KEY &upp, std::list< const KDNode * > &nodes)
	finds all neighbors in the hyperrectangle defined by the lower bound and the upper bound

Static Public Member Functions
static KDTree< KEY, DIM > *	buildTree (std::vector< KDNode > &nodes, rw::core::Ptr< rw::math::Metric< KEY >> metric)
	Builds a KDTree from a list of key values and nodes. This method is more efficient than creating an empty KDTree and then inserting nodes. More...
static KDTree< KEY, DIM > *	buildTree (const std::vector< KDNode * > &nodes, rw::core::Ptr< rw::math::Metric< KEY >> metric)
	Builds a KDTree from a list of key values and nodes. This method is more efficient than creating an empty KDTree and then inserting nodes. More...

Detailed Description

template<class KEY, size_t DIM>
class rwlibs::algorithms::KDTree< KEY, DIM >

a space partitioning structure for organizing points in k-dimensional space. Used for searches involving multi.dimensional search keys, including nearest neighbor and range search.

KEY must implement: copyable operator[] operator() TODO: remove one of the operators (change code in KDTREE)

Constructor & Destructor Documentation

KDTree()

KDTree ( rw::core::Ptr< rw::math::Metric< KEY >>  metric )

inline

Constructor.

Parameters

metric

documentation missing !

Member Function Documentation

addNode()

void addNode ( const KEY &  key, boost::any  val  )

inline

adds a key value pair to the KDTree.

Parameters

key	[in] must be the same length as the dimensionality of the KDTree
val	[in] value that is to be stored at the keys position

buildTree() [1/2]

static KDTree<KEY, DIM>* buildTree ( const std::vector< KDNode * > &  nodes, rw::core::Ptr< rw::math::Metric< KEY >>  metric  )

inlinestatic

Builds a KDTree from a list of key values and nodes. This method is more efficient than creating an empty KDTree and then inserting nodes.

Parameters

nodes	[in] a list of KDNode's
metric	documentation missing !

Returns

if build succesfull then a pointer to a KD-tree is returned else NULL

buildTree() [2/2]

static KDTree<KEY, DIM>* buildTree ( std::vector< KDNode > &  nodes, rw::core::Ptr< rw::math::Metric< KEY >>  metric  )

inlinestatic

Builds a KDTree from a list of key values and nodes. This method is more efficient than creating an empty KDTree and then inserting nodes.

Parameters

nodes	[in] a list of KDNode's
metric	documentation missing !

Returns

if build succesfull then a pointer to a KD-tree is returned else NULL

getDimensions()

size_t getDimensions ( ) const

inline

gets the number of dimensions that this KDTree supports

Returns

the nr of dimensions of this KD-Tree

nnSearch()

KDNode& nnSearch ( const KEY &  nnkey )

inline

finds the KDNode with the key closest too nnkey

Parameters

nnkey

[in] the key to which the nearest neighbor is found

Returns

the nearest neighbor to nnkey

nnSearchElipse()

void nnSearchElipse ( const KEY &  nnkey, const KEY &  radi, std::list< const KDNode * > &  nodes  )

inline

finds all neighbors in the hyperelipse with radius radi and center in nnkey.

Parameters

nnkey	[in] the center of the hyperelipse
radi	[in] the radius of the hyperelipse in euclidean 2-norm
nodes	[out] a container for all nodes that is found within the hyperelipse

nnSearchElipseRect()

void nnSearchElipseRect ( const KEY &  nnkey, const KEY &  radi, std::list< const KDNode * > &  nodes  )

inline

finds all neighbors in the hyperelipse with radius radi and center in nnkey.

Parameters

nnkey	[in] the center of the hyperelipse
radi	[in] the radius of the hyperelipse in euclidean 2-norm
nodes	[out] a container for all nodes that is found within the hyperelipse

search()

KDNode* search ( const KEY &  nnkey )

inline

finds the KDNode with key equal to nnkey

Parameters

nnkey

[in] the key that is to be found

Returns

KDNode with key equal to nnkey if existing, else NULL

---

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

• KDTree.hpp