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.
Definition at line 55 of file KDTreeCapable.h.
#include <mrpt/math/KDTreeCapable.h>
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. |
mrpt::math::KDTreeCapable::KDTreeCapable | ( | ) |
Default ctor.
virtual mrpt::math::KDTreeCapable::~KDTreeCapable | ( | ) | [virtual] |
Dtor.
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:
x0 | The X coordinate of the query. |
y0 | The Y coordinate of the query. |
out_x | The X coordinate of the found closest correspondence. |
out_y | The Y coordinate of the found closest correspondence. |
out_dist_sqr | The square distance between the query and the returned point. |
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:
x0 | The X coordinate of the query. |
y0 | The Y coordinate of the query. |
z0 | The Z coordinate of the query. |
out_x | The X coordinate of the found closest correspondence. |
out_y | The Y coordinate of the found closest correspondence. |
out_z | The Z coordinate of the found closest correspondence. |
out_dist_sqr | The square distance between the query and the returned point. |
size_t mrpt::math::KDTreeCapable::kdTreeClosestPoint3D | ( | const TPoint3D & | p0, |
TPoint3D & | pOut, | ||
float & | outDistSqr | ||
) | const [inline] |
Definition at line 230 of file KDTreeCapable.h.
References mrpt::math::TPoint3D::x, mrpt::math::TPoint3D::y, and mrpt::math::TPoint3D::z.
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:
x0 | The X coordinate of the query. |
y0 | The Y coordinate of the query. |
N | The number of closest points to search. |
out_x | The vector containing the X coordinates of the correspondences. |
out_y | The vector containing the Y coordinates of the correspondences. |
out_dist_sqr | The vector containing the square distance between the query and the returned points. |
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:
x0 | The X coordinate of the query. |
y0 | The Y coordinate of the query. |
N | The number of closest points to search. |
out_idx | The indexes of the found closest correspondence. |
out_dist_sqr | The square distance between the query and the returned point. |
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] |
Definition at line 266 of file KDTreeCapable.h.
References mrpt::math::TPoint3D::x, mrpt::math::TPoint3D::y, and mrpt::math::TPoint3D::z.
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:
x0 | The X coordinate of the query. |
y0 | The Y coordinate of the query. |
z0 | The Z coordinate of the query. |
N | The number of closest points to search. |
out_x | The vector containing the X coordinates of the correspondences. |
out_y | The vector containing the Y coordinates of the correspondences. |
out_z | The vector containing the Z coordinates of the correspondences. |
out_dist_sqr | The vector containing the square distance between the query and the returned points. |
void mrpt::math::KDTreeCapable::kdTreeNClosestPoint3DIdx | ( | const TPoint3D & | p0, |
size_t | N, | ||
std::vector< int > & | outIdx, | ||
std::vector< float > & | outDistSqr | ||
) | const [inline] |
Definition at line 300 of file KDTreeCapable.h.
References mrpt::math::TPoint3D::x, mrpt::math::TPoint3D::y, and mrpt::math::TPoint3D::z.
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:
x0 | The X coordinate of the query. |
y0 | The Y coordinate of the query. |
z0 | The Z coordinate of the query. |
N | The number of closest points to search. |
out_idx | The indexes of the found closest correspondence. |
out_dist_sqr | The square distance between the query and the returned point. |
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:
x0 | The X coordinate of the query. |
y0 | The Y coordinate of the query. |
out_x1 | The X coordinate of the first correspondence. |
out_y1 | The Y coordinate of the first correspondence. |
out_x2 | The X coordinate of the second correspondence. |
out_y2 | The Y coordinate of the second correspondence. |
out_dist_sqr1 | The square distance between the query and the first returned point. |
out_dist_sqr2 | The square distance between the query and the second returned point. |
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).
TKDTreeData mrpt::math::KDTreeCapable::KDTreeData [mutable, private] |
Definition at line 348 of file KDTreeCapable.h.
bool mrpt::math::KDTreeCapable::m_KDTreeDataIsUpToDate [mutable, private] |
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 |