![]() |
Tulip
4.6.0
Better Visualization Through Research
|
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