te::sam::kdtree::AdaptativeIndex< KdTreeNode > Class Template Reference

A class that represents a two dimensional K-d Tree (2-d Tree) that store data-elements into the leafs. More...

#include <Index.h>

Public Types

typedef KdTreeNode::kdData kdData
 Export data type. More...
 
typedef KdTreeNode::kdDataItem kdDataItem
 Export data item type. More...
 
typedef KdTreeNode::kdKey kdKey
 Export key type. More...
 
typedef KdTreeNode kdNode
 Export node type. More...
 

Public Member Functions

 AdaptativeIndex (const te::gm::Envelope &mbr, const std::size_t &bucketSize=12)
 Constructor. More...
 
void build (std::vector< std::pair< kdKey, kdDataItem > > &dataSet)
 It inserts the data set into the tree. More...
 
void clear ()
 It clears all tree nodes. More...
 
const std::size_t & getBucketSize () const
 It gets bucket size for leaf nodes. More...
 
const te::gm::EnvelopegetMBR () const
 It gets the minimum bounding box of all elements in the tree. More...
 
bool isEmpty () const
 It returns true if the tree is empty and false otherwise. More...
 
void nearestNeighborSearch (const kdKey &key, std::vector< kdDataItem > &report, std::vector< double > &sqrDists, const std::size_t &k) const
 It searches the nearest data in nodes: you must pass an array of kdDataItem of size "k" with coordinates values (X() and Y()) adjusted to td::numeric_limits<double>::max() (this dummy values will be replaced at processing time), and if not all neighbors are found so sqrDists will contains td::numeric_limits<double>::max() in array index. More...
 
void search (const te::gm::Envelope &e, std::vector< KdTreeNode * > &report) const
 Range search query. More...
 
void search (const te::gm::Envelope &e, std::vector< kdDataItem > &report) const
 Range search query: the refinement is already done. More...
 
void setBucketSize (const std::size_t &size)
 It sets bucket size for leaf nodes. More...
 
void setMBR (const te::gm::Envelope &mbr)
 It sets the minimum bounding box of all elements in the tree. More...
 
const std::size_t & size () const
 It returns the number of tree nodes. More...
 
 ~AdaptativeIndex ()
 Destructor. More...
 

Private Member Functions

 AdaptativeIndex (const AdaptativeIndex &rhs)
 No copy constructor allowed. More...
 
double average (std::vector< std::pair< kdKey, kdDataItem > > &dataSet, const char &discriminator) const
 It returns the average value along the axis. More...
 
KdTreeNode * build (std::vector< std::pair< kdKey, kdDataItem > > &dataSet, double averageValue, const te::gm::Envelope &mbr)
 It builds the tree recursivily. More...
 
void erase (KdTreeNode *node)
 It Erases a node from the tree and all nodes below it. More...
 
void nearestNeighborSearch (KdTreeNode *node, const kdKey &key, std::vector< kdDataItem > &report, std::vector< double > &sqrDists, te::gm::Envelope &e) const
 Recursive nearest neighbor search. More...
 
AdaptativeIndexoperator= (const AdaptativeIndex &rhs)
 No assignment operator allowed. More...
 
void search (const te::gm::Envelope &e, KdTreeNode *node, std::vector< KdTreeNode * > &report) const
 Recursive range query. More...
 
void update (KdTreeNode *node, const kdKey &key, std::vector< kdDataItem > &report, std::vector< double > &sqrDists, te::gm::Envelope &e) const
 It updates the neighbor list. More...
 

Private Attributes

std::size_t m_bucketSize
 Bucket size (maximum number of elements in each node). More...
 
te::gm::Envelope m_mbr
 Minimum bounding box of all nodes. More...
 
KdTreeNode * m_root
 Pointer to the root node. More...
 
std::size_t m_size
 The size of the K-d Tree (number of nodes). More...
 

Detailed Description

template<class KdTreeNode>
class te::sam::kdtree::AdaptativeIndex< KdTreeNode >

A class that represents a two dimensional K-d Tree (2-d Tree) that store data-elements into the leafs.

Note
This type of tree stores the data only in the leaf nodes.
The process of construction expect that the tree is almost balanced.
This type of tree may be of special interest of NEAREST NEIGHBOR SEARCH QUERIES.
After a extent search it will be necessary to do a refinement.

Definition at line 352 of file Index.h.

Member Typedef Documentation

template<class KdTreeNode >
typedef KdTreeNode::kdData te::sam::kdtree::AdaptativeIndex< KdTreeNode >::kdData

Export data type.

Definition at line 360 of file Index.h.

template<class KdTreeNode >
typedef KdTreeNode::kdDataItem te::sam::kdtree::AdaptativeIndex< KdTreeNode >::kdDataItem

Export data item type.

Definition at line 363 of file Index.h.

template<class KdTreeNode >
typedef KdTreeNode::kdKey te::sam::kdtree::AdaptativeIndex< KdTreeNode >::kdKey

Export key type.

Definition at line 357 of file Index.h.

template<class KdTreeNode >
typedef KdTreeNode te::sam::kdtree::AdaptativeIndex< KdTreeNode >::kdNode

Export node type.

Definition at line 366 of file Index.h.

Constructor & Destructor Documentation

template<class KdTreeNode >
te::sam::kdtree::AdaptativeIndex< KdTreeNode >::AdaptativeIndex ( const te::gm::Envelope mbr,
const std::size_t &  bucketSize = 12 
)
inline

Constructor.

Definition at line 369 of file Index.h.

template<class KdTreeNode >
te::sam::kdtree::AdaptativeIndex< KdTreeNode >::~AdaptativeIndex ( )
inline

Destructor.

Definition at line 378 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::clear().

template<class KdTreeNode >
te::sam::kdtree::AdaptativeIndex< KdTreeNode >::AdaptativeIndex ( const AdaptativeIndex< KdTreeNode > &  rhs)
private

No copy constructor allowed.

Parameters
rhsThe other index.

Member Function Documentation

template<class KdTreeNode >
double te::sam::kdtree::AdaptativeIndex< KdTreeNode >::average ( std::vector< std::pair< kdKey, kdDataItem > > &  dataSet,
const char &  discriminator 
) const
inlineprivate

It returns the average value along the axis.

Definition at line 494 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::size().

template<class KdTreeNode >
void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::build ( std::vector< std::pair< kdKey, kdDataItem > > &  dataSet)
inline

It inserts the data set into the tree.

Definition at line 431 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_mbr, and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_root.

template<class KdTreeNode >
KdTreeNode * te::sam::kdtree::AdaptativeIndex< KdTreeNode >::build ( std::vector< std::pair< kdKey, kdDataItem > > &  dataSet,
double  averageValue,
const te::gm::Envelope mbr 
)
inlineprivate

It builds the tree recursivily.

Definition at line 562 of file Index.h.

References te::gm::Envelope::m_llx, te::gm::Envelope::m_lly, te::gm::Envelope::m_urx, and te::gm::Envelope::m_ury.

template<class KdTreeNode >
void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::erase ( KdTreeNode *  node)
inlineprivate

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

Definition at line 470 of file Index.h.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::clear().

template<class KdTreeNode >
const std::size_t& te::sam::kdtree::AdaptativeIndex< KdTreeNode >::getBucketSize ( ) const
inline

It gets bucket size for leaf nodes.

Definition at line 425 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_bucketSize.

template<class KdTreeNode >
const te::gm::Envelope& te::sam::kdtree::AdaptativeIndex< KdTreeNode >::getMBR ( ) const
inline

It gets the minimum bounding box of all elements in the tree.

Definition at line 413 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_mbr.

template<class KdTreeNode >
bool te::sam::kdtree::AdaptativeIndex< KdTreeNode >::isEmpty ( ) const
inline

It returns true if the tree is empty and false otherwise.

Definition at line 401 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_root.

template<class KdTreeNode >
void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::nearestNeighborSearch ( const kdKey key,
std::vector< kdDataItem > &  report,
std::vector< double > &  sqrDists,
const std::size_t &  k 
) const
inline

It searches the nearest data in nodes: you must pass an array of kdDataItem of size "k" with coordinates values (X() and Y()) adjusted to td::numeric_limits<double>::max() (this dummy values will be replaced at processing time), and if not all neighbors are found so sqrDists will contains td::numeric_limits<double>::max() in array index.

Definition at line 441 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_root.

template<class KdTreeNode >
void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::nearestNeighborSearch ( KdTreeNode *  node,
const kdKey key,
std::vector< kdDataItem > &  report,
std::vector< double > &  sqrDists,
te::gm::Envelope e 
) const
inlineprivate

Recursive nearest neighbor search.

Definition at line 663 of file Index.h.

References te::gm::Envelope::m_llx, te::gm::Envelope::m_lly, te::gm::Envelope::m_urx, and te::gm::Envelope::m_ury.

template<class KdTreeNode >
AdaptativeIndex& te::sam::kdtree::AdaptativeIndex< KdTreeNode >::operator= ( const AdaptativeIndex< KdTreeNode > &  rhs)
private

No assignment operator allowed.

Parameters
rhsThe other index.
Returns
A reference for this.
template<class KdTreeNode >
void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::search ( const te::gm::Envelope e,
std::vector< KdTreeNode * > &  report 
) const
inline

Range search query.

Definition at line 458 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_root.

template<class KdTreeNode >
void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::search ( const te::gm::Envelope e,
std::vector< kdDataItem > &  report 
) const
inline

Range search query: the refinement is already done.

Definition at line 541 of file Index.h.

References te::gm::Intersects().

template<class KdTreeNode >
void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::search ( const te::gm::Envelope e,
KdTreeNode *  node,
std::vector< KdTreeNode * > &  report 
) const
inlineprivate

Recursive range query.

Definition at line 706 of file Index.h.

References te::gm::Envelope::m_llx, te::gm::Envelope::m_lly, te::gm::Envelope::m_urx, and te::gm::Envelope::m_ury.

template<class KdTreeNode >
void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::setBucketSize ( const std::size_t &  size)
inline

It sets bucket size for leaf nodes.

Definition at line 419 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_bucketSize, and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::size().

template<class KdTreeNode >
void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::setMBR ( const te::gm::Envelope mbr)
inline

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

Definition at line 407 of file Index.h.

References te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_mbr.

template<class KdTreeNode >
const std::size_t& te::sam::kdtree::AdaptativeIndex< KdTreeNode >::size ( ) const
inline
template<class KdTreeNode >
void te::sam::kdtree::AdaptativeIndex< KdTreeNode >::update ( KdTreeNode *  node,
const kdKey key,
std::vector< kdDataItem > &  report,
std::vector< double > &  sqrDists,
te::gm::Envelope e 
) const
inlineprivate

It updates the neighbor list.

Definition at line 733 of file Index.h.

References te::gm::Envelope::m_llx, te::gm::Envelope::m_lly, te::gm::Envelope::m_urx, and te::gm::Envelope::m_ury.

Member Data Documentation

template<class KdTreeNode >
std::size_t te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_bucketSize
private

Bucket size (maximum number of elements in each node).

Definition at line 537 of file Index.h.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::getBucketSize(), and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::setBucketSize().

template<class KdTreeNode >
std::size_t te::sam::kdtree::AdaptativeIndex< KdTreeNode >::m_size
private

The size of the K-d Tree (number of nodes).

Definition at line 536 of file Index.h.

Referenced by te::sam::kdtree::AdaptativeIndex< KdTreeNode >::clear(), and te::sam::kdtree::AdaptativeIndex< KdTreeNode >::size().


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