| 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/TeRTree.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_RTREE_H
    00031 #define  __TERRALIB_INTERNAL_RTREE_H
    00032
    00033 #include "TeGeometry.h"
    00034 #include "TeGeometryAlgorithms.h"
    00035
    00039 namespace TeSAM
    00040 {
    00042
    00050 template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
    00051 class TeRTreeNode
    00052 {
    00053            public:
    00054
    00056
    00060                       struct TeRTreeBranch
    00061                       {
    00062                                  TeBox rect_;
    00063
    00064                                  union
    00065                                  {
    00066                                             TeRTreeNode* child_;
    00067                                             DATATYPE data_;
    00068                                  };
    00069                       };
    00070
    00071            public:
    00072
    00073                       int count_;
    00074
    00075                       int level_;
    00076
    00077                       TeRTreeBranch branch_[MAXNODES];
    00078
    00080
    00081
    00082                       TeRTreeNode()
    00083                                  : count_(0), level_(-1)
    00084                       {
    00085                       }
    00086
    00088         bool isInternalNode() const
    00089                       {
    00090                                  return (level_ > 0);
    00091                       }
    00092
    00094         bool isLeaf() const
    00095                       {
    00096                                  return (level_ == 0);
    00097                       }
    00098
    00100                       void init()
    00101                       {
    00102                                  count_ = 0;
    00103
    00104                                  level_ = -1;
    00105                       }
    00106
    00107            private:
    00108
    00110                       TeRTreeNode(const TeRTreeNode& other);
    00111
    00113                       TeRTreeNode& operator=(const TeRTreeNode& other);
    00114
    00115 };         // end of class TeRTreeNode
    00116
    00118
    00135 template<class DATATYPE, int MAXNODES = 8, int MINNODES = MAXNODES / 2>
    00136 class TeRTree
    00137 {
    00138            public:
    00139
    00141                       typedef TeRTreeNode<DATATYPE, MAXNODES, MINNODES> TeRTreeNodeType;
    00142
    00144                       typedef typename TeRTreeNodeType::TeRTreeBranch TeRTreeBranch;
    00145
    00146            protected:
    00147
    00149                       struct TePartitionVars
    00150                       {
    00151                                  int partition_[MAXNODES + 1];
    00152                                  int taken_[MAXNODES + 1];
    00153                                  int count_[2];
    00154                                  TeBox cover_[2];
    00155                                  double area_[2];
    00156
    00157                                  TeRTreeBranch branchBuf_[MAXNODES + 1];
    00158                                  TeBox coverSplit_;
    00159
    00161                                  void init()
    00162                                  {
    00163                                             count_[0] = 0;
    00164                                             count_[1] = 0;
    00165
    00166                 for(int i = 0; i <= MAXNODES; ++i)
    00167                 {
    00168                     taken_[i] = 0;
    00169                     partition_[i] = -1;
    00170                 }
    00171                                  }
    00172                       };
    00173
    00174                       TeRTreeNodeType* root_;
    00175
    00176                       TeBox mbr_;
    00177
    00178                       mutable unsigned int size_;
    00179
    00180            public:
    00181
    00183                       TeRTree(const TeBox& mbr)
    00184                                  : root_(0), mbr_(mbr), size_(0)
    00185                       {
    00186                                  ++size_;
    00187                                  root_ = new TeRTreeNodeType();
    00188             root_->level_ = 0;
    00189                       }
    00190
    00192                       ~TeRTree()
    00193                       {
    00194                                  clear();
    00195
    00196                                  if(root_)
    00197                                             delete root_;
    00198                       }
    00199
    00201                       const unsigned int& size(void) const
    00202                       {
    00203                                  return size_;
    00204                       }
    00205
    00207                       bool isEmpty(void) const
    00208                       {
    00209                                  return (root_->count_ == 0);
    00210                       }
    00211
    00213                       void clear(void)
    00214                       {
    00215                                  if(root_)
    00216                                  {
    00217                                             erase(root_);
    00218                                             root_ = 0;
    00219
    00220                                             size_ = 1;
    00221                                             root_ = new TeRTreeNodeType();
    00222                                             root_->level_ = 0;
    00223                                  }
    00224                       }
    00225
    00227                       void insert(const TeBox& rect, const DATATYPE& data)
    00228                       {
    00229                                  insert(rect, data, &root_, 0);
    00230                       }
    00231
    00233                       bool remove(const TeBox& rect, const DATATYPE& data)
    00234                       {
    00235                                  return remove(rect, data, &root_);
    00236                       }
    00237
    00239                       int search(const TeBox& rect, vector<DATATYPE>& report) const
    00240                       {
    00241                                  int foundObjs = 0;
    00242
    00243                                  if(root_)
    00244                                             search(rect, root_, report, foundObjs);
    00245
    00246                                  return foundObjs;
    00247                       }
    00248
    00250                       void setBox(const TeBox& mbr)
    00251                       {
    00252                                  mbr_ = mbr;
    00253                       }
    00254
    00256                       const TeBox& getBox(void) const
    00257                       {
    00258                                  return mbr_;
    00259                       }
    00260
    00261            protected:
    00262
    00264
    00271                       inline bool insert(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType** root, int level);
    00272
    00274
    00279                       inline bool remove(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType** root);
    00280
    00282
    00287                       inline bool remove2(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType* n, vector<TeRTreeNodeType*>& ee);
    00288
    00290                       inline void disconBranch(TeRTreeNodeType* n, int i);
    00291
    00293
    00301                       inline bool chooseLeaf(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType* node, TeRTreeNodeType** newNode, int level);
    00302
    00304                       inline void search(const TeBox& rect, TeRTreeNodeType* node, vector<DATATYPE>& report, int& foundObjs) const;
    00305
    00307                       inline TeBox nodeCover(TeRTreeNodeType* n) const;
    00308
    00310                       inline TeBox combineRect(const TeBox& rectA, const TeBox& rectB) const;
    00311
    00313
    00320                       inline bool addBranch(TeRTreeBranch* branch, TeRTreeNodeType* node, TeRTreeNodeType** newNode) const;
    00321
    00323
    00330                       inline int pickBranch(const TeBox& rect, TeRTreeNodeType* node) const;
    00331
    00333
    00337                       inline void splitNode(TeRTreeNodeType* node, TeRTreeBranch* branch, TeRTreeNodeType** newNode) const;
    00338
    00340                       inline void getBranches(TeRTreeNodeType* n, TeRTreeBranch* b, TePartitionVars& p) const;
    00341
    00343
    00347                       inline void methodZero(TePartitionVars& p) const;
    00348
    00350
    00355                       inline void pickSeeds(TePartitionVars& p) const;
    00356
    00358                       inline void classify(int i, int group, TePartitionVars& p) const;
    00359
    00361
    00375                       inline void pigeonhole(TePartitionVars& p) const;
    00376
    00378                       inline void loadNodes(TeRTreeNodeType* n, TeRTreeNodeType* q, TePartitionVars& p) const;
    00379
    00381                       double rectArea(const TeBox& b) const
    00382                       {
    00383                                  return b.width() * b.height();
    00384                       }
    00385
    00387                       void erase(TeRTreeNodeType* node)
    00388                       {
    00389                                  if(node->isLeaf())
    00390                                  {
    00391                                             delete node;
    00392
    00393                                             return;
    00394                                  }
    00395
    00396                                  for(int i = 0u; i < node->count_; ++i)
    00397                                             erase(node->branch_[i].child_);
    00398
    00399                                  delete node;
    00400
    00401                                  return;
    00402                       }
    00403
    00405                       bool rtreeBoxIntersects(const TeBox& bx1, const TeBox& bx2) const
    00406                       {
    00407                                  return ::TeIntersects(bx1, bx2);
    00408                       }
    00409
    00410            private:
    00411
    00413                       TeRTree(const TeRTree& other);
    00414
    00416                       TeRTree& operator=(const TeRTree& other);
    00417
    00418 };         // end of class TeRTree
    00419
    00420
    00421 //------------------- Implementation of the templates classes
    00422
    00423 template<class DATATYPE, int MAXNODES, int MINNODES>
    00424 bool TeRTree<DATATYPE, MAXNODES, MINNODES>::insert(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType** root, int level)
    00425 {
    00426 // this is the algorithm insert
    00427     TeRTreeNodeType* newRoot;
    00428            TeRTreeNodeType* newNode;
    00429     TeRTreeBranch    branch;
    00430
    00431     if(chooseLeaf(rect, data, *root, &newNode, level))  // I1
    00432     {
    00433 // I4
    00434 // if root was split
    00435 // grow a new root, make tree taller
    00436                       ++size_;
    00437         newRoot = new TeRTreeNodeType();
    00438
    00439         newRoot->level_ = (*root)->level_ + 1;
    00440
    00441 // first half node
    00442         branch.rect_  = nodeCover(*root);
    00443         branch.child_ = *root;
    00444         addBranch(&branch, newRoot, 0);
    00445
    00446 // second half node
    00447         branch.rect_ = nodeCover(newNode);
    00448         branch.child_ = newNode;
    00449                       addBranch(&branch, newRoot, 0);
    00450
    00451         *root = newRoot;
    00452
    00453         return true;
    00454     }
    00455
    00456     return false;
    00457 }
    00458
    00459 template<class DATATYPE, int MAXNODES, int MINNODES>
    00460 bool TeRTree<DATATYPE, MAXNODES, MINNODES>::remove(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType** root)
    00461 {
    00462            int i;
    00463            TeRTreeNodeType *t;
    00464            vector<TeRTreeNodeType*> reInsertList;
    00465
    00466            if(remove2(rect, data, *root, reInsertList))
    00467            {
    00468 // if we are here, so we have found and deleted a data item
    00469
    00470 // reinsert any branches from eliminated nodes
    00471                       while(!reInsertList.empty())
    00472                       {
    00473                                  t = reInsertList[0];
    00474                                  for(i = 0; i < t->count_; ++i)
    00475                                             insert(t->branch_[i].rect_, t->branch_[i].data_, root, t->level_);
    00476
    00477 // erase node from list
    00478                                  reInsertList.erase(reInsertList.begin());
    00479
    00480 // remove node card from memory
    00481                                  delete t;
    00482                                  --size_;
    00483                       }
    00484
    00485                       /* check for redundant root (not leaf, 1 child) and eliminate */
    00486                       if(((*root)->count_ == 1) && ((*root)->isInternalNode()))
    00487                       {
    00488                                  t = (*root)->branch_[0].child_;
    00489
    00490                                  delete (*root);
    00491                                  --size_;
    00492
    00493                                  *root = t;
    00494                       }
    00495
    00496                       return true;
    00497            }
    00498
    00499            return false;
    00500 }
    00501
    00502 template<class DATATYPE, int MAXNODES, int MINNODES>
    00503 bool TeRTree<DATATYPE, MAXNODES, MINNODES>::remove2(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType* n, vector<TeRTreeNodeType*>& ee)
    00504 {
    00505            int i;
    00506
    00507            if(n->isInternalNode()) /* not a leaf node */
    00508            {
    00509                       for(i = 0; i < n->count_; ++i)
    00510                       {
    00511                                  if(rtreeBoxIntersects(rect, n->branch_[i].rect_))
    00512                                  {
    00513                                             if(remove2(rect, data, n->branch_[i].child_, ee))
    00514                                             {
    00515                                                        if(n->branch_[i].child_->count_ >= MINNODES)
    00516                                                                   n->branch_[i].rect_ = nodeCover(n->branch_[i].child_);
    00517                                                        else
    00518                                                        {
    00519                                                                   /* not enough entries in child, eliminate child node */
    00520                                                                   ee.push_back(n->branch_[i].child_);         //reInsert(n->branch_[i].child_, ee);
    00521                                                                   disconBranch(n, i);
    00522                                                        }
    00523
    00524                                                        return true;          // found item
    00525                                             }
    00526                                  }
    00527                       }
    00528
    00529                       return false;         // din't find item
    00530            }
    00531            else  /* a leaf node */
    00532            {
    00533                       for(i = 0; i < n->count_; ++i)
    00534                       {
    00535                                  if(n->branch_[i].data_ == data)
    00536                                  {
    00537                                             disconBranch(n, i);
    00538                                             return true;          // found item
    00539                                  }
    00540                       }
    00541
    00542                       return false;         // didn't find item
    00543            }
    00544 }
    00545
    00546 /*template<class DATATYPE, int MAXNODES, int MINNODES> void TeRTree<DATATYPE, MAXNODES, MINNODES>::reInsert(TeRTreeNodeType* n, vector<TeRTreeNodeType*>& ee)
    00547 {
    00548            ee.push_back(n);
    00549 }*/
    00550
    00551 template<class DATATYPE, int MAXNODES, int MINNODES>
    00552 void TeRTree<DATATYPE, MAXNODES, MINNODES>::disconBranch(TeRTreeNodeType* n, int i)
    00553 {
    00554 // remove element copying the last element in array
    00555            n->branch_[i] = n->branch_[n->count_ - 1];
    00556
    00557            --(n->count_);
    00558 }
    00559
    00560 // CHOOSELEAF
    00561 template<class DATATYPE, int MAXNODES, int MINNODES>
    00562 bool TeRTree<DATATYPE, MAXNODES, MINNODES>::chooseLeaf(const TeBox& rect, const DATATYPE& data, TeRTreeNodeType* node, TeRTreeNodeType** newNode, int level)
    00563 {
    00564            TeRTreeBranch    b;
    00565            TeRTreeNodeType* n2;
    00566
    00567            if(node->level_ > level)
    00568            {
    00569 // Still above level for insertion, go down tree recursively
    00570                       int i = pickBranch(rect, node);             // CL3
    00571
    00572                       if(!chooseLeaf(rect, data, node->branch_[i].child_, &n2, level))
    00573                       {
    00574 // child was not split
    00575                                  node->branch_[i].rect_ = combineRect(rect, node->branch_[i].rect_);
    00576
    00577                                  return false;
    00578                       }
    00579                       else
    00580                       {
    00581 // child was split
    00582                                  node->branch_[i].rect_ = nodeCover(node->branch_[i].child_);
    00583
    00584                                  b.child_ = n2;
    00585                                  b.rect_ = nodeCover(n2);
    00586
    00587                                  return addBranch(&b, node, newNode);
    00588                       }
    00589            }
    00590            else if (node->level_ == level)
    00591            {
    00592 // have reached level for insertion. Add rect, split if necessary
    00593
    00594                       b.rect_ = rect;
    00595                       //b.child_ = (TeRTreeNodeType*) data;
    00596                       b.data_ = data;
    00597
    00598 // child field of leaves contains tid of data record
    00599                       return addBranch(&b, node, newNode);
    00600            }
    00601            else
    00602            {
    00603 // Not supposed to happen
    00604                       throw;
    00605                       return false;
    00606            }
    00607 }
    00608
    00609 template<class DATATYPE, int MAXNODES, int MINNODES>
    00610 void TeRTree<DATATYPE, MAXNODES, MINNODES>::search(const TeBox& rect, TeRTreeNodeType* node, vector<DATATYPE>& report, int& foundObjs) const
    00611 {
    00612            int i;
    00613 // S1
    00614     if(node->isInternalNode()) // This is an internal node in the tree
    00615            {
    00616         for(i = 0; i < node->count_; ++i)
    00617                       {
    00618             if(rtreeBoxIntersects(rect, node->branch_[i].rect_))
    00619                 search(rect, node->branch_[i].child_, report, foundObjs);
    00620                       }
    00621            }
    00622 // S2
    00623            else       // This is a leaf node
    00624            {
    00625         for(i = 0; i < node->count_; ++i)
    00626                       {
    00627             if(rtreeBoxIntersects(rect, node->branch_[i].rect_))
    00628                                  {
    00629                 DATATYPE& id = node->branch_[i].data_;
    00630
    00631                                             report.push_back(id);
    00632
    00633                 ++foundObjs;
    00634                                  }
    00635                       }
    00636            }
    00637
    00638            return;
    00639 }
    00640
    00641 template<class DATATYPE, int MAXNODES, int MINNODES>
    00642 TeBox TeRTree<DATATYPE, MAXNODES, MINNODES>::nodeCover(TeRTreeNodeType* n) const
    00643 {
    00644            bool flag = true;
    00645
    00646            TeBox r;
    00647
    00648            for(int i = 0; i < n->count_; ++i)
    00649            {
    00650         if(flag)
    00651                       {
    00652                                  r = n->branch_[i].rect_;
    00653                                  flag = false;
    00654                       }
    00655                       else
    00656                                  r = combineRect(r, n->branch_[i].rect_);
    00657            }
    00658
    00659            return r;
    00660 }
    00661
    00662 template<class DATATYPE, int MAXNODES, int MINNODES>
    00663 TeBox TeRTree<DATATYPE, MAXNODES, MINNODES>::combineRect(const TeBox& rectA, const TeBox& rectB) const
    00664 {
    00665     TeBox newRect;
    00666
    00667            newRect.x1_ = MIN(rectA.x1_, rectB.x1_);
    00668            newRect.y1_ = MIN(rectA.y1_, rectB.y1_);
    00669            newRect.x2_ = MAX(rectA.x2_, rectB.x2_);
    00670            newRect.y2_ = MAX(rectA.y2_, rectB.y2_);
    00671
    00672            return newRect;
    00673 }
    00674
    00675 template<class DATATYPE, int MAXNODES, int MINNODES>
    00676 bool TeRTree<DATATYPE, MAXNODES, MINNODES>::addBranch(TeRTreeBranch* branch, TeRTreeNodeType* node, TeRTreeNodeType** newNode) const
    00677 {
    00678     if(node->count_ < MAXNODES)             /* split won't be necessary */
    00679            {
    00680                       node->branch_[node->count_] = *branch;
    00681
    00682                       ++(node->count_);
    00683
    00684                       return false;
    00685            }
    00686            else
    00687            {
    00688         splitNode(node, branch, newNode);
    00689
    00690                       return true;
    00691            }
    00692 }
    00693
    00694 template<class DATATYPE, int MAXNODES, int MINNODES>
    00695 int TeRTree<DATATYPE, MAXNODES, MINNODES>::pickBranch(const TeBox& rect, TeRTreeNodeType* node) const
    00696 {
    00697 // CL3
    00698            bool flag = true;
    00699
    00700            double bestIncr = -1.0;
    00701
    00702            double bestArea = 0.;
    00703
    00704     int best = 0;
    00705
    00706            for(int i = 0; i < node->count_; ++i)
    00707            {
    00708                       TeBox rr = node->branch_[i].rect_;
    00709                       double area = rectArea(rr);
    00710
    00711                       rr = combineRect(rect, rr);
    00712
    00713                       double increase = rectArea(rr) - area;
    00714
    00715         if((increase <  bestIncr) || flag)
    00716                       {
    00717                                  best = i;
    00718
    00719             bestArea = area;
    00720             bestIncr = increase;
    00721
    00722             flag = false;
    00723                       }
    00724                       else if((increase == bestIncr) && (area < bestArea))
    00725                       {
    00726                                  best = i;
    00727                                  bestArea = area;
    00728                                  bestIncr = increase;
    00729                       }
    00730            }
    00731
    00732            return best;
    00733 }
    00734
    00735 template<class DATATYPE, int MAXNODES, int MINNODES>
    00736 void TeRTree<DATATYPE, MAXNODES, MINNODES>::splitNode(TeRTreeNodeType* node, TeRTreeBranch* branch, TeRTreeNodeType** newNode) const
    00737 {
    00738     TePartitionVars partitions;
    00739
    00740 // load all the branches into a buffer, initialize old node
    00741            int level = node->level_;
    00742
    00743            getBranches(node, branch, partitions);
    00744
    00745 // find partition
    00746            methodZero(partitions);
    00747
    00748 // put branches from buffer into 2 nodes according to chosen partition
    00749            ++size_;
    00750
    00751            *newNode = new TeRTreeNodeType();
    00752            (*newNode)->level_ = node->level_ = level;
    00753
    00754            loadNodes(node, *newNode, partitions);
    00755 }
    00756
    00757 template<class DATATYPE, int MAXNODES, int MINNODES>
    00758 void TeRTree<DATATYPE, MAXNODES, MINNODES>::getBranches(TeRTreeNodeType* n, TeRTreeBranch* b, TePartitionVars& p) const
    00759 {
    00760            int i;
    00761 // load the branch buffer
    00762            for(i = 0; i < MAXNODES; ++i)
    00763            {
    00764                       p.branchBuf_[i] = n->branch_[i];
    00765            }
    00766
    00767            p.branchBuf_[MAXNODES] = *b;
    00768
    00769 // calculate rect containing all in the set
    00770            p.coverSplit_ = p.branchBuf_[0].rect_;
    00771
    00772            for(i = 1; i <= MAXNODES; ++i)
    00773                       p.coverSplit_ = combineRect(p.coverSplit_, p.branchBuf_[i].rect_);
    00774
    00775            n->init();
    00776 }
    00777
    00778 template<class DATATYPE, int MAXNODES, int MINNODES>
    00779 void TeRTree<DATATYPE, MAXNODES, MINNODES>::methodZero(TePartitionVars& p) const
    00780 {
    00781            p.init();
    00782            pickSeeds(p);
    00783            pigeonhole(p);
    00784 }
    00785
    00786 template<class DATATYPE, int MAXNODES, int MINNODES>
    00787 void TeRTree<DATATYPE, MAXNODES, MINNODES>::pickSeeds(TePartitionVars& p) const
    00788 {
    00789            double w;
    00790            double separation;
    00791            double bestSep;
    00792            double width[2];
    00793            int leastUpper[2];
    00794            int greatestLower[2];
    00795            int seed0;
    00796            int seed1;
    00797            int i;
    00798 // LPS1
    00799 // find the rectangles farthest out in each direction along dimens "x"
    00800            greatestLower[0] = leastUpper[0] = 0;
    00801
    00802            for(i = 1; i <= MAXNODES; ++i)
    00803            {
    00804                       TeBox& r = p.branchBuf_[i].rect_;
    00805
    00806                       if(r.x1_ > p.branchBuf_[greatestLower[0]].rect_.x1_)
    00807                                  greatestLower[0] = i;
    00808
    00809                       if(r.x2_ < p.branchBuf_[leastUpper[0]].rect_.x2_)
    00810                                  leastUpper[0] = i;
    00811            }
    00812
    00813 // LPS2
    00814 // LPS3
    00815 // find the width of the whole collection along this dimension
    00816            width[0] = p.coverSplit_.x2_ - p.coverSplit_.x1_;
    00817
    00818 // find the rectangles farthest out in each direction along dimens "y"
    00819            greatestLower[1] = leastUpper[1] = 0;
    00820
    00821            for(i = 1; i <= MAXNODES; ++i)
    00822            {
    00823                       TeBox& r = p.branchBuf_[i].rect_;
    00824
    00825                       if(r.y1_ > p.branchBuf_[greatestLower[1]].rect_.y1_)
    00826                                  greatestLower[1] = i;
    00827
    00828                       if(r.y2_ < p.branchBuf_[leastUpper[1]].rect_.y2_)
    00829                                  leastUpper[1] = i;
    00830            }
    00831
    00832 // LPS2
    00833 // LPS3
    00834 // find the width of the whole collection along this dimension
    00835            width[1] = p.coverSplit_.y2_ - p.coverSplit_.y1_;
    00836
    00837
    00838 // pick the best separation dimension and the two seed rects
    00839
    00840 // divisor for normalizing by width
    00841
    00842 // x
    00843            if(width[0] == 0.0)
    00844                       w = 1.0;
    00845            else
    00846                       w = width[0];
    00847
    00848            TeBox rlow  = p.branchBuf_[leastUpper[0]].rect_;
    00849     TeBox rhigh = p.branchBuf_[greatestLower[0]].rect_;
    00850
    00851     seed0 = leastUpper[0];
    00852            seed1 = greatestLower[0];
    00853
    00854            bestSep = (rhigh.x1_ - rlow.x2_) / w;
    00855
    00856 // y
    00857            if(width[1] == 0.0)
    00858                       w = 1.0;
    00859            else
    00860                       w = width[1];
    00861
    00862            rlow  = p.branchBuf_[leastUpper[1]].rect_;
    00863     rhigh = p.branchBuf_[greatestLower[1]].rect_;
    00864
    00865     separation = (rhigh.y1_ - rlow.y2_) / w;
    00866
    00867 // LPS3
    00868            if(separation > bestSep)
    00869            {
    00870                       seed0 = leastUpper[1];
    00871                       seed1 = greatestLower[1];
    00872
    00873                       bestSep = separation;
    00874            }
    00875
    00876            if(seed0 != seed1)
    00877            {
    00878                       classify(seed0, 0, p);
    00879                       classify(seed1, 1, p);
    00880            }
    00881 }
    00882
    00883 template<class DATATYPE, int MAXNODES, int MINNODES>
    00884 void TeRTree<DATATYPE, MAXNODES, MINNODES>::classify(int i, int group, TePartitionVars& p) const
    00885 {
    00886     p.partition_[i] = group;
    00887            p.taken_[i] = 1;
    00888
    00889            if(p.count_[group] == 0)
    00890                       p.cover_[group] = p.branchBuf_[i].rect_;
    00891            else
    00892                       p.cover_[group] = combineRect(p.branchBuf_[i].rect_, p.cover_[group]);
    00893
    00894            p.area_[group] = rectArea(p.cover_[group]);
    00895
    00896            ++(p.count_[group]);
    00897 }
    00898
    00899 template<class DATATYPE, int MAXNODES, int MINNODES>
    00900 void TeRTree<DATATYPE, MAXNODES, MINNODES>::pigeonhole(TePartitionVars& p) const
    00901 {
    00902            TeBox newCover[2];
    00903
    00904            double newArea[2];
    00905            double increase[2];
    00906
    00907            for(int i = 0; i <= MAXNODES; ++i)
    00908            {
    00909                       if(p.taken_[i] == 0)
    00910                       {
    00911 // if one group too full, put rect in the other regardless
    00912                                  if(p.count_[0] >= (MAXNODES + 1 - MINNODES))
    00913                                  {
    00914                                             classify(i, 1, p);
    00915
    00916                                             continue;
    00917                                  }
    00918                                  else if(p.count_[1] >= (MAXNODES + 1 - MINNODES))
    00919                                  {
    00920                                             classify(i, 0, p);
    00921
    00922                                             continue;
    00923                                  }
    00924
    00925 // find the areas of the two groups' old and new covers
    00926                                  for(int group = 0; group < 2; ++group)
    00927                                  {
    00928                                             if(p.count_[group] > 0)
    00929                                             {
    00930                                                        newCover[group] = combineRect(p.branchBuf_[i].rect_, p.cover_[group]);
    00931                                             }
    00932                                             else
    00933                                             {
    00934                                                        newCover[group] = p.branchBuf_[i].rect_;
    00935                                             }
    00936
    00937                                             newArea[group] = rectArea(newCover[group]);
    00938                                             increase[group] = newArea[group] - p.area_[group];
    00939                                  }
    00940
    00941 // put rect in group whose cover will need to expand less
    00942                                  if(increase[0] < increase[1])
    00943                                             classify(i, 0, p);
    00944                                  else if(increase[1] < increase[0])
    00945                                             classify(i, 1, p);
    00946 // put rect in group that will have a smaller area cover
    00947                                  else if(p.area_[0] < p.area_[1])
    00948                                             classify(i, 0, p);
    00949                                  else if(p.area_[1] < p.area_[0])
    00950                                             classify(i, 1, p);
    00951 // put rect in group with fewer elements
    00952                                  else if(p.count_[0] < p.count_[1])
    00953                                             classify(i, 0, p);
    00954                                  else
    00955                                             classify(i, 1, p);
    00956                       }
    00957            }
    00958 }
    00959
    00960 template<class DATATYPE, int MAXNODES, int MINNODES>
    00961 void TeRTree<DATATYPE, MAXNODES, MINNODES>::loadNodes(TeRTreeNodeType* n, TeRTreeNodeType* q, TePartitionVars& p) const
    00962 {
    00963            for(int i = 0; i <= MAXNODES; ++i)
    00964            {
    00965                       if(p.partition_[i] == 0)
    00966                                  addBranch(&(p.branchBuf_[i]), n, 0);
    00967                       else if(p.partition_[i] == 1)
    00968                                  addBranch(&(p.branchBuf_[i]), q, 0);
    00969                       //else
    00970                       //         throw;     // ERROR
    00971            }
    00972 }
    00973 };         // end namespace TeSAM
    00974
    00975
    00976 #endif     // __TERRALIB_INTERNAL_RTREE_H
    00977
    00978
    00979
    00980

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines