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