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 353 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 361 of file Index.h.

template<class KdTreeNode >

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

Export data item type.

Definition at line 364 of file Index.h.

template<class KdTreeNode >

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

Export key type.

Definition at line 358 of file Index.h.

template<class KdTreeNode >

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

Export node type.

Definition at line 367 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 370 of file Index.h.

template<class KdTreeNode >

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

inline

Destructor.

Definition at line 379 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 495 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 432 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 563 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 385 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 471 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 426 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 414 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 402 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 442 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 664 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 459 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 542 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 707 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 420 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 408 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 396 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 734 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 538 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 536 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 535 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 537 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/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 >