A class that represents an R-tree. More...

#include <Index.h>

Public Types
typedef NodeType::BranchType	BranchType

typedef Node< DATATYPE, MAXNODES, MINNODES >	NodeType

typedef te::sam::rtree::PartitionVars < BranchType, MAXNODES >	PartitionVarsType

Public Member Functions
void	clear (void)

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

	Index ()
	Constructor. More...

	Index (const te::gm::Envelope &mbr)
	Constructor. More...

void	insert (const te::gm::Envelope &mbr, const DATATYPE &data)
	It inserts an item into the tree. More...

bool	isEmpty (void) const
	It returns true if the tree is empty. More...

bool	remove (const te::gm::Envelope &mbr, const DATATYPE &data)
	It removes an item from the tree. More...

int	search (const te::gm::Envelope &mbr, std::vector< DATATYPE > &report) const
	Range search query. More...

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

std::size_t	size (void) const
	It returns the number of elements in the tree. More...

	~Index ()
	Destructor. More...

Protected Member Functions
bool	addBranch (BranchType branch, NodeType node, NodeType **newNode) const
	Add a branch to a node. More...

bool	chooseLeaf (const te::gm::Envelope &mbr, const DATATYPE &data, NodeType node, NodeType *newNode, int level)
	It inserts a new data rectangle into the index structure. More...

void	classify (int i, int group, PartitionVarsType &p) const

te::gm::Envelope	combineRect (const te::gm::Envelope &mbrA, const te::gm::Envelope &mbrB) const
	Combine two rectangles into larger one containing both. More...

void	disconBranch (NodeType *n, int i)
	It disconnects a dependent node. More...

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

void	getBranches (NodeType n, BranchType b, PartitionVarsType &p) const

bool	insert (const te::gm::Envelope &mbr, const DATATYPE &data, NodeType **root, int level)
	It inserts a data rectangle into an index structure. More...

void	loadNodes (NodeType n, NodeType q, PartitionVarsType &p) const

void	methodZero (PartitionVarsType &p) const

te::gm::Envelope	nodeCover (NodeType *n) const
	Find the smallest rectangle that includes all rectangles in branches of a node. More...

int	pickBranch (const te::gm::Envelope &mbr, NodeType *node) const
	Pick a branch. More...

void	pickSeeds (PartitionVarsType &p) const

void	pigeonhole (PartitionVarsType &p) const

bool	remove (const te::gm::Envelope &mbr, const DATATYPE &data, NodeType **root)
	It deletes a data rectangle from an index structure. More...

bool	remove2 (const te::gm::Envelope &mbr, const DATATYPE &data, NodeType n, std::vector< NodeType > &ee)
	It deletes a rectangle from non-root part of an index structure. More...

void	search (const te::gm::Envelope &mbr, NodeType *node, std::vector< DATATYPE > &report, int &foundObjs) const
	Recursive range query. More...

void	splitNode (NodeType node, BranchType branch, NodeType **newNode) const
	Split a node. More...

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

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

Private Attributes
te::gm::Envelope	m_mbr
	Bounding box of the tree. More...

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

std::size_t	m_size
	The size of R-Tree (number of nodes). More...

Detailed Description

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
class te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >

A class that represents an R-tree.

This implementation is based on:

Antonin Guttman. R-Trees: A Dynamic Index Structure for Spatial Searching. ACM SIGMOD: International Conference on Management of Data, 1984, pp. 47-57.

and in his original source code.

Definition at line 56 of file Index.h.

Member Typedef Documentation

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>

typedef NodeType::BranchType te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::BranchType

Definition at line 61 of file Index.h.

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>

typedef Node<DATATYPE, MAXNODES, MINNODES> te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::NodeType

Definition at line 60 of file Index.h.

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>

typedef te::sam::rtree::PartitionVars<BranchType, MAXNODES> te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::PartitionVarsType

Definition at line 62 of file Index.h.

Constructor & Destructor Documentation

template<class DATATYPE , int MAXNODES, int MINNODES>

te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index ( )

inline

Constructor.

Definition at line 261 of file Index.h.

References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level, te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_root, and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_size.

template<class DATATYPE , int MAXNODES, int MINNODES>

te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index ( const te::gm::Envelope & mbr )

inline

Constructor.

Parameters

mbr	The MBR of all elements in the R-tree.

Precondition: The given MBR must be valid.

Definition at line 270 of file Index.h.

References te::gm::Envelope::isValid(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level, te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_mbr, te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_root, and te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_size.

template<class DATATYPE , int MAXNODES, int MINNODES>

te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::~Index ( )

inline

Destructor.

Definition at line 280 of file Index.h.

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>

te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index ( const Index< DATATYPE, MAXNODES, MINNODES > & rhs )

private

No copy constructor allowed.

Parameters

rhs	The other rtree.

Member Function Documentation

template<class DATATYPE , int MAXNODES, int MINNODES>

bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::addBranch	(	BranchType *	branch,
		NodeType *	node,
		NodeType **	newNode
	)		const

inlineprotected

Add a branch to a node.

Definition at line 591 of file Index.h.

References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, and te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count.

template<class DATATYPE, int MAXNODES, int MINNODES>

bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::chooseLeaf	(	const te::gm::Envelope &	mbr,
		const DATATYPE &	data,
		NodeType *	node,
		NodeType **	newNode,
		int	level
	)

protected

It inserts a new data rectangle into the index structure.

Definition at line 482 of file Index.h.

References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::Branch< NODE, DATATYPE >::m_child, te::sam::rtree::Branch< NODE, DATATYPE >::m_data, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level, and te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr.

template<class DATATYPE , int MAXNODES, int MINNODES>

void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::classify	(	int	i,
		int	group,
		PartitionVarsType &	p
	)		const

inlineprotected

Definition at line 790 of file Index.h.

References te::gm::Envelope::getArea(), te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_area, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_branchBuf, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_count, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_cover, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_partition, and te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_taken.

template<class DATATYPE , int MAXNODES, int MINNODES>

void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::clear ( void )

inline

It clears all tree nodes and make it ready for new insertions.

Definition at line 299 of file Index.h.

Referenced by BufferMemory().

template<class DATATYPE , int MAXNODES, int MINNODES>

te::gm::Envelope te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::combineRect	(	const te::gm::Envelope &	mbrA,
		const te::gm::Envelope &	mbrB
	)		const

inlineprotected

Combine two rectangles into larger one containing both.

Definition at line 583 of file Index.h.

References te::gm::Envelope::Union().

template<class DATATYPE , int MAXNODES, int MINNODES>

void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::disconBranch	(	NodeType *	n,
		int	i
	)

protected

It disconnects a dependent node.

Definition at line 473 of file Index.h.

References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, and te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count.

template<class DATATYPE , int MAXNODES, int MINNODES>

void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::erase ( NodeType * node )

inlineprotected

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

Parameters

node	The node to be removed.

The node pointer will be invalidated.

Definition at line 879 of file Index.h.

References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::isLeaf(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::Branch< NODE, DATATYPE >::m_child, and te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count.

template<class DATATYPE , int MAXNODES, int MINNODES>

void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::getBranches	(	NodeType *	n,
		BranchType *	b,
		PartitionVarsType &	p
	)		const

inlineprotected

Definition at line 665 of file Index.h.

References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::init(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_branchBuf, and te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_coverSplit.

template<class DATATYPE , int MAXNODES, int MINNODES>

const te::gm::Envelope & te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::getMBR ( void ) const

inline

It returns the bounding box of all elements in the tree.

Returns: The bounding box of all elements in the tree.

Definition at line 343 of file Index.h.

template<class DATATYPE, int MAXNODES, int MINNODES>

void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::insert	(	const te::gm::Envelope &	mbr,
		const DATATYPE &	data
	)

inline

It inserts an item into the tree.

Parameters

mbr	The object MBR.
data	The object to be indexed.

Definition at line 313 of file Index.h.

References insert().

Referenced by BufferMemory(), te::graph::RAGGraphBuilder::createEdgeObjects(), CreateRTree(), te::rp::TiePointsLocator::executeMatchingByCorrelationThreadEntry(), and te::rp::TiePointsLocator::executeMatchingByEuclideanDistThreadEntry().

template<class DATATYPE, int MAXNODES, int MINNODES>

bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::insert	(	const te::gm::Envelope &	mbr,
		const DATATYPE &	data,
		NodeType **	root,
		int	level
	)

inlineprotected

It inserts a data rectangle into an index structure.

Returns: It returns true if root was split, false if it was not.

Definition at line 349 of file Index.h.

References te::sam::rtree::Branch< NODE, DATATYPE >::m_child, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level, and te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr.

template<class DATATYPE , int MAXNODES, int MINNODES>

bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::isEmpty ( void ) const

inline

It returns true if the tree is empty.

Returns: True if the tree is empty.

Definition at line 293 of file Index.h.

template<class DATATYPE , int MAXNODES, int MINNODES>

void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::loadNodes	(	NodeType *	n,
		NodeType *	q,
		PartitionVarsType &	p
	)		const

inlineprotected

Definition at line 865 of file Index.h.

References te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_branchBuf, and te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_partition.

template<class DATATYPE , int MAXNODES, int MINNODES>

void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::methodZero ( PartitionVarsType & p ) const

inlineprotected

Definition at line 685 of file Index.h.

References te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::init().

template<class DATATYPE , int MAXNODES, int MINNODES>

te::gm::Envelope te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::nodeCover ( NodeType * n ) const

protected

Find the smallest rectangle that includes all rectangles in branches of a node.

Definition at line 562 of file Index.h.

References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count, and te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr.

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>

Index& te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::operator= ( const Index< DATATYPE, MAXNODES, MINNODES > & rhs )

private

No assignment operator allowed.

Parameters

rhs	The other rtree.

Returns: A reference for this instance.

template<class DATATYPE , int MAXNODES, int MINNODES>

int te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::pickBranch	(	const te::gm::Envelope &	mbr,
		NodeType *	node
	)		const

inlineprotected

Pick a branch.

Definition at line 607 of file Index.h.

References te::gm::Envelope::getArea(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count, and te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr.

template<class DATATYPE , int MAXNODES, int MINNODES>

void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::pickSeeds ( PartitionVarsType & p ) const

inlineprotected

Definition at line 693 of file Index.h.

References te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_branchBuf, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_coverSplit, te::gm::Envelope::m_llx, te::gm::Envelope::m_lly, te::gm::Envelope::m_urx, and te::gm::Envelope::m_ury.

template<class DATATYPE , int MAXNODES, int MINNODES>

void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::pigeonhole ( PartitionVarsType & p ) const

inlineprotected

Definition at line 806 of file Index.h.

References te::gm::Envelope::getArea(), te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_area, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_branchBuf, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_count, te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_cover, and te::sam::rtree::PartitionVars< BRANCH, MAXNODES >::m_taken.

template<class DATATYPE, int MAXNODES, int MINNODES>

bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::remove	(	const te::gm::Envelope &	mbr,
		const DATATYPE &	data
	)

inline

It removes an item from the tree.

Parameters

mbr	The object MBR.
data	The object to be removed from the tree.

Returns: True if the object is found and removed, false otherwise.

Definition at line 320 of file Index.h.

Referenced by BufferMemory().

template<class DATATYPE, int MAXNODES, int MINNODES>

bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::remove	(	const te::gm::Envelope &	mbr,
		const DATATYPE &	data,
		NodeType **	root
	)

inlineprotected

It deletes a data rectangle from an index structure.

Returns: It returns 1 if record not found, 0 if success.

Definition at line 385 of file Index.h.

References insert(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::Branch< NODE, DATATYPE >::m_child, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count, te::sam::rtree::Branch< NODE, DATATYPE >::m_data, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level, and te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr.

template<class DATATYPE, int MAXNODES, int MINNODES>

bool te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::remove2	(	const te::gm::Envelope &	mbr,
		const DATATYPE &	data,
		NodeType *	n,
		std::vector< NodeType * > &	ee
	)

inlineprotected

It deletes a rectangle from non-root part of an index structure.

Returns

Definition at line 429 of file Index.h.

References te::gm::Envelope::intersects(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::isInternalNode(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::Branch< NODE, DATATYPE >::m_child, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count, te::sam::rtree::Branch< NODE, DATATYPE >::m_data, and te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr.

template<class DATATYPE, int MAXNODES, int MINNODES>

int te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::search	(	const te::gm::Envelope &	mbr,
		std::vector< DATATYPE > &	report
	)		const

inline

Range search query.

Parameters

mbr	The search rectangle.
report	A vector to output the founded objects.

Returns: the number of found objects.

Definition at line 326 of file Index.h.

Referenced by BufferMemory(), te::graph::RAGGraphBuilder::createEdgeObjects(), te::rp::TiePointsLocator::executeMatchingByCorrelationThreadEntry(), te::rp::TiePointsLocator::executeMatchingByEuclideanDistThreadEntry(), and PairwiseIntersection().

template<class DATATYPE, int MAXNODES, int MINNODES>

void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::search	(	const te::gm::Envelope &	mbr,
		NodeType *	node,
		std::vector< DATATYPE > &	report,
		int &	foundObjs
	)		const

protected

Recursive range query.

Definition at line 530 of file Index.h.

References te::gm::Envelope::intersects(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::isInternalNode(), te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_branch, te::sam::rtree::Branch< NODE, DATATYPE >::m_child, te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_count, te::sam::rtree::Branch< NODE, DATATYPE >::m_data, and te::sam::rtree::Branch< NODE, DATATYPE >::m_mbr.

template<class DATATYPE , int MAXNODES, int MINNODES>

void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::setMBR ( const te::gm::Envelope & mbr )

inline

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

Parameters

mbr	The bounding box of all elements in the tree.

Definition at line 337 of file Index.h.

template<class DATATYPE , int MAXNODES, int MINNODES>

std::size_t te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::size ( void ) const

inline

It returns the number of elements in the tree.

Returns: The number of indexed elements.

Definition at line 287 of file Index.h.

template<class DATATYPE , int MAXNODES, int MINNODES>

void te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::splitNode	(	NodeType *	node,
		BranchType *	branch,
		NodeType **	newNode
	)		const

inlineprotected

Split a node.

Definition at line 643 of file Index.h.

References te::sam::rtree::Node< DATATYPE, MAXNODES, MINNODES >::m_level.

Member Data Documentation

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>

te::gm::Envelope te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_mbr

private

Bounding box of the tree.

Definition at line 256 of file Index.h.

Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index().

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>

NodeType* te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_root

private

Pointer to the root node.

Definition at line 255 of file Index.h.

Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index().

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>

std::size_t te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::m_size

mutableprivate

The size of R-Tree (number of nodes).

Definition at line 257 of file Index.h.

Referenced by te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >::Index().

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

/home/castejon/castejon_files/develop/terralib5/git/src/terralib/sam/rtree/Index.h

Public Types

Public Member Functions

Protected Member Functions

Private Member Functions

Private Attributes

Detailed Description

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2> class te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Member Data Documentation

template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
class te::sam::rtree::Index< DATATYPE, MAXNODES, MINNODES >