PointKDTree< _NodeType > Class Template Reference

Generic multi-dimensional kd-tree data structure for point data. More...

#include <kdtree.h>

Collaboration diagram for PointKDTree< _NodeType >:

Classes
struct	SearchResult
	Result data type for k-nn queries. More...

Public Types
enum	{ Dimension = VectorType::RowsAtCompileTime }
enum	Heuristic { Balanced = 0 , SlidingMidpoint }
	Supported tree construction heuristics. More...
typedef _NodeType	NodeType
typedef NodeType::PointType	PointType
typedef NodeType::IndexType	IndexType
typedef PointType::Scalar	Scalar
typedef PointType::VectorType	VectorType
typedef TBoundingBox< PointType >	BoundingBoxType

Public Member Functions
	PointKDTree (size_t nodes=0, Heuristic heuristic=SlidingMidpoint)
	Create an empty KD-tree that can hold the specified number of points.
void	setBoundingBox (const BoundingBoxType &bbox)
	Set the BoundingBox of the underlying point data.
const BoundingBoxType &	getBoundingBox () const
	Return the BoundingBox of the underlying point data.
size_t	getDepth () const
	Return the depth of the constructed KD-tree.
void	setDepth (size_t depth)
	Set the depth of the constructed KD-tree (be careful with this)
void	build (bool recomputeBoundingBox=false)
	Construct the KD-tree hierarchy. More...
void	search (const PointType &p, float searchRadius, std::vector< IndexType > &results) const
	Run a search query. More...
size_t	nnSearch (const PointType &p, float &_sqrSearchRadius, size_t k, SearchResult *results) const
	Run a k-nearest-neighbor search query. More...
size_t	nnSearch (const PointType &p, size_t k, SearchResult *results) const
	Run a k-nearest-neighbor search query without any search radius threshold. More...
\c stl::vector-like interface
void	clear ()
	Clear the kd-tree array.
void	resize (size_t size)
	Resize the kd-tree array.
void	reserve (size_t size)
	Reserve a certain amount of memory for the kd-tree array.
size_t	size () const
	Return the size of the kd-tree.
size_t	capacity () const
	Return the capacity of the kd-tree.
void	push_back (const NodeType &node)
	Append a kd-tree node to the node array.
NodeType &	operator[] (size_t idx)
	Return one of the KD-tree nodes by index.
const NodeType &	operator[] (size_t idx) const
	Return one of the KD-tree nodes by index (const version)

Protected Member Functions
bool	hasRightChild (IndexType index) const
	Return whether or not the inner node of the specified index has a right child node.
void	build (size_t depth, typename std::vector< IndexType >::iterator base, typename std::vector< IndexType >::iterator rangeStart, typename std::vector< IndexType >::iterator rangeEnd)
	Tree construction routine.

Protected Attributes
std::vector< NodeType >	m_nodes
BoundingBoxType	m_bbox
Heuristic	m_heuristic
size_t	m_depth

Detailed Description

template<typename _NodeType>
class PointKDTree< _NodeType >

Generic multi-dimensional kd-tree data structure for point data.

This class organizes point data in a hierarchical manner so various types of queries can be performed efficiently. It supports several heuristics for building `‘good’' trees, and it is oblivious to the data layout of the nodes themselves.

Template Parameters

_NodeType

Underlying node data structure. See GenericKDTreeNode as an example for the required public interface

See also

GenericKDTreeNode

Definition at line 124 of file kdtree.h.

Member Enumeration Documentation

Heuristic

template<typename _NodeType >

enum PointKDTree::Heuristic

Supported tree construction heuristics.

Enumerator
Balanced	Create a balanced tree by splitting along the median.
SlidingMidpoint	Use the sliding midpoint tree construction rule. This ensures that cells do not become overly elongated.

Definition at line 138 of file kdtree.h.

Member Function Documentation

build()

template<typename _NodeType >

void PointKDTree< _NodeType >::build ( bool  recomputeBoundingBox = false )

inline

Construct the KD-tree hierarchy.

When only adding nodes using the push_back() function, the bounding box is already computed, hence true can be passed to this function to avoid an unnecessary recomputation.

Definition at line 221 of file kdtree.h.

nnSearch() [1/2]

template<typename _NodeType >

size_t PointKDTree< _NodeType >::nnSearch ( const PointType &  p, float &  _sqrSearchRadius, size_t  k, SearchResult *  results  ) const

inline

Run a k-nearest-neighbor search query.

Parameters

p	Search position
sqrSearchRadius	Specifies the squared maximum search radius. This parameter can be used to restrict the k-nn query to a subset of the data – it that is not desired, simply set it to positive infinity. After the query finishes, the parameter value will correspond to the (generally lower) maximum query radius that was necessary to ensure that the number of results did not exceed k.
k	Maximum number of search results
results	Target array for search results. Must contain storage for at least k+1 entries! (one extra entry is needed for shuffling data around)

Returns

The number of search results (equal to k or less)

Definition at line 334 of file kdtree.h.

nnSearch() [2/2]

template<typename _NodeType >

size_t PointKDTree< _NodeType >::nnSearch ( const PointType &  p, size_t  k, SearchResult *  results  ) const

inline

Run a k-nearest-neighbor search query without any search radius threshold.

Parameters

p	Search position
k	Maximum number of search results
results	Target array for search results. Must contain storage for at least k+1 entries! (one extra entry is needed for shuffling data around)

Returns

The number of used traversal steps

Definition at line 430 of file kdtree.h.

search()

template<typename _NodeType >

void PointKDTree< _NodeType >::search ( const PointType &  p, float  searchRadius, std::vector< IndexType > &  results  ) const

inline

Run a search query.

Parameters

p	Search position
results	Index list of search results
searchRadius	Search radius

Definition at line 260 of file kdtree.h.

---

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

• kdtree.h