Tulip  5.7.4
Large graphs analysis and drawing
QuadTree.h
1 /*
2  *
3  * This file is part of Tulip (https://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>
36 class QuadTreeNode {
37 
38 public:
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  * Constructor, 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] = nullptr;
53  }
54  /**
55  * Basic destructor
56  */
57  ~QuadTreeNode() {
58  for (int i = 0; i < 4; ++i)
59  if (children[i] != nullptr)
60  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] != nullptr)
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] != nullptr)
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 several items 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,
138  float ratio = 1000.) const {
139  assert(_box.isValid());
140  assert(box.isValid());
141 
142  if (_box.intersect(box)) {
143  float xRatio = (box[1][0] - box[0][0]) / (_box[1][0] - _box[0][0]);
144  float yRatio = (box[1][1] - box[0][1]) / (_box[1][1] - _box[0][1]);
145 
146  // elements are big enough and all of them must be displayed
147  if (xRatio < ratio || yRatio < ratio) {
148  for (size_t i = 0; i < entities.size(); ++i) {
149  result.push_back(entities[i]);
150  }
151 
152  for (unsigned int i = 0; i < 4; ++i) {
153  if (children[i] != nullptr)
154  children[i]->getElementsWithRatio(box, result, ratio);
155  }
156  }
157  // elements are too small return only one elements (we must search it)
158  else {
159  bool find = false;
160 
161  if (!entities.empty()) {
162  result.push_back(entities[0]);
163  find = true;
164  }
165 
166  if (!find) {
167  for (unsigned int i = 0; i < 4; ++i) {
168  if (children[i] != nullptr && children[i]->_box.intersect(box)) {
169  // if children[i]!=nullptr we are sure to find an elements in that branch of the tree
170  // thus we do not have to explore the other branches.
171  children[i]->getElementsWithRatio(box, result, ratio);
172  break;
173  }
174  }
175  }
176  }
177  }
178  }
179 
180 private:
181  //======================================
182  QuadTreeNode *getChild(int i) {
183  if (children[i] == nullptr) {
184  Rectangle<float> box(getChildBox(i));
185 
186  if (box[0] == _box[0] && box[1] == _box[1])
187  return nullptr;
188 
189  children[i] = new QuadTreeNode<TYPE>(box);
190  }
191 
192  return children[i];
193  }
194  //======================================
195  Rectangle<float> getChildBox(int i) {
196  assert(_box.isValid());
197  // A***I***B
198  // *-------*
199  // E---F---G
200  // *-------*
201  // *-------*
202  // D***H***C
203  // 0 => AIFE
204  // 1 => IBGF
205  // 2 => FGCH
206  // 3 => FHDE
207  Vec2f I;
208  I[0] = (_box[0][0] + _box[1][0]) / 2.;
209  I[1] = _box[0][1];
210  Vec2f E;
211  E[0] = _box[0][0];
212  E[1] = (_box[0][1] + _box[1][1]) / 2.;
213  Vec2f F;
214  F[0] = I[0];
215  F[1] = E[1];
216  Vec2f G;
217  G[0] = _box[1][0];
218  G[1] = F[1];
219  Vec2f H;
220  H[0] = F[0];
221  H[1] = _box[1][1];
222 
223  switch (i) {
224  case 0:
225  return Rectangle<float>(_box[0], F);
226  break;
227 
228  case 1:
229  return Rectangle<float>(I, G);
230  break;
231 
232  case 2:
233  return Rectangle<float>(F, _box[1]);
234  break;
235 
236  case 3:
237  return Rectangle<float>(E, H);
238 
239  default:
240  tlp::error() << "ERROR" << __PRETTY_FUNCTION__ << std::endl;
241  exit(1);
242  }
243  }
244  //======================================
245  QuadTreeNode *children[4];
246  std::vector<TYPE> entities;
247  tlp::Rectangle<float> _box;
248 };
249 } // namespace tlp
250 
251 #endif // QUADTREE_H
252 
253 ///@endcond