te::sam::kdtree Namespace Reference

This is the namespace for the K-d Tree Spatial Access Method. More...

Classes
class	AdaptativeIndex
	A class that represents a two dimensional K-d Tree (2-d Tree) that store data-elements into the leafs. More...
class	AdaptativeNode
	A class that represents an Kd-tree node. More...
class	Index
	A class that represents a two dimensional K-d Tree (2-d Tree). More...
struct	kd_node_m_dataset_tag
	Kd-Tree node type for nodes with multuple elements (used by template instantiation). More...
struct	kd_node_m_datasingle_tag
	Kd-tree node type for nodes with single elements (used by template instantiation). More...
class	Node
	A class that represents an Kd-tree node. More...

Functions
template<class CONTAINER , class COMPFUNCTOR >
void	HoareFind (CONTAINER &A, const std::size_t &kthElement, const std::size_t &firstElement, const std::size_t &lastElement, const COMPFUNCTOR &compFunctor)
	This function partition the container in two parts: k-1 elements to the left (elements less than or equals to k-th element) and the right part with all other elements (elements greater than or equal to k-th element). More...
template<class CONTAINER , class LESSTHANX , class LESSTHANY >
void	kdsort (CONTAINER &dataSet, const std::size_t &first, const std::size_t &last, const char &level, const LESSTHANX &lessThanCompFunctorByX, const LESSTHANY &lessThanCompFunctorByY)
	This partition the container like a bidimensional K-d Tree using Hoare algorithms. More...

Detailed Description

This is the namespace for the K-d Tree Spatial Access Method.

Note

See namespace te comments for any detail on using namespaces.

Function Documentation

template<class CONTAINER , class COMPFUNCTOR >

void te::sam::kdtree::HoareFind	(	CONTAINER &	A,
		const std::size_t &	kthElement,
		const std::size_t &	firstElement,
		const std::size_t &	lastElement,
		const COMPFUNCTOR &	compFunctor
	)

This function partition the container in two parts: k-1 elements to the left (elements less than or equals to k-th element) and the right part with all other elements (elements greater than or equal to k-th element).

Parameters

A	Container of elements to partition.
kthElement	Position of the k-th element, around the container will be pertitionated.
firstElement	Position of the first element.
lastElement	Position of the las element.
compFunctor	Functor to compare elements: implements the function "less than".

Definition at line 47 of file Partition.h.

Referenced by kdsort().

template<class CONTAINER , class LESSTHANX , class LESSTHANY >

void te::sam::kdtree::kdsort	(	CONTAINER &	dataSet,
		const std::size_t &	first,
		const std::size_t &	last,
		const char &	level,
		const LESSTHANX &	lessThanCompFunctorByX,
		const LESSTHANY &	lessThanCompFunctorByY
	)

This partition the container like a bidimensional K-d Tree using Hoare algorithms.

Parameters

dataSet	Container elements to be sorted like a K-d Tree.
first	Position of the first element in container, where the sort will begin.
last	Position of the last element, where the sort ends.
level	Indicates the axis to begin the sort ('x' or 'y') and is used during the recursion process.
lessThanCompFunctorByX	Functor to compare elements along the 'x' axis.
lessThanCompFunctorByY	Functor to compare elements along the 'y' axis.

Note

The expected complexity is O(N log N), where N is the number of elements in container.

Definition at line 106 of file Partition.h.

References HoareFind().