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:

kdtree_get_point_count()
kdtree_fill_point_data() and must be aware of the need to call "kdtree_mark_as_outdated()" when the data points change to mark the cached KD-tree as invalid.

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:

[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:

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.

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:

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.

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]`

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:

It is called for the first time
The map has changed
The KD-tree was build for 3D.

Parameters:

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.

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:

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.

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]`

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:

It is called for the first time
The map has changed
The KD-tree was build for 2D.

Parameters:

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.

See also:: kdTreeNClosestPoint2D

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:

It is called for the first time
The map has changed
The KD-tree was build for 2D.

Parameters:

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.

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:

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.

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

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.

mrpt::math::KDTreeCapable Class Reference

Detailed Description

Classes

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation