k-D Node class for the k-D Tree data structure More...

#include <KDNode.h>

Inheritance diagram for DirectGraphicalModels::CKDNode:

Collaboration diagram for DirectGraphicalModels::CKDNode:

Public Member Functions
	CKDNode (Mat &key, byte value)
	Leaf node constructor. More...

	CKDNode (pair_mat_t &boundingBox, byte splitVal, int splitDim, std::shared_ptr< CKDNode > left, std::shared_ptr< CKDNode > right)
	Branch node constructor. More...

	CKDNode (const CKDNode &)=delete

	~CKDNode (void)

bool	operator= (const CKDNode)=delete

void	save (FILE *pFile) const
	Saves the state of the node to the file. More...

bool	isLeaf (void) const
	Checks whether the node is either leaf or brach node. More...

void	findNearestNeighbors (const Mat &key, size_t maxNeighbors, pair_mat_t &searchBox, float &searchRadius, std::vector< std::shared_ptr< const CKDNode >> &nearestNeighbors) const
	Auxiliary recursive method for finding the k-nearest (in terms of the Euclidian distance between the keys) nearestNeighbors nodes. More...

Mat	getKey (void) const
	Returns the key of the leaf-node (k-d point) More...

byte	getValue (void) const
	Returns the value of the leaf-node. More...

pair_mat_t	getBoundingBox (void) const
	Returns the spatial bounding box, containing all the keys for the current branch. More...

byte	getSplitVal (void) const
	Returns the split value of the brach-node. More...

int	getSplitDim (void) const
	Returns the split dimension of the branch-node. More...

std::shared_ptr< CKDNode >	Left (void) const
	Returns the pointer to the left child. More...

std::shared_ptr< CKDNode >	Right (void) const
	Returns the pointer to the right child. More...

Private Member Functions
	CKDNode (Mat &key, byte value, pair_mat_t &boundingBox, byte splitVal, int splitDim, std::shared_ptr< CKDNode > left, std::shared_ptr< CKDNode > right)

Private Attributes
Mat	m_key

byte	m_value

pair_mat_t	m_boundingBox

byte	m_splitVal

int	m_splitDim

std::shared_ptr< CKDNode >	m_pLeft

std::shared_ptr< CKDNode >	m_pRight

Detailed Description

k-D Node class for the k-D Tree data structure

This class is used for an implementation of a non-uniform k-D Tree data structure. The are 3 types of the nodes: root, leaf and branch nodes. Branch nodes have upto two child nodes, and leaf nodes have no children. If the root node is the only one node in the tree it is also the leaf node.

Author: Sergey G. Kosov, serge.nosp@m.y.ko.nosp@m.sov@p.nosp@m.roje.nosp@m.ct-10.nosp@m..de

Definition at line 17 of file KDNode.h.

Constructor & Destructor Documentation

◆ CKDNode() [1/4]

DirectGraphicalModels::CKDNode::CKDNode	(	Mat &	key,
		byte	value
	)

inline

Leaf node constructor.

Parameters

key	The node key (k-d point): Mat(size: 1 x k; type: CV_8UC1))
value	The node value

Definition at line 25 of file KDNode.h.

◆ CKDNode() [2/4]

DirectGraphicalModels::CKDNode::CKDNode	(	pair_mat_t &	boundingBox,
		byte	splitVal,
		int	splitDim,
		std::shared_ptr< CKDNode >	left,
		std::shared_ptr< CKDNode >	right
	)

inline

Branch node constructor.

All the points with key[splitDim] < splitVal must be assigned to the left sub-tree, and the points key[splitDim] >= splitVal - to the right.

Parameters

boundingBox	The spatial bounding box, containing all the keys for the current branch: pair<Mat, Mat>(minCoordinates, maxCoordinates).
splitVal	The threshold in which the split of the k-d space is performed.
splitDim	The dimension ( [0; k) ) in which the split of the k-d space is performed.
left	The pointer to the root of the left sub-tree.
right	The pointer to the root of the right sub-tree.

Definition at line 37 of file KDNode.h.

◆ CKDNode() [3/4]

DirectGraphicalModels::CKDNode::CKDNode ( const CKDNode & )

delete

◆ ~CKDNode()

DirectGraphicalModels::CKDNode::~CKDNode ( void )

inline

Definition at line 42 of file KDNode.h.

◆ CKDNode() [4/4]

DirectGraphicalModels::CKDNode::CKDNode	(	Mat &	key,
		byte	value,
		pair_mat_t &	boundingBox,
		byte	splitVal,
		int	splitDim,
		std::shared_ptr< CKDNode >	left,
		std::shared_ptr< CKDNode >	right
	)

private

Definition at line 7 of file KDNode.cpp.

Member Function Documentation

◆ findNearestNeighbors()

void DirectGraphicalModels::CKDNode::findNearestNeighbors	(	const Mat &	key,
		size_t	maxNeighbors,
		pair_mat_t &	searchBox,
		float &	searchRadius,
		std::vector< std::shared_ptr< const CKDNode >> &	nearestNeighbors
	)		const

Auxiliary recursive method for finding the k-nearest (in terms of the Euclidian distance between the keys) nearestNeighbors nodes.

Parameters

[in]	key	The search key (k-d point): Mat(size: 1 x k; type: CV_8UC1))
[in]	maxNeighbors	The number of desired neares neighbors
[in,out]	searchBox	The bounding box, that is used to find the overlapping branch nodes
[in,out]	searchRadius	The radius of a k-d sphere, within which the nodes are searched
[out]	nearestNeighbors	The resulting nearest nodes. The amount of nodes is <= maxNeighbors.

Definition at line 36 of file KDNode.cpp.

Here is the call graph for this function:

◆ getBoundingBox()

pair_mat_t DirectGraphicalModels::CKDNode::getBoundingBox ( void ) const

inline

Returns the spatial bounding box, containing all the keys for the current branch.

Returns: The bounding box (pair<Mat, Mat>(minCoordinates, maxCoordinates))

Definition at line 80 of file KDNode.h.

Here is the call graph for this function:

◆ getKey()

Mat DirectGraphicalModels::CKDNode::getKey ( void ) const

inline

Returns the key of the leaf-node (k-d point)

Returns: The key of the node: Mat(size: 1 x k; type: CV_8UC1)

Definition at line 70 of file KDNode.h.

◆ getSplitDim()

int DirectGraphicalModels::CKDNode::getSplitDim ( void ) const

inline

Returns the split dimension of the branch-node.

The split dimension is the dimension in which the split of the k-d space is performed.

Returns: The split dimension: (a value from the interval [0; k))

Definition at line 92 of file KDNode.h.

◆ getSplitVal()

byte DirectGraphicalModels::CKDNode::getSplitVal ( void ) const

inline

Returns the split value of the brach-node.

The split value is a threshold in which the split of the k-d space is performed.

Returns: The split value

Definition at line 86 of file KDNode.h.

◆ getValue()

byte DirectGraphicalModels::CKDNode::getValue ( void ) const

inline

Returns the value of the leaf-node.

Return values

The	value of the node

Definition at line 75 of file KDNode.h.

◆ isLeaf()

bool DirectGraphicalModels::CKDNode::isLeaf ( void ) const

inline

Checks whether the node is either leaf or brach node.

Return values

true	if the node is a leaf-node
false	if the node is a branch-node

Definition at line 56 of file KDNode.h.

Here is the caller graph for this function:

◆ Left()

std::shared_ptr<CKDNode> DirectGraphicalModels::CKDNode::Left ( void ) const

inline

Returns the pointer to the left child.

Returns: The pointer to the root-node of the left sub-tree

Definition at line 97 of file KDNode.h.

Here is the caller graph for this function:

◆ operator=()

bool DirectGraphicalModels::CKDNode::operator= ( const CKDNode )

delete

◆ Right()

std::shared_ptr<CKDNode> DirectGraphicalModels::CKDNode::Right ( void ) const

inline

Returns the pointer to the right child.

Returns: The pointer to the root-node of the right sub-tree

Definition at line 102 of file KDNode.h.

◆ save()

void DirectGraphicalModels::CKDNode::save ( FILE * pFile ) const

Saves the state of the node to the file.

Parameters

pFile The pointer to the file, opened for writing

Definition at line 18 of file KDNode.cpp.

Here is the call graph for this function:

Member Data Documentation

◆ m_boundingBox

pair_mat_t DirectGraphicalModels::CKDNode::m_boundingBox

private

Definition at line 112 of file KDNode.h.

◆ m_key

Mat DirectGraphicalModels::CKDNode::m_key

private

Definition at line 110 of file KDNode.h.

◆ m_pLeft

std::shared_ptr<CKDNode> DirectGraphicalModels::CKDNode::m_pLeft

private

Definition at line 115 of file KDNode.h.

◆ m_pRight

std::shared_ptr<CKDNode> DirectGraphicalModels::CKDNode::m_pRight

private

Definition at line 116 of file KDNode.h.

◆ m_splitDim

int DirectGraphicalModels::CKDNode::m_splitDim

private

Definition at line 114 of file KDNode.h.

◆ m_splitVal

byte DirectGraphicalModels::CKDNode::m_splitVal

private

Definition at line 113 of file KDNode.h.

◆ m_value

byte DirectGraphicalModels::CKDNode::m_value

private

Definition at line 111 of file KDNode.h.

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

D:/Projects/DGM/modules/DGM/KDNode.h
D:/Projects/DGM/modules/DGM/KDNode.cpp

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

Constructor & Destructor Documentation

◆ CKDNode() [1/4]

◆ CKDNode() [2/4]

◆ CKDNode() [3/4]

◆ ~CKDNode()

◆ CKDNode() [4/4]

Member Function Documentation

◆ findNearestNeighbors()

◆ getBoundingBox()

◆ getKey()

◆ getSplitDim()

◆ getSplitVal()

◆ getValue()

◆ isLeaf()

◆ Left()

◆ operator=()

◆ Right()

◆ save()

Member Data Documentation

◆ m_boundingBox

◆ m_key

◆ m_pLeft

◆ m_pRight

◆ m_splitDim

◆ m_splitVal

◆ m_value