This class implements a k-d tree. More...

Data Structures
class	Node
	This class defines a node of the k-d tree. More...

Public Member Functions
	KdTree (const unsigned int dimension)
	Creates a new k-d tree. More...

	~KdTree ()=default
	Destructs a k-d tree. More...

bool	insert (const T **values, const size_t number)
	Inserts a set of values to this empty tree. More...

const T *	nearestNeighbor (const T *value, typename SquareValueTyper< T >::Type &distance) const
	Applies a nearest neighbor search for a given value. More...

size_t	radiusSearch (const T value, const typename SquareValueTyper< T >::Type radius, const T *values, const size_t maxValues) const
	Applies a radius search for neighbors of a given value. More...

unsigned int	dimension () const
	Returns the dimension of the tree's values. More...

size_t	size () const
	Returns the number of tree nodes. More...

Protected Types
typedef std::vector< T >	Elements
	Definition of a vector holding single elements. More...

typedef std::vector< const T * >	Pointers
	Definition of a vector holding single pointers. More...

Protected Member Functions
void	insertLeft (Node &parent, const T **values, const size_t number, const unsigned int depth)
	Inserts a set of values to a given parent as left children. More...

void	insertRight (Node &parent, const T **values, const size_t number, const unsigned int depth)
	Inserts a set of values to a given parent as right children. More...

void	nearestNeighbor (Node &node, const T value, const T &nearest, typename SquareValueTyper< T >::Type &distance, const unsigned int index) const
	Applies a nearest neighbor search for a given node and value. More...

size_t	radiusSearch (Node &node, const T value, const typename SquareValueTyper< T >::Type radius, const T *values, const size_t maxValues, const unsigned int index) const
	Applies a radius search for neighbors of a given value. More...

SquareValueTyper< T >::Type	determineSquareDistance (const T first, const T second) const
	Determines the square distance between two values. More...

Static Protected Member Functions
static T	median (const T **values, const size_t number, const unsigned int index)
	Returns the median for a given set of values. More...

static void	distribute (const T *values, const size_t number, const unsigned int index, const T &medianValue, Pointers &leftValues, Pointers &rightValues)
	Distributes a given set of values into two subset according to the median. More...

Protected Attributes
std::unique_ptr< Node >	root_
	Root node of this tree. More...

size_t	size_ = 0
	Number of nodes. More...

const unsigned int	dimension_ = 0u
	Number of dimensions. More...

Detailed Description

template<typename T>
class Ocean::KdTree< T >

This class implements a k-d tree.

In general, k-d trees should be applied for problems with small dimensions only as the performance benefit decreases with increasing dimension significantly.
That means for the number of nodes (n) and the dimension (k) the following should hold: n >> 2^k.

Template Parameters

T	The data type of one element for all dimensions.

Member Typedef Documentation

◆ Elements

template<typename T >

typedef std::vector<T> Ocean::KdTree< T >::Elements

protected

Definition of a vector holding single elements.

◆ Pointers

template<typename T >

typedef std::vector<const T*> Ocean::KdTree< T >::Pointers

protected

Definition of a vector holding single pointers.

Constructor & Destructor Documentation

◆ KdTree()

template<typename T >

Ocean::KdTree< T >::KdTree ( const unsigned int dimension )

inlineexplicit

Creates a new k-d tree.

Parameters

dimension Number of dimensions the tree will have, with range [1, infinity)

◆ ~KdTree()

template<typename T >

Ocean::KdTree< T >::~KdTree ( )

default

Destructs a k-d tree.

Member Function Documentation

◆ determineSquareDistance()

template<typename T >

SquareValueTyper< T >::Type Ocean::KdTree< T >::determineSquareDistance	(	const T *	first,
		const T *	second
	)		const

inlineprotected

Determines the square distance between two values.

Parameters

first	The first value
second	The second value

Returns: Square distance

◆ dimension()

template<typename T >

unsigned int Ocean::KdTree< T >::dimension

inline

Returns the dimension of the tree's values.

Returns: The tree's dimension

◆ distribute()

template<typename T >

void Ocean::KdTree< T >::distribute	(	const T **	values,
		const size_t	number,
		const unsigned int	index,
		const T *&	medianValue,
		Pointers &	leftValues,
		Pointers &	rightValues
	)

staticprotected

Distributes a given set of values into two subset according to the median.

Parameters

values	The values to distribute
number	The number of values
index	Dimension index to be used for distribution
medianValue	Resulting median value
leftValues	Resulting left values
rightValues	Resulting right values

◆ insert()

template<typename T >

bool Ocean::KdTree< T >::insert	(	const T **	values,
		const size_t	number
	)

Inserts a set of values to this empty tree.

Beware: Adding elements to an already existing tree with nodes is not supported.

Parameters

values	The values to be added
number	The number of elements to be added, with range [0, infinity)

Returns: True, if succeeded

◆ insertLeft()

template<typename T >

void Ocean::KdTree< T >::insertLeft	(	Node &	parent,
		const T **	values,
		const size_t	number,
		const unsigned int	depth
	)

protected

Inserts a set of values to a given parent as left children.

Parameters

parent	The parent node
values	The values to be added
number	The number of elements to be added
depth	Current depth of the new nodes

◆ insertRight()

template<typename T >

void Ocean::KdTree< T >::insertRight	(	Node &	parent,
		const T **	values,
		const size_t	number,
		const unsigned int	depth
	)

protected

Inserts a set of values to a given parent as right children.

Parameters

parent	The parent node
values	The values to be added
number	The number of elements to be added
depth	Current depth of the new nodes

◆ median()

template<typename T >

T Ocean::KdTree< T >::median	(	const T **	values,
		const size_t	number,
		const unsigned int	index
	)

staticprotected

Returns the median for a given set of values.

Parameters

values	The values to return the median for
number	The number of values
index	Dimension index

Returns: Resulting median

◆ nearestNeighbor() [1/2]

template<typename T >

const T * Ocean::KdTree< T >::nearestNeighbor	(	const T *	value,
		typename SquareValueTyper< T >::Type &	distance
	)		const

Applies a nearest neighbor search for a given value.

Parameters

value	The value to be searched
distance	Resulting minimal distance

Returns: Resulting nearest neighbor

◆ nearestNeighbor() [2/2]

template<typename T >

void Ocean::KdTree< T >::nearestNeighbor	(	Node &	node,
		const T *	value,
		const T *&	nearest,
		typename SquareValueTyper< T >::Type &	distance,
		const unsigned int	index
	)		const

protected

Applies a nearest neighbor search for a given node and value.

Parameters

node	Reference node
value	The value to be searched
nearest	Resulting nearest value
distance	Resulting minimal distance
index	The index of the dimension for the recent search, with range [0, dimension())

◆ radiusSearch() [1/2]

template<typename T >

size_t Ocean::KdTree< T >::radiusSearch	(	const T *	value,
		const typename SquareValueTyper< T >::Type	radius,
		const T **	values,
		const size_t	maxValues
	)		const

Applies a radius search for neighbors of a given value.

Beware: Function offers performance boost over brute force search only if radius is so small that relatively few values are returned.

Parameters

value	The value to be searched
radius	The neighborhood radius, with range [0, infinity)
values	Found values within radius distance from a given value
maxValues	Limit number of returned values

Returns: Number of returned values

◆ radiusSearch() [2/2]

template<typename T >

size_t Ocean::KdTree< T >::radiusSearch	(	Node &	node,
		const T *	value,
		const typename SquareValueTyper< T >::Type	radius,
		const T **	values,
		const size_t	maxValues,
		const unsigned int	index
	)		const

protected

Applies a radius search for neighbors of a given value.

Parameters

node	Reference node
value	The value to be searched
radius	The neighborhood radius, with range [0, infinity)
values	Found values within radius distance from a given value
maxValues	Limit number of returned values
index	The index of the dimension for the recent search, with range [0, dimension())

Returns: Number of returned values

◆ size()

template<typename T >

size_t Ocean::KdTree< T >::size

inline

Returns the number of tree nodes.

Returns: Tree size

Field Documentation

◆ dimension_

template<typename T >

const unsigned int Ocean::KdTree< T >::dimension_ = 0u

protected

Number of dimensions.

◆ root_

template<typename T >

std::unique_ptr<Node> Ocean::KdTree< T >::root_

protected

Root node of this tree.

◆ size_

template<typename T >

size_t Ocean::KdTree< T >::size_ = 0

protected

Number of nodes.

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

KdTree.h

Data Structures

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Member Functions

Protected Attributes

Detailed Description

template<typename T> class Ocean::KdTree< T >

Member Typedef Documentation

◆ Elements

◆ Pointers

Constructor & Destructor Documentation

◆ KdTree()

◆ ~KdTree()

Member Function Documentation

◆ determineSquareDistance()

◆ dimension()

◆ distribute()

◆ insert()

◆ insertLeft()

◆ insertRight()

◆ median()

◆ nearestNeighbor() [1/2]

◆ nearestNeighbor() [2/2]

◆ radiusSearch() [1/2]

◆ radiusSearch() [2/2]

◆ size()

Field Documentation

◆ dimension_

◆ root_

◆ size_

template<typename T>
class Ocean::KdTree< T >