Tulip 5.7.1
Large graphs analysis and drawing
Loading...
Searching...
No Matches
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
29namespace tlp {
30
31/** \brief QuadTree template class
32 *
33 * This class provide QuadTree system
34 */
35template <class TYPE>
36class QuadTreeNode {
37
38public:
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
180private:
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