26 #ifndef __TERRALIB_SAM_KDTREE_INTERNAL_INDEX_H
27 #define __TERRALIB_SAM_KDTREE_INTERNAL_INDEX_H
30 #include "../../geometry/Envelope.h"
31 #include "../../geometry/Utils.h"
68 template<
class KdTreeNode>
class Index
73 typedef typename KdTreeNode::kdKey
kdKey;
76 typedef typename KdTreeNode::kdData
kdData;
110 const std::size_t&
size()
const
134 inline void insert(
const kdKey& key,
const kdDataItem& item);
139 const std::size_t last = dataSet.size() - 1;
156 erase(node->getLeft());
159 erase(node->getRight());
178 inline void search(
const te::gm::Envelope& e, KdTreeNode* node,
const char& level, std::vector<KdTreeNode*>& report)
const;
181 KdTreeNode*
buildOptimized(std::vector<std::pair<kdKey, kdDataItem> >& dataSet,
const std::size_t& first,
const std::size_t& last)
183 const std::size_t kth = (last - first + 1) / 2;
185 KdTreeNode* newNode =
new KdTreeNode(dataSet[first + kth].first);
187 newNode->setData(dataSet[first + kth].second);
191 if(first + kth > first)
192 newNode->setLeft(
buildOptimized(dataSet, first, first + kth - 1));
194 if(first + kth < last)
195 newNode->setRight(
buildOptimized(dataSet, first + kth + 1, last));
223 template<
class KdTreeNode>
228 m_root =
new KdTreeNode(key);
237 KdTreeNode* x = m_root;
246 if(key.getX() > x->getKey().getX())
251 else if(key.getX() < x->getKey().getX())
256 else if(key.getY() == x->getKey().getY())
271 if(key.getY() > x->getKey().getY())
276 else if(key.getY() < x->getKey().getY())
281 else if(key.getX() == x->getKey().getX())
296 KdTreeNode* newNode =
new KdTreeNode(key);
303 y->setRight(newNode);
309 template<
class KdTreeNode>
312 if((node->getKey().getX() >= e.
m_llx) && (node->getKey().getX() <= e.
m_urx) &&
313 (node->getKey().getY() >= e.
m_lly) && (node->getKey().getY() <= e.
m_ury))
315 report.push_back(node);
321 if(node->getKey().getX() >= e.
m_llx)
322 search(e, node->getLeft(),
'y', report);
325 if(node->getKey().getX() <= e.
m_urx)
326 search(e, node->getRight(),
'y', report);
331 if(node->getKey().getY() >= e.
m_lly)
332 search(e, node->getLeft(),
'x', report);
335 if(node->getKey().getY() <= e.
m_ury)
336 search(e, node->getRight(),
'x', report);
358 typedef typename KdTreeNode::kdKey
kdKey;
361 typedef typename KdTreeNode::kdData
kdData;
396 const std::size_t&
size()
const
432 void build(std::vector<std::pair<kdKey, kdDataItem> >& dataSet)
442 void nearestNeighborSearch(
const kdKey& key, std::vector<kdDataItem>& report, std::vector<double>& sqrDists,
const std::size_t& k)
const
448 for(std::size_t i = 0; i < k; ++i)
449 sqrDists.push_back(std::numeric_limits<double>::max());
451 te::gm::Envelope e(-std::numeric_limits<double>::max(), -std::numeric_limits<double>::max(),
452 +std::numeric_limits<double>::max(), +std::numeric_limits<double>::max());
474 erase(node->getLeft());
477 erase(node->getRight());
483 inline KdTreeNode*
build(std::vector<std::pair<kdKey, kdDataItem> >& dataSet,
double averageValue,
const te::gm::Envelope& mbr);
492 inline void update(KdTreeNode* node,
const kdKey& key, std::vector<kdDataItem>& report, std::vector<double>& sqrDists,
te::gm::Envelope& e)
const;
495 double average(std::vector<std::pair<kdKey, kdDataItem> >& dataSet,
const char& discriminator)
const
497 const std::size_t
size = dataSet.size();
499 double medianValue = 0.0;
501 if(discriminator ==
'x')
503 for(
unsigned int i = 0; i <
size; ++i)
504 medianValue += dataSet[i].first.getX();
506 return medianValue /
size;
510 for(
unsigned int i = 0; i <
size; ++i)
511 medianValue += dataSet[i].first.getY();
513 return medianValue /
size;
541 template<
class KdTreeNode>
544 std::vector<KdTreeNode*> reportNodes;
546 search(e, reportNodes);
548 std::size_t nNodes = reportNodes.size();
550 for(std::size_t i = 0; i < nNodes; ++i)
552 std::size_t nElements = reportNodes[i]->getData().size();
554 for(std::size_t j = 0; j < nElements; ++j)
557 report.push_back((reportNodes[i])->getData()[j]);
562 template<
class KdTreeNode>
567 if(dataSet.size() <= m_bucketSize)
569 KdTreeNode* node =
new KdTreeNode(averageValue);
571 node->setDiscriminator(
'l');
573 std::size_t size = dataSet.size();
575 for(std::size_t i = 0; i < size; ++i)
576 node->getData().push_back(dataSet[i].second);
584 char discriminator =
'x';
586 std::vector<std::pair<kdKey, kdDataItem> > leftDataSet;
587 std::vector<std::pair<kdKey, kdDataItem> > rightDataSet;
593 averageValue = average(dataSet,
'x');
596 newMbr1.
m_urx = averageValue;
597 newMbr2.
m_llx = averageValue;
599 std::size_t size = dataSet.size();
601 for(std::size_t i = 0; i < size; ++ i)
603 if(dataSet[i].first.getX() <= averageValue)
604 leftDataSet.push_back(dataSet[i]);
606 rightDataSet.push_back(dataSet[i]);
614 averageValue = average(dataSet,
'y');
617 newMbr1.
m_ury = averageValue;
618 newMbr2.
m_lly = averageValue;
620 std::size_t size = dataSet.size();
622 for(std::size_t i = 0; i < size; ++ i)
624 if(dataSet[i].first.getY() <= averageValue)
625 leftDataSet.push_back(dataSet[i]);
627 rightDataSet.push_back(dataSet[i]);
633 KdTreeNode* node =
new KdTreeNode(averageValue);
635 if(rightDataSet.size() == 0)
637 node->setDiscriminator(
'l');
639 std::size_t size = leftDataSet.size();
641 for(std::size_t i = 0; i < size; ++i)
642 node->getData().push_back(leftDataSet[i].second);
644 else if(leftDataSet.size() == 0)
646 node->setDiscriminator(
'l');
648 std::size_t size = rightDataSet.size();
650 for(std::size_t i = 0; i < size; ++i)
651 node->getData().push_back(rightDataSet[i].second);
655 node->setDiscriminator(discriminator);
656 node->setLeft(build(leftDataSet, averageValue, newMbr1));
657 node->setRight(build(rightDataSet, averageValue, newMbr2));
663 template<
class KdTreeNode>
666 if(node->getDiscriminator() ==
'l')
668 update(node, key, report, sqrDists, e);
670 else if(node->getDiscriminator() ==
'x')
672 if(key.getX() <= node->getKey())
674 nearestNeighborSearch(node->getLeft(), key, report, sqrDists, e);
676 if((e.
m_llx < node->getKey()) && (node->getKey() < e.
m_urx))
677 nearestNeighborSearch(node->getRight(), key, report, sqrDists, e);
681 nearestNeighborSearch(node->getRight(), key, report, sqrDists, e);
683 if((e.
m_llx < node->getKey()) &&(node->getKey() < e.
m_urx))
684 nearestNeighborSearch(node->getLeft(), key, report, sqrDists, e);
687 else if(node->getDiscriminator() ==
'y')
689 if(key.getY() <= node->getKey())
691 nearestNeighborSearch(node->getLeft(), key, report, sqrDists, e);
693 if((e.
m_lly < node->getKey()) &&(node->getKey() < e.
m_ury))
694 nearestNeighborSearch(node->getRight(), key, report, sqrDists, e);
698 nearestNeighborSearch(node->getRight(), key, report, sqrDists, e);
700 if((e.
m_lly < node->getKey()) &&(node->getKey() < e.
m_ury))
701 nearestNeighborSearch(node->getLeft(), key, report, sqrDists, e);
706 template<
class KdTreeNode>
709 if(node->getDiscriminator() ==
'x')
712 if(e.
m_llx <= node->getKey())
713 search(e, node->getLeft(), report);
716 if(e.
m_urx >= node->getKey())
717 search(e, node->getRight(), report);
719 else if(node->getDiscriminator() ==
'y')
722 if(e.
m_lly <= node->getKey())
723 search(e, node->getLeft(), report);
726 if(e.
m_ury >= node->getKey())
727 search(e, node->getRight(), report);
730 report.push_back(node);
733 template<
class KdTreeNode>
736 const std::size_t size = node->getData().size();
738 const std::size_t nNeighbors = report.size();
741 for(std::size_t i = 0; i < size; ++i)
743 double dx = (key.getX() - node->getData()[i].getX());
744 double dy = (key.getY() - node->getData()[i].getY());
746 double dkp = (dx * dx) + (dy * dy);
749 if(dkp < sqrDists[nNeighbors - 1])
753 for(std::size_t j = 0; j < nNeighbors; ++j)
755 if(dkp < sqrDists[j])
758 for(std::size_t k = nNeighbors - 1; k > j; --k)
760 report[k] = report[k - 1];
761 sqrDists[k] = sqrDists[k - 1];
765 report[j] = node->getData()[i];
775 double maxDist = sqrDists[nNeighbors - 1];
777 if(maxDist != std::numeric_limits<double>::max())
778 maxDist = sqrt(maxDist);
780 e.
m_llx = key.getX() - maxDist;
781 e.
m_lly = key.getY() - maxDist;
782 e.
m_urx = key.getX() + maxDist;
783 e.
m_ury = key.getY() + maxDist;
790 #endif // __TERRALIB_SAM_KDTREE_INTERNAL_INDEX_H
void insert(const kdKey &key, const kdDataItem &item)
It inserts the data with a given key in tree.
void clear()
It clears all tree nodes.
void setMBR(const te::gm::Envelope &mbr)
It sets the minimum bounding box of all elements in the tree.
const te::gm::Envelope & getMBR() const
It gets the minimum bounding box of all elements in the tree.
KdTreeNode::kdDataTag kdDataTag
Export data type.
A class that represents an Kd-tree node.
std::size_t m_bucketSize
Bucket size (maximum number of elements in each node).
void search(const te::gm::Envelope &e, std::vector< KdTreeNode * > &report) const
Range search query.
void erase(KdTreeNode *node)
It Erases a node from the tree and all nodes below it.
KdTreeNode::kdKey kdKey
Export key type.
A class that represents a two dimensional K-d Tree (2-d Tree) that store data-elements into the leafs...
te::gm::Envelope m_mbr
Minimum bounding box of all nodes.
double m_urx
Upper right corner x-coordinate.
KdTreeNode kdNode
Export node type.
KdTreeNode::kdData kdData
Export data type.
const std::size_t & size() const
It returns the number of tree nodes.
bool isEmpty() const
It returns true if the tree is empty and false otherwise.
double average(std::vector< std::pair< kdKey, kdDataItem > > &dataSet, const char &discriminator) const
It returns the average value along the axis.
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.
KdTreeNode * m_root
Pointer to the root node.
KdTreeNode::kdData kdData
Export data type.
std::size_t m_size
The size of the K-d Tree (number of nodes).
void setBucketSize(const std::size_t &size)
It sets bucket size for leaf nodes.
double m_llx
Lower left corner x-coordinate.
An Envelope defines a 2D rectangular region.
const std::size_t & size() const
It returns the number of tree nodes.
void build(std::vector< std::pair< kdKey, kdDataItem > > &dataSet)
It inserts the data set into the tree.
void buildOptimized(std::vector< std::pair< kdKey, kdDataItem > > &dataSet)
It inserts the data in the tree and and keeps it balanced: the kdsort algorithm must be called before...
const te::gm::Envelope & getMBR() const
It gets the minimum bounding box of all elements in the tree.
AdaptativeIndex(const te::gm::Envelope &mbr, const std::size_t &bucketSize=12)
Constructor.
te::gm::Envelope m_mbr
Minimum bounding box of all nodes.
const std::size_t & getBucketSize() const
It gets bucket size for leaf nodes.
A class that represents a two dimensional K-d Tree (2-d Tree).
bool Intersects(const T1 &o1, const T2 &o2)
double m_lly
Lower left corner y-coordinate.
KdTreeNode::kdDataItem kdDataItem
Export data item type.
KdTreeNode * m_root
Pointer to the root node.
void insertData(KdTreeNode *&node, const kdDataItem &data, const kd_node_m_datasingle_tag &)
It inserts data for single nodes, i.e. nodes that stores only one element.
Kd-tree node type for nodes with single elements (used by template instantiation).
AdaptativeIndex & operator=(const AdaptativeIndex &rhs)
No assignment operator allowed.
double m_ury
Upper right corner y-coordinate.
void clear()
It clears all tree nodes.
KdTreeNode::kdDataItem kdDataItem
Export data item type.
std::size_t m_size
The size of the K-d Tree (number of nodes).
void setMBR(const te::gm::Envelope &mbr)
It sets the minimum bounding box of all elements in the tree.
Index(const te::gm::Envelope &mbr)
Constructor.
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 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 coordina...
Index & operator=(const Index &rhs)
No assignment operator allowed.
~AdaptativeIndex()
Destructor.
KdTreeNode * buildOptimized(std::vector< std::pair< kdKey, kdDataItem > > &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.
KdTreeNode::kdKey kdKey
Export key type.