Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
test-quadtree.C
Go to the documentation of this file.
1
2/* Aleph-w
3
4 / \ | | ___ _ __ | |__ __ __
5 / _ \ | |/ _ \ '_ \| '_ \ ____\ \ /\ / / Data structures & Algorithms
6 / ___ \| | __/ |_) | | | |_____\ V V / version 1.9c
7 /_/ \_\_|\___| .__/|_| |_| \_/\_/ https://github.com/lrleon/Aleph-w
8 |_|
9
10 This file is part of Aleph-w library
11
12 Copyright (c) 2002-2018 Leandro Rabindranath Leon
13
14 Permission is hereby granted, free of charge, to any person obtaining a copy
15 of this software and associated documentation files (the "Software"), to deal
16 in the Software without restriction, including without limitation the rights
17 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
18 copies of the Software, and to permit persons to whom the Software is
19 furnished to do so, subject to the following conditions:
20
21 The above copyright notice and this permission notice shall be included in all
22 copies or substantial portions of the Software.
23
24 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
25 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
26 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
27 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
28 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
29 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
30 SOFTWARE.
31*/
32# include <iostream>
33# include <cassert>
34
35# include <quadtree.H>
36
37using namespace std;
38
39using Tree = QuadTree;
40
41void write_tree(Tree::Node * root, size_t indent)
42{
43 for (size_t i = 0; i < indent; ++i)
44 cout << "-";
45
46 if (not root->is_leaf())
47 {
48 cout << endl;
49 write_tree(NW_CHILD(root), indent + 2);
50 write_tree(NE_CHILD(root), indent + 2);
51 write_tree(SW_CHILD(root), indent + 2);
52 write_tree(SE_CHILD(root), indent + 2);
53 return;
54 }
55
56 root->for_each_point([](const Point & p) { cout << p.to_string(); });
57 cout << endl;
58}
59
60int main()
61{
62 Tree tree(0, 100, 0, 100, 4);
63
64 tree.insert(5, 5);
65
66 tree.insert(95, 5);
67
68 tree.insert(5, 95);
69
70 tree.insert(95, 95);
71
72
73 Tree::Node * root = tree.get_root();
74
75 assert(root->is_leaf());
76 assert(root->get_num_points() == 4);
77
78 write_tree(root, 2);
79
80 tree.insert(Point(5, 45));
81
82 // Re-acquire root pointer and its children after mutation
83 root = tree.get_root();
84
85 assert(not root->is_leaf());
86 assert(root->get_num_points() == 5);
87
88 Tree::Node * root_nw_child = NW_CHILD(root);
89 assert(root_nw_child != nullptr);
90 assert(root_nw_child->is_leaf());
91 assert(root_nw_child->get_num_points() == 2);
92
93 Tree::Node * root_ne_child = NE_CHILD(root);
94 assert(root_ne_child != nullptr);
95 assert(root_ne_child->is_leaf());
96 assert(root_ne_child->get_num_points() == 1);
97
98 Tree::Node * root_sw_child = SW_CHILD(root);
99 assert(root_sw_child != nullptr);
100 assert(root_sw_child->is_leaf());
101 assert(root_sw_child->get_num_points() == 1);
102
103 Tree::Node * root_se_child = SE_CHILD(root);
104 assert(root_se_child != nullptr);
105 assert(root_se_child->is_leaf());
106 assert(root_se_child->get_num_points() == 1);
107
108 cout << endl;
109 write_tree(root, 2);
110
111 tree.insert(Point(45, 5));
112
113 tree.insert(Point(45, 45));
114
115 tree.insert(Point(20, 20));
116
117 // Re-acquire root pointer after mutations
118 root = tree.get_root();
119 root_nw_child = NW_CHILD(root);
120 root_ne_child = NE_CHILD(root);
121 root_sw_child = SW_CHILD(root);
122 root_se_child = SE_CHILD(root);
123
124 assert(root->get_num_points() == 8);
125
126 assert(root_nw_child->get_num_points() == 5);
127 assert(root_ne_child->get_num_points() == 1);
128 assert(root_sw_child->get_num_points() == 1);
129 assert(root_se_child->get_num_points() == 1);
130
131 assert(not root->is_leaf());
132 assert(not root_nw_child->is_leaf());
133 assert(root_ne_child->is_leaf());
134 assert(root_sw_child->is_leaf());
135 assert(root_se_child->is_leaf());
136
137 Tree::Node * root_nw_child_nw_child = NW_CHILD(root_nw_child);
138 assert(root_nw_child_nw_child != nullptr);
139 assert(root_nw_child_nw_child->is_leaf());
140 assert(root_nw_child_nw_child->get_num_points() == 2);
141
142 Tree::Node * root_nw_child_ne_child = NE_CHILD(root_nw_child);
143 assert(root_nw_child_ne_child != nullptr);
144 assert(root_nw_child_ne_child->is_leaf());
145 assert(root_nw_child_ne_child->get_num_points() == 1);
146
147 Tree::Node * root_nw_child_sw_child = SW_CHILD(root_nw_child);
148 assert(root_nw_child_sw_child != nullptr);
149 assert(root_nw_child_sw_child->is_leaf());
150 assert(root_nw_child_sw_child->get_num_points() == 1);
151
152 Tree::Node * root_nw_child_se_child = SE_CHILD(root_nw_child);
153 assert(root_nw_child_se_child != nullptr);
154 assert(root_nw_child_se_child->is_leaf());
155 assert(root_nw_child_se_child->get_num_points() == 1);
156
157 cout << endl;
158 write_tree(root, 2);
159
160 tree.insert(Point(30, 30));
161 tree.insert(Point(45, 30));
162 tree.insert(Point(30, 45));
163 tree.insert(Point(30, 40));
164
165 // Re-acquire pointers after mutations
166 root = tree.get_root();
167 root_nw_child = NW_CHILD(root);
168 root_ne_child = NE_CHILD(root);
169 root_sw_child = SW_CHILD(root);
170 root_se_child = SE_CHILD(root);
171 root_nw_child_nw_child = NW_CHILD(root_nw_child);
172 root_nw_child_ne_child = NE_CHILD(root_nw_child);
173 root_nw_child_sw_child = SW_CHILD(root_nw_child);
174 root_nw_child_se_child = SE_CHILD(root_nw_child);
175
176 assert(not root->is_leaf());
177 assert(not root_nw_child->is_leaf());
178 assert(root_nw_child_nw_child->is_leaf());
179 assert(root_nw_child_ne_child->is_leaf());
180 assert(root_nw_child_sw_child->is_leaf());
181 assert(not root_nw_child_se_child->is_leaf());
182 assert(root_ne_child->is_leaf());
183 assert(root_sw_child->is_leaf());
184 assert(root_se_child->is_leaf());
185
186 assert(root->get_num_points() == 12);
187 assert(root_nw_child->get_num_points() == 9);
188 assert(root_nw_child_se_child->get_num_points() == 5);
189
190 Tree::Node * root_nw_child_se_child_nw_child =
191 NW_CHILD(root_nw_child_se_child);
192 assert(root_nw_child_se_child_nw_child != nullptr);
193 assert(root_nw_child_se_child_nw_child->is_leaf());
194 assert(root_nw_child_se_child_nw_child->get_num_points() == 1);
195
196 Tree::Node * root_nw_child_se_child_ne_child =
197 NE_CHILD(root_nw_child_se_child);
198 assert(root_nw_child_se_child_ne_child != nullptr);
199 assert(root_nw_child_se_child_ne_child->is_leaf());
200 assert(root_nw_child_se_child_ne_child->get_num_points() == 1);
201
202 Tree::Node * root_nw_child_se_child_sw_child =
203 SW_CHILD(root_nw_child_se_child);
204 assert(root_nw_child_se_child_sw_child != nullptr);
205 assert(root_nw_child_se_child_sw_child->is_leaf());
206 assert(root_nw_child_se_child_sw_child->get_num_points() == 2);
207
208 Tree::Node * root_nw_child_se_child_se_child =
209 SE_CHILD(root_nw_child_se_child);
210 assert(root_nw_child_se_child_se_child != nullptr);
211 assert(root_nw_child_se_child_se_child->is_leaf());
212 assert(root_nw_child_se_child_se_child->get_num_points() == 1);
213
214 cout << endl;
215 write_tree(root, 2);
216
217 tree.remove(Point(20, 20));
218
219 // Re-acquire pointers after removal
220 root = tree.get_root();
221 root_nw_child = NW_CHILD(root);
222 root_ne_child = NE_CHILD(root);
223 root_sw_child = SW_CHILD(root);
224 root_se_child = SE_CHILD(root);
225 root_nw_child_nw_child = NW_CHILD(root_nw_child);
226 root_nw_child_ne_child = NE_CHILD(root_nw_child);
227 root_nw_child_sw_child = SW_CHILD(root_nw_child);
228 root_nw_child_se_child = SE_CHILD(root_nw_child);
229
230 assert(not root->is_leaf());
231 assert(not root_nw_child->is_leaf());
232 assert(root_nw_child_nw_child->is_leaf());
233 assert(root_nw_child_ne_child->is_leaf());
234 assert(root_nw_child_sw_child->is_leaf());
235 assert(not root_nw_child_se_child->is_leaf());
236 assert(root_ne_child->is_leaf());
237 assert(root_sw_child->is_leaf());
238 assert(root_se_child->is_leaf());
239
240 assert(root->get_num_points() == 11);
241 assert(root_nw_child->get_num_points() == 8);
242 assert(root_nw_child_se_child->get_num_points() == 5);
243 assert(root_nw_child_se_child_nw_child->is_leaf());
244 assert(root_nw_child_se_child_nw_child->get_num_points() == 1);
245 assert(root_nw_child_se_child_ne_child->is_leaf());
246 assert(root_nw_child_se_child_ne_child->get_num_points() == 1);
247 assert(root_nw_child_se_child_sw_child->is_leaf());
248 assert(root_nw_child_se_child_sw_child->get_num_points() == 2);
249 assert(root_nw_child_se_child_se_child->is_leaf());
250 assert(root_nw_child_se_child_se_child->get_num_points() == 1);
251
252 cout << endl;
253 write_tree(root, 2);
254
255 tree.remove(Point(45, 45));
256
257 // Re-acquire pointers after removal
258 root = tree.get_root();
259 root_nw_child = NW_CHILD(root);
260 root_ne_child = NE_CHILD(root);
261 root_sw_child = SW_CHILD(root);
262 root_se_child = SE_CHILD(root);
263 root_nw_child_nw_child = NW_CHILD(root_nw_child);
264 root_nw_child_ne_child = NE_CHILD(root_nw_child);
265 root_nw_child_sw_child = SW_CHILD(root_nw_child);
266 root_nw_child_se_child = SE_CHILD(root_nw_child);
267
268 assert(not root->is_leaf());
269 assert(not root_nw_child->is_leaf());
270 assert(root_nw_child_nw_child->is_leaf());
271 assert(root_nw_child_ne_child->is_leaf());
272 assert(root_nw_child_sw_child->is_leaf());
273 assert(root_nw_child_se_child->is_leaf());
274 assert(root_ne_child->is_leaf());
275 assert(root_sw_child->is_leaf());
276 assert(root_se_child->is_leaf());
277
278 assert(root->get_num_points() == 10);
279 assert(root_nw_child->get_num_points() == 7);
280 assert(root_nw_child_se_child->get_num_points() == 4);
281
282 cout << endl;
283 write_tree(root, 2);
284
285 cout << "\nQuadtree ok!\n";
286
287 return 0;
288}
289
Aleph::Point
Represents a point with rectangular coordinates in a 2D plane.
Definition point.H:221
Aleph::Point::to_string
std::string to_string() const
Returns a string representation of the point as "(x,y)".
Definition point.H:640
QuadNode
Node for QuadTree spatial data structure.
Definition quadnode.H:94
QuadTree
QuadTree - Hierarchical spatial index for 2D points.
Definition quadtree.H:126
QuadTree::remove
void remove(const Point &p)
Remove a point from the tree.
Definition quadtree.H:565
QuadTree::insert
Point * insert(Node *&r, const Point &p)
Recursive insert helper.
Definition quadtree.H:281
QuadTree::get_root
Node * get_root() noexcept
Get the root node.
Definition quadtree.H:451
root
__gmp_expr< T, __gmp_binary_expr< __gmp_expr< T, U >, unsigned long int, __gmp_root_function > > root(const __gmp_expr< T, U > &expr, unsigned long int l)
Definition gmpfrxx.h:4071
Aleph::blossom_maximum_cardinality_matching
size_t blossom_maximum_cardinality_matching(const GT &g, DynDlist< typename GT::Arc * > &matching, SA sa=SA())
Alias of compute_maximum_cardinality_general_matching().
Definition Blossom.H:466
std
STL namespace.
SE_CHILD
#define SE_CHILD(p)
Definition quadnode.H:57
NE_CHILD
#define NE_CHILD(p)
Definition quadnode.H:55
NW_CHILD
#define NW_CHILD(p)
Definition quadnode.H:54
SW_CHILD
#define SW_CHILD(p)
Definition quadnode.H:56
quadtree.H
QuadTree spatial data structure for efficient 2D point indexing.
write_tree
void write_tree(Tree::Node *root, size_t indent)
Definition test-quadtree.C:41
main
int main()
Definition test-quadtree.C:60