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 This program is free software: you can redistribute it and/or modify
15 it under the terms of the GNU General Public License as published by
16 the Free Software Foundation, either version 3 of the License, or
17 (at your option) any later version.
18
19 This program is distributed in the hope that it will be useful, but
20 WITHOUT ANY WARRANTY; without even the implied warranty of
21 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
22 General Public License for more details.
23
24 You should have received a copy of the GNU General Public License
25 along with this program. If not, see <https://www.gnu.org/licenses/>.
26*/
27# include <iostream>
28# include <cassert>
29
30# include <quadtree.H>
31
32using namespace std;
33
34using Tree = QuadTree;
35
36void write_tree(Tree::Node * root, size_t indent)
37{
38 for (size_t i = 0; i < indent; ++i)
39 cout << "-";
40
41 if (not root->is_leaf())
42 {
43 cout << endl;
44 write_tree(NW_CHILD(root), indent + 2);
45 write_tree(NE_CHILD(root), indent + 2);
46 write_tree(SW_CHILD(root), indent + 2);
47 write_tree(SE_CHILD(root), indent + 2);
48 return;
49 }
50
51 root->for_each_point([](const Point & p) { cout << p.to_string(); });
52 cout << endl;
53}
54
55int main()
56{
57 Tree tree(0, 100, 0, 100, 4);
58
59 tree.insert(5, 5);
60
61 tree.insert(95, 5);
62
63 tree.insert(5, 95);
64
65 tree.insert(95, 95);
66
67
68 Tree::Node * root = tree.get_root();
69
70 assert(root->is_leaf());
71 assert(root->get_num_points() == 4);
72
73 write_tree(root, 2);
74
75 tree.insert(Point(5, 45));
76
77 // Re-acquire root pointer and its children after mutation
78 root = tree.get_root();
79
80 assert(not root->is_leaf());
81 assert(root->get_num_points() == 5);
82
83 Tree::Node * root_nw_child = NW_CHILD(root);
84 assert(root_nw_child != nullptr);
85 assert(root_nw_child->is_leaf());
86 assert(root_nw_child->get_num_points() == 2);
87
88 Tree::Node * root_ne_child = NE_CHILD(root);
89 assert(root_ne_child != nullptr);
90 assert(root_ne_child->is_leaf());
91 assert(root_ne_child->get_num_points() == 1);
92
93 Tree::Node * root_sw_child = SW_CHILD(root);
94 assert(root_sw_child != nullptr);
95 assert(root_sw_child->is_leaf());
96 assert(root_sw_child->get_num_points() == 1);
97
98 Tree::Node * root_se_child = SE_CHILD(root);
99 assert(root_se_child != nullptr);
100 assert(root_se_child->is_leaf());
101 assert(root_se_child->get_num_points() == 1);
102
103 cout << endl;
104 write_tree(root, 2);
105
106 tree.insert(Point(45, 5));
107
108 tree.insert(Point(45, 45));
109
110 tree.insert(Point(20, 20));
111
112 // Re-acquire root pointer after mutations
113 root = tree.get_root();
114 root_nw_child = NW_CHILD(root);
115 root_ne_child = NE_CHILD(root);
116 root_sw_child = SW_CHILD(root);
117 root_se_child = SE_CHILD(root);
118
119 assert(root->get_num_points() == 8);
120
121 assert(root_nw_child->get_num_points() == 5);
122 assert(root_ne_child->get_num_points() == 1);
123 assert(root_sw_child->get_num_points() == 1);
124 assert(root_se_child->get_num_points() == 1);
125
126 assert(not root->is_leaf());
127 assert(not root_nw_child->is_leaf());
128 assert(root_ne_child->is_leaf());
129 assert(root_sw_child->is_leaf());
130 assert(root_se_child->is_leaf());
131
132 Tree::Node * root_nw_child_nw_child = NW_CHILD(root_nw_child);
133 assert(root_nw_child_nw_child != nullptr);
134 assert(root_nw_child_nw_child->is_leaf());
135 assert(root_nw_child_nw_child->get_num_points() == 2);
136
137 Tree::Node * root_nw_child_ne_child = NE_CHILD(root_nw_child);
138 assert(root_nw_child_ne_child != nullptr);
139 assert(root_nw_child_ne_child->is_leaf());
140 assert(root_nw_child_ne_child->get_num_points() == 1);
141
142 Tree::Node * root_nw_child_sw_child = SW_CHILD(root_nw_child);
143 assert(root_nw_child_sw_child != nullptr);
144 assert(root_nw_child_sw_child->is_leaf());
145 assert(root_nw_child_sw_child->get_num_points() == 1);
146
147 Tree::Node * root_nw_child_se_child = SE_CHILD(root_nw_child);
148 assert(root_nw_child_se_child != nullptr);
149 assert(root_nw_child_se_child->is_leaf());
150 assert(root_nw_child_se_child->get_num_points() == 1);
151
152 cout << endl;
153 write_tree(root, 2);
154
155 tree.insert(Point(30, 30));
156 tree.insert(Point(45, 30));
157 tree.insert(Point(30, 45));
158 tree.insert(Point(30, 40));
159
160 // Re-acquire pointers after mutations
161 root = tree.get_root();
162 root_nw_child = NW_CHILD(root);
163 root_ne_child = NE_CHILD(root);
164 root_sw_child = SW_CHILD(root);
165 root_se_child = SE_CHILD(root);
166 root_nw_child_nw_child = NW_CHILD(root_nw_child);
167 root_nw_child_ne_child = NE_CHILD(root_nw_child);
168 root_nw_child_sw_child = SW_CHILD(root_nw_child);
169 root_nw_child_se_child = SE_CHILD(root_nw_child);
170
171 assert(not root->is_leaf());
172 assert(not root_nw_child->is_leaf());
173 assert(root_nw_child_nw_child->is_leaf());
174 assert(root_nw_child_ne_child->is_leaf());
175 assert(root_nw_child_sw_child->is_leaf());
176 assert(not root_nw_child_se_child->is_leaf());
177 assert(root_ne_child->is_leaf());
178 assert(root_sw_child->is_leaf());
179 assert(root_se_child->is_leaf());
180
181 assert(root->get_num_points() == 12);
182 assert(root_nw_child->get_num_points() == 9);
183 assert(root_nw_child_se_child->get_num_points() == 5);
184
185 Tree::Node * root_nw_child_se_child_nw_child =
186 NW_CHILD(root_nw_child_se_child);
187 assert(root_nw_child_se_child_nw_child != nullptr);
188 assert(root_nw_child_se_child_nw_child->is_leaf());
189 assert(root_nw_child_se_child_nw_child->get_num_points() == 1);
190
191 Tree::Node * root_nw_child_se_child_ne_child =
192 NE_CHILD(root_nw_child_se_child);
193 assert(root_nw_child_se_child_ne_child != nullptr);
194 assert(root_nw_child_se_child_ne_child->is_leaf());
195 assert(root_nw_child_se_child_ne_child->get_num_points() == 1);
196
197 Tree::Node * root_nw_child_se_child_sw_child =
198 SW_CHILD(root_nw_child_se_child);
199 assert(root_nw_child_se_child_sw_child != nullptr);
200 assert(root_nw_child_se_child_sw_child->is_leaf());
201 assert(root_nw_child_se_child_sw_child->get_num_points() == 2);
202
203 Tree::Node * root_nw_child_se_child_se_child =
204 SE_CHILD(root_nw_child_se_child);
205 assert(root_nw_child_se_child_se_child != nullptr);
206 assert(root_nw_child_se_child_se_child->is_leaf());
207 assert(root_nw_child_se_child_se_child->get_num_points() == 1);
208
209 cout << endl;
210 write_tree(root, 2);
211
212 tree.remove(Point(20, 20));
213
214 // Re-acquire pointers after removal
215 root = tree.get_root();
216 root_nw_child = NW_CHILD(root);
217 root_ne_child = NE_CHILD(root);
218 root_sw_child = SW_CHILD(root);
219 root_se_child = SE_CHILD(root);
220 root_nw_child_nw_child = NW_CHILD(root_nw_child);
221 root_nw_child_ne_child = NE_CHILD(root_nw_child);
222 root_nw_child_sw_child = SW_CHILD(root_nw_child);
223 root_nw_child_se_child = SE_CHILD(root_nw_child);
224
225 assert(not root->is_leaf());
226 assert(not root_nw_child->is_leaf());
227 assert(root_nw_child_nw_child->is_leaf());
228 assert(root_nw_child_ne_child->is_leaf());
229 assert(root_nw_child_sw_child->is_leaf());
230 assert(not root_nw_child_se_child->is_leaf());
231 assert(root_ne_child->is_leaf());
232 assert(root_sw_child->is_leaf());
233 assert(root_se_child->is_leaf());
234
235 assert(root->get_num_points() == 11);
236 assert(root_nw_child->get_num_points() == 8);
237 assert(root_nw_child_se_child->get_num_points() == 5);
238 assert(root_nw_child_se_child_nw_child->is_leaf());
239 assert(root_nw_child_se_child_nw_child->get_num_points() == 1);
240 assert(root_nw_child_se_child_ne_child->is_leaf());
241 assert(root_nw_child_se_child_ne_child->get_num_points() == 1);
242 assert(root_nw_child_se_child_sw_child->is_leaf());
243 assert(root_nw_child_se_child_sw_child->get_num_points() == 2);
244 assert(root_nw_child_se_child_se_child->is_leaf());
245 assert(root_nw_child_se_child_se_child->get_num_points() == 1);
246
247 cout << endl;
248 write_tree(root, 2);
249
250 tree.remove(Point(45, 45));
251
252 // Re-acquire pointers after removal
253 root = tree.get_root();
254 root_nw_child = NW_CHILD(root);
255 root_ne_child = NE_CHILD(root);
256 root_sw_child = SW_CHILD(root);
257 root_se_child = SE_CHILD(root);
258 root_nw_child_nw_child = NW_CHILD(root_nw_child);
259 root_nw_child_ne_child = NE_CHILD(root_nw_child);
260 root_nw_child_sw_child = SW_CHILD(root_nw_child);
261 root_nw_child_se_child = SE_CHILD(root_nw_child);
262
263 assert(not root->is_leaf());
264 assert(not root_nw_child->is_leaf());
265 assert(root_nw_child_nw_child->is_leaf());
266 assert(root_nw_child_ne_child->is_leaf());
267 assert(root_nw_child_sw_child->is_leaf());
268 assert(root_nw_child_se_child->is_leaf());
269 assert(root_ne_child->is_leaf());
270 assert(root_sw_child->is_leaf());
271 assert(root_se_child->is_leaf());
272
273 assert(root->get_num_points() == 10);
274 assert(root_nw_child->get_num_points() == 7);
275 assert(root_nw_child_se_child->get_num_points() == 4);
276
277 cout << endl;
278 write_tree(root, 2);
279
280 cout << "\nQuadtree ok!\n";
281
282 return 0;
283}
284
Aleph::Point
Represents a point with rectangular coordinates in a 2D plane.
Definition point.H:229
Aleph::Point::to_string
std::string to_string() const
Returns a string representation of the point as "(x,y)".
Definition point.H:651
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:502
QuadTree::insert
Point * insert(Node *&r, const Point &p)
Recursive insert helper.
Definition quadtree.H:237
QuadTree::get_root
Node * get_root() noexcept
Get the root node.
Definition quadtree.H:396
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:4060
Aleph::divide_and_conquer_partition_dp
Divide_Conquer_DP_Result< Cost > divide_and_conquer_partition_dp(const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
Optimize partition DP using divide-and-conquer optimization.
Definition DP_Optimizations.H:133
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:36
main
int main()
Definition test-quadtree.C:55