A class that represents a two dimensional K-d Tree (2-d Tree) that store data-elements into the leafs. More...

#include <Index.h>

Public Types
typedef KdTreeNode::kdData	kdData
	Export data type. More...

typedef KdTreeNode::kdDataItem	kdDataItem
	Export data item type. More...

typedef KdTreeNode::kdKey	kdKey
	Export key type. More...

typedef KdTreeNode	kdNode
	Export node type. More...

Public Member Functions
	AdaptativeIndex (const te::gm::Envelope &mbr, const std::size_t &bucketSize=12)
	Constructor. More...

void	build (std::vector< std::pair< kdKey, kdDataItem > > &dataSet)
	It inserts the data set into the tree. More...

void	clear ()
	It clears all tree nodes. More...

const std::size_t &	getBucketSize () const
	It gets bucket size for leaf nodes. More...

const te::gm::Envelope &	getMBR () const
	It gets the minimum bounding box of all elements in the tree. More...

bool	isEmpty () const
	It returns true if the tree is empty and false otherwise. More...

void	nearestNeighborSearch (const kdKey &key, std::vector< kdDataItem > &report, std::vector< double > &sqrDists, const std::size_t &k) const
	It searches the nearest data in nodes: you must pass an array of kdDataItem of size "k" with coordinates values (X() and Y()) adjusted to td::numeric_limits<double>::max() (this dummy values will be replaced at processing time), and if not all neighbors are found so sqrDists will contains td::numeric_limits<double>::max() in array index. More...

void	search (const te::gm::Envelope &e, std::vector< KdTreeNode * > &report) const
	Range search query. More...

void	search (const te::gm::Envelope &e, std::vector< kdDataItem > &report) const
	Range search query: the refinement is already done. More...

void	setBucketSize (const std::size_t &size)
	It sets bucket size for leaf nodes. More...

void	setMBR (const te::gm::Envelope &mbr)
	It sets the minimum bounding box of all elements in the tree. More...

const std::size_t &	size () const
	It returns the number of tree nodes. More...

	~AdaptativeIndex ()
	Destructor. More...

Private Member Functions
	AdaptativeIndex (const AdaptativeIndex &rhs)
	No copy constructor allowed. More...

double	average (std::vector< std::pair< kdKey, kdDataItem > > &dataSet, const char &discriminator) const
	It returns the average value along the axis. More...

KdTreeNode *	build (std::vector< std::pair< kdKey, kdDataItem > > &dataSet, double averageValue, const te::gm::Envelope &mbr)
	It builds the tree recursivily. More...

void	erase (KdTreeNode *node)
	It Erases a node from the tree and all nodes below it. More...

void	nearestNeighborSearch (KdTreeNode *node, const kdKey &key, std::vector< kdDataItem > &report, std::vector< double > &sqrDists, te::gm::Envelope &e) const
	Recursive nearest neighbor search. More...

AdaptativeIndex &	operator= (const AdaptativeIndex &rhs)
	No assignment operator allowed. More...

void	search (const te::gm::Envelope &e, KdTreeNode node, std::vector< KdTreeNode > &report) const
	Recursive range query. More...

void	update (KdTreeNode *node, const kdKey &key, std::vector< kdDataItem > &report, std::vector< double > &sqrDists, te::gm::Envelope &e) const
	It updates the neighbor list. More...

Private Attributes
std::size_t	m_bucketSize
	Bucket size (maximum number of elements in each node). More...

te::gm::Envelope	m_mbr
	Minimum bounding box of all nodes. More...

KdTreeNode *	m_root
	Pointer to the root node. More...

std::size_t	m_size
	The size of the K-d Tree (number of nodes). More...

Detailed Description

template<class KdTreeNode>
class te::sam::kdtree::AdaptativeIndex< KdTreeNode >

A class that represents a two dimensional K-d Tree (2-d Tree) that store data-elements into the leafs.

Note: This type of tree stores the data only in the leaf nodes.; The process of construction expect that the tree is almost balanced.; This type of tree may be of special interest of NEAREST NEIGHBOR SEARCH QUERIES.; After a extent search it will be necessary to do a refinement.

Definition at line 352 of file Index.h.

Member Typedef Documentation

template<class KdTreeNode >

typedef KdTreeNode::kdData te::sam::kdtree::AdaptativeIndex< KdTreeNode >::kdData

Export data type.

Definition at line 360 of file Index.h.

template<class KdTreeNode >

typedef KdTreeNode::kdDataItem te::sam::kdtree::AdaptativeIndex< KdTreeNode >::kdDataItem

Export data item type.

Definition at line 363 of file Index.h.

template<class KdTreeNode >

typedef KdTreeNode::kdKey te::sam::kdtree::AdaptativeIndex< KdTreeNode >::kdKey

Export key type.

Definition at line 357 of file Index.h.

template<class KdTreeNode >

typedef KdTreeNode te::sam::kdtree::AdaptativeIndex< KdTreeNode >::kdNode

Export node type.

Definition at line 366 of file Index.h.

Constructor & Destructor Documentation

template<class KdTreeNode >

te::sam::kdtree::AdaptativeIndex< KdTreeNode >::AdaptativeIndex	(	const te::gm::Envelope &	mbr,
		const std::size_t &	bucketSize = `12`
	)

inline

Constructor.

Definition at line 369 of file Index.h.

template<class KdTreeNode >

te::sam::kdtree::AdaptativeIndex< KdTreeNode >::~AdaptativeIndex ( )

inline

Destructor.

Definition at line 378 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::clear().

template<class KdTreeNode >

te::sam::kdtree::AdaptativeIndex< KdTreeNode >::AdaptativeIndex ( const AdaptativeIndex< KdTreeNode > & rhs )

private

No copy constructor allowed.

Parameters

rhs	The other index.

Member Function Documentation

template<class KdTreeNode >

double te::sam::kdtree::AdaptativeIndex< KdTreeNode >::average	(	std::vector< std::pair< kdKey, kdDataItem > > &	dataSet,
		const char &	discriminator
	)		const

inlineprivate

It returns the average value along the axis.

Definition at line 494 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::size().

template<class KdTreeNode >

void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::build ( std::vector< std::pair< kdKey, kdDataItem > > & dataSet )

inline

It inserts the data set into the tree.

Definition at line 431 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_mbr, and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_root.

template<class KdTreeNode >

KdTreeNode * te::sam::kdtree::AdaptativeIndex< KdTreeNode >::build	(	std::vector< std::pair< kdKey, kdDataItem > > &	dataSet,
		double	averageValue,
		const te::gm::Envelope &	mbr
	)

inlineprivate

It builds the tree recursivily.

Definition at line 562 of file Index.h.

References te::gm::Envelope::m_llx, te::gm::Envelope::m_lly, te::gm::Envelope::m_urx, and te::gm::Envelope::m_ury.

template<class KdTreeNode >

void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::clear ( )

inline

It clears all tree nodes.

Definition at line 384 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::erase(), te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_root, and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_size.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::~AdaptativeIndex().

template<class KdTreeNode >

void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::erase ( KdTreeNode * node )

inlineprivate

It Erases a node from the tree and all nodes below it.

Definition at line 470 of file Index.h.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::clear().

template<class KdTreeNode >

const std::size_t& te::sam::kdtree::AdaptativeIndex< KdTreeNode >::getBucketSize ( ) const

inline

It gets bucket size for leaf nodes.

Definition at line 425 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_bucketSize.

template<class KdTreeNode >

const te::gm::Envelope& te::sam::kdtree::AdaptativeIndex< KdTreeNode >::getMBR ( ) const

inline

It gets the minimum bounding box of all elements in the tree.

Definition at line 413 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_mbr.

template<class KdTreeNode >

bool te::sam::kdtree::AdaptativeIndex< KdTreeNode >::isEmpty ( ) const

inline

It returns true if the tree is empty and false otherwise.

Definition at line 401 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_root.

template<class KdTreeNode >

void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::nearestNeighborSearch	(	const kdKey &	key,
		std::vector< kdDataItem > &	report,
		std::vector< double > &	sqrDists,
		const std::size_t &	k
	)		const

inline

It searches the nearest data in nodes: you must pass an array of kdDataItem of size "k" with coordinates values (X() and Y()) adjusted to td::numeric_limits<double>::max() (this dummy values will be replaced at processing time), and if not all neighbors are found so sqrDists will contains td::numeric_limits<double>::max() in array index.

Definition at line 441 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_root.

template<class KdTreeNode >

void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::nearestNeighborSearch	(	KdTreeNode *	node,
		const kdKey &	key,
		std::vector< kdDataItem > &	report,
		std::vector< double > &	sqrDists,
		te::gm::Envelope &	e
	)		const

inlineprivate

Recursive nearest neighbor search.

Definition at line 663 of file Index.h.

References te::gm::Envelope::m_llx, te::gm::Envelope::m_lly, te::gm::Envelope::m_urx, and te::gm::Envelope::m_ury.

template<class KdTreeNode >

AdaptativeIndex& te::sam::kdtree::AdaptativeIndex< KdTreeNode >::operator= ( const AdaptativeIndex< KdTreeNode > & rhs )

private

No assignment operator allowed.

Parameters

rhs	The other index.

Returns: A reference for this.

template<class KdTreeNode >

void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::search	(	const te::gm::Envelope &	e,
		std::vector< KdTreeNode * > &	report
	)		const

inline

Range search query.

Definition at line 458 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_root.

template<class KdTreeNode >

void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::search	(	const te::gm::Envelope &	e,
		std::vector< kdDataItem > &	report
	)		const

inline

Range search query: the refinement is already done.

Definition at line 541 of file Index.h.

References te::gm::Intersects().

template<class KdTreeNode >

void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::search	(	const te::gm::Envelope &	e,
		KdTreeNode *	node,
		std::vector< KdTreeNode * > &	report
	)		const

inlineprivate

Recursive range query.

Definition at line 706 of file Index.h.

References te::gm::Envelope::m_llx, te::gm::Envelope::m_lly, te::gm::Envelope::m_urx, and te::gm::Envelope::m_ury.

template<class KdTreeNode >

void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::setBucketSize ( const std::size_t & size )

inline

It sets bucket size for leaf nodes.

Definition at line 419 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_bucketSize, and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::size().

template<class KdTreeNode >

void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::setMBR ( const te::gm::Envelope & mbr )

inline

It sets the minimum bounding box of all elements in the tree.

Definition at line 407 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_mbr.

template<class KdTreeNode >

const std::size_t& te::sam::kdtree::AdaptativeIndex< KdTreeNode >::size ( ) const

inline

It returns the number of tree nodes.

Definition at line 395 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_size.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::average(), and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::setBucketSize().

template<class KdTreeNode >

void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::update	(	KdTreeNode *	node,
		const kdKey &	key,
		std::vector< kdDataItem > &	report,
		std::vector< double > &	sqrDists,
		te::gm::Envelope &	e
	)		const

inlineprivate

It updates the neighbor list.

Definition at line 733 of file Index.h.

References te::gm::Envelope::m_llx, te::gm::Envelope::m_lly, te::gm::Envelope::m_urx, and te::gm::Envelope::m_ury.

Member Data Documentation

template<class KdTreeNode >

std::size_t te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_bucketSize

private

Bucket size (maximum number of elements in each node).

Definition at line 537 of file Index.h.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::getBucketSize(), and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::setBucketSize().

template<class KdTreeNode >

te::gm::Envelope te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_mbr

private

Minimum bounding box of all nodes.

Definition at line 535 of file Index.h.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::build(), te::sam::kdtree::AdaptativeIndex< KdTreeNode >::getMBR(), and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::setMBR().

template<class KdTreeNode >

KdTreeNode* te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_root

private

Pointer to the root node.

Definition at line 534 of file Index.h.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::build(), te::sam::kdtree::AdaptativeIndex< KdTreeNode >::clear(), te::sam::kdtree::AdaptativeIndex< KdTreeNode >::isEmpty(), te::sam::kdtree::AdaptativeIndex< KdTreeNode >::nearestNeighborSearch(), and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::search().

template<class KdTreeNode >

std::size_t te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_size

private

The size of the K-d Tree (number of nodes).

Definition at line 536 of file Index.h.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::clear(), and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::size().

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

/home/castejon/castejon_files/develop/terralib5/git_master/terralib5/src/terralib/sam/kdtree/Index.h

Public Types

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<class KdTreeNode> class te::sam::kdtree::AdaptativeIndex< KdTreeNode >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class KdTreeNode>
class te::sam::kdtree::AdaptativeIndex< KdTreeNode >