class for kd-tree data structure. More...

Public Member Functions
	KdTree (int stack_size=10)

void	clear (void)

int	exist (const T *)

int	exist (const T *, T1 &)

template<class T2 >
int	hNeighbor (const T *, T1 &, T2, int n=0, int l=0)

template<class T2 >
int	hNeighbor (const T *, T2, bool, int n=0, int l=0)

template<class T2 >
void	hNeighbors (const T , T2, std::vector< T1 > , std::vector< T1 > *, int n=0, int l=0)

void	insert (T *)

void	insert (T *, T1 &)

Public Attributes
int	MAXSTK

int	n_nodes

std::vector< KdNode< T, T1 > >	nodes

Detailed Description

template<int d, class T, class T1 = int>
class bitpit::KdTree< d, T, T1 >

class for kd-tree data structure.

Sort vertices in a d-dimensional Euclidean space into a kd-tree structure.

Template parameters are:

d, number dimensions (i.e. number of coordinates for vertices)
T, container used to store vertex coordinates
T1, label type associated to each node in the kd-tree.

Template parameters can be any type fulfilling the following requirements:

operator* (dereferencing operator) must be defined for class T
T1 must be a copy-constructible type.
operator== must be defined for container T, which returns true if two objects of type T have the same content (i.e. two vertices have the same coordinates)

Definition at line 83 of file SortAlgorithms.hpp.

Constructor & Destructor Documentation

◆ KdTree()

template<int d, class T , class T1 >

bitpit::KdTree< d, T, T1 >::KdTree ( int maxstack = 10 )

Default constructor for class KdTree.

Initialize an empty kd-tree structure and reserve memory for the insertion of maxstack nodes.

Parameters

[in] maxstack memory reserve (in terms of number of elements)

Definition at line 162 of file KdTree.tpp.

Member Function Documentation

◆ clear()

template<int d, class T , class T1 >

void bitpit::KdTree< d, T, T1 >::clear ( void )

Clear current content without freeing memory.

Definition at line 196 of file KdTree.tpp.

◆ exist() [1/2]

template<int d, class T , class T1 >

int bitpit::KdTree< d, T, T1 >::exist ( const T * P_ )

Check whether a given vertex already exist in the kd-tree. Check is performed via lexicographical comparison of vertex coordinates.

Parameters

[in] P_ pointer to container storing the coordinates of the vertex to be checked.

Returns: on output returns the index of the kd-node in the tree having the same coordinates of the input vertex. If no node is found in the kd-tree, returns -1.

Definition at line 235 of file KdTree.tpp.

◆ exist() [2/2]

template<int d, class T , class T1 >

int bitpit::KdTree< d, T, T1 >::exist	(	const T *	P_,
		T1 &	label )

Check whether a given vertex already exist in the kd-tree. Check is performed via lexicographical comparison of vertex coordinates.

Parameters

[in]	P_	pointer to container storing the coordinates of the vertex to be checked.
[in,out]	label	on output stores the label associated with the KdNode (if any) whose coordinates match those of the input vector

Returns: on output returns the index of the kd-node in the tree having the same coordinates of the input vertex. If no node is found in the kd-tree, returns -1.

Definition at line 295 of file KdTree.tpp.

◆ hNeighbor() [1/2]

template<int d, class T , class T1 >

template<class T2 >

int bitpit::KdTree< d, T, T1 >::hNeighbor	(	const T *	P_,
		T1 &	label,
		T2	h,
		int	next_ = 0,
		int	lev = 0 )

Given an input vertex P, returns the index of the first node encountered in the kd-tree which is in the 1-ball centered on P and having a radius of h. The 1-ball is defined as: B1(x; h) = {y: norm_1(y-x) <= h}

Parameters

[in]	P_	pointer to container storing the coordinates of P
[in,out]	label	on output stores the label of the KdNode in the 1-ball centered on P (if any).
[in]	h	1-ball radius
[in]	next_	(default = 0) index of element in the kd tree used as starting point by the kd-tree search algorithm
[in]	lev	(default = 0) level in kd-tree of node used as starting point by the kd-tree search algorithm.

Returns: on output returns the index of the first kd-node encountered in the tree which lies in the 1-ball centered on P. If no node is found, returns -1.

Definition at line 432 of file KdTree.tpp.

◆ hNeighbor() [2/2]

template<int d, class T , class T1 >

template<class T2 >

int bitpit::KdTree< d, T, T1 >::hNeighbor	(	const T *	P_,
		T2	h,
		bool	debug,
		int	next_ = 0,
		int	lev = 0 )

Given an input vertex P, returns the index of the first node encountered in the kd-tree which is in the 1-ball centered on P and having a radius of h. The 1-ball is defined as: B1(x; h) = {y: norm_1(y-x) <= h}

Parameters

[in]	P_	pointer to container storing the coordinates of P
[in]	h	1-ball radius
[in]	debug	(default = false) flag for running the search in debug mode
[in]	next_	(default = 0) index of element in the kd tree used as starting point by the kd-tree search algorithm
[in]	lev	(default = 0) level in kd-tree of node used as starting point by the kd-tree search algorithm.

Returns: on output returns the index of the first kd-node encountered in the tree which lies in the 1-ball centered on P. If no node is found, returns -1.

Definition at line 361 of file KdTree.tpp.

◆ hNeighbors()

template<int d, class T , class T1 >

template<class T2 >

void bitpit::KdTree< d, T, T1 >::hNeighbors	(	const T *	P_,
		T2	h,
		std::vector< T1 > *	L_,
		std::vector< T1 > *	EX_,
		int	next_ = 0,
		int	lev = 0 )

Given an input vertex P, returns the labels of all the nodes encountered in the kd-tree which are in the 1-ball centered on P and having a radius of h. The 1-ball is defined as: B1(x; h) = {y: norm_1(y-x) <= h}

Parameters

[in]	P_	pointer to container storing the coordinates of P
[in]	h	1-ball radius
[out]	L_	pointer to container filled with labels of the kd-nodes encountered in the tree which lies in the 1-ball centered on P.
[in]	EX_	pointers to vector with labels to be excluded from the results
[in]	next_	(default = 0) index of element in the kd tree used as starting point by the kd-tree search algorithm
[in]	lev	(default = 0) level in kd-tree of node used as starting point by the kd-tree search algorithm.

Definition at line 733 of file KdTree.tpp.

◆ insert() [1/2]

template<int d, class T , class T1 >

void bitpit::KdTree< d, T, T1 >::insert ( T * P_ )

Insert a new vertex in the kd-tree.

Parameters

[in] P_ pointer to container storing vertex coordinates.

Definition at line 488 of file KdTree.tpp.

◆ insert() [2/2]

template<int d, class T , class T1 >

void bitpit::KdTree< d, T, T1 >::insert	(	T *	P_,
		T1 &	label )

Insert a new vertex and the associated label into kd-tree.

Parameters

[in]	P_	pointer to container storing vertex coordinates.
[in]	label	label associated to P_

Definition at line 562 of file KdTree.tpp.

Member Data Documentation

◆ MAXSTK

template<int d, class T , class T1 = int>

int bitpit::KdTree< d, T, T1 >::MAXSTK

max stack size

Definition at line 87 of file SortAlgorithms.hpp.

◆ n_nodes

template<int d, class T , class T1 = int>

int bitpit::KdTree< d, T, T1 >::n_nodes

number of nodes

Definition at line 88 of file SortAlgorithms.hpp.

◆ nodes

template<int d, class T , class T1 = int>

std::vector< KdNode<T, T1> > bitpit::KdTree< d, T, T1 >::nodes

kd-tree nodes

Definition at line 89 of file SortAlgorithms.hpp.

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

src/SA/SortAlgorithms.hpp
src/SA/KdTree.tpp

Public Member Functions

Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ KdTree()

Member Function Documentation

◆ clear()

◆ exist() [1/2]

◆ exist() [2/2]

◆ hNeighbor() [1/2]

◆ hNeighbor() [2/2]

◆ hNeighbors()

◆ insert() [1/2]

◆ insert() [2/2]

Member Data Documentation

◆ MAXSTK

◆ n_nodes

◆ nodes