RobWorkProject  24.5.15-
Classes | Public Types | Public Member Functions | Static Public Member Functions | List of all members
KDTreeQ< VALUE_TYPE > 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 <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...
 
KDNodesearch (const rw::math::Q &nnkey)
 finds the KDNode with key equal to nnkey More...
 
KDNodennSearch (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 KDTreeQbuildTree (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 KDTreeQbuildTree (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: