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 <KDTreeQ.hpp>

Inherits Serializable.

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

struct	KDResult

Public Types
typedef rw::core::Ptr< KDTreeQ< VALUE_TYPE > >	Ptr

typedef rw::math::Q	KEY

typedef KDNode	Node

typedef KDResult	Result

typedef VALUE_TYPE	Value

Public Member Functions
	KDTreeQ (size_t dim)
	Constructor. More...

virtual	~KDTreeQ ()
	destructor

size_t	getDimensions () const
	gets the number of dimensions that this KDTreeQ supports More...

void	addNode (const rw::math::Q &key, VALUE_TYPE val)
	adds a key value pair to the KDTreeQ. More...

void	removeNode (const rw::math::Q &nnkey)
	remove the node with key nnkey More...

KDNode *	search (const rw::math::Q &nnkey)
	finds the KDNode with key equal to nnkey More...

KDNode &	nnSearch (const rw::math::Q &nnkey)
	finds the KDNode with the key closest too nnkey More...

void	nnSearchElipse (const rw::math::Q &nnkey, const rw::math::Q &radi, std::list< const KDNode * > &nodes)
	finds all neighbors in the hyperelipse with radius radi and center in nnkey. More...

void	nnSearchElipseRect (const rw::math::Q &nnkey, const rw::math::Q &radi, std::list< const KDNode * > &nodes)
	finds all neighbors in the hyperelipse with radius radi and center in nnkey. More...

void	nnSearchRect (const rw::math::Q &low, const rw::math::Q &upp, std::list< const KDNode * > &nodes)
	finds all neighbors in the hyperrectangle defined by the lower bound and the upper bound

void	read (rw::common::InputArchive &iarchive, const std::string &id)

void	write (rw::common::OutputArchive &oarchive, const std::string &id) const

Public Member Functions inherited from Serializable
virtual	~Serializable ()
	destructor

Static Public Member Functions
static KDTreeQ *	buildTree (std::vector< KDNode > &nodes)
	Builds a KDTreeQ from a list of key values and nodes. This method is more efficient than creating an empty KDTreeQ and then inserting nodes. More...

static KDTreeQ *	buildTree (const std::vector< KDNode * > &nodes)
	Builds a KDTreeQ from a list of key values and nodes. This method is more efficient than creating an empty KDTreeQ and then inserting nodes. More...

Detailed Description

template<class VALUE_TYPE>
class rwlibs::algorithms::KDTreeQ< VALUE_TYPE >

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.

This KDTree implementation takes any value type but the key is constrained to a rw::math::Q

Constructor & Destructor Documentation

◆ KDTreeQ()

KDTreeQ ( size_t dim )

inline

Constructor.

Parameters

dim	[in] the dimension of the keys in the KDTreeQ

Member Function Documentation

◆ addNode()

void addNode	(	const rw::math::Q &	key,
		VALUE_TYPE	val
	)

adds a key value pair to the KDTreeQ.

Parameters

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

◆ buildTree() [1/2]

static KDTreeQ* buildTree ( const std::vector< KDNode * > & nodes )

static

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

Parameters

nodes [in] a list of KDNode's

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

◆ buildTree() [2/2]

static KDTreeQ* buildTree ( std::vector< KDNode > & nodes )

static

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

Parameters

nodes [in] a list of KDNode's

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 KDTreeQ supports

Returns: the nr of dimensions of this KD-Tree

◆ nnSearch()

KDTreeQ< T >::KDNode & nnSearch ( const rw::math::Q & nnkey )

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 rw::math::Q &	nnkey,
		const rw::math::Q &	radi,
		std::list< const KDNode * > &	nodes
	)

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 rw::math::Q &	nnkey,
		const rw::math::Q &	radi,
		std::list< const KDNode * > &	nodes
	)

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

◆ read()

void read	(	rw::common::InputArchive &	iarchive,
		const std::string &	id
	)

inlinevirtual

Enable read-serialization of inherited class by implementing this method. Data is read from iarchive and filled into this object.

Parameters

iarchive	[in] the InputArchive from which to read data.
id	[in] The id of the serialized sobject.

Note: the id can be empty in which case the overloaded method should provide a default identifier. E.g. the Vector3D class defined "Vector3D" as its default id.

Implements Serializable.

◆ removeNode()

void removeNode ( const rw::math::Q & nnkey )

remove the node with key nnkey

Parameters

nnkey [in] the key of the node to remove

Returns

◆ search()

KDTreeQ< T >::KDNode * search ( const rw::math::Q & nnkey )

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

◆ write()

void write	(	rw::common::OutputArchive &	oarchive,
		const std::string &	id
	)		const

inlinevirtual

Enable write-serialization of inherited class by implementing this method. Data is written to oarchive from this object.

Parameters

oarchive	[out] the OutputArchive in which data should be written.
id	[in] The id of the serialized sobject.

Note: the id can be empty in which case the overloaded method should provide a default identifier. E.g. the Vector3D class defined "Vector3D" as its default id.

Implements Serializable.

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

KDTreeQ.hpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Detailed Description

template<class VALUE_TYPE> class rwlibs::algorithms::KDTreeQ< VALUE_TYPE >

Constructor & Destructor Documentation

◆ KDTreeQ()

Member Function Documentation

◆ addNode()

◆ buildTree() [1/2]

◆ buildTree() [2/2]

◆ getDimensions()

◆ nnSearch()

◆ nnSearchElipse()

◆ nnSearchElipseRect()

◆ read()

◆ removeNode()

◆ search()

◆ write()

template<class VALUE_TYPE>
class rwlibs::algorithms::KDTreeQ< VALUE_TYPE >