| TerraLib 4.1

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

- File List
- File Members

E:/Projetos_Primeiro_Semestre_2012/TerraView/terralib/src/terralib/kernel/TeKdTree.h
Go to the documentation of this file.

    00001 /************************************************************************************
    00002 TerraLib - a library for developing GIS applications.
    00003 Copyright © 2001-2007 INPE and Tecgraf/PUC-Rio.
    00004
    00005 This code is part of the TerraLib library.
    00006 This library is free software; you can redistribute it and/or
    00007 modify it under the terms of the GNU Lesser General Public
    00008 License as published by the Free Software Foundation; either
    00009 version 2.1 of the License, or (at your option) any later version.
    00010
    00011 You should have received a copy of the GNU Lesser General Public
    00012 License along with this library.
    00013
    00014 The authors reassure the license terms regarding the warranties.
    00015 They specifically disclaim any warranties, including, but not limited to,
    00016 the implied warranties of merchantability and fitness for a particular purpose.
    00017 The library provided hereunder is on an "as is" basis, and the authors have no
    00018 obligation to provide maintenance, support, updates, enhancements, or modifications.
    00019 In no event shall INPE and Tecgraf / PUC-Rio be held liable to any party for direct,
    00020 indirect, special, incidental, or consequential damages arising out of the use
    00021 of this library and its documentation.
    00022 *************************************************************************************/
    00030 #ifndef  __TERRALIB_INTERNAL_KDTREE_H
    00031 #define  __TERRALIB_INTERNAL_KDTREE_H
    00032
    00033 #include "TeGeometry.h"
    00034
    00041 namespace TeSAM
    00042 {
    00048
    00049 /*
    00050            \param A             Conteiner of elements to partition
    00051            \param kthElement    Position of the k-th element, around the conteiner will be pertitionated
    00052            \param firstElement  Position of the first element
    00053            \param lastElement   Position of the las element
    00054            \param compFunctor   Functor to compare elements: implements the function "less than"
    00055
    00056 */
    00057 template<class CONTAINER, class COMPFUNCTOR>
    00058 void TeHoareFind(CONTAINER& A, const unsigned int& kthElement, const unsigned int& firstElement, const unsigned int& lastElement,  const COMPFUNCTOR& compFunctor)
    00059 {
    00060            unsigned int m = firstElement;
    00061            unsigned int n = lastElement;
    00062
    00063 // Test if the median is in the bounds
    00064            if((kthElement < firstElement) || (kthElement > lastElement))
    00065                       return;
    00066
    00067 // Do conteiner partition
    00068            while(m < n)
    00069            {
    00070                       unsigned int i = m;
    00071                       unsigned int j = n;
    00072
    00073                       typename CONTAINER::value_type r = A[kthElement];
    00074
    00075                       while(i <= j)
    00076                       {
    00077                                  while(compFunctor(A[i], r))
    00078                                             ++i;
    00079
    00080                                  while(compFunctor(r, A[j]))
    00081                                             --j;
    00082
    00083                                  if(i <= j)
    00084                                  {
    00085                                             typename CONTAINER::value_type w = A[i];
    00086                                             A[i] = A[j];
    00087                                             A[j] = w;
    00088
    00089                                      ++i;
    00090                                             --j;
    00091                                  }
    00092                       }
    00093
    00094                       if(kthElement <= j)                         // if the meet point was to the right, so all points above j are greater than the k-th element
    00095                                  n = j;
    00096                       else if(i <= kthElement)         // otherwise, if the meeting point was to the left of k-th, so all elements before i are already in the correct location
    00097                                  m = i;
    00098                       else
    00099                                  break;
    00100            }
    00101 }
    00102
    00104 /*
    00105            \param dataSet                                                    Conteinet elements to be sorted like a K-dTree
    00106            \param first                                                      Position of the first element in conteiner, where the sort will begin
    00107            \param last                                                                  Position of the last element, where the sort ends
    00108            \param level                                                      Indicates the axis to begin the sort ('x' or 'y') and is used during the recursion process
    00109            \param lessThanCompFunctorByX    Functor to compare elements along the 'x' axis
    00110            \param lessThanCompFunctorByY    Functor to compare elements along the 'y' axis
    00111
    00112            The expected complexity is O(N log N), where N is the number of elements in conteiner.
    00113 */
    00114 template<class CONTAINER, class LESSTHANX, class LESSTHANY>
    00115 void kdsort(CONTAINER& dataSet, const unsigned int& first, const unsigned int& last, const char& level, const LESSTHANX& lessThanCompFunctorByX, const LESSTHANY& lessThanCompFunctorByY)
    00116 {
    00117            const unsigned int kth = (last - first + 1u) / 2u;
    00118
    00119            if(level == 'x')
    00120            {
    00121 // Move data around X axis
    00122                       TeHoareFind(dataSet, first + kth, first, last, lessThanCompFunctorByX);
    00123
    00124 // Recursive sort the left half and right half
    00125                       if((first + kth) > first)
    00126                                  kdsort(dataSet, first, first + kth - 1u, 'y', lessThanCompFunctorByX, lessThanCompFunctorByY);
    00127
    00128                       if((first + kth) < last)
    00129                                  kdsort(dataSet, first + kth + 1u, last, 'y', lessThanCompFunctorByX, lessThanCompFunctorByY);
    00130            }
    00131            else
    00132            {
    00133 // Move data around Y axis
    00134                       TeHoareFind(dataSet, first + kth, first, last, lessThanCompFunctorByY);
    00135
    00136 // Recursive sort the left half and right half
    00137                       if((first + kth) > first)
    00138                                  kdsort(dataSet, first, first + kth - 1u, 'x', lessThanCompFunctorByX, lessThanCompFunctorByY);
    00139
    00140                       if((first + kth) < last)
    00141                                  kdsort(dataSet, first + kth + 1u, last, 'x', lessThanCompFunctorByX, lessThanCompFunctorByY);
    00142            }
    00143 }
    00146
    00147 struct TL_DLL kd_node_data_single_tag {};
    00148
    00150 struct TL_DLL kd_node_data_set_tag {};
    00151
    00152
    00154
    00172 template<class NodeKey, class NodeData, class NodeDataItem,
    00173          class NodeDataTag = kd_node_data_single_tag>
    00174 class TeKdTreeNode
    00175 {
    00176            protected:
    00177
    00179                       NodeKey key_;
    00180
    00182                       NodeData data_;
    00183
    00185                       TeKdTreeNode* left_;
    00186
    00188                       TeKdTreeNode* right_;
    00189
    00190            public:
    00191
    00193                       typedef NodeKey kdKey;
    00194
    00196                       typedef NodeData kdData;
    00197
    00199                       typedef NodeDataItem kdDataItem;
    00200
    00202                       typedef NodeDataTag  kdDataTag;
    00203
    00205                       TeKdTreeNode(const NodeKey& k)
    00206                                  : key_(k), left_(0), right_(0)
    00207                       {
    00208                       }
    00209
    00211                       void setKey(const NodeKey& k)
    00212                       {
    00213                                  key_ = k;
    00214                       }
    00215
    00217                       const NodeKey& getKey(void) const
    00218                       {
    00219                                  return key_;
    00220                       }
    00221
    00223                       void setData(const NodeData& data)
    00224                       {
    00225                                  data_ = data;
    00226                       }
    00227
    00229                       NodeData& getData(void)
    00230                       {
    00231                                  return data_;
    00232                       }
    00233
    00235                       void setLeft(TeKdTreeNode* node)
    00236                       {
    00237                                  left_ = node;
    00238                       }
    00239
    00241                       void setRight(TeKdTreeNode* node)
    00242                       {
    00243                                  right_ = node;
    00244                       }
    00245
    00247                       TeKdTreeNode* getLeft(void) const
    00248                       {
    00249                                  return left_;
    00250                       }
    00251
    00253                       TeKdTreeNode* getRight(void) const
    00254                       {
    00255                                  return right_;
    00256                       }
    00257
    00259                       bool hasLeft(void) const
    00260                       {
    00261                                  return (left_ != 0);
    00262                       }
    00263
    00265                       bool hasRight(void) const
    00266                       {
    00267                                  return (right_ != 0);
    00268                       }
    00269
    00271                       bool isLeaf(void) const
    00272                       {
    00273                                  return !(hasLeft() || hasRight());
    00274                       }
    00275
    00277                       unsigned int descendants(void) const
    00278                       {
    00279                                  unsigned int totalLeft  = 0u;
    00280                                  unsigned int totalRight = 0u;
    00281
    00282                                  if(hasLeft())
    00283                                             totalLeft = 1u + getLeft()->descendants();
    00284
    00285                                  if(hasRight())
    00286                                             totalRight = 1u + getRight()->descendants();
    00287
    00288                                  return (totalLeft + totalRight);
    00289                       }
    00290
    00291            private:
    00292
    00294                       TeKdTreeNode(const TeKdTreeNode& other);
    00295
    00297                       TeKdTreeNode& operator=(const TeKdTreeNode& other);
    00298
    00299 };         // end of class TeKdTreeNode
    00300
    00302
    00305 template<class KdTreeNode>
    00306 class TeBasicKdTree
    00307 {
    00308            protected:
    00309
    00311                       KdTreeNode* root_;
    00312
    00314                       TeBox mbr_;
    00315
    00317                       unsigned int size_;
    00318
    00319            public:
    00320
    00322                       TeBasicKdTree(const TeBox& mbr)
    00323                                  : root_(0), mbr_(mbr), size_(0u)
    00324                       {
    00325                       }
    00326
    00328                       ~TeBasicKdTree()
    00329                       {
    00330                                  clear();
    00331                       }
    00332
    00334                       void clear(void)
    00335                       {
    00336                                  if(root_)
    00337                                  {
    00338                                             erase(root_);
    00339                                             root_ = 0;
    00340                                             size_ = 0;
    00341                                  }
    00342                       }
    00343
    00345                       const unsigned int& size(void) const
    00346                       {
    00347                                  return size_;
    00348                       }
    00349
    00351                       bool isEmpty(void) const
    00352                       {
    00353                                  return root_ == 0;
    00354                       }
    00355
    00357                       void setBox(const TeBox& mbr)
    00358                       {
    00359                                  mbr_ = mbr;
    00360                       }
    00361
    00363                       const TeBox& getBox(void) const
    00364                       {
    00365                                  return mbr_;
    00366                       }
    00367
    00368            protected:
    00369
    00371                       void erase(KdTreeNode* node)
    00372                       {
    00373                                  if(node->hasLeft())
    00374                                             erase(node->getLeft());
    00375
    00376                                  if(node->hasRight())
    00377                                             erase(node->getRight());
    00378
    00379                                  delete node;
    00380
    00381                                  return;
    00382                       }
    00383
    00384            private:
    00385
    00387                       TeBasicKdTree(const TeBasicKdTree& other);
    00388
    00390                       TeBasicKdTree& operator=(const TeBasicKdTree& other);
    00391 };
    00392
    00393
    00395
    00416 template<class KdTreeNode>
    00417 class TeKdTree : public TeBasicKdTree<KdTreeNode>
    00418 {
    00419         using TeBasicKdTree<KdTreeNode>::root_;
    00420         using TeBasicKdTree<KdTreeNode>::size_;
    00421         using TeBasicKdTree<KdTreeNode>::mbr_;
    00422
    00423            public:
    00424
    00426                       typedef typename KdTreeNode::kdKey kdKey;
    00427
    00429                       typedef typename KdTreeNode::kdData kdData;
    00430
    00432                       typedef typename KdTreeNode::kdDataItem kdDataItem;
    00433
    00435                       typedef typename KdTreeNode::kdDataTag kdDataTag;
    00436
    00438                       TeKdTree(const TeBox& mbr)
    00439                                  : TeBasicKdTree<KdTreeNode>(mbr)
    00440                       {
    00441                       }
    00442
    00444                       inline void insert(const kdKey& key, const kdDataItem& item);
    00445
    00447                       void buildOptimized(vector<pair<kdKey, kdDataItem> >& dataSet)
    00448                       {
    00449                                  const unsigned int last = dataSet.size() - 1u;
    00450
    00451                                  root_ = buildOptimized(dataSet, 0u, last);
    00452                       }
    00453
    00455                       void search(const TeBox& rect, vector<KdTreeNode*>& report) const
    00456                       {
    00457                                  if(root_)
    00458                                             search(rect, root_, 'x', report);
    00459
    00460                                  return;
    00461                       }
    00462
    00463            protected:
    00464
    00466                       void insertData(KdTreeNode*& node, const kdDataItem& data, const kd_node_data_single_tag&)
    00467                       {
    00468                                  node->setData(data);
    00469                       }
    00470
    00472                       void insertData(KdTreeNode*& node, const kdDataItem& data, const kd_node_data_set_tag&)
    00473                       {
    00474                                  node->getData().push_back(data);
    00475                       }
    00476
    00478                       inline void search(const TeBox& rect, KdTreeNode* node, const char& level, vector<KdTreeNode*>& report) const;
    00479
    00481                       KdTreeNode* buildOptimized(vector<pair<kdKey, kdDataItem> >& dataSet, const unsigned int& first, const unsigned int& last)
    00482                       {
    00483                                  const unsigned int kth = (last - first + 1u) / 2u;
    00484
    00485                                  KdTreeNode* newNode = new KdTreeNode(dataSet[first + kth].first);
    00486
    00487                                  newNode->setData(dataSet[first + kth].second);
    00488
    00489                                  ++size_;
    00490
    00491                                  if((first + kth) > first)
    00492                                             newNode->setLeft(buildOptimized(dataSet, first, first + kth - 1u));
    00493
    00494                                  if((first + kth) < last)
    00495                                             newNode->setRight(buildOptimized(dataSet, first + kth + 1u, last));
    00496
    00497                                  return newNode;
    00498                       }
    00499
    00500            private:
    00501
    00503                       TeKdTree(const TeKdTree& other);
    00504
    00506                       TeKdTree& operator=(const TeKdTree& other);
    00507
    00508 };         // end class TeKdTree
    00509
    00510 template<class KdTreeNode>
    00511 void TeKdTree<KdTreeNode>::insert(const kdKey& key, const kdDataItem& item)
    00512 {
    00513            if(root_ == 0)
    00514            {
    00515                       root_ = new KdTreeNode(key);
    00516
    00517                       insertData(root_, item, kdDataTag());
    00518            }
    00519            else
    00520            {
    00521                       char level = 'x';
    00522
    00523                       bool left = false;
    00524
    00525                       KdTreeNode* x = root_;
    00526                       KdTreeNode* y = 0;
    00527
    00528                       while(x != 0)
    00529                       {
    00530                                  y = x;
    00531
    00532                                  if(level == 'x')
    00533                                  {
    00534                                             if(key.x() > x->getKey().x())               // if the key is greater than, inserts in the right subtree
    00535                                             {
    00536                                                        x = x->getRight();
    00537                                                        left = false;
    00538                                             }
    00539                                             else if(key.x() < x->getKey().x())                     // if the key is smaller than, inserts in the left subtree
    00540                                             {
    00541                                                        x = x->getLeft();
    00542                                                        left = true;
    00543                                             }
    00544                                             else if(key.y() == x->getKey().y())                    // 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
    00545                 {
    00546                                                        insertData(x, item, kdDataTag());
    00547
    00548                                                        return;
    00549                                             }
    00550                                             else                                                   // found the same axis partition, so go left
    00551                                             {
    00552                                                        x = x->getLeft();
    00553                                                        left = true;
    00554                                             }
    00555
    00556                                             level = 'y';
    00557                                  }
    00558                                  else
    00559                                  {
    00560                                             if(key.y() > x->getKey().y())
    00561                                             {
    00562                                                        x = x->getRight();
    00563                                                        left = false;
    00564                                             }
    00565                                             else if(key.y() < x->getKey().y())
    00566                                             {
    00567                                                        x = x->getLeft();
    00568                                                        left = true;
    00569                                             }
    00570                                             else if(key.x() == x->getKey().x())
    00571                                 {
    00572                                                        insertData(x, item, kdDataTag());
    00573
    00574                                                        return;
    00575                                             }
    00576                                             else
    00577                                             {
    00578                                                        x = x->getLeft();
    00579                                                        left = true;
    00580                                             }
    00581
    00582                                             level = 'x';
    00583                                  }
    00584                       }
    00585
    00586                       KdTreeNode* newNode = new KdTreeNode(key);
    00587
    00588                       insertData(newNode, item, kdDataTag());
    00589
    00590                       if(left)
    00591                                  y->setLeft(newNode);
    00592                       else
    00593                                  y->setRight(newNode);
    00594            }
    00595
    00596            ++size_;
    00597
    00598            return;
    00599 }
    00600
    00601 template<class KdTreeNode>
    00602 void TeKdTree<KdTreeNode>::search(const TeBox& rect, KdTreeNode* node, const char& level, vector<KdTreeNode*>& report) const
    00603 {
    00604            if((node->getKey().x() >= rect.x1_) && (node->getKey().x() <= rect.x2_) &&
    00605               (node->getKey().y() >= rect.y1_) && (node->getKey().y() <= rect.y2_))
    00606                       report.push_back(node);
    00607
    00608            if(level == 'x')
    00609            {
    00610                       if(node->hasLeft())
    00611                                  if(node->getKey().x() >= rect.x1_)
    00612                                             search(rect, node->getLeft(), 'y', report);
    00613
    00614                       if(node->hasRight())
    00615                                  if(node->getKey().x() <= rect.x2_)
    00616                                             search(rect, node->getRight(), 'y', report);
    00617            }
    00618            else
    00619            {
    00620                       if(node->hasLeft())
    00621                                  if(node->getKey().y() >= rect.y1_)
    00622                                             search(rect, node->getLeft(), 'x', report);
    00623
    00624                       if(node->hasRight())
    00625                                  if(node->getKey().y() <= rect.y2_)
    00626                                             search(rect, node->getRight(), 'x', report);
    00627            }
    00628
    00629            return;
    00630 }
    00631
    00633
    00646 template<class NodeKey, class NodeData, class NodeDataItem>
    00647 class TeAdaptativeKdTreeNode
    00648 {
    00649 protected:
    00651                       double key_;
    00652
    00654                       NodeData data_;
    00655
    00657                       char discriminator_;
    00658
    00660                       TeAdaptativeKdTreeNode* left_;
    00661
    00663                       TeAdaptativeKdTreeNode* right_;
    00664
    00665 public:
    00667                       typedef NodeKey kdKey;
    00668
    00670                       typedef NodeData kdData;
    00671
    00673                       typedef NodeDataItem kdDataItem;
    00674
    00676                       TeAdaptativeKdTreeNode(const double& k)
    00677                                  : key_(k), discriminator_('x'), left_(0), right_(0)
    00678                       { }
    00679
    00681                       void setKey(const double& k)
    00682                       {
    00683                                  key_ = k;
    00684                       }
    00685
    00687                       const double& getKey(void) const
    00688                       {
    00689                                  return key_;
    00690                       }
    00691
    00693                       void setData(const NodeData& data)
    00694                       {
    00695                                  data_ = data;
    00696                       }
    00697
    00699                       NodeData& getData(void)
    00700                       {
    00701                                  return data_;
    00702                       }
    00703
    00705                       void setDiscriminator(const char& d)
    00706                       {
    00707                                  discriminator_ = d;
    00708                       }
    00709
    00711                       const char& getDiscriminator(void) const
    00712                       {
    00713                                  return discriminator_;
    00714                       }
    00715
    00717                       void setLeft(TeAdaptativeKdTreeNode* node)
    00718                       {
    00719                                  left_ = node;
    00720                       }
    00721
    00723                       void setRight(TeAdaptativeKdTreeNode* node)
    00724                       {
    00725                                  right_ = node;
    00726                       }
    00727
    00729                       TeAdaptativeKdTreeNode* getLeft(void) const
    00730                       {
    00731                                  return left_;
    00732                       }
    00733
    00735                       TeAdaptativeKdTreeNode* getRight(void) const
    00736                       {
    00737                                  return right_;
    00738                       }
    00739
    00741                       bool hasLeft(void) const
    00742                       {
    00743                                  return (left_ != 0);
    00744                       }
    00745
    00747                       bool hasRight(void) const
    00748                       {
    00749                                  return (right_ != 0);
    00750                       }
    00751
    00753                       bool isLeaf(void) const
    00754                       {
    00755                                  return !(hasLeft() || hasRight());
    00756                       }
    00757
    00759                       unsigned int descendants(void) const
    00760                       {
    00761                                  unsigned int totalLeft  = 0u;
    00762                                  unsigned int totalRight = 0u;
    00763
    00764                                  if(hasLeft())
    00765                                             totalLeft = 1u + getLeft()->descendants();
    00766
    00767                                  if(hasRight())
    00768                                             totalRight = 1u + getRight()->descendants();
    00769
    00770                                  return (totalLeft + totalRight);
    00771                       }
    00772
    00773            private:
    00774
    00776                       TeAdaptativeKdTreeNode(const TeAdaptativeKdTreeNode& other);
    00777
    00779                       TeAdaptativeKdTreeNode& operator=(const TeAdaptativeKdTreeNode& other);
    00780
    00781 };         // end of class TeAdaptativeKdTreeNode
    00782
    00784
    00795 template<class KdTreeNode>
    00796 class TeAdaptativeKdTree : public TeBasicKdTree<KdTreeNode>
    00797 {
    00798            using TeBasicKdTree<KdTreeNode>::root_;
    00799            using TeBasicKdTree<KdTreeNode>::size_;
    00800            using TeBasicKdTree<KdTreeNode>::mbr_;
    00801
    00802 protected:
    00804                       unsigned int bucketSize_;
    00805
    00806 public:
    00808                       typedef typename KdTreeNode::kdKey kdKey;
    00809
    00811                       typedef typename KdTreeNode::kdData kdData;
    00812
    00814                       typedef typename KdTreeNode::kdDataItem kdDataItem;
    00815
    00817                       typedef KdTreeNode kdNode;
    00818
    00820                       TeAdaptativeKdTree(const TeBox& box, const unsigned int& bucketSize = 12)
    00821                                  : TeBasicKdTree<KdTreeNode>(box), bucketSize_(bucketSize)
    00822                       {
    00823                       }
    00824
    00826                       void setBucketSize(const unsigned int& size)
    00827                       {
    00828                                  bucketSize_ = size;
    00829                       }
    00830
    00832                       const unsigned int& getBucketSize(void) const
    00833                       {
    00834                                  return bucketSize_;
    00835                       }
    00836
    00838                       void build(vector<pair<kdKey, kdDataItem> >& dataSet)
    00839                       {
    00840                                  root_ = build(dataSet, 0.0, mbr_);
    00841                       }
    00842
    00844                       void nearestNeighborSearch(const kdKey& key, vector<kdDataItem>& report, vector<double>& sqrDists, const unsigned int& k) const
    00845                       {
    00846                                  if(root_)
    00847                                  {
    00848                                             sqrDists.clear();
    00849
    00850                                             for(unsigned int i = 0; i < k; ++i)
    00851                                                        sqrDists.push_back(TeMAXFLOAT);
    00852
    00853                                             TeBox rect(-TeMAXFLOAT, -TeMAXFLOAT, +TeMAXFLOAT, +TeMAXFLOAT);
    00854
    00855                                             nearestNeighborSearch(root_, key, report, sqrDists, rect);
    00856                                  }
    00857                       }
    00858
    00860                       void search(const TeBox& rect, vector<KdTreeNode*>& report) const
    00861                       {
    00862                                  if(root_)
    00863                                             search(rect, root_, report);
    00864
    00865                                  return;
    00866                       }
    00867
    00869                       inline void search(const TeBox& rect, vector<kdDataItem>& report) const;
    00870
    00871 protected:
    00873                       inline KdTreeNode* build(vector<pair<kdKey, kdDataItem> >& dataSet, double averageValue, const TeBox& mbr);
    00874
    00876                       inline void search(const TeBox& rect, KdTreeNode* node, vector<KdTreeNode*>& report) const;
    00877
    00879                       inline void nearestNeighborSearch(KdTreeNode* node, const kdKey& key, vector<kdDataItem>& report, vector<double>& sqrDists, TeBox& rect) const;
    00880
    00882                       inline void update(KdTreeNode* node, const kdKey& key, vector<kdDataItem>& report, vector<double>& sqrDists, TeBox& rect) const;
    00883
    00885                       double average(vector<pair<kdKey, kdDataItem> >& dataSet, const char& discriminator) const
    00886                       {
    00887                                  const unsigned int size = dataSet.size();
    00888
    00889                                  double medianValue = 0.0;
    00890
    00891                                  if(discriminator == 'x')
    00892                                  {
    00893                                             for(unsigned int i = 0; i < size; ++i)
    00894                                                        medianValue += dataSet[i].first.x();
    00895
    00896                                             return medianValue / size;
    00897                                  }
    00898                                  else
    00899                                  {
    00900                                             for(unsigned int i = 0; i < size; ++i)
    00901                                                        medianValue += dataSet[i].first.y();
    00902
    00903                                             return medianValue / size;
    00904                                  }
    00905                       }
    00906
    00907 private:
    00909                       TeAdaptativeKdTree(const TeAdaptativeKdTree& other);
    00910
    00912                       TeAdaptativeKdTree& operator=(const TeAdaptativeKdTree& other);
    00913
    00914 };         // end class TeAdaptativeKdTree
    00915
    00916 template<class KdTreeNode>
    00917 KdTreeNode* TeAdaptativeKdTree<KdTreeNode>::build(vector<pair<kdKey, kdDataItem> >& dataSet, double averageValue, const TeBox& mbr)
    00918 {
    00919            ++size_;
    00920
    00921            if(dataSet.size() <= bucketSize_)
    00922            {
    00923                       KdTreeNode* node = new KdTreeNode(averageValue);
    00924
    00925                       node->setDiscriminator('l');
    00926                       //node->setBox(mbr);
    00927
    00928                       unsigned int size = dataSet.size();
    00929
    00930                       for(unsigned int i = 0; i < size; ++i)
    00931                                  node->getData().push_back(dataSet[i].second);
    00932
    00933                       return node;
    00934            }
    00935
    00936            TeBox newMbr1(mbr);
    00937            TeBox newMbr2(mbr);
    00938
    00939            char discriminator = 'x';
    00940
    00941            vector<pair<kdKey, kdDataItem> > leftDataSet;
    00942            vector<pair<kdKey, kdDataItem> > rightDataSet;
    00943
    00944 // Finds the largest dimension
    00945            if((mbr.x2_ - mbr.x1_) > (mbr.y2_ - mbr.y1_))
    00946            {
    00947 // Finds the median along "x" axis
    00948                       averageValue = average(dataSet, 'x');
    00949
    00950 // Adjust box for left and right branchs
    00951                       newMbr1.x2_ = averageValue;
    00952                       newMbr2.x1_ = averageValue;
    00953
    00954                       unsigned int size = dataSet.size();
    00955
    00956                       for(unsigned int i = 0; i < size; ++ i)
    00957                       {
    00958                                  if(dataSet[i].first.x() <= averageValue)
    00959                                             leftDataSet.push_back(dataSet[i]);
    00960                                  else
    00961                                             rightDataSet.push_back(dataSet[i]);
    00962                       }
    00963            }
    00964            else
    00965            {
    00966                       discriminator = 'y';
    00967
    00968 // Finds the median along "y" axis
    00969                       averageValue = average(dataSet, 'y');
    00970
    00971 // Adjust box for left and right branchs
    00972                       newMbr1.y2_ = averageValue;
    00973                       newMbr2.y1_ = averageValue;
    00974
    00975                       unsigned int size = dataSet.size();
    00976
    00977                       for(unsigned int i = 0; i < size; ++ i)
    00978                       {
    00979                                  if(dataSet[i].first.y() <= averageValue)
    00980                                             leftDataSet.push_back(dataSet[i]);
    00981                                  else
    00982                                             rightDataSet.push_back(dataSet[i]);
    00983                       }
    00984            }
    00985
    00986            dataSet.clear();
    00987
    00988            KdTreeNode* node = new KdTreeNode(averageValue);
    00989
    00990            //node->setBox(mbr);
    00991
    00992            if(rightDataSet.size() == 0u)               // If all coordinates have the same coordinate values, the right vector will be empty so we need stop division to
    00993            {
    00994                       node->setDiscriminator('l');
    00995                       //node->setBox(newMbr1);
    00996
    00997                       unsigned int size = leftDataSet.size();
    00998
    00999                       for(unsigned int i = 0; i < size; ++i)
    01000                                  node->getData().push_back(leftDataSet[i].second);
    01001
    01002                       //throw;
    01003            }
    01004            else if(leftDataSet.size() == 0u)                      // If all coordinates have the same coordinate values, the left vector is empty, so we need to stop
    01005            {
    01006                       node->setDiscriminator('l');
    01007                       //node->setBox(newMbr2);
    01008
    01009                       unsigned int size = rightDataSet.size();
    01010
    01011                       for(unsigned int i = 0; i < size; ++i)
    01012                                  node->getData().push_back(rightDataSet[i].second);
    01013
    01014                       //throw;
    01015            }
    01016            else
    01017            {
    01018                       node->setDiscriminator(discriminator);
    01019                       node->setLeft(build(leftDataSet, averageValue, newMbr1));
    01020                       node->setRight(build(rightDataSet, averageValue, newMbr2));
    01021            }
    01022
    01023            return node;
    01024 }
    01025
    01026 template<class KdTreeNode>
    01027 void TeAdaptativeKdTree<KdTreeNode>::search(const TeBox& rect, vector<kdDataItem>& report) const
    01028 {
    01029            vector<KdTreeNode*> reportNodes;
    01030
    01031            search(rect, reportNodes);
    01032
    01033     unsigned int nNodes = reportNodes.size();
    01034
    01035            for(unsigned int i = 0; i < nNodes; ++i)
    01036            {
    01037                       unsigned int nElements = reportNodes[i]->getData().size();
    01038
    01039                       for(unsigned int j = 0; j < nElements; ++j)
    01040                       {
    01041             if(TeIntersects((reportNodes[i])->getData()[j], rect))
    01042                                  {
    01043                                             report.push_back((reportNodes[i])->getData()[j]);
    01044                                  }
    01045                       }
    01046            }
    01047 }
    01048
    01049 template<class KdTreeNode>
    01050 void TeAdaptativeKdTree<KdTreeNode>::search(const TeBox& rect, KdTreeNode* node, vector<KdTreeNode*>& report) const
    01051 {
    01052            if(node->getDiscriminator() == 'x')
    01053            {
    01054                       if(node->hasLeft())
    01055                                  if(rect.x1_ <= node->getKey())
    01056                                             search(rect, node->getLeft(), report);
    01057
    01058                       if(node->hasRight())
    01059                                  if(rect.x2_ >= node->getKey())
    01060                                             search(rect, node->getRight(), report);
    01061            }
    01062            else if(node->getDiscriminator() == 'y')
    01063            {
    01064                       if(node->hasLeft())
    01065                                  if(rect.y1_ <= node->getKey())
    01066                                             search(rect, node->getLeft(), report);
    01067
    01068                       if(node->hasRight())
    01069                                  if(rect.y2_ >= node->getKey())
    01070                                             search(rect, node->getRight(), report);
    01071            }
    01072            else
    01073            {
    01074                       report.push_back(node);
    01075            }
    01076
    01077            return;
    01078 }
    01079
    01080 template<class KdTreeNode>
    01081 void TeAdaptativeKdTree<KdTreeNode>::nearestNeighborSearch(KdTreeNode* node, const kdKey& key, vector<kdDataItem>& report, vector<double>& sqrDists, TeBox& rect) const
    01082 {
    01083            if(node->getDiscriminator() == 'l')
    01084            {
    01085                       update(node, key, report, sqrDists, rect);  // this is a leaf node -> update list of neighbours
    01086            }
    01087            else if(node->getDiscriminator() == 'x')
    01088            {
    01089                       if(key.x() <= node->getKey())
    01090                       {
    01091                                  nearestNeighborSearch(node->getLeft(), key, report, sqrDists, rect);
    01092
    01093                                  if((rect.x1_ < node->getKey()) && (node->getKey() < rect.x2_))
    01094                                             nearestNeighborSearch(node->getRight(), key, report, sqrDists, rect);
    01095                       }
    01096                       else
    01097                       {
    01098                                  nearestNeighborSearch(node->getRight(), key, report, sqrDists, rect);
    01099
    01100                                  if((rect.x1_ < node->getKey()) &&(node->getKey() < rect.x2_))
    01101                                             nearestNeighborSearch(node->getLeft(), key, report, sqrDists, rect);
    01102                       }
    01103            }
    01104            else if(node->getDiscriminator() == 'y')
    01105            {
    01106                        if(key.y() <= node->getKey())
    01107                       {
    01108                                  nearestNeighborSearch(node->getLeft(), key, report, sqrDists, rect);
    01109
    01110                                  if((rect.y1_ < node->getKey()) &&(node->getKey() < rect.y2_ ))
    01111                                             nearestNeighborSearch(node->getRight(), key, report, sqrDists, rect);
    01112                       }
    01113                       else
    01114                       {
    01115                                  nearestNeighborSearch(node->getRight(), key, report, sqrDists, rect);
    01116
    01117                                  if((rect.y1_ < node->getKey()) &&(node->getKey() < rect.y2_))
    01118                                             nearestNeighborSearch(node->getLeft(), key, report, sqrDists, rect);
    01119                       }
    01120            }
    01121
    01122 }
    01123
    01124 template<class KdTreeNode>
    01125 void TeAdaptativeKdTree<KdTreeNode>::update(KdTreeNode* node, const kdKey& key, vector<kdDataItem>& report, vector<double>& sqrDists, TeBox& rect) const
    01126 {
    01127 // rect is the bounding box of neighbors
    01128
    01129            const unsigned int size = node->getData().size();
    01130
    01131            const unsigned int nNeighbors = report.size();
    01132
    01133 // for each element in the node, we need to search for distances less than of some one of sqrDists
    01134            for(unsigned int i = 0u; i < size; ++i)
    01135            {
    01136                       double dx = (key.x() - node->getData()[i].location().x());
    01137                       double dy = (key.y() - node->getData()[i].location().y());
    01138
    01139                       double dkp = (dx * dx) + (dy * dy);         // square distance from the key point to the node
    01140
    01141 // if the distance of "i-th" element is less than the maximum distance in the sqrDists
    01142                       if(dkp < sqrDists[nNeighbors - 1])
    01143                       {
    01144 // so the element must be reported
    01145
    01146 // and the srqDists vector must be rearranged
    01147                                  for(unsigned int j = 0u; j < nNeighbors; ++j)
    01148                                  {
    01149                                             if(dkp < sqrDists[j]) // if the position is found
    01150                                             {
    01151 // move the elements to the right
    01152                                                        for(unsigned int k = nNeighbors - 1; k > j; --k)
    01153                                                        {
    01154                                                                   report[k]   = report[k - 1];
    01155                                                                   sqrDists[k] = sqrDists[k - 1];
    01156                                                        }
    01157
    01158 // inserts the element in the report and update its distance
    01159                                                        report[j] = node->getData()[i];
    01160
    01161                                                        sqrDists[j] = dkp;
    01162
    01163                                                        break;
    01164                                             }
    01165                                  }
    01166                       }
    01167            }
    01168
    01169            double maxDist = sqrDists[nNeighbors - 1];
    01170
    01171            if(maxDist != TeMAXFLOAT)
    01172            {
    01173                       maxDist = sqrt(maxDist);
    01174            }
    01175
    01176            rect.x1_ = key.x() - maxDist;
    01177            rect.y1_ = key.y() - maxDist;
    01178            rect.x2_ = key.x() + maxDist;
    01179            rect.y2_ = key.y() + maxDist;
    01180 }
    01183 };         // end namespace TeSAM
    01184
    01185
    01186 #endif     // __TERRALIB_INTERNAL_KDTREE_H
    01187
    01188
    01189
    01190

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines