TrigVSI::KDTree< T, D > Class Template Reference

KDTree. More...

#include <KDPoint.h>

Collaboration diagram for TrigVSI::KDTree< T, D >:

Classes
struct	Node
	Node class for KDTree. More...

Public Member Functions
	KDTree (std::vector< KDPoint< T, D >> &v_data)
	KDTree ()
void	genTree ()
	Command to generate tree. More...
void	lock ()
void	unlock ()
KDPoint< T, D >	at (size_t n)

Private Member Functions
std::unique_ptr< Node >	buildTree (int, int, int)
	recursive function to create tree structure. More...
void	nearestNeighborRec (const KDPoint< T, D > &, const Node *, double &, int &, std::function< double(const KDPoint< T, D > &, const KDPoint< T, D > &)> &)
	recursive function for nearest neighbor searching. More...

Private Attributes
std::unique_ptr< Node >	m_rootNode
	The root node of the tree. More...
std::vector< KDPoint< T, D > >	m_datas
	Container of the points. More...
std::vector< size_t >	m_indices
	A list of indices of points in m_datas. More...
size_t	m_idLength
bool	m_locked

Detailed Description

template<typename T, size_t D>
class TrigVSI::KDTree< T, D >

KDTree.

Can be used for fast point searching, which is needed in clustering.

Definition at line 159 of file KDPoint.h.

Constructor & Destructor Documentation

KDTree() [1/2]

template<typename T , size_t D>

TrigVSI::KDTree< T, D >::KDTree ( std::vector< KDPoint< T, D >> &  v_data )

inline

Definition at line 174 of file KDPoint.h.

                                              : m_datas( v_data ), m_idLength( m_datas.size() ), m_locked( false )
      {
         m_indices.clear();
         for (size_t i = 0; i < m_idLength; i++) { m_indices.emplace_back(i); }
      };

KDTree() [2/2]

template<typename T , size_t D>

TrigVSI::KDTree< T, D >::KDTree ( )

inline

Definition at line 180 of file KDPoint.h.

: m_idLength(0), m_locked(false){};

Member Function Documentation

at()

template<typename T , size_t D>

KDPoint<T,D> TrigVSI::KDTree< T, D >::at ( size_t  n )

inline

Definition at line 186 of file KDPoint.h.

{ return m_datas.at(n); };

buildTree()

template<typename T , size_t D>

std::unique_ptr< typename KDTree< T, D >::Node > TrigVSI::KDTree< T, D >::buildTree ( int  l, int  r, int  depth  )

private

recursive function to create tree structure.

Returns

unique ptr to current node

Parameters

[in]	l	Index of the left edge of current region.
[in]	r	Index of the right edge of current region.
[in]	depth	Depth of current node. Axe to be separated is selected according to this param.

Definition at line 220 of file KDPoint.h.

{
   if ( l >= r ) return std::make_unique<Node>(nullptr);
 
   const int axis_  = depth % D;
   const int mid   = ( l + r ) >> 1;
 
   std::nth_element( m_indices.begin()+l, m_indices.begin()+l+mid, m_indices.begin()+r,
                     [this, axis_](size_t lcnt, size_t rcnt) {
                        return m_datas[lcnt].getId(axis_) < m_datas[rcnt].getId(axis_);
                     } );
 
   std::unique_ptr<Node> node_ptr = std::make_unique<Node> ( m_datas.at(m_indices[mid]), m_indices[mid] );
   node_ptr->axis  = axis_;
 
   node_ptr->leftPtr  = buildTree( l,     mid,  depth+1 );
   node_ptr->rightPtr = buildTree( mid+1, r,    depth+1 );
 
   return node_ptr;
}

genTree()

template<typename T , size_t D>

void TrigVSI::KDTree< T, D >::genTree

Command to generate tree.

Needed to be locked before execute this command.

Definition at line 205 of file KDPoint.h.

{
   if (m_locked) return;
   m_rootNode = buildTree(0, m_idLength, 0);
}

lock()

template<typename T , size_t D>

void TrigVSI::KDTree< T, D >::lock ( )

inline

Definition at line 183 of file KDPoint.h.

{ m_locked = true;  };

nearestNeighborRec()

template<typename T , size_t D>

void TrigVSI::KDTree< T, D >::nearestNeighborRec ( const KDPoint< T, D > &  , const Node *  , double &  , int &  , std::function< double(const KDPoint< T, D > &, const KDPoint< T, D > &)> &    )

private

recursive function for nearest neighbor searching.

Parameters

[in]	query	query point for searching.
[in]	node	current node to check.
[out]	r	minimum distance to query point.
[out]	idx	index of candidate point.
[in]	dist_func	function to calculate the distance between current point and the query point.

Definition at line 251 of file KDPoint.h.

{
   // end processing when reach leaf
   if ( node == nullptr ) {
      return;
   }
 
   const KDPoint<T,D>& point = node->dataRef;
 
   // update minimum distance and candidate point
   const double dist = dist_func(query, point);
   if (dist < r) {
      idx = node->dataIdx;
      r = dist;
   }
 
   const int axis_ = node->axis;
   const Node* next_node = (query.at(axis_) < point.at(axis_))? node->leftPtr.get() : node->rightPtr.get();
 
   // recursively call self until reach leaf node
   nearestNeighborRec( query, next_node, r, idx, dist_func );
 
   // Check if hyper-sphere with radius r overlaps neighbor hyper-plane.
   KDPoint<T,D> proj = query;
   proj[axis_] = point.at(axis_); // proj is the projected point of query on hyperplane x[axis_]=point[axis_]
   double diff = dist_func(proj, query);
   if ( diff < r ) {
      // if hyper-sphere overlaps, check the other region separated by the hyper-plane.
      const Node* next_node_opps = (query.at(axis_) < point.at(axis_))? node->rightPtr.get() : node->leftPtr.get();
      nearestNeighborRec( query, next_node_opps, r, idx, dist_func );
   }
   return;
}

unlock()

template<typename T , size_t D>

void TrigVSI::KDTree< T, D >::unlock ( )

inline

Definition at line 184 of file KDPoint.h.

{ m_locked = false; };

Member Data Documentation

m_datas

template<typename T , size_t D>

std::vector<KDPoint<T,D> > TrigVSI::KDTree< T, D >::m_datas

private

Container of the points.

Definition at line 190 of file KDPoint.h.

m_idLength

template<typename T , size_t D>

size_t TrigVSI::KDTree< T, D >::m_idLength

private

Definition at line 192 of file KDPoint.h.

m_indices

template<typename T , size_t D>

std::vector<size_t> TrigVSI::KDTree< T, D >::m_indices

private

A list of indices of points in m_datas.

Definition at line 191 of file KDPoint.h.

m_locked

template<typename T , size_t D>

bool TrigVSI::KDTree< T, D >::m_locked

private

Definition at line 193 of file KDPoint.h.

m_rootNode

template<typename T , size_t D>

std::unique_ptr<Node> TrigVSI::KDTree< T, D >::m_rootNode

private

The root node of the tree.

Definition at line 189 of file KDPoint.h.

---

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

• KDPoint.h