KdTree represents the base spatial locator class for kd-tree implementations. More...

#include <pcl/kdtree/kdtree.h>

Inheritance diagram for pcl::KdTree< PointT >:

Public Types
using	IndicesPtr = shared_ptr<Indices >
using	IndicesConstPtr = shared_ptr<const Indices >
using	PointCloud = pcl::PointCloud<PointT>
using	PointCloudPtr = typename PointCloud::Ptr
using	PointCloudConstPtr = typename PointCloud::ConstPtr
using	PointRepresentation = pcl::PointRepresentation<PointT>
using	PointRepresentationConstPtr = typename PointRepresentation::ConstPtr
using	Ptr = shared_ptr<KdTree<PointT> >
using	ConstPtr = shared_ptr<const KdTree<PointT> >

Public Member Functions
	KdTree (bool sorted=true)
	Empty constructor for KdTree.
virtual void	setInputCloud (const PointCloudConstPtr &cloud, const IndicesConstPtr &indices=IndicesConstPtr())
	Provide a pointer to the input dataset.
IndicesConstPtr	getIndices () const
	Get a pointer to the vector of indices used.
PointCloudConstPtr	getInputCloud () const
	Get a pointer to the input point cloud dataset.
void	setPointRepresentation (const PointRepresentationConstPtr &point_representation)
	Provide a pointer to the point representation to use to convert points into k-D vectors.
PointRepresentationConstPtr	getPointRepresentation () const
	Get a pointer to the point representation used when converting points into k-D vectors.
virtual	~KdTree ()
	Destructor for KdTree.
virtual int	nearestKSearch (const PointT &p_q, unsigned int k, Indices &k_indices, std::vector< float > &k_sqr_distances) const =0
	Search for k-nearest neighbors for the given query point.
virtual int	nearestKSearch (const PointCloud &cloud, int index, unsigned int k, Indices &k_indices, std::vector< float > &k_sqr_distances) const
	Search for k-nearest neighbors for the given query point.
template<typename PointTDiff>
int	nearestKSearchT (const PointTDiff &point, unsigned int k, Indices &k_indices, std::vector< float > &k_sqr_distances) const
	Search for k-nearest neighbors for the given query point.
virtual int	nearestKSearch (int index, unsigned int k, Indices &k_indices, std::vector< float > &k_sqr_distances) const
	Search for k-nearest neighbors for the given query point (zero-copy).
virtual int	radiusSearch (const PointT &p_q, double radius, Indices &k_indices, std::vector< float > &k_sqr_distances, unsigned int max_nn=0) const =0
	Search for all the nearest neighbors of the query point in a given radius.
virtual int	radiusSearch (const PointCloud &cloud, int index, double radius, Indices &k_indices, std::vector< float > &k_sqr_distances, unsigned int max_nn=0) const
	Search for all the nearest neighbors of the query point in a given radius.
template<typename PointTDiff>
int	radiusSearchT (const PointTDiff &point, double radius, Indices &k_indices, std::vector< float > &k_sqr_distances, unsigned int max_nn=0) const
	Search for all the nearest neighbors of the query point in a given radius.
virtual int	radiusSearch (int index, double radius, Indices &k_indices, std::vector< float > &k_sqr_distances, unsigned int max_nn=0) const
	Search for all the nearest neighbors of the query point in a given radius (zero-copy).
virtual void	setEpsilon (float eps)
	Set the search epsilon precision (error bound) for nearest neighbors searches.
float	getEpsilon () const
	Get the search epsilon precision (error bound) for nearest neighbors searches.
void	setMinPts (int min_pts)
	Minimum allowed number of k nearest neighbors points that a viable result must contain.
int	getMinPts () const
	Get the minimum allowed number of k nearest neighbors points that a viable result must contain.

Protected Member Functions
virtual std::string	getName () const =0
	Class getName method.

Protected Attributes
PointCloudConstPtr	input_
	The input point cloud dataset containing the points we need to use.
IndicesConstPtr	indices_
	A pointer to the vector of point indices to use.
float	epsilon_
	Epsilon precision (error bound) for nearest neighbors searches.
int	min_pts_
	Minimum allowed number of k nearest neighbors points that a viable result must contain.
bool	sorted_
	Return the radius search neighbours sorted.
PointRepresentationConstPtr	point_representation_
	For converting different point structures into k-dimensional vectors for nearest-neighbor search.

Detailed Description

template<typename PointT>
class pcl::KdTree< PointT >

KdTree represents the base spatial locator class for kd-tree implementations.

Author: Radu B Rusu, Bastian Steder, Michael Dixon

Definition at line 54 of file kdtree.h.

Member Typedef Documentation

◆ ConstPtr

template<typename PointT>

using pcl::KdTree< PointT >::ConstPtr = shared_ptr<const KdTree<PointT> >

Definition at line 69 of file kdtree.h.

◆ IndicesConstPtr

template<typename PointT>

using pcl::KdTree< PointT >::IndicesConstPtr = shared_ptr<const Indices >

Definition at line 58 of file kdtree.h.

◆ IndicesPtr

template<typename PointT>

using pcl::KdTree< PointT >::IndicesPtr = shared_ptr<Indices >

Definition at line 57 of file kdtree.h.

◆ PointCloud

template<typename PointT>

using pcl::KdTree< PointT >::PointCloud = pcl::PointCloud<PointT>

Definition at line 60 of file kdtree.h.

◆ PointCloudConstPtr

template<typename PointT>

using pcl::KdTree< PointT >::PointCloudConstPtr = typename PointCloud::ConstPtr

Definition at line 62 of file kdtree.h.

◆ PointCloudPtr

template<typename PointT>

using pcl::KdTree< PointT >::PointCloudPtr = typename PointCloud::Ptr

Definition at line 61 of file kdtree.h.

◆ PointRepresentation

template<typename PointT>

using pcl::KdTree< PointT >::PointRepresentation = pcl::PointRepresentation<PointT>

Definition at line 64 of file kdtree.h.

◆ PointRepresentationConstPtr

template<typename PointT>

using pcl::KdTree< PointT >::PointRepresentationConstPtr = typename PointRepresentation::ConstPtr

Definition at line 65 of file kdtree.h.

◆ Ptr

template<typename PointT>

using pcl::KdTree< PointT >::Ptr = shared_ptr<KdTree<PointT> >

Definition at line 68 of file kdtree.h.

Constructor & Destructor Documentation

◆ KdTree()

template<typename PointT>

pcl::KdTree< PointT >::KdTree ( bool sorted = true )

inline

Empty constructor for KdTree.

Sets some internal values to their defaults.

Parameters

[in] sorted set to true if the application that the tree will be used for requires sorted nearest neighbor indices (default). False otherwise.

Definition at line 74 of file kdtree.h.

Referenced by pcl::KdTreeFLANN< PointT, Dist >::KdTreeFLANN(), pcl::KdTreeFLANN< PointT, Dist >::KdTreeFLANN(), and pcl::KdTreeFLANN< PointT, Dist >::operator=().

◆ ~KdTree()

template<typename PointT>

virtual pcl::KdTree< PointT >::~KdTree ( )

inlinevirtual

Destructor for KdTree.

Deletes all allocated data arrays and destroys the kd-tree structures.

Definition at line 124 of file kdtree.h.

Member Function Documentation

◆ getEpsilon()

template<typename PointT>

float pcl::KdTree< PointT >::getEpsilon ( ) const

inline

Get the search epsilon precision (error bound) for nearest neighbors searches.

Definition at line 313 of file kdtree.h.

◆ getIndices()

template<typename PointT>

IndicesConstPtr pcl::KdTree< PointT >::getIndices ( ) const

inline

Get a pointer to the vector of indices used.

Definition at line 93 of file kdtree.h.

Referenced by pcl::extractEuclideanClusters().

◆ getInputCloud()

template<typename PointT>

PointCloudConstPtr pcl::KdTree< PointT >::getInputCloud ( ) const

inline

Get a pointer to the input point cloud dataset.

Definition at line 100 of file kdtree.h.

Referenced by pcl::extractEuclideanClusters(), and pcl::extractEuclideanClusters().

◆ getMinPts()

template<typename PointT>

int pcl::KdTree< PointT >::getMinPts ( ) const

inline

Get the minimum allowed number of k nearest neighbors points that a viable result must contain.

Definition at line 329 of file kdtree.h.

◆ getName()

template<typename PointT>

virtual std::string pcl::KdTree< PointT >::getName ( ) const

protectedpure virtual

Class getName method.

◆ getPointRepresentation()

template<typename PointT>

PointRepresentationConstPtr pcl::KdTree< PointT >::getPointRepresentation ( ) const

inline

Get a pointer to the point representation used when converting points into k-D vectors.

Definition at line 118 of file kdtree.h.

◆ nearestKSearch() [1/3]

template<typename PointT>

virtual int pcl::KdTree< PointT >::nearestKSearch	(	const PointCloud &	cloud,
		int	index,
		unsigned int	k,
		Indices &	k_indices,
		std::vector< float > &	k_sqr_distances ) const

inlinevirtual

Search for k-nearest neighbors for the given query point.

Attention: This method does not do any bounds checking for the input index (i.e., index >= cloud.size () || index < 0), and assumes valid (i.e., finite) data.

Parameters

[in]	cloud	the point cloud data
[in]	index	a valid index in cloud representing a valid (i.e., finite) query point
[in]	k	the number of neighbors to search for
[out]	k_indices	the resultant indices of the neighboring points (must be resized to k a priori!)
[out]	k_sqr_distances	the resultant squared distances to the neighboring points (must be resized to k a priori!)

Returns: number of neighbors found

Exceptions

asserts in debug mode if the index is not between 0 and the maximum number of points

Definition at line 155 of file kdtree.h.

◆ nearestKSearch() [2/3]

template<typename PointT>

virtual int pcl::KdTree< PointT >::nearestKSearch	(	const PointT &	p_q,
		unsigned int	k,
		Indices &	k_indices,
		std::vector< float > &	k_sqr_distances ) const

pure virtual

Search for k-nearest neighbors for the given query point.

Parameters

[in]	p_q	the given query point
[in]	k	the number of neighbors to search for
[out]	k_indices	the resultant indices of the neighboring points (must be resized to k a priori!)
[out]	k_sqr_distances	the resultant squared distances to the neighboring points (must be resized to k a priori!)

Returns: number of neighbors found

Implemented in pcl::KdTreeFLANN< PointT, Dist >, pcl::KdTreeFLANN< FeatureT >, pcl::KdTreeFLANN< pcl::InterestPoint >, pcl::KdTreeFLANN< pcl::PointXYZLAB >, pcl::KdTreeFLANN< pcl::PointXYZRGB >, pcl::KdTreeFLANN< pcl::VFHSignature308 >, pcl::KdTreeFLANN< PointTarget >, and pcl::KdTreeFLANN< SceneT >.

◆ nearestKSearch() [3/3]

template<typename PointT>

virtual int pcl::KdTree< PointT >::nearestKSearch	(	int	index,
		unsigned int	k,
		Indices &	k_indices,
		std::vector< float > &	k_sqr_distances ) const

inlinevirtual

Search for k-nearest neighbors for the given query point (zero-copy).

Attention: This method does not do any bounds checking for the input index (i.e., index >= cloud.size () || index < 0), and assumes valid (i.e., finite) data.

Parameters

[in]	index	a valid index representing a valid query point in the dataset given by setInputCloud. If indices were given in setInputCloud, index will be the position in the indices vector.
[in]	k	the number of neighbors to search for
[out]	k_indices	the resultant indices of the neighboring points (must be resized to k a priori!)
[out]	k_sqr_distances	the resultant squared distances to the neighboring points (must be resized to k a priori!)

Returns: number of neighbors found

Exceptions

asserts in debug mode if the index is not between 0 and the maximum number of points

Definition at line 198 of file kdtree.h.

◆ nearestKSearchT()

template<typename PointT>

template<typename PointTDiff>

int pcl::KdTree< PointT >::nearestKSearchT	(	const PointTDiff &	point,
		unsigned int	k,
		Indices &	k_indices,
		std::vector< float > &	k_sqr_distances ) const

inline

Search for k-nearest neighbors for the given query point.

This method accepts a different template parameter for the point type.

Parameters

[in]	point	the given query point
[in]	k	the number of neighbors to search for
[out]	k_indices	the resultant indices of the neighboring points (must be resized to k a priori!)
[out]	k_sqr_distances	the resultant squared distances to the neighboring points (must be resized to k a priori!)

Returns: number of neighbors found

Definition at line 172 of file kdtree.h.

Referenced by pcl::getApproximateIndices().

◆ radiusSearch() [1/3]

template<typename PointT>

virtual int pcl::KdTree< PointT >::radiusSearch	(	const PointCloud &	cloud,
		int	index,
		double	radius,
		Indices &	k_indices,
		std::vector< float > &	k_sqr_distances,
		unsigned int	max_nn = 0 ) const

inlinevirtual

Search for all the nearest neighbors of the query point in a given radius.

Attention: This method does not do any bounds checking for the input index (i.e., index >= cloud.size () || index < 0), and assumes valid (i.e., finite) data.

Parameters

[in]	cloud	the point cloud data
[in]	index	a valid index in cloud representing a valid (i.e., finite) query point
[in]	radius	the radius of the sphere bounding all of p_q's neighbors
[out]	k_indices	the resultant indices of the neighboring points
[out]	k_sqr_distances	the resultant squared distances to the neighboring points
[in]	max_nn	if given, bounds the maximum returned neighbors to this value. If max_nn is set to 0 or to a number higher than the number of points in the input cloud, all neighbors in radius will be returned.

Returns: number of neighbors found in radius

Exceptions

asserts in debug mode if the index is not between 0 and the maximum number of points

Definition at line 243 of file kdtree.h.

◆ radiusSearch() [2/3]

template<typename PointT>

virtual int pcl::KdTree< PointT >::radiusSearch	(	const PointT &	p_q,
		double	radius,
		Indices &	k_indices,
		std::vector< float > &	k_sqr_distances,
		unsigned int	max_nn = 0 ) const

pure virtual

Search for all the nearest neighbors of the query point in a given radius.

Parameters

[in]	p_q	the given query point
[in]	radius	the radius of the sphere bounding all of p_q's neighbors
[out]	k_indices	the resultant indices of the neighboring points
[out]	k_sqr_distances	the resultant squared distances to the neighboring points
[in]	max_nn	if given, bounds the maximum returned neighbors to this value. If max_nn is set to 0 or to a number higher than the number of points in the input cloud, all neighbors in radius will be returned.

Returns: number of neighbors found in radius

Implemented in pcl::KdTreeFLANN< PointT, Dist >, pcl::KdTreeFLANN< FeatureT >, pcl::KdTreeFLANN< pcl::InterestPoint >, pcl::KdTreeFLANN< pcl::PointXYZLAB >, pcl::KdTreeFLANN< pcl::PointXYZRGB >, pcl::KdTreeFLANN< pcl::VFHSignature308 >, pcl::KdTreeFLANN< PointTarget >, and pcl::KdTreeFLANN< SceneT >.

Referenced by pcl::extractEuclideanClusters(), pcl::extractEuclideanClusters(), and pcl::KdTree< PointInT >::radiusSearch().

◆ radiusSearch() [3/3]

template<typename PointT>

virtual int pcl::KdTree< PointT >::radiusSearch	(	int	index,
		double	radius,
		Indices &	k_indices,
		std::vector< float > &	k_sqr_distances,
		unsigned int	max_nn = 0 ) const

inlinevirtual

Search for all the nearest neighbors of the query point in a given radius (zero-copy).

Attention: This method does not do any bounds checking for the input index (i.e., index >= cloud.size () || index < 0), and assumes valid (i.e., finite) data.

Parameters

[in]	index	a valid index representing a valid query point in the dataset given by setInputCloud. If indices were given in setInputCloud, index will be the position in the indices vector.
[in]	radius	the radius of the sphere bounding all of p_q's neighbors
[out]	k_indices	the resultant indices of the neighboring points
[out]	k_sqr_distances	the resultant squared distances to the neighboring points
[in]	max_nn	if given, bounds the maximum returned neighbors to this value. If max_nn is set to 0 or to a number higher than the number of points in the input cloud, all neighbors in radius will be returned.

Returns: number of neighbors found in radius

Exceptions

asserts in debug mode if the index is not between 0 and the maximum number of points

Definition at line 290 of file kdtree.h.

◆ radiusSearchT()

template<typename PointT>

template<typename PointTDiff>

int pcl::KdTree< PointT >::radiusSearchT	(	const PointTDiff &	point,
		double	radius,
		Indices &	k_indices,
		std::vector< float > &	k_sqr_distances,
		unsigned int	max_nn = 0 ) const

inline

Search for all the nearest neighbors of the query point in a given radius.

Parameters

[in]	point	the given query point
[in]	radius	the radius of the sphere bounding all of p_q's neighbors
[out]	k_indices	the resultant indices of the neighboring points
[out]	k_sqr_distances	the resultant squared distances to the neighboring points
[in]	max_nn	if given, bounds the maximum returned neighbors to this value. If max_nn is set to 0 or to a number higher than the number of points in the input cloud, all neighbors in radius will be returned.

Returns: number of neighbors found in radius

Definition at line 262 of file kdtree.h.

◆ setEpsilon()

template<typename PointT>

virtual void pcl::KdTree< PointT >::setEpsilon ( float eps )

inlinevirtual

Set the search epsilon precision (error bound) for nearest neighbors searches.

Parameters

[in] eps precision (error bound) for nearest neighbors searches

Reimplemented in pcl::KdTreeFLANN< PointT, Dist >, pcl::KdTreeFLANN< FeatureT >, pcl::KdTreeFLANN< pcl::InterestPoint >, pcl::KdTreeFLANN< pcl::PointXYZLAB >, pcl::KdTreeFLANN< pcl::PointXYZRGB >, pcl::KdTreeFLANN< pcl::VFHSignature308 >, pcl::KdTreeFLANN< PointTarget >, and pcl::KdTreeFLANN< SceneT >.

Definition at line 306 of file kdtree.h.

◆ setInputCloud()

template<typename PointT>

virtual void pcl::KdTree< PointT >::setInputCloud	(	const PointCloudConstPtr &	cloud,
		const IndicesConstPtr &	indices = IndicesConstPtr () )

inlinevirtual

Provide a pointer to the input dataset.

Parameters

[in]	cloud	the const boost shared pointer to a PointCloud message
[in]	indices	the point indices subset that is to be used from cloud - if NULL the whole cloud is used

Reimplemented in pcl::KdTreeFLANN< PointT, Dist >, pcl::KdTreeFLANN< FeatureT >, pcl::KdTreeFLANN< pcl::InterestPoint >, pcl::KdTreeFLANN< pcl::PointXYZLAB >, pcl::KdTreeFLANN< pcl::PointXYZRGB >, pcl::KdTreeFLANN< pcl::VFHSignature308 >, pcl::KdTreeFLANN< PointTarget >, and pcl::KdTreeFLANN< SceneT >.

Definition at line 85 of file kdtree.h.

Referenced by pcl::KdTree< PointInT >::setPointRepresentation().

◆ setMinPts()

template<typename PointT>

void pcl::KdTree< PointT >::setMinPts ( int min_pts )

inline

Minimum allowed number of k nearest neighbors points that a viable result must contain.

Parameters

[in] min_pts the minimum number of neighbors in a viable neighborhood

Definition at line 322 of file kdtree.h.

◆ setPointRepresentation()

template<typename PointT>

void pcl::KdTree< PointT >::setPointRepresentation ( const PointRepresentationConstPtr & point_representation )

inline

Provide a pointer to the point representation to use to convert points into k-D vectors.

Parameters

[in] point_representation the const boost shared pointer to a PointRepresentation

Definition at line 109 of file kdtree.h.

Member Data Documentation

◆ epsilon_

template<typename PointT>

float pcl::KdTree< PointT >::epsilon_

protected

Epsilon precision (error bound) for nearest neighbors searches.

Definition at line 342 of file kdtree.h.

Referenced by pcl::KdTreeFLANN< PointT, Dist >::KdTreeFLANN(), pcl::KdTreeFLANN< PointT, Dist >::KdTreeFLANN(), pcl::KdTreeFLANN< PointT, Dist >::setEpsilon(), pcl::KdTreeFLANN< PointT, Dist >::setInputCloud(), and pcl::KdTreeFLANN< PointT, Dist >::setSortedResults().

◆ indices_

template<typename PointT>

IndicesConstPtr pcl::KdTree< PointT >::indices_

protected

A pointer to the vector of point indices to use.

Definition at line 339 of file kdtree.h.

Referenced by pcl::KdTreeFLANN< PointT, Dist >::setInputCloud().

◆ input_

template<typename PointT>

PointCloudConstPtr pcl::KdTree< PointT >::input_

protected

The input point cloud dataset containing the points we need to use.

Definition at line 336 of file kdtree.h.

Referenced by pcl::KdTreeFLANN< PointT, Dist >::setInputCloud().

◆ min_pts_

template<typename PointT>

int pcl::KdTree< PointT >::min_pts_

protected

Minimum allowed number of k nearest neighbors points that a viable result must contain.

Definition at line 345 of file kdtree.h.

◆ point_representation_

template<typename PointT>

PointRepresentationConstPtr pcl::KdTree< PointT >::point_representation_

protected

For converting different point structures into k-dimensional vectors for nearest-neighbor search.

Definition at line 351 of file kdtree.h.

Referenced by pcl::KdTreeFLANN< PointT, Dist >::nearestKSearch(), pcl::KdTreeFLANN< PointT, Dist >::radiusSearch(), and pcl::KdTreeFLANN< PointT, Dist >::setInputCloud().

◆ sorted_

template<typename PointT>

bool pcl::KdTree< PointT >::sorted_

protected

Return the radius search neighbours sorted.

Definition at line 348 of file kdtree.h.

Referenced by pcl::KdTreeFLANN< PointT, Dist >::setEpsilon(), and pcl::KdTreeFLANN< PointT, Dist >::setSortedResults().

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

pcl/kdtree/kdtree.h

Public Types

Public Member Functions

Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ ConstPtr

◆ IndicesConstPtr

◆ IndicesPtr

◆ PointCloud

◆ PointCloudConstPtr

◆ PointCloudPtr

◆ PointRepresentation

◆ PointRepresentationConstPtr

◆ Ptr

Constructor & Destructor Documentation

◆ KdTree()

◆ ~KdTree()

Member Function Documentation

◆ getEpsilon()

◆ getIndices()

◆ getInputCloud()

◆ getMinPts()

◆ getName()

◆ getPointRepresentation()

◆ nearestKSearch() [1/3]

◆ nearestKSearch() [2/3]

◆ nearestKSearch() [3/3]

◆ nearestKSearchT()

◆ radiusSearch() [1/3]

◆ radiusSearch() [2/3]

◆ radiusSearch() [3/3]

◆ radiusSearchT()

◆ setEpsilon()

◆ setInputCloud()

◆ setMinPts()

◆ setPointRepresentation()

Member Data Documentation

◆ epsilon_

◆ indices_

◆ input_

◆ min_pts_

◆ point_representation_

◆ sorted_