CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement > Class Template Reference

Simple tree structure with alternating half splitting nodes. More...

#include <KDTree.h>

Classes
struct	Node
	Stores kd-tree node data. More...

Public Types
typedef TCoordType	coord_type
typedef CDT::V2d< coord_type >	point_type
typedef CDT::VertInd	point_index
typedef std::pair< point_type, point_index >	value_type
typedef std::vector< point_index >	point_data_vec
typedef point_data_vec::const_iterator	pd_cit
typedef CDT::VertInd	node_index
typedef CDT::array< node_index, 2 >	children_type

Public Member Functions
	KDTree ()
	Default constructor.
	KDTree (const point_type &min, const point_type &max)
	Constructor with bounding box known in advance.
CDT::VertInd	size () const
void	insert (const point_index &iPoint, const std::vector< point_type > &points)
	Insert a point into kd-tree.
value_type	nearest (const point_type &point, const std::vector< point_type > &points) const
	Query kd-tree for a nearest neighbor point.

Detailed Description

template<typename TCoordType, size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>
class CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >

Simple tree structure with alternating half splitting nodes.

Simple tree structure

• Tree to incrementally add points to the structure.
• Get the nearest point to a given input.
• Does not check for duplicates, expect unique points.

  Template Parameters

  TCoordType	type used for storing point coordinate.
  NumVerticesInLeaf	The number of points per leaf.
  InitialStackDepth	initial size of stack depth for nearest query. Should be at least 1.
  StackDepthIncrement	increment of stack depth for nearest query when stack depth is reached.

Definition at line 45 of file KDTree.h.

Member Typedef Documentation

children_type

template<typename TCoordType , size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>

typedef CDT::array<node_index, 2> CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >::children_type

Definition at line 55 of file KDTree.h.

coord_type

template<typename TCoordType , size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>

typedef TCoordType CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >::coord_type

Definition at line 48 of file KDTree.h.

node_index

template<typename TCoordType , size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>

typedef CDT::VertInd CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >::node_index

Definition at line 54 of file KDTree.h.

pd_cit

template<typename TCoordType , size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>

typedef point_data_vec::const_iterator CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >::pd_cit

Definition at line 53 of file KDTree.h.

point_data_vec

template<typename TCoordType , size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>

typedef std::vector<point_index> CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >::point_data_vec

Definition at line 52 of file KDTree.h.

point_index

template<typename TCoordType , size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>

typedef CDT::VertInd CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >::point_index

Definition at line 50 of file KDTree.h.

point_type

template<typename TCoordType , size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>

typedef CDT::V2d<coord_type> CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >::point_type

Definition at line 49 of file KDTree.h.

value_type

template<typename TCoordType , size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>

typedef std::pair<point_type, point_index> CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >::value_type

Definition at line 51 of file KDTree.h.

Constructor & Destructor Documentation

KDTree() [1/2]

template<typename TCoordType , size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>

CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >::KDTree ( )

inline

Default constructor.

Definition at line 82 of file KDTree.h.

KDTree() [2/2]

template<typename TCoordType , size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>

CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >::KDTree ( const point_type & min, const point_type & max )

inline

Constructor with bounding box known in advance.

Definition at line 98 of file KDTree.h.

Member Function Documentation

insert()

template<typename TCoordType , size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>

void CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >::insert ( const point_index & iPoint, const std::vector< point_type > & points )

inline

Insert a point into kd-tree.

Note

external point-buffer is used to reduce kd-tree's memory footprint

Parameters

iPoint	index of point in external point-buffer
points	external point-buffer

Definition at line 119 of file KDTree.h.

nearest()

template<typename TCoordType , size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>

value_type CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >::nearest ( const point_type & point, const std::vector< point_type > & points ) const

inline

Query kd-tree for a nearest neighbor point.

Note

external point-buffer is used to reduce kd-tree's memory footprint

Parameters

point	query point position
points	external point-buffer

Definition at line 188 of file KDTree.h.

size()

template<typename TCoordType , size_t NumVerticesInLeaf, size_t InitialStackDepth, size_t StackDepthIncrement>

CDT::VertInd CDT::KDTree::KDTree< TCoordType, NumVerticesInLeaf, InitialStackDepth, StackDepthIncrement >::size ( ) const

inline

Definition at line 109 of file KDTree.h.

---

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

• include/KDTree.h