|
| void | buildOptimized (std::vector< std::pair< kdKey, kdData > > &dataSet) |
| | It inserts the data in the tree and and keeps it balanced: the kdsort algorithm must be called before.
|
| |
| void | clear () |
| | It clears all tree nodes.
|
| |
| const te::gm::Envelope & | getMBR () const |
| | It gets the minimum bounding box of all elements in the tree.
|
| |
| | Index (const te::gm::Envelope &mbr) |
| | Constructor.
|
| |
| void | insert (const kdKey &key, const kdData &item) |
| | It inserts the data with a given key in tree.
|
| |
| bool | isEmpty () const |
| | It returns true if the tree is empty and false otherwise.
|
| |
| void | search (const te::gm::Envelope &e, std::vector< KdTreeNode * > &report) const |
| | Range search query.
|
| |
| void | setMBR (const te::gm::Envelope &mbr) |
| | It sets the minimum bounding box of all elements in the tree.
|
| |
| const std::size_t & | size () const |
| | It returns the number of tree nodes.
|
| |
| | ~Index () |
| | Destructor.
|
| |
|
| KdTreeNode * | buildOptimized (std::vector< std::pair< kdKey, kdData > > &dataSet, const std::size_t &first, const std::size_t &last) |
| | It builds the tree recursively.
|
| |
| void | erase (KdTreeNode *node) |
| | It Erases a node from the tree and all nodes below it.
|
| |
| | Index (const Index &rhs) |
| | No copy constructor allowed.
|
| |
| void | insertData (KdTreeNode *&node, const kdData &data, const kd_node_m_dataset_tag &) |
| | It inserts data for set nodes, i.e., nodes that may stores many element.
|
| |
| void | insertData (KdTreeNode *&node, const kdData &data, const kd_node_m_datasingle_tag &) |
| | It inserts data for single nodes, i.e. nodes that stores only one element.
|
| |
| Index & | operator= (const Index &rhs) |
| | No assignment operator allowed.
|
| |
| void | search (const te::gm::Envelope &e, KdTreeNode *node, const char &level, std::vector< KdTreeNode * > &report) const |
| | Recursive range query.
|
| |
template<class KdTreeNode>
class te::sam::kdtree::Index< KdTreeNode >
A class that represents a two dimensional K-d Tree (2-d Tree).
- Note
- This type of tree stores the data into nodes (not only in the leafs node).
-
This tree may be built by two ways: 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) 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!
-
This type of tree may be of special interest of EXTENT SEARCH QUERIES.
-
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.
-
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.
Definition at line 67 of file Index.h.
1.13.2