Index.h
Go to the documentation of this file.
1 /* Copyright (C) 2008 National Institute For Space Research (INPE) - Brazil.
2 
3  This file is part of the TerraLib - a Framework for building GIS enabled applications.
4 
5  TerraLib is free software: you can redistribute it and/or modify
6  it under the terms of the GNU Lesser General Public License as published by
7  the Free Software Foundation, either version 3 of the License,
8  or (at your option) any later version.
9 
10  TerraLib is distributed in the hope that it will be useful,
11  but WITHOUT ANY WARRANTY; without even the implied warranty of
12  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13  GNU Lesser General Public License for more details.
14 
15  You should have received a copy of the GNU Lesser General Public License
16  along with TerraLib. See COPYING. If not, write to
17  TerraLib Team at <terralib-team@terralib.org>.
18  */
19 
20 /*!
21  \file terralib/sam/kdtree/Index.h
22 
23  \brief A class that represents a two dimensional K-d Tree (2-d Tree).
24 */
25 
26 #ifndef __TERRALIB_SAM_KDTREE_INTERNAL_INDEX_H
27 #define __TERRALIB_SAM_KDTREE_INTERNAL_INDEX_H
28 
29 // TerraLib
30 #include "../../geometry/Envelope.h"
31 #include "../../geometry/Utils.h"
32 #include "Node.h"
33 
34 // STL
35 #include <limits>
36 #include <vector>
37 #include <utility>
38 
39 namespace te
40 {
41  namespace sam
42  {
43  namespace kdtree
44  {
45  /*!
46  \class Index
47 
48  \brief A class that represents a two dimensional K-d Tree (2-d Tree).
49 
50  \note This type of tree stores the data into nodes (not only in the leafs node).
51 
52  \note This tree may be built by two ways:
53  1) Inserting each element in the tree. In this case the tree can becomes unbalanced, but in practical
54  cases this is not the expected, and is the best way to construct the tree (faster way).
55  2) Passing a container with pairs (key/data-item) and using the method buildOptimized after
56  calling kdsort. The tree built this way is almost balanced but will be construct in time O(N log N).
57  Warning: In this case items with the same key will be stores in different nodes!
58 
59  \note This type of tree may be of special interest of EXTENT SEARCH QUERIES.
60 
61  \note If the node type is kd_node_data_single_tag than NodeData and NodeDataItem are the same types.
62  And if one entry with the same key already exist, so they will be overwrite.
63 
64  \note If the node type is kd_node_data_set_tag than NodeData mus have a method called push_back(NodeDataItem)
65  that permits to store elements with the same key in the node.
66  */
67  template<class KdTreeNode> class Index
68  {
69  public:
70 
71  //! Export key type.
72  typedef typename KdTreeNode::kdKey kdKey;
73 
74  //! Export data type.
75  typedef typename KdTreeNode::kdData kdData;
76 
77  //! Export data item type.
78  typedef typename KdTreeNode::kdDataItem kdDataItem;
79 
80  //! Export data type.
81  typedef typename KdTreeNode::kdDataTag kdDataTag;
82 
83  /*! \brief Constructor. */
84  Index(const te::gm::Envelope& mbr)
85  : m_root(0),
86  m_mbr(mbr),
87  m_size(0)
88  {
89  }
90 
91  /*! \brief Destructor. */
93  {
94  clear();
95  }
96 
97  /*! \brief It clears all tree nodes. */
98  void clear()
99  {
100  if(m_root)
101  {
102  erase(m_root);
103  m_root = 0;
104  m_size = 0;
105  }
106  }
107 
108  /*! \brief It returns the number of tree nodes. */
109  const std::size_t& size() const
110  {
111  return m_size;
112  }
113 
114  /*! \brief It returns true if the tree is empty and false otherwise. */
115  bool isEmpty() const
116  {
117  return m_root == 0;
118  }
119 
120  /*! \brief It sets the minimum bounding box of all elements in the tree. */
121  void setMBR(const te::gm::Envelope& mbr)
122  {
123  m_mbr = mbr;
124  }
125 
126  /*! \brief It gets the minimum bounding box of all elements in the tree. */
127  const te::gm::Envelope& getMBR() const
128  {
129  return m_mbr;
130  }
131 
132  /*! \brief It inserts the data with a given key in tree. */
133  inline void insert(const kdKey& key, const kdDataItem& item);
134 
135  /*! \brief It inserts the data in the tree and and keeps it balanced: the kdsort algorithm must be called before. */
136  void buildOptimized(std::vector<std::pair<kdKey, kdDataItem> >& dataSet)
137  {
138  const std::size_t last = dataSet.size() - 1;
139  m_root = buildOptimized(dataSet, 0, last);
140  }
141 
142  /*! \brief Range search query. */
143  void search(const te::gm::Envelope& e, std::vector<KdTreeNode*>& report) const
144  {
145  if(m_root)
146  search(e, m_root, 'x', report);
147  }
148 
149  private:
150 
151  /*! \brief It Erases a node from the tree and all nodes below it. */
152  void erase(KdTreeNode* node)
153  {
154  if(node->hasLeft())
155  erase(node->getLeft());
156 
157  if(node->hasRight())
158  erase(node->getRight());
159 
160  delete node;
161  }
162 
163  /*! \brief It inserts data for single nodes, i.e. nodes that stores only one element. */
164  void insertData(KdTreeNode*& node, const kdDataItem& data, const kd_node_m_datasingle_tag&)
165  {
166  node->setData(data);
167  }
168 
169  // Not build!
170  /*! \brief It inserts data for set nodes, i.e., nodes that may stores many element. */
171  /*void insertData(KdTreeNode*& node, const kdDataItem& data, const kd_node_data_set_tag&)
172  {
173  node->getData().push_back(data);
174  }*/
175 
176  /*! \brief Recursive range query. */
177  inline void search(const te::gm::Envelope& e, KdTreeNode* node, const char& level, std::vector<KdTreeNode*>& report) const;
178 
179  /*! \brief It builds the tree recursively. */
180  KdTreeNode* buildOptimized(std::vector<std::pair<kdKey, kdDataItem> >& dataSet, const std::size_t& first, const std::size_t& last)
181  {
182  const std::size_t kth = (last - first + 1) / 2;
183 
184  KdTreeNode* newNode = new KdTreeNode(dataSet[first + kth].first);
185 
186  newNode->setData(dataSet[first + kth].second);
187 
188  ++m_size;
189 
190  if(first + kth > first)
191  newNode->setLeft(buildOptimized(dataSet, first, first + kth - 1));
192 
193  if(first + kth < last)
194  newNode->setRight(buildOptimized(dataSet, first + kth + 1, last));
195 
196  return newNode;
197  }
198 
199  /*!
200  \brief No copy constructor allowed.
201 
202  \param rhs The other index.
203  */
204  Index(const Index& rhs);
205 
206  /*!
207  \brief No assignment operator allowed.
208 
209  \param rhs The other index.
210 
211  \return A reference for this.
212  */
213  Index& operator=(const Index& rhs);
214 
215  private:
216 
217  KdTreeNode* m_root; //!< Pointer to the root node.
218  te::gm::Envelope m_mbr; //!< Minimum bounding box of all nodes.
219  std::size_t m_size; //!< The size of the K-d Tree (number of nodes).
220  };
221 
222  template<class KdTreeNode>
223  void Index<KdTreeNode>::insert(const kdKey& key, const kdDataItem& item)
224  {
225  if(m_root == 0)
226  {
227  m_root = new KdTreeNode(key);
228  insertData(m_root, item, kdDataTag());
229  }
230  else
231  {
232  char level = 'x';
233 
234  bool left = false;
235 
236  KdTreeNode* x = m_root;
237  KdTreeNode* y = 0;
238 
239  while(x != 0)
240  {
241  y = x;
242 
243  if(level == 'x')
244  {
245  if(key.getX() > x->getKey().getX()) // if the key is greater than, inserts in the right subtree
246  {
247  x = x->getRight();
248  left = false;
249  }
250  else if(key.getX() < x->getKey().getX()) // if the key is smaller than, inserts in the left subtree
251  {
252  x = x->getLeft();
253  left = true;
254  }
255  else if(key.getY() == x->getKey().getY()) // if the key already exist, in the case of single node the data will be overwrite and in the case of set node they will push_back the item
256  {
257  insertData(x, item, kdDataTag());
258  return;
259  }
260  else // found the same axis partition, so go left
261  {
262  x = x->getLeft();
263  left = true;
264  }
265 
266  level = 'y';
267  }
268  else
269  {
270  if(key.getY() > x->getKey().getY())
271  {
272  x = x->getRight();
273  left = false;
274  }
275  else if(key.getY() < x->getKey().getY())
276  {
277  x = x->getLeft();
278  left = true;
279  }
280  else if(key.getX() == x->getKey().getX())
281  {
282  insertData(x, item, kdDataTag());
283  return;
284  }
285  else
286  {
287  x = x->getLeft();
288  left = true;
289  }
290 
291  level = 'x';
292  }
293  }
294 
295  KdTreeNode* newNode = new KdTreeNode(key);
296 
297  insertData(newNode, item, kdDataTag());
298 
299  if(left)
300  y->setLeft(newNode);
301  else
302  y->setRight(newNode);
303  }
304 
305  ++m_size;
306  }
307 
308  template<class KdTreeNode>
309  void Index<KdTreeNode>::search(const te::gm::Envelope& e, KdTreeNode* node, const char& level, std::vector<KdTreeNode*>& report) const
310  {
311  if((node->getKey().getX() >= e.m_llx) && (node->getKey().getX() <= e.m_urx) &&
312  (node->getKey().getY() >= e.m_lly) && (node->getKey().getY() <= e.m_ury))
313  {
314  report.push_back(node);
315  }
316 
317  if(level == 'x')
318  {
319  if(node->hasLeft())
320  if(node->getKey().getX() >= e.m_llx)
321  search(e, node->getLeft(), 'y', report);
322 
323  if(node->hasRight())
324  if(node->getKey().getX() <= e.m_urx)
325  search(e, node->getRight(), 'y', report);
326  }
327  else
328  {
329  if(node->hasLeft())
330  if(node->getKey().getY() >= e.m_lly)
331  search(e, node->getLeft(), 'x', report);
332 
333  if(node->hasRight())
334  if(node->getKey().getY() <= e.m_ury)
335  search(e, node->getRight(), 'x', report);
336  }
337  }
338 
339  /*!
340  \class AdaptativeIndex
341 
342  \brief A class that represents a two dimensional K-d Tree (2-d Tree) that store data-elements into the leafs.
343 
344  \note This type of tree stores the data only in the leaf nodes.
345 
346  \note The process of construction expect that the tree is almost balanced.
347 
348  \note This type of tree may be of special interest of NEAREST NEIGHBOR SEARCH QUERIES.
349 
350  \note After a extent search it will be necessary to do a refinement.
351  */
352  template<class KdTreeNode> class AdaptativeIndex
353  {
354  public:
355 
356  //! Export key type.
357  typedef typename KdTreeNode::kdKey kdKey;
358 
359  //! Export data type.
360  typedef typename KdTreeNode::kdData kdData;
361 
362  //! Export data item type.
363  typedef typename KdTreeNode::kdDataItem kdDataItem;
364 
365  //! Export node type.
366  typedef KdTreeNode kdNode;
367 
368  /*! \brief Constructor. */
369  AdaptativeIndex(const te::gm::Envelope& mbr, const std::size_t& bucketSize = 12)
370  : m_root(0),
371  m_mbr(mbr),
372  m_size(0),
373  m_bucketSize(bucketSize)
374  {
375  }
376 
377  /*! \brief Destructor. */
379  {
380  clear();
381  }
382 
383  /*! \brief It clears all tree nodes. */
384  void clear()
385  {
386  if(m_root)
387  {
388  erase(m_root);
389  m_root = 0;
390  m_size = 0;
391  }
392  }
393 
394  /*! \brief It returns the number of tree nodes. */
395  const std::size_t& size() const
396  {
397  return m_size;
398  }
399 
400  /*! \brief It returns true if the tree is empty and false otherwise. */
401  bool isEmpty() const
402  {
403  return m_root == 0;
404  }
405 
406  /*! \brief It sets the minimum bounding box of all elements in the tree. */
407  void setMBR(const te::gm::Envelope& mbr)
408  {
409  m_mbr = mbr;
410  }
411 
412  /*! \brief It gets the minimum bounding box of all elements in the tree. */
413  const te::gm::Envelope& getMBR() const
414  {
415  return m_mbr;
416  }
417 
418  /*! \brief It sets bucket size for leaf nodes. */
419  void setBucketSize(const std::size_t& size)
420  {
421  m_bucketSize = size;
422  }
423 
424  /*! \brief It gets bucket size for leaf nodes. */
425  const std::size_t& getBucketSize() const
426  {
427  return m_bucketSize;
428  }
429 
430  /*! \brief It inserts the data set into the tree. */
431  void build(std::vector<std::pair<kdKey, kdDataItem> >& dataSet)
432  {
433  m_root = build(dataSet, 0.0, m_mbr);
434  }
435 
436  /*!
437  \brief It searches the nearest data in nodes: you must pass an array of kdDataItem of size "k"
438  with coordinates values (X() and Y()) adjusted to td::numeric_limits<double>::max() (this dummy values will be replaced at processing time),
439  and if not all neighbors are found so sqrDists will contains td::numeric_limits<double>::max() in array index.
440  */
441  void nearestNeighborSearch(const kdKey& key, std::vector<kdDataItem>& report, std::vector<double>& sqrDists, const std::size_t& k) const
442  {
443  if(m_root)
444  {
445  sqrDists.clear();
446 
447  for(std::size_t i = 0; i < k; ++i)
448  sqrDists.push_back(std::numeric_limits<double>::max());
449 
450  te::gm::Envelope e(-std::numeric_limits<double>::max(), -std::numeric_limits<double>::max(),
451  +std::numeric_limits<double>::max(), +std::numeric_limits<double>::max());
452 
453  nearestNeighborSearch(m_root, key, report, sqrDists, e);
454  }
455  }
456 
457  /*! \brief Range search query. */
458  void search(const te::gm::Envelope& e, std::vector<KdTreeNode*>& report) const
459  {
460  if(m_root)
461  search(e, m_root, report);
462  }
463 
464  /*! \brief Range search query: the refinement is already done. */
465  inline void search(const te::gm::Envelope& e, std::vector<kdDataItem>& report) const;
466 
467  private:
468 
469  /*! \brief It Erases a node from the tree and all nodes below it. */
470  void erase(KdTreeNode* node)
471  {
472  if(node->hasLeft())
473  erase(node->getLeft());
474 
475  if(node->hasRight())
476  erase(node->getRight());
477 
478  delete node;
479  }
480 
481  /*! \brief It builds the tree recursivily. */
482  inline KdTreeNode* build(std::vector<std::pair<kdKey, kdDataItem> >& dataSet, double averageValue, const te::gm::Envelope& mbr);
483 
484  /*! \brief Recursive nearest neighbor search. */
485  inline void nearestNeighborSearch(KdTreeNode* node, const kdKey& key, std::vector<kdDataItem>& report, std::vector<double>& sqrDists, te::gm::Envelope& e) const;
486 
487  /*! \brief Recursive range query. */
488  inline void search(const te::gm::Envelope& e, KdTreeNode* node, std::vector<KdTreeNode*>& report) const;
489 
490  /*! \brief It updates the neighbor list. */
491  inline void update(KdTreeNode* node, const kdKey& key, std::vector<kdDataItem>& report, std::vector<double>& sqrDists, te::gm::Envelope& e) const;
492 
493  /*! \brief It returns the average value along the axis. */
494  double average(std::vector<std::pair<kdKey, kdDataItem> >& dataSet, const char& discriminator) const
495  {
496  const std::size_t size = dataSet.size();
497 
498  double medianValue = 0.0;
499 
500  if(discriminator == 'x')
501  {
502  for(unsigned int i = 0; i < size; ++i)
503  medianValue += dataSet[i].first.getX();
504 
505  return medianValue / size;
506  }
507  else
508  {
509  for(unsigned int i = 0; i < size; ++i)
510  medianValue += dataSet[i].first.getY();
511 
512  return medianValue / size;
513  }
514  }
515 
516  /*!
517  \brief No copy constructor allowed.
518 
519  \param rhs The other index.
520  */
521  AdaptativeIndex(const AdaptativeIndex& rhs);
522 
523  /*!
524  \brief No assignment operator allowed.
525 
526  \param rhs The other index.
527 
528  \return A reference for this.
529  */
531 
532  private:
533 
534  KdTreeNode* m_root; //!< Pointer to the root node.
535  te::gm::Envelope m_mbr; //!< Minimum bounding box of all nodes.
536  std::size_t m_size; //!< The size of the K-d Tree (number of nodes).
537  std::size_t m_bucketSize; //!< Bucket size (maximum number of elements in each node).
538  };
539 
540  template<class KdTreeNode>
541  void AdaptativeIndex<KdTreeNode>::search(const te::gm::Envelope& e, std::vector<kdDataItem>& report) const
542  {
543  std::vector<KdTreeNode*> reportNodes;
544 
545  search(e, reportNodes);
546 
547  std::size_t nNodes = reportNodes.size();
548 
549  for(std::size_t i = 0; i < nNodes; ++i)
550  {
551  std::size_t nElements = reportNodes[i]->getData().size();
552 
553  for(std::size_t j = 0; j < nElements; ++j)
554  {
555  if(te::gm::Intersects((reportNodes[i])->getData()[j], e))
556  report.push_back((reportNodes[i])->getData()[j]);
557  }
558  }
559  }
560 
561  template<class KdTreeNode>
562  KdTreeNode* AdaptativeIndex<KdTreeNode>::build(std::vector<std::pair<kdKey, kdDataItem> >& dataSet, double averageValue, const te::gm::Envelope& mbr)
563  {
564  ++m_size;
565 
566  if(dataSet.size() <= m_bucketSize)
567  {
568  KdTreeNode* node = new KdTreeNode(averageValue);
569 
570  node->setDiscriminator('l');
571 
572  std::size_t size = dataSet.size();
573 
574  for(std::size_t i = 0; i < size; ++i)
575  node->getData().push_back(dataSet[i].second);
576 
577  return node;
578  }
579 
580  te::gm::Envelope newMbr1(mbr);
581  te::gm::Envelope newMbr2(mbr);
582 
583  char discriminator = 'x';
584 
585  std::vector<std::pair<kdKey, kdDataItem> > leftDataSet;
586  std::vector<std::pair<kdKey, kdDataItem> > rightDataSet;
587 
588  // Finds the largest dimension
589  if((mbr.m_urx - mbr.m_llx) > (mbr.m_ury - mbr.m_lly))
590  {
591  // Finds the median along "x" axis
592  averageValue = average(dataSet, 'x');
593 
594  // Adjust box for left and right branchs
595  newMbr1.m_urx = averageValue;
596  newMbr2.m_llx = averageValue;
597 
598  std::size_t size = dataSet.size();
599 
600  for(std::size_t i = 0; i < size; ++ i)
601  {
602  if(dataSet[i].first.getX() <= averageValue)
603  leftDataSet.push_back(dataSet[i]);
604  else
605  rightDataSet.push_back(dataSet[i]);
606  }
607  }
608  else
609  {
610  discriminator = 'y';
611 
612  // Finds the median along "y" axis
613  averageValue = average(dataSet, 'y');
614 
615  // Adjust box for left and right branchs
616  newMbr1.m_ury = averageValue;
617  newMbr2.m_lly = averageValue;
618 
619  std::size_t size = dataSet.size();
620 
621  for(std::size_t i = 0; i < size; ++ i)
622  {
623  if(dataSet[i].first.getY() <= averageValue)
624  leftDataSet.push_back(dataSet[i]);
625  else
626  rightDataSet.push_back(dataSet[i]);
627  }
628  }
629 
630  dataSet.clear();
631 
632  KdTreeNode* node = new KdTreeNode(averageValue);
633 
634  if(rightDataSet.size() == 0) // If all coordinates have the same coordinate values, the right vector will be empty so we need stop division to
635  {
636  node->setDiscriminator('l');
637 
638  std::size_t size = leftDataSet.size();
639 
640  for(std::size_t i = 0; i < size; ++i)
641  node->getData().push_back(leftDataSet[i].second);
642  }
643  else if(leftDataSet.size() == 0) // If all coordinates have the same coordinate values, the left vector is empty, so we need to stop
644  {
645  node->setDiscriminator('l');
646 
647  std::size_t size = rightDataSet.size();
648 
649  for(std::size_t i = 0; i < size; ++i)
650  node->getData().push_back(rightDataSet[i].second);
651  }
652  else
653  {
654  node->setDiscriminator(discriminator);
655  node->setLeft(build(leftDataSet, averageValue, newMbr1));
656  node->setRight(build(rightDataSet, averageValue, newMbr2));
657  }
658 
659  return node;
660  }
661 
662  template<class KdTreeNode>
663  void AdaptativeIndex<KdTreeNode>::nearestNeighborSearch(KdTreeNode* node, const kdKey& key, std::vector<kdDataItem>& report, std::vector<double>& sqrDists, te::gm::Envelope& e) const
664  {
665  if(node->getDiscriminator() == 'l')
666  {
667  update(node, key, report, sqrDists, e); // this is a leaf node -> update list of neighbours
668  }
669  else if(node->getDiscriminator() == 'x')
670  {
671  if(key.getX() <= node->getKey())
672  {
673  nearestNeighborSearch(node->getLeft(), key, report, sqrDists, e);
674 
675  if((e.m_llx < node->getKey()) && (node->getKey() < e.m_urx))
676  nearestNeighborSearch(node->getRight(), key, report, sqrDists, e);
677  }
678  else
679  {
680  nearestNeighborSearch(node->getRight(), key, report, sqrDists, e);
681 
682  if((e.m_llx < node->getKey()) &&(node->getKey() < e.m_urx))
683  nearestNeighborSearch(node->getLeft(), key, report, sqrDists, e);
684  }
685  }
686  else if(node->getDiscriminator() == 'y')
687  {
688  if(key.getY() <= node->getKey())
689  {
690  nearestNeighborSearch(node->getLeft(), key, report, sqrDists, e);
691 
692  if((e.m_lly < node->getKey()) &&(node->getKey() < e.m_ury))
693  nearestNeighborSearch(node->getRight(), key, report, sqrDists, e);
694  }
695  else
696  {
697  nearestNeighborSearch(node->getRight(), key, report, sqrDists, e);
698 
699  if((e.m_lly < node->getKey()) &&(node->getKey() < e.m_ury))
700  nearestNeighborSearch(node->getLeft(), key, report, sqrDists, e);
701  }
702  }
703  }
704 
705  template<class KdTreeNode>
706  void AdaptativeIndex<KdTreeNode>::search(const te::gm::Envelope& e, KdTreeNode* node, std::vector<KdTreeNode*>& report) const
707  {
708  if(node->getDiscriminator() == 'x')
709  {
710  if(node->hasLeft())
711  if(e.m_llx <= node->getKey())
712  search(e, node->getLeft(), report);
713 
714  if(node->hasRight())
715  if(e.m_urx >= node->getKey())
716  search(e, node->getRight(), report);
717  }
718  else if(node->getDiscriminator() == 'y')
719  {
720  if(node->hasLeft())
721  if(e.m_lly <= node->getKey())
722  search(e, node->getLeft(), report);
723 
724  if(node->hasRight())
725  if(e.m_ury >= node->getKey())
726  search(e, node->getRight(), report);
727  }
728  else
729  report.push_back(node);
730  }
731 
732  template<class KdTreeNode>
733  void AdaptativeIndex<KdTreeNode>::update(KdTreeNode* node, const kdKey& key, std::vector<kdDataItem>& report, std::vector<double>& sqrDists, te::gm::Envelope& e) const
734  {
735  const std::size_t size = node->getData().size();
736 
737  const std::size_t nNeighbors = report.size();
738 
739 // for each element in the node, we need to search for distances less than of some one of sqrDists
740  for(std::size_t i = 0; i < size; ++i)
741  {
742  double dx = (key.getX() - node->getData()[i].getX());
743  double dy = (key.getY() - node->getData()[i].getY());
744 
745  double dkp = (dx * dx) + (dy * dy); // square distance from the key point to the node
746 
747 // if the distance of "i-th" element is less than the maximum distance in the sqrDists
748  if(dkp < sqrDists[nNeighbors - 1])
749  {
750 // so the element must be reported
751 // and the srqDists vector must be rearranged
752  for(std::size_t j = 0; j < nNeighbors; ++j)
753  {
754  if(dkp < sqrDists[j]) // if the position is found
755  {
756 // move the elements to the right
757  for(std::size_t k = nNeighbors - 1; k > j; --k)
758  {
759  report[k] = report[k - 1];
760  sqrDists[k] = sqrDists[k - 1];
761  }
762 
763 // inserts the element in the report and update its distance
764  report[j] = node->getData()[i];
765 
766  sqrDists[j] = dkp;
767 
768  break;
769  }
770  }
771  }
772  }
773 
774  double maxDist = sqrDists[nNeighbors - 1];
775 
776  if(maxDist != std::numeric_limits<double>::max())
777  maxDist = sqrt(maxDist);
778 
779  e.m_llx = key.getX() - maxDist;
780  e.m_lly = key.getY() - maxDist;
781  e.m_urx = key.getX() + maxDist;
782  e.m_ury = key.getY() + maxDist;
783  }
784 
785  } // end namespace kdtree
786  } // end namespace sam
787 } // end namespace te
788 
789 #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.
Definition: Index.h:223
void clear()
It clears all tree nodes.
Definition: Index.h:384
void setMBR(const te::gm::Envelope &mbr)
It sets the minimum bounding box of all elements in the tree.
Definition: Index.h:407
const te::gm::Envelope & getMBR() const
It gets the minimum bounding box of all elements in the tree.
Definition: Index.h:413
KdTreeNode::kdDataTag kdDataTag
Export data type.
Definition: Index.h:81
A class that represents an Kd-tree node.
std::size_t m_bucketSize
Bucket size (maximum number of elements in each node).
Definition: Index.h:537
void search(const te::gm::Envelope &e, std::vector< KdTreeNode * > &report) const
Range search query.
Definition: Index.h:458
void erase(KdTreeNode *node)
It Erases a node from the tree and all nodes below it.
Definition: Index.h:152
KdTreeNode::kdKey kdKey
Export key type.
Definition: Index.h:357
A class that represents a two dimensional K-d Tree (2-d Tree) that store data-elements into the leafs...
Definition: Index.h:352
te::gm::Envelope m_mbr
Minimum bounding box of all nodes.
Definition: Index.h:218
double m_urx
Upper right corner x-coordinate.
Definition: Envelope.h:346
KdTreeNode kdNode
Export node type.
Definition: Index.h:366
KdTreeNode::kdData kdData
Export data type.
Definition: Index.h:75
const std::size_t & size() const
It returns the number of tree nodes.
Definition: Index.h:395
bool isEmpty() const
It returns true if the tree is empty and false otherwise.
Definition: Index.h:115
double average(std::vector< std::pair< kdKey, kdDataItem > > &dataSet, const char &discriminator) const
It returns the average value along the axis.
Definition: Index.h:494
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.
Definition: Index.h:733
KdTreeNode * m_root
Pointer to the root node.
Definition: Index.h:217
KdTreeNode::kdData kdData
Export data type.
Definition: Index.h:360
std::size_t m_size
The size of the K-d Tree (number of nodes).
Definition: Index.h:219
void setBucketSize(const std::size_t &size)
It sets bucket size for leaf nodes.
Definition: Index.h:419
double m_llx
Lower left corner x-coordinate.
Definition: Envelope.h:344
An Envelope defines a 2D rectangular region.
Definition: Envelope.h:51
const std::size_t & size() const
It returns the number of tree nodes.
Definition: Index.h:109
void build(std::vector< std::pair< kdKey, kdDataItem > > &dataSet)
It inserts the data set into the tree.
Definition: Index.h:431
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...
Definition: Index.h:136
const te::gm::Envelope & getMBR() const
It gets the minimum bounding box of all elements in the tree.
Definition: Index.h:127
AdaptativeIndex(const te::gm::Envelope &mbr, const std::size_t &bucketSize=12)
Constructor.
Definition: Index.h:369
URI C++ Library.
te::gm::Envelope m_mbr
Minimum bounding box of all nodes.
Definition: Index.h:535
const std::size_t & getBucketSize() const
It gets bucket size for leaf nodes.
Definition: Index.h:425
A class that represents a two dimensional K-d Tree (2-d Tree).
Definition: Index.h:67
bool Intersects(const T1 &o1, const T2 &o2)
double m_lly
Lower left corner y-coordinate.
Definition: Envelope.h:345
KdTreeNode::kdDataItem kdDataItem
Export data item type.
Definition: Index.h:363
KdTreeNode * m_root
Pointer to the root node.
Definition: Index.h:534
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.
Definition: Index.h:164
Kd-tree node type for nodes with single elements (used by template instantiation).
Definition: Node.h:36
AdaptativeIndex & operator=(const AdaptativeIndex &rhs)
No assignment operator allowed.
double m_ury
Upper right corner y-coordinate.
Definition: Envelope.h:347
void clear()
It clears all tree nodes.
Definition: Index.h:98
KdTreeNode::kdDataItem kdDataItem
Export data item type.
Definition: Index.h:78
std::size_t m_size
The size of the K-d Tree (number of nodes).
Definition: Index.h:536
void setMBR(const te::gm::Envelope &mbr)
It sets the minimum bounding box of all elements in the tree.
Definition: Index.h:121
Index(const te::gm::Envelope &mbr)
Constructor.
Definition: Index.h:84
bool isEmpty() const
It returns true if the tree is empty and false otherwise.
Definition: Index.h:401
void search(const te::gm::Envelope &e, std::vector< KdTreeNode * > &report) const
Range search query.
Definition: Index.h:143
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...
Definition: Index.h:441
Index & operator=(const Index &rhs)
No assignment operator allowed.
~AdaptativeIndex()
Destructor.
Definition: Index.h:378
~Index()
Destructor.
Definition: Index.h:92
KdTreeNode * buildOptimized(std::vector< std::pair< kdKey, kdDataItem > > &dataSet, const std::size_t &first, const std::size_t &last)
It builds the tree recursively.
Definition: Index.h:180
void erase(KdTreeNode *node)
It Erases a node from the tree and all nodes below it.
Definition: Index.h:470
KdTreeNode::kdKey kdKey
Export key type.
Definition: Index.h:72