Main MRPT website > C++ reference
MRPT logo
Classes | Public Member Functions | Protected Member Functions | Private Member Functions | Private Attributes

mrpt::math::KDTreeCapable Class Reference


Detailed Description

A base virtual class providing automatic, cached KD-tree-based look-up of points among data of arbitrary dimensionality.

Any derived class must only implement:

The KD-tree will be built on demand only upon call of any of the query methods provided by this class (kdTreeClosestPoint2D, etc.).

Notice that there is only ONE internal cached KD-tree, so if a method to query a 2D point is called, then another method for 3D points, then again the 2D method, three KD-trees will be built. So, try to group all the calls for a given dimensionality together or build different class instances for queries of each dimensionality, etc.

See also:
See some of the derived classes for example implementations of the pure virtual methods.

Definition at line 55 of file KDTreeCapable.h.

#include <mrpt/math/KDTreeCapable.h>

Inheritance diagram for mrpt::math::KDTreeCapable:
Inheritance graph
[legend]

List of all members.

Classes

struct  TKDTreeData
 Internal structure with a KD-tree representation. More...

Public Member Functions

 KDTreeCapable ()
 Default ctor.
virtual ~KDTreeCapable ()
 Dtor.
Public utility methods to query the KD-tree
size_t kdTreeClosestPoint2D (float x0, float y0, float &out_x, float &out_y, float &out_dist_sqr) const
 KD Tree-based search for the closest point (only ONE) to some given 2D coordinates.
size_t kdTreeClosestPoint2D (const TPoint2D &p0, TPoint2D &pOut, float &outDistSqr) const
float kdTreeClosestPoint2DsqrError (float x0, float y0) const
 Like kdTreeClosestPoint2D, but just return the square error from some point to its closest neighbor.
float kdTreeClosestPoint2DsqrError (const TPoint2D &p0) const
void kdTreeTwoClosestPoint2D (float x0, float y0, float &out_x1, float &out_y1, float &out_x2, float &out_y2, float &out_dist_sqr1, float &out_dist_sqr2) const
 KD Tree-based search for the TWO closest point to some given 2D coordinates.
void kdTreeTwoClosestPoint2D (const TPoint2D &p0, TPoint2D &pOut1, TPoint2D &pOut2, float &outDistSqr1, float &outDistSqr2) const
std::vector< size_t > kdTreeNClosestPoint2D (float x0, float y0, size_t N, std::vector< float > &out_x, std::vector< float > &out_y, std::vector< float > &out_dist_sqr) const
 KD Tree-based search for the N closest point to some given 2D coordinates.
std::vector< size_t > kdTreeNClosestPoint2D (const TPoint2D &p0, size_t N, std::vector< TPoint2D > &pOut, std::vector< float > &outDistSqr) const
void kdTreeNClosestPoint2DIdx (float x0, float y0, size_t N, std::vector< int > &out_idx, std::vector< float > &out_dist_sqr) const
 KD Tree-based search for the N closest point to some given 2D coordinates and returns their indexes.
void kdTreeNClosestPoint2DIdx (const TPoint2D &p0, size_t N, std::vector< int > &outIdx, std::vector< float > &outDistSqr) const
size_t kdTreeClosestPoint3D (float x0, float y0, float z0, float &out_x, float &out_y, float &out_z, float &out_dist_sqr) const
 KD Tree-based search for the closest point (only ONE) to some given 3D coordinates.
size_t kdTreeClosestPoint3D (const TPoint3D &p0, TPoint3D &pOut, float &outDistSqr) const
void kdTreeNClosestPoint3D (float x0, float y0, float z0, size_t N, std::vector< float > &out_x, std::vector< float > &out_y, std::vector< float > &out_z, std::vector< float > &out_dist_sqr) const
 KD Tree-based search for the N closest points to some given 3D coordinates.
void kdTreeNClosestPoint3D (const TPoint3D &p0, size_t N, std::vector< TPoint3D > &pOut, std::vector< float > &outDistSqr) const
void kdTreeNClosestPoint3DIdx (float x0, float y0, float z0, size_t N, std::vector< int > &out_idx, std::vector< float > &out_dist_sqr) const
 KD Tree-based search for the N closest point to some given 3D coordinates and returns their indexes.
void kdTreeNClosestPoint3DIdx (const TPoint3D &p0, size_t N, std::vector< int > &outIdx, std::vector< float > &outDistSqr) const

Protected Member Functions

void kdtree_mark_as_outdated () const
 To be called by child classes when KD tree data changes.
Virtual methods that MUST be implemented by children classes of KDTreeCapable
virtual size_t kdtree_get_point_count () const =0
 Must return the number of data points.
virtual void kdtree_fill_point_data (ANNpointArray &data, const int nDims) const =0
 Must fill out the data points in "data", such as the i'th point will be stored in (data[i][0],...,data[i][nDims-1]).

Private Member Functions

void rebuild_kdTree (size_t nDims) const
 Rebuild, if needed the KD-tree for 2D (nDims=2), 3D (nDims=3), ... usage (asking the child class for the data points).

Private Attributes

TKDTreeData KDTreeData
bool m_KDTreeDataIsUpToDate
 whether the KD tree needs to be rebuilt or not.

Constructor & Destructor Documentation

mrpt::math::KDTreeCapable::KDTreeCapable ( )

Default ctor.

virtual mrpt::math::KDTreeCapable::~KDTreeCapable ( ) [virtual]

Dtor.


Member Function Documentation

virtual void mrpt::math::KDTreeCapable::kdtree_fill_point_data ( ANNpointArray data,
const int  nDims 
) const [protected, pure virtual]

Must fill out the data points in "data", such as the i'th point will be stored in (data[i][0],...,data[i][nDims-1]).

Implemented in mrpt::slam::CPointsMap, and mrpt::vision::CFeatureList.

virtual size_t mrpt::math::KDTreeCapable::kdtree_get_point_count ( ) const [protected, pure virtual]

Must return the number of data points.

Implemented in mrpt::slam::CPointsMap, and mrpt::vision::CFeatureList.

void mrpt::math::KDTreeCapable::kdtree_mark_as_outdated ( ) const [inline, protected]

To be called by child classes when KD tree data changes.

Definition at line 308 of file KDTreeCapable.h.

size_t mrpt::math::KDTreeCapable::kdTreeClosestPoint2D ( float  x0,
float  y0,
float &  out_x,
float &  out_y,
float &  out_dist_sqr 
) const

KD Tree-based search for the closest point (only ONE) to some given 2D coordinates.

This method automatically build the "KDTreeData" structure when:

  • It is called for the first time
  • The map has changed
  • The KD-tree was build for 3D.
Parameters:
x0The X coordinate of the query.
y0The Y coordinate of the query.
out_xThe X coordinate of the found closest correspondence.
out_yThe Y coordinate of the found closest correspondence.
out_dist_sqrThe square distance between the query and the returned point.
Returns:
The index of the closest point in the map array.
See also:
kdTreeClosestPoint3D, kdTreeTwoClosestPoint2D
size_t mrpt::math::KDTreeCapable::kdTreeClosestPoint2D ( const TPoint2D p0,
TPoint2D pOut,
float &  outDistSqr 
) const [inline]

Definition at line 88 of file KDTreeCapable.h.

References mrpt::math::TPoint2D::x, and mrpt::math::TPoint2D::y.

float mrpt::math::KDTreeCapable::kdTreeClosestPoint2DsqrError ( const TPoint2D p0) const [inline]

Definition at line 102 of file KDTreeCapable.h.

References mrpt::math::TPoint2D::x, and mrpt::math::TPoint2D::y.

float mrpt::math::KDTreeCapable::kdTreeClosestPoint2DsqrError ( float  x0,
float  y0 
) const

Like kdTreeClosestPoint2D, but just return the square error from some point to its closest neighbor.

size_t mrpt::math::KDTreeCapable::kdTreeClosestPoint3D ( float  x0,
float  y0,
float  z0,
float &  out_x,
float &  out_y,
float &  out_z,
float &  out_dist_sqr 
) const

KD Tree-based search for the closest point (only ONE) to some given 3D coordinates.

This method automatically build the "KDTreeData" structure when:

  • It is called for the first time
  • The map has changed
  • The KD-tree was build for 2D.
Parameters:
x0The X coordinate of the query.
y0The Y coordinate of the query.
z0The Z coordinate of the query.
out_xThe X coordinate of the found closest correspondence.
out_yThe Y coordinate of the found closest correspondence.
out_zThe Z coordinate of the found closest correspondence.
out_dist_sqrThe square distance between the query and the returned point.
Returns:
The index of the closest point in the map array.
See also:
kdTreeClosestPoint2D
size_t mrpt::math::KDTreeCapable::kdTreeClosestPoint3D ( const TPoint3D p0,
TPoint3D pOut,
float &  outDistSqr 
) const [inline]
std::vector<size_t> mrpt::math::KDTreeCapable::kdTreeNClosestPoint2D ( const TPoint2D p0,
size_t  N,
std::vector< TPoint2D > &  pOut,
std::vector< float > &  outDistSqr 
) const [inline]

Definition at line 167 of file KDTreeCapable.h.

References mrpt::math::TPoint2D::x, and mrpt::math::TPoint2D::y.

std::vector<size_t> mrpt::math::KDTreeCapable::kdTreeNClosestPoint2D ( float  x0,
float  y0,
size_t  N,
std::vector< float > &  out_x,
std::vector< float > &  out_y,
std::vector< float > &  out_dist_sqr 
) const

KD Tree-based search for the N closest point to some given 2D coordinates.

This method automatically build the "KDTreeData" structure when:

  • It is called for the first time
  • The map has changed
  • The KD-tree was build for 3D.
Parameters:
x0The X coordinate of the query.
y0The Y coordinate of the query.
NThe number of closest points to search.
out_xThe vector containing the X coordinates of the correspondences.
out_yThe vector containing the Y coordinates of the correspondences.
out_dist_sqrThe vector containing the square distance between the query and the returned points.
Returns:
The list of indices
See also:
kdTreeClosestPoint2D
kdTreeTwoClosestPoint2D
void mrpt::math::KDTreeCapable::kdTreeNClosestPoint2DIdx ( float  x0,
float  y0,
size_t  N,
std::vector< int > &  out_idx,
std::vector< float > &  out_dist_sqr 
) const

KD Tree-based search for the N closest point to some given 2D coordinates and returns their indexes.

This method automatically build the "KDTreeData" structure when:

  • It is called for the first time
  • The map has changed
  • The KD-tree was build for 3D.
Parameters:
x0The X coordinate of the query.
y0The Y coordinate of the query.
NThe number of closest points to search.
out_idxThe indexes of the found closest correspondence.
out_dist_sqrThe square distance between the query and the returned point.
See also:
kdTreeClosestPoint2D
void mrpt::math::KDTreeCapable::kdTreeNClosestPoint2DIdx ( const TPoint2D p0,
size_t  N,
std::vector< int > &  outIdx,
std::vector< float > &  outDistSqr 
) const [inline]

Definition at line 199 of file KDTreeCapable.h.

References mrpt::math::TPoint2D::x, and mrpt::math::TPoint2D::y.

void mrpt::math::KDTreeCapable::kdTreeNClosestPoint3D ( const TPoint3D p0,
size_t  N,
std::vector< TPoint3D > &  pOut,
std::vector< float > &  outDistSqr 
) const [inline]
void mrpt::math::KDTreeCapable::kdTreeNClosestPoint3D ( float  x0,
float  y0,
float  z0,
size_t  N,
std::vector< float > &  out_x,
std::vector< float > &  out_y,
std::vector< float > &  out_z,
std::vector< float > &  out_dist_sqr 
) const

KD Tree-based search for the N closest points to some given 3D coordinates.

This method automatically build the "KDTreeData" structure when:

  • It is called for the first time
  • The map has changed
  • The KD-tree was build for 2D.
Parameters:
x0The X coordinate of the query.
y0The Y coordinate of the query.
z0The Z coordinate of the query.
NThe number of closest points to search.
out_xThe vector containing the X coordinates of the correspondences.
out_yThe vector containing the Y coordinates of the correspondences.
out_zThe vector containing the Z coordinates of the correspondences.
out_dist_sqrThe vector containing the square distance between the query and the returned points.
See also:
kdTreeNClosestPoint2D
void mrpt::math::KDTreeCapable::kdTreeNClosestPoint3DIdx ( const TPoint3D p0,
size_t  N,
std::vector< int > &  outIdx,
std::vector< float > &  outDistSqr 
) const [inline]
void mrpt::math::KDTreeCapable::kdTreeNClosestPoint3DIdx ( float  x0,
float  y0,
float  z0,
size_t  N,
std::vector< int > &  out_idx,
std::vector< float > &  out_dist_sqr 
) const

KD Tree-based search for the N closest point to some given 3D coordinates and returns their indexes.

This method automatically build the "KDTreeData" structure when:

  • It is called for the first time
  • The map has changed
  • The KD-tree was build for 2D.
Parameters:
x0The X coordinate of the query.
y0The Y coordinate of the query.
z0The Z coordinate of the query.
NThe number of closest points to search.
out_idxThe indexes of the found closest correspondence.
out_dist_sqrThe square distance between the query and the returned point.
See also:
kdTreeClosestPoint2D
void mrpt::math::KDTreeCapable::kdTreeTwoClosestPoint2D ( const TPoint2D p0,
TPoint2D pOut1,
TPoint2D pOut2,
float &  outDistSqr1,
float &  outDistSqr2 
) const [inline]

Definition at line 133 of file KDTreeCapable.h.

References mrpt::math::TPoint2D::x, and mrpt::math::TPoint2D::y.

void mrpt::math::KDTreeCapable::kdTreeTwoClosestPoint2D ( float  x0,
float  y0,
float &  out_x1,
float &  out_y1,
float &  out_x2,
float &  out_y2,
float &  out_dist_sqr1,
float &  out_dist_sqr2 
) const

KD Tree-based search for the TWO closest point to some given 2D coordinates.

This method automatically build the "KDTreeData" structure when:

  • It is called for the first time
  • The map has changed
  • The KD-tree was build for 3D.
Parameters:
x0The X coordinate of the query.
y0The Y coordinate of the query.
out_x1The X coordinate of the first correspondence.
out_y1The Y coordinate of the first correspondence.
out_x2The X coordinate of the second correspondence.
out_y2The Y coordinate of the second correspondence.
out_dist_sqr1The square distance between the query and the first returned point.
out_dist_sqr2The square distance between the query and the second returned point.
See also:
kdTreeClosestPoint2D
void mrpt::math::KDTreeCapable::rebuild_kdTree ( size_t  nDims) const [private]

Rebuild, if needed the KD-tree for 2D (nDims=2), 3D (nDims=3), ... usage (asking the child class for the data points).


Member Data Documentation

Definition at line 348 of file KDTreeCapable.h.

whether the KD tree needs to be rebuilt or not.

Definition at line 350 of file KDTreeCapable.h.




Page generated by Doxygen 1.7.3 for MRPT 0.9.4 SVN: at Sat Mar 26 06:16:28 UTC 2011