Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/QuadTree.h
00001 /*
00002  *
00003  * This file is part of Tulip (www.tulip-software.org)
00004  *
00005  * Authors: David Auber and the Tulip development Team
00006  * from LaBRI, University of Bordeaux
00007  *
00008  * Tulip is free software; you can redistribute it and/or modify
00009  * it under the terms of the GNU Lesser General Public License
00010  * as published by the Free Software Foundation, either version 3
00011  * of the License, or (at your option) any later version.
00012  *
00013  * Tulip is distributed in the hope that it will be useful,
00014  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00015  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
00016  * See the GNU General Public License for more details.
00017  *
00018  */
00019 ///@cond DOXYGEN_HIDDEN
00020 
00021 #ifndef QUADTREE_H
00022 #define QUADTREE_H
00023 
00024 #include <vector>
00025 
00026 #include <tulip/Rectangle.h>
00027 #include <tulip/Coord.h>
00028 
00029 namespace tlp {
00030 
00031 /** \brief QuadTree template class
00032  *
00033  * This class provide QuadTree system
00034  */
00035 template <class TYPE> class QuadTreeNode {
00036 
00037 public:
00038 
00039   //======================================
00040   /*
00041      * build a new Quadtree
00042      * to work correctly box should be the bounding box
00043      * of all elements inserted in that QuadTree
00044      */
00045   /**
00046    * Contructor, you have to put the global bounding box of the quadtree
00047    */
00048   QuadTreeNode(const tlp::Rectangle<float> &box):_box(box) {
00049     assert(_box.isValid());
00050 
00051     for(int i=0; i<4; ++i)
00052       children[i] = 0;
00053   }
00054   /**
00055    * Basic destructor
00056    */
00057   ~QuadTreeNode() {
00058     for(int i=0; i<4; ++i)
00059       if (children[i] != NULL) delete children[i];
00060   }
00061   /**
00062    * Insert an element in the quadtree
00063    */
00064   void insert(const tlp::Rectangle<float> &box, const TYPE id) {
00065     assert(box.isValid());
00066     assert(_box.isValid());
00067 
00068     if (box[0]==box[1])
00069       return;
00070 
00071     //Check for infini recursion : check if we are on float limit case
00072     Vec2f subBox((_box[0]+_box[1])/2.f);
00073 
00074     if( !((subBox == _box[0]) || (subBox == _box[1]))) {
00075       for (int i=0; i<4; ++i) {
00076         if (getChildBox(i).isInside(box)) {
00077           QuadTreeNode *child=getChild(i);
00078 
00079           if(child)
00080             child->insert(box, id);
00081           else
00082             entities.push_back(id);
00083 
00084           return;
00085         }
00086       }
00087     }
00088 
00089     entities.push_back(id);
00090   }
00091   /**
00092    * return all elements that could be in
00093    * the given box (the function ensures that
00094    * all elements inside the box are return. However
00095    * some elements not inside the box can be returned.
00096    */
00097   void getElements(const tlp::Rectangle<float> &box, std::vector<TYPE> &result) const {
00098     assert(box.isValid());
00099     assert(_box.isValid());
00100 
00101     if (_box.intersect(box)) {
00102       for (size_t i=0; i<entities.size(); ++i) {
00103         result.push_back(entities[i]);
00104       }
00105 
00106       for (unsigned int i=0; i<4; ++i) {
00107         if (children[i]!=NULL)
00108           children[i]->getElements(box, result);
00109       }
00110     }
00111   }
00112 
00113   /**
00114    * Return all elements of the quadtree
00115    */
00116   void getElements(std::vector<TYPE> &result) const {
00117     for (size_t i=0; i<entities.size(); ++i) {
00118       result.push_back(entities[i]);
00119     }
00120 
00121     for (unsigned int i=0; i<4; ++i) {
00122       if (children[i]!=NULL)
00123         children[i]->getElements(result);
00124     }
00125   }
00126 
00127   /**
00128    * same as getElements, however if the size of the elements are to small compare
00129    * to the size of the box (equivalent to have severeal item at the same position on the screen)
00130    * only one elements is returned for the small cells.
00131    * The ratio should fixed according to the number of pixels displayed.
00132    * If we have a 1000*800 screen we can merge items of box into a single item if
00133    * the size of box is max(1000,800) times smaller than the box given in parameter.
00134    * so the ratio should be 1000.(merge elements that are 1000 times smaller
00135    */
00136   void getElementsWithRatio(const tlp::Rectangle<float> &box, std::vector<TYPE> &result, float ratio = 1000.) const {
00137     assert(_box.isValid());
00138     assert(box.isValid());
00139 
00140     if (_box.intersect(box)) {
00141       float xRatio = (box[1][0] - box[0][0]) / (_box[1][0] - _box[0][0]) ;
00142       float yRatio = (box[1][1] - box[0][1]) / (_box[1][1] - _box[0][1]);
00143 
00144       //elements are big enough and all of them must be displayed
00145       if (xRatio < ratio || yRatio < ratio) {
00146         for (size_t i=0; i<entities.size(); ++i) {
00147           result.push_back(entities[i]);
00148         }
00149 
00150         for (unsigned int i=0; i<4; ++i) {
00151           if (children[i]!=NULL)
00152             children[i]->getElementsWithRatio(box, result, ratio);
00153         }
00154       }
00155       //elements are too small return only one elements (we must seach it)
00156       else {
00157         bool find=false;
00158 
00159         if (entities.size() > 0) {
00160           result.push_back(entities[0]);
00161           find=true;
00162         }
00163 
00164         if(!find) {
00165           for (unsigned int i=0; i<4; ++i) {
00166             if (children[i]!=NULL && children[i]->_box.intersect(box)) {
00167               //if children[i]!=NULL we are sure to find an elements in that branch of the tree
00168               //thus we do not have to explore the other branches.
00169               children[i]->getElementsWithRatio(box, result, ratio);
00170               break;
00171             }
00172           }
00173         }
00174       }
00175     }
00176   }
00177 
00178 private:
00179   //======================================
00180   QuadTreeNode* getChild(int i) {
00181     if (children[i] == 0) {
00182       Rectangle<float> box (getChildBox(i));
00183 
00184       if(box[0] ==_box[0] && box[1]==_box[1])
00185         return NULL;
00186 
00187       children[i] = new QuadTreeNode<TYPE>(box);
00188     }
00189 
00190     return children[i];
00191   }
00192   //======================================
00193   Rectangle<float> getChildBox(int i) {
00194     assert(_box.isValid());
00195     // A***I***B
00196     // *-------*
00197     // E---F---G
00198     // *-------*
00199     // *-------*
00200     // D***H***C
00201     // 0 => AIFE
00202     // 1 => IBGF
00203     // 2 => FGCH
00204     // 3 => FHDE
00205     Vec2f I;
00206     I[0] = (_box[0][0] + _box[1][0]) / 2.;
00207     I[1] = _box[0][1];
00208     Vec2f E;
00209     E[0] =  _box[0][0];
00210     E[1] = (_box[0][1] + _box[1][1]) / 2.;
00211     Vec2f F;
00212     F[0] = I[0];
00213     F[1] = E[1];
00214     Vec2f G;
00215     G[0] = _box[1][0];
00216     G[1] = F[1];
00217     Vec2f H;
00218     H[0] = F[0];
00219     H[1] = _box[1][1];
00220 
00221     switch(i) {
00222     case 0:
00223       return Rectangle<float>(_box[0], F);
00224       break;
00225 
00226     case 1:
00227       return Rectangle<float>(I, G);
00228       break;
00229 
00230     case 2:
00231       return Rectangle<float>(F, _box[1]);
00232       break;
00233 
00234     case 3:
00235       return Rectangle<float>(E, H);
00236 
00237     default:
00238       tlp::error() << "ERROR" << __PRETTY_FUNCTION__  << std::endl;
00239       exit(1);
00240     }
00241   }
00242   //======================================
00243   QuadTreeNode *children[4];
00244   std::vector<TYPE> entities;
00245   tlp::Rectangle<float> _box;
00246 };
00247 
00248 }
00249 
00250 #endif // QUADTREE_H
00251 
00252 ///@endcond
 All Classes Files Functions Variables Enumerations Enumerator Properties