Tulip  5.1.0
Large graphs analysis and drawing
QuadTree.h
1 /*
2  *
3  * This file is part of Tulip (http://tulip.labri.fr)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 ///@cond DOXYGEN_HIDDEN
20 
21 #ifndef QUADTREE_H
22 #define QUADTREE_H
23 
24 #include <vector>
25 
26 #include <tulip/Rectangle.h>
27 #include <tulip/Coord.h>
28 
29 namespace tlp {
30 
31 /** \brief QuadTree template class
32  *
33  * This class provide QuadTree system
34  */
35 template <class TYPE> class QuadTreeNode {
36 
37 public:
38 
39  //======================================
40  /*
41  * build a new Quadtree
42  * to work correctly box should be the bounding box
43  * of all elements inserted in that QuadTree
44  */
45  /**
46  * Contructor, you have to put the global bounding box of the quadtree
47  */
48  QuadTreeNode(const tlp::Rectangle<float> &box):_box(box) {
49  assert(_box.isValid());
50 
51  for(int i=0; i<4; ++i)
52  children[i] = 0;
53  }
54  /**
55  * Basic destructor
56  */
57  ~QuadTreeNode() {
58  for(int i=0; i<4; ++i)
59  if (children[i] != NULL) delete children[i];
60  }
61  /**
62  * Insert an element in the quadtree
63  */
64  void insert(const tlp::Rectangle<float> &box, const TYPE id) {
65  assert(box.isValid());
66  assert(_box.isValid());
67 
68  if (box[0]==box[1])
69  return;
70 
71  //Check for infini recursion : check if we are on float limit case
72  Vec2f subBox((_box[0]+_box[1])/2.f);
73 
74  if( !((subBox == _box[0]) || (subBox == _box[1]))) {
75  for (int i=0; i<4; ++i) {
76  if (getChildBox(i).isInside(box)) {
77  QuadTreeNode *child=getChild(i);
78 
79  if(child)
80  child->insert(box, id);
81  else
82  entities.push_back(id);
83 
84  return;
85  }
86  }
87  }
88 
89  entities.push_back(id);
90  }
91  /**
92  * return all elements that could be in
93  * the given box (the function ensures that
94  * all elements inside the box are return. However
95  * some elements not inside the box can be returned.
96  */
97  void getElements(const tlp::Rectangle<float> &box, std::vector<TYPE> &result) const {
98  assert(box.isValid());
99  assert(_box.isValid());
100 
101  if (_box.intersect(box)) {
102  for (size_t i=0; i<entities.size(); ++i) {
103  result.push_back(entities[i]);
104  }
105 
106  for (unsigned int i=0; i<4; ++i) {
107  if (children[i]!=NULL)
108  children[i]->getElements(box, result);
109  }
110  }
111  }
112 
113  /**
114  * Return all elements of the quadtree
115  */
116  void getElements(std::vector<TYPE> &result) const {
117  for (size_t i=0; i<entities.size(); ++i) {
118  result.push_back(entities[i]);
119  }
120 
121  for (unsigned int i=0; i<4; ++i) {
122  if (children[i]!=NULL)
123  children[i]->getElements(result);
124  }
125  }
126 
127  /**
128  * same as getElements, however if the size of the elements are to small compare
129  * to the size of the box (equivalent to have severeal item at the same position on the screen)
130  * only one elements is returned for the small cells.
131  * The ratio should fixed according to the number of pixels displayed.
132  * If we have a 1000*800 screen we can merge items of box into a single item if
133  * the size of box is max(1000,800) times smaller than the box given in parameter.
134  * so the ratio should be 1000.(merge elements that are 1000 times smaller
135  */
136  void getElementsWithRatio(const tlp::Rectangle<float> &box, std::vector<TYPE> &result, float ratio = 1000.) const {
137  assert(_box.isValid());
138  assert(box.isValid());
139 
140  if (_box.intersect(box)) {
141  float xRatio = (box[1][0] - box[0][0]) / (_box[1][0] - _box[0][0]) ;
142  float yRatio = (box[1][1] - box[0][1]) / (_box[1][1] - _box[0][1]);
143 
144  //elements are big enough and all of them must be displayed
145  if (xRatio < ratio || yRatio < ratio) {
146  for (size_t i=0; i<entities.size(); ++i) {
147  result.push_back(entities[i]);
148  }
149 
150  for (unsigned int i=0; i<4; ++i) {
151  if (children[i]!=NULL)
152  children[i]->getElementsWithRatio(box, result, ratio);
153  }
154  }
155  //elements are too small return only one elements (we must seach it)
156  else {
157  bool find=false;
158 
159  if (entities.size() > 0) {
160  result.push_back(entities[0]);
161  find=true;
162  }
163 
164  if(!find) {
165  for (unsigned int i=0; i<4; ++i) {
166  if (children[i]!=NULL && children[i]->_box.intersect(box)) {
167  //if children[i]!=NULL we are sure to find an elements in that branch of the tree
168  //thus we do not have to explore the other branches.
169  children[i]->getElementsWithRatio(box, result, ratio);
170  break;
171  }
172  }
173  }
174  }
175  }
176  }
177 
178 private:
179  //======================================
180  QuadTreeNode* getChild(int i) {
181  if (children[i] == 0) {
182  Rectangle<float> box (getChildBox(i));
183 
184  if(box[0] ==_box[0] && box[1]==_box[1])
185  return NULL;
186 
187  children[i] = new QuadTreeNode<TYPE>(box);
188  }
189 
190  return children[i];
191  }
192  //======================================
193  Rectangle<float> getChildBox(int i) {
194  assert(_box.isValid());
195  // A***I***B
196  // *-------*
197  // E---F---G
198  // *-------*
199  // *-------*
200  // D***H***C
201  // 0 => AIFE
202  // 1 => IBGF
203  // 2 => FGCH
204  // 3 => FHDE
205  Vec2f I;
206  I[0] = (_box[0][0] + _box[1][0]) / 2.;
207  I[1] = _box[0][1];
208  Vec2f E;
209  E[0] = _box[0][0];
210  E[1] = (_box[0][1] + _box[1][1]) / 2.;
211  Vec2f F;
212  F[0] = I[0];
213  F[1] = E[1];
214  Vec2f G;
215  G[0] = _box[1][0];
216  G[1] = F[1];
217  Vec2f H;
218  H[0] = F[0];
219  H[1] = _box[1][1];
220 
221  switch(i) {
222  case 0:
223  return Rectangle<float>(_box[0], F);
224  break;
225 
226  case 1:
227  return Rectangle<float>(I, G);
228  break;
229 
230  case 2:
231  return Rectangle<float>(F, _box[1]);
232  break;
233 
234  case 3:
235  return Rectangle<float>(E, H);
236 
237  default:
238  tlp::error() << "ERROR" << __PRETTY_FUNCTION__ << std::endl;
239  exit(1);
240  }
241  }
242  //======================================
243  QuadTreeNode *children[4];
244  std::vector<TYPE> entities;
245  tlp::Rectangle<float> _box;
246 };
247 
248 }
249 
250 #endif // QUADTREE_H
251 
252 ///@endcond