| TerraLib 4.1

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

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

Public Types | Public Member Functions | Protected Member Functions
TeSAM::TeKdTree< KdTreeNode > Class Template Reference

A class that represents a two dimensional K-d Tree (2-d Tree) More...

`#include <TeKdTree.h>`

Inheritance diagram for TeSAM::TeKdTree< KdTreeNode >:

List of all members.

## Public Types

typedef KdTreeNode::kdKey | kdKey
| Export key type.
typedef KdTreeNode::kdData | kdData
| Export data type.
typedef KdTreeNode::kdDataItem | kdDataItem
| Export data item type.
typedef KdTreeNode::kdDataTag | kdDataTag
| Export data type.

## Public Member Functions

| TeKdTree (const TeBox &mbr)
| Constructor.
void | insert (const kdKey &key, const kdDataItem &item)
| Inserts the data with a given key in tree.
void | buildOptimized (vector< pair< kdKey, kdDataItem > > &dataSet)
| Inserts the data in the tree and and keeps it balanced: the kdsort algorithm must be called before.
void | search (const TeBox &rect, vector< KdTreeNode * > &report) const
| Range search query.

## Protected Member Functions

void | insertData (KdTreeNode *&node, const kdDataItem &data, const kd_node_data_single_tag &)
| Inserts data for single nodes, i.e., nodes that stores only one element.
void | insertData (KdTreeNode *&node, const kdDataItem &data, const kd_node_data_set_tag &)
| Inserts data for set nodes, i.e., nodes that may stores many element.
void | search (const TeBox &rect, KdTreeNode *node, const char &level, vector< KdTreeNode * > &report) const
| Recursive range query.
KdTreeNode * | buildOptimized (vector< pair< kdKey, kdDataItem > > &dataSet, const unsigned int &first, const unsigned int &last)
| Builds the tree recursively.

## Detailed Description

### template<class KdTreeNode>
class TeSAM::TeKdTree< KdTreeNode >

A class that represents a two dimensional K-d Tree (2-d Tree)

WARNING:

1. This type of tree stores the data into nodes (not only in the leafs node).

2. This tree may be built by two ways:
2.1. Inserting each element in the tree. In this case the tree can becomes unbalanced, but in practical cases this is not the expected, and is the best way to construct the tree (faster way).
2.2. Passing a container with pairs (key/data-item) and using the method buildOptimized after calling kdsort. The tree built this way is almost balanced but will be construct in time O(N log N).
WARNING: In this case items with the same key will be stores in different nodes!

3. This type of tree may be of special interest of BOX SEARCH QUERIES.

4. If the node type is kd_node_data_single_tag than NodeData and NodeDataItem are the same types. And if one entry with the same key already exist, so they will be overwrite.

5. If the node type is kd_node_data_set_tag than NodeData mus have a method called push_back(NodeDataItem) that permits to store elements with the same key in the node.

## Member Typedef Documentation

template<class KdTreeNode >

typedef KdTreeNode::kdData TeSAM::TeKdTree< KdTreeNode >::kdData

Export data type.

template<class KdTreeNode >

typedef KdTreeNode::kdDataItem TeSAM::TeKdTree< KdTreeNode >::kdDataItem

Export data item type.

template<class KdTreeNode >

typedef KdTreeNode::kdDataTag TeSAM::TeKdTree< KdTreeNode >::kdDataTag

Export data type.

template<class KdTreeNode >

typedef KdTreeNode::kdKey TeSAM::TeKdTree< KdTreeNode >::kdKey

Export key type.

## Constructor & Destructor Documentation

template<class KdTreeNode >

TeSAM::TeKdTree< KdTreeNode >::TeKdTree | ( | const TeBox & | mbr | ) | `[inline]`

Constructor.

## Member Function Documentation

template<class KdTreeNode >

void TeSAM::TeKdTree< KdTreeNode >::buildOptimized | ( | vector< pair< kdKey, kdDataItem > > & | dataSet | ) | `[inline]`

Inserts the data in the tree and and keeps it balanced: the kdsort algorithm must be called before.

template<class KdTreeNode >

KdTreeNode* TeSAM::TeKdTree< KdTreeNode >::buildOptimized | ( | vector< pair< kdKey, kdDataItem > > & | dataSet,
|  | const unsigned int & | first,
|  | const unsigned int & | last
| ) |  | `[inline, protected]`

Builds the tree recursively.

template<class KdTreeNode >

void TeSAM::TeKdTree< KdTreeNode >::insert | ( | const kdKey & | key,
|  | const kdDataItem & | item
| ) |  | `[inline]`

Inserts the data with a given key in tree.

template<class KdTreeNode >

void TeSAM::TeKdTree< KdTreeNode >::insertData | ( | KdTreeNode *& | node,
|  | const kdDataItem & | data,
|  | const kd_node_data_set_tag & |
| ) |  | `[inline, protected]`

Inserts data for set nodes, i.e., nodes that may stores many element.

template<class KdTreeNode >

void TeSAM::TeKdTree< KdTreeNode >::insertData | ( | KdTreeNode *& | node,
|  | const kdDataItem & | data,
|  | const kd_node_data_single_tag & |
| ) |  | `[inline, protected]`

Inserts data for single nodes, i.e., nodes that stores only one element.

template<class KdTreeNode >

void TeSAM::TeKdTree< KdTreeNode >::search | ( | const TeBox & | rect,
|  | vector< KdTreeNode * > & | report
| ) |  | const`[inline]`

Range search query.

template<class KdTreeNode >

void TeSAM::TeKdTree< KdTreeNode >::search | ( | const TeBox & | rect,
|  | KdTreeNode * | node,
|  | const char & | level,
|  | vector< KdTreeNode * > & | report
| ) |  | const`[inline, protected]`

Recursive range query.

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

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

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines