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

◆ BranchType

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.

◆ NodeType

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.

◆ PartitionVarsType

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

◆ Index() [1/3]

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.

◆ Index() [2/3]

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.

◆ ~Index()

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.

◆ Index() [3/3]

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

◆ addBranch()

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

◆ chooseLeaf()

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

◆ classify()

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

◆ clear()

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.

◆ combineRect()

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

◆ disconBranch()

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

◆ erase()

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

◆ getBranches()

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

◆ getMBR()

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.

◆ insert() [1/2]

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.

◆ insert() [2/2]

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.

◆ isEmpty()

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.

◆ loadNodes()

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

◆ methodZero()

template<class DATATYPE , int MAXNODES, int MINNODES>

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

inlineprotected

Definition at line 681 of file Index.h.

◆ nodeCover()

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

◆ operator=()

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.

◆ pickBranch()

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

◆ pickSeeds()

template<class DATATYPE , int MAXNODES, int MINNODES>

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

inlineprotected

Definition at line 689 of file Index.h.

◆ pigeonhole()

template<class DATATYPE , int MAXNODES, int MINNODES>

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

inlineprotected

Definition at line 802 of file Index.h.

◆ remove() [1/2]

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.

◆ remove() [2/2]

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

◆ remove2()

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

◆ search() [1/2]

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.

◆ search() [2/2]

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

◆ setMBR()

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.

◆ size()

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.

◆ splitNode()

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

Member Data Documentation

◆ m_mbr

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.

◆ m_root

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.

◆ m_size

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.

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

/home/castejon/castejon_files/develop/terralib5/git_release/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

◆ BranchType

◆ NodeType

◆ PartitionVarsType

Constructor & Destructor Documentation

◆ Index() [1/3]

◆ Index() [2/3]

◆ ~Index()

◆ Index() [3/3]

Member Function Documentation

◆ addBranch()

◆ chooseLeaf()

◆ classify()

◆ clear()

◆ combineRect()

◆ disconBranch()

◆ erase()

◆ getBranches()

◆ getMBR()

◆ insert() [1/2]

◆ insert() [2/2]

◆ isEmpty()

◆ loadNodes()

◆ methodZero()

◆ nodeCover()

◆ operator=()

◆ pickBranch()

◆ pickSeeds()

◆ pigeonhole()

◆ remove() [1/2]

◆ remove() [2/2]

◆ remove2()

◆ search() [1/2]

◆ search() [2/2]

◆ setMBR()

◆ size()

◆ splitNode()

Member Data Documentation

◆ m_mbr

◆ m_root

◆ m_size

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