| TerraLib 4.1

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

- Class List
- Class Index
- Class Hierarchy
- Class Members

Classes | Public Types | Public Member Functions | Protected Member Functions | Protected Attributes
TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES > Class Template Reference

A class that represents a two dimensional R-Tree. More...

`#include <TeRTree.h>`

List of all members.

## Classes

struct | TePartitionVars
| Structure of auxiliary variables for finding a split partition. More...

## Public Types

typedef TeRTreeNode< DATATYPE, MAXNODES, MINNODES > | TeRTreeNodeType
| Export this typename.
typedef TeRTreeNodeType::TeRTreeBranch | TeRTreeBranch
| Export this typename.

## Public Member Functions

| TeRTree (const TeBox &mbr)
| Construtor.
| ~TeRTree ()
| Destructor.
const unsigned int & | size (void) const
| The number of elements of the tree.
bool | isEmpty (void) const
| Return true if the tree is empty.
void | clear (void)
| Clear all tree nodes.
void | insert (const TeBox &rect, const DATATYPE &data)
| Inserts item into the tree.
bool | remove (const TeBox &rect, const DATATYPE &data)
| Removes item from tree.
int | search (const TeBox &rect, vector< DATATYPE > &report) const
| Range search query.
void | setBox (const TeBox &mbr)
| Sets the bounding box of all elements in the tree.
const TeBox & | getBox (void) const
| Gets the bounding box of all elements in the tree.

## Protected Member Functions

bool | insert (const TeBox &rect, const DATATYPE &data, TeRTreeNodeType **root, int level)
| Insert a data rectangle into an index structure.
bool | remove (const TeBox &rect, const DATATYPE &data, TeRTreeNodeType **root)
| Delete a data rectangle from an index structure.
bool | remove2 (const TeBox &rect, const DATATYPE &data, TeRTreeNodeType *n, vector< TeRTreeNodeType * > &ee)
| Delete a rectangle from non-root part of an index structure.
void | disconBranch (TeRTreeNodeType *n, int i)
| Disconnect a dependent node.
bool | chooseLeaf (const TeBox &rect, const DATATYPE &data, TeRTreeNodeType *node, TeRTreeNodeType **newNode, int level)
| Inserts a new data rectangle into the index structure.
void | search (const TeBox &rect, TeRTreeNodeType *node, vector< DATATYPE > &report, int &foundObjs) const
| Recursive range query.
TeBox | nodeCover (TeRTreeNodeType *n) const
| Find the smallest rectangle that includes all rectangles in branches of a node.
TeBox | combineRect (const TeBox &rectA, const TeBox &rectB) const
| Combine two rectangles into larger one containing both.
bool | addBranch (TeRTreeBranch *branch, TeRTreeNodeType *node, TeRTreeNodeType **newNode) const
| Add a branch to a node.
int | pickBranch (const TeBox &rect, TeRTreeNodeType *node) const
| Pick a branch.
void | splitNode (TeRTreeNodeType *node, TeRTreeBranch *branch, TeRTreeNodeType **newNode) const
| Split a node.
void | getBranches (TeRTreeNodeType *n, TeRTreeBranch *b, TePartitionVars &p) const
| Load branch buffer with branches from full node plus the extra branch.
void | methodZero (TePartitionVars &p) const
| Method 0 for finding a partition.
void | pickSeeds (TePartitionVars &p) const
| Pick two rects from set to be the first elements of the two groups.
void | classify (int i, int group, TePartitionVars &p) const
| Put a branch in one of the groups.
void | pigeonhole (TePartitionVars &p) const
| Put each rect that is not already in a group into a group.
void | loadNodes (TeRTreeNodeType *n, TeRTreeNodeType *q, TePartitionVars &p) const
| Copy branches from the buffer into two nodes according to the partition.
double | rectArea (const TeBox &b) const
| Calculate rect area.
void | erase (TeRTreeNodeType *node)
| Erases a node from the tree and all nodes below it.
bool | rtreeBoxIntersects (const TeBox &bx1, const TeBox &bx2) const
| Only to determine if the two box intersects withou using an epsilon.

## Protected Attributes

TeRTreeNodeType * | root_
| Pointer to root node.
TeBox | mbr_
| Bounding box of the tree.
unsigned int | size_
| The size of R-Tree (number of nodes)

## Detailed Description

### template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
class TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >

A class that represents a two dimensional 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.

WARNING:

1. Don't use this class! It is for TerraLib internal use.

2. Only the basic methods for inserting and searching were implemented.

3. In future we will implement:

- the delete method.
- the near query
- point query

## Member Typedef Documentation

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

typedef TeRTreeNodeType::TeRTreeBranch TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::TeRTreeBranch

Export this typename.

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

typedef TeRTreeNode<DATATYPE, MAXNODES, MINNODES> TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::TeRTreeNodeType

Export this typename.

## Constructor & Destructor Documentation

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

TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::TeRTree | ( | const TeBox & | mbr | ) | `[inline]`

Construtor.

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

TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::~TeRTree | ( |  | ) | `[inline]`

Destructor.

## Member Function Documentation

template<class DATATYPE , int MAXNODES, int MINNODES>

bool TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::addBranch | ( | TeRTreeBranch * | branch,
|  | TeRTreeNodeType * | node,
|  | TeRTreeNodeType ** | newNode
| ) |  | const`[inline, protected]`

Add a branch to a node.

Split the node if necessary.
Returns false if node not split.
Old node updated.
Returns true if node split, sets *new to address of new node.
Old node updated, becomes one of two.

template<class DATATYPE, int MAXNODES, int MINNODES>

bool TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::chooseLeaf | ( | const TeBox & | rect,
|  | const DATATYPE & | data,
|  | TeRTreeNodeType * | node,
|  | TeRTreeNodeType ** | newNode,
|  | int | level
| ) |  | `[inline, protected]`

Inserts a new data rectangle into the index structure.

Recursively descends tree, propagates splits back up. Returns false if node was not split. Old node updated. If node was split, returns true and sets the pointer pointed to by new to point to the new node. Old node updated to become one of two. The level argument specifies the number of steps up from the leaf level to insert; e.g. a data rectangle goes in at level = 0.

template<class DATATYPE , int MAXNODES, int MINNODES>

void TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::classify | ( | int | i,
|  | int | group,
|  | TePartitionVars & | p
| ) |  | const`[inline, protected]`

Put a branch in one of the groups.

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

void TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::clear | ( | void |  | ) | `[inline]`

Clear all tree nodes.

template<class DATATYPE , int MAXNODES, int MINNODES>

TeBox TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::combineRect | ( | const TeBox & | rectA,
|  | const TeBox & | rectB
| ) |  | const`[inline, protected]`

Combine two rectangles into larger one containing both.

template<class DATATYPE , int MAXNODES, int MINNODES>

void TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::disconBranch | ( | TeRTreeNodeType * | n,
|  | int | i
| ) |  | `[inline, protected]`

Disconnect a dependent node.

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

void TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::erase | ( | TeRTreeNodeType * | node | ) | `[inline, protected]`

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

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

const TeBox& TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::getBox | ( | void |  | ) | const`[inline]`

Gets the bounding box of all elements in the tree.

template<class DATATYPE , int MAXNODES, int MINNODES>

void TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::getBranches | ( | TeRTreeNodeType * | n,
|  | TeRTreeBranch * | b,
|  | TePartitionVars & | p
| ) |  | const`[inline, protected]`

Load branch buffer with branches from full node plus the extra branch.

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

void TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::insert | ( | const TeBox & | rect,
|  | const DATATYPE & | data
| ) |  | `[inline]`

Inserts item into the tree.

template<class DATATYPE, int MAXNODES, int MINNODES>

bool TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::insert | ( | const TeBox & | rect,
|  | const DATATYPE & | data,
|  | TeRTreeNodeType ** | root,
|  | int | level
| ) |  | `[inline, protected]`

Insert a data rectangle into an index structure.

Insert provides for splitting the root.
Returns true if root was split, false if it was not.
The level argument specifies the number of steps up from the leaf level to insert; e.g. a data rectangle goes in at level = 0.
chooseLeaf does the recursion.

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

bool TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::isEmpty | ( | void |  | ) | const`[inline]`

Return true if the tree is empty.

template<class DATATYPE , int MAXNODES, int MINNODES>

void TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::loadNodes | ( | TeRTreeNodeType * | n,
|  | TeRTreeNodeType * | q,
|  | TePartitionVars & | p
| ) |  | const`[inline, protected]`

Copy branches from the buffer into two nodes according to the partition.

template<class DATATYPE , int MAXNODES, int MINNODES>

void TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::methodZero | ( | TePartitionVars & | p | ) | const`[inline, protected]`

Method 0 for finding a partition.

First find two seeds, one for each group, well separated. Then put other rects in whichever group will be smallest after addition.

template<class DATATYPE , int MAXNODES, int MINNODES>

TeBox TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::nodeCover | ( | TeRTreeNodeType * | n | ) | const`[inline, protected]`

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

template<class DATATYPE , int MAXNODES, int MINNODES>

int TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::pickBranch | ( | const TeBox & | rect,
|  | TeRTreeNodeType * | node
| ) |  | const`[inline, protected]`

Pick a branch.

Pick the one that will need the smallest increase in area to accomodate the new rectangle. This will result in the least total area for the covering rectangles in the current node. In case of a tie, pick the one which was smaller before, to get the best resolution when searching.

template<class DATATYPE , int MAXNODES, int MINNODES>

void TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::pickSeeds | ( | TePartitionVars & | p | ) | const`[inline, protected]`

Pick two rects from set to be the first elements of the two groups.

Pick the two that are separated most along any dimension, or overlap least. Distance for separation or overlap is measured modulo the width of the space covered by the entire set along that dimension.

template<class DATATYPE , int MAXNODES, int MINNODES>

void TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::pigeonhole | ( | TePartitionVars & | p | ) | const`[inline, protected]`

Put each rect that is not already in a group into a group.

Process one rect at a time, using the following hierarchy of criteria. In case of a tie, go to the next test.
1) If one group already has the max number of elements that will allow the minimum fill for the other group, put r in the other.
2) Put r in the group whose cover will expand less. This automatically takes care of the case where one group cover contains r.
3) Put r in the group whose cover will be smaller. This takes care of the case where r is contained in both covers.
4) Put r in the group with fewer elements.
5) Put in group 1 (arbitrary).

Also update the covers for both groups.

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

double TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::rectArea | ( | const TeBox & | b | ) | const`[inline, protected]`

Calculate rect area.

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

bool TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::remove | ( | const TeBox & | rect,
|  | const DATATYPE & | data
| ) |  | `[inline]`

Removes item from tree.

template<class DATATYPE, int MAXNODES, int MINNODES>

bool TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::remove | ( | const TeBox & | rect,
|  | const DATATYPE & | data,
|  | TeRTreeNodeType ** | root
| ) |  | `[inline, protected]`

Delete a data rectangle from an index structure.

Pass in a pointer to a Rect, the tid of the record, ptr to ptr to root node.
Returns 1 if record not found, 0 if success.
DeleteRect provides for eliminating the root.

template<class DATATYPE, int MAXNODES, int MINNODES>

bool TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::remove2 | ( | const TeBox & | rect,
|  | const DATATYPE & | data,
|  | TeRTreeNodeType * | n,
|  | vector< TeRTreeNodeType * > & | ee
| ) |  | `[inline, protected]`

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

Called by DeleteRect.
Descends tree recursively, merges branches on the way back up.

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

bool TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::rtreeBoxIntersects | ( | const TeBox & | bx1,
|  | const TeBox & | bx2
| ) |  | const`[inline, protected]`

Only to determine if the two box intersects withou using an epsilon.

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

int TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::search | ( | const TeBox & | rect,
|  | vector< DATATYPE > & | report
| ) |  | const`[inline]`

Range search query.

template<class DATATYPE, int MAXNODES, int MINNODES>

void TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::search | ( | const TeBox & | rect,
|  | TeRTreeNodeType * | node,
|  | vector< DATATYPE > & | report,
|  | int & | foundObjs
| ) |  | const`[inline, protected]`

Recursive range query.

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

void TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::setBox | ( | const TeBox & | mbr | ) | `[inline]`

Sets the bounding box of all elements in the tree.

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

const unsigned int& TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::size | ( | void |  | ) | const`[inline]`

The number of elements of the tree.

template<class DATATYPE , int MAXNODES, int MINNODES>

void TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::splitNode | ( | TeRTreeNodeType * | node,
|  | TeRTreeBranch * | branch,
|  | TeRTreeNodeType ** | newNode
| ) |  | const`[inline, protected]`

Split a node.

Divides the nodes branches and the extra one between two nodes.
Old node is one of the new ones, and one really new one is created.

## Member Data Documentation

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

TeBox TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::mbr_`[protected]`

Bounding box of the tree.

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

TeRTreeNodeType* TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::root_`[protected]`

Pointer to root node.

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

unsigned int TeSAM::TeRTree< DATATYPE, MAXNODES, MINNODES >::size_`[mutable, protected]`

The size of R-Tree (number of nodes)

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

- E:/Projetos_Primeiro_Semestre_2012/TerraView/terralib/src/terralib/kernel/TeRTree.h

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines