1 // Boost.Geometry Index
2 // Additional tests
3
4 // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
5
6 // Use, modification and distribution is subject to the Boost Software License,
7 // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
8 // http://www.boost.org/LICENSE_1_0.txt)
9
10 #define BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
11
12 #include <iostream>
13
14 #include <boost/chrono.hpp>
15 #include <boost/foreach.hpp>
16 #include <boost/random.hpp>
17 #include <boost/range/algorithm/copy.hpp>
18
19 #include <boost/geometry.hpp>
20 #include <boost/geometry/index/rtree.hpp>
21 #include <boost/geometry/geometries/linestring.hpp>
22 #include <boost/geometry/geometries/segment.hpp>
23
24 #include <boost/geometry/index/detail/rtree/utilities/are_levels_ok.hpp>
25 #include <boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp>
26
27 namespace bg = boost::geometry;
28 namespace bgi = bg::index;
29
30 typedef bg::model::point<double, 2, bg::cs::cartesian> P;
31 typedef bg::model::box<P> B;
32 typedef bg::model::linestring<P> LS;
33 typedef bg::model::segment<P> S;
34 //typedef P V;
35 typedef B V;
36 //typedef S V;
37 //#define SEGMENT_INDEXABLE
38
39 template <typename V>
40 struct generate_value {};
41
42 template <>
43 struct generate_value<B>
44 {
applygenerate_value45 static inline B apply(float x, float y) { return B(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f)); }
46 };
47
48 template <>
49 struct generate_value<S>
50 {
applygenerate_value51 static inline S apply(float x, float y) { return S(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f)); }
52 };
53
54 template <>
55 struct generate_value<P>
56 {
applygenerate_value57 static inline P apply(float x, float y) { return P(x, y); }
58 };
59
60 //#include <boost/geometry/extensions/nsphere/nsphere.hpp>
61 //typedef bg::model::nsphere<P, double> NS;
62 //typedef NS V;
63 //
64 //template <>
65 //struct generate_value<NS>
66 //{
67 // static inline NS apply(float x, float y) { return NS(P(x, y), 0.5); }
68 //};
69
70 template <typename I1, typename I2, typename O>
mycopy(I1 first,I2 last,O o)71 void mycopy(I1 first, I2 last, O o)
72 {
73 for ( ; first != last ; ++o, ++first )
74 *o = *first;
75 }
76
77 //#define BOOST_GEOMETRY_INDEX_BENCHMARK_DEBUG
78
main()79 int main()
80 {
81 typedef boost::chrono::thread_clock clock_t;
82 typedef boost::chrono::duration<float> dur_t;
83
84 #ifndef BOOST_GEOMETRY_INDEX_BENCHMARK_DEBUG
85 size_t values_count = 1000000;
86 size_t queries_count = 100000;
87 size_t nearest_queries_count = 20000;
88 unsigned neighbours_count = 10;
89 size_t path_queries_count = 2000;
90 size_t path_queries_count2 = 20000;
91 unsigned path_values_count = 10;
92 #else
93 size_t values_count = 1000;
94 size_t queries_count = 1;
95 size_t nearest_queries_count = 1;
96 unsigned neighbours_count = 10;
97 size_t path_queries_count = 1;
98 size_t path_queries_count2 = 1;
99 unsigned path_values_count = 10;
100 #endif
101
102 float max_val = static_cast<float>(values_count / 2);
103 std::vector< std::pair<float, float> > coords;
104 std::vector<V> values;
105
106 //randomize values
107 {
108 boost::mt19937 rng;
109 //rng.seed(static_cast<unsigned int>(std::time(0)));
110 boost::uniform_real<float> range(-max_val, max_val);
111 boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
112
113 coords.reserve(values_count);
114
115 std::cout << "randomizing data\n";
116 for ( size_t i = 0 ; i < values_count ; ++i )
117 {
118 float x = rnd();
119 float y = rnd();
120 coords.push_back(std::make_pair(x, y));
121 values.push_back(generate_value<V>::apply(x, y));
122 }
123 std::cout << "randomized\n";
124 }
125
126 typedef bgi::rtree<V, bgi::linear<16, 4> > RT;
127 //typedef bgi::rtree<V, bgi::quadratic<16, 4> > RT;
128 //typedef bgi::rtree<V, bgi::rstar<16, 4> > RT;
129
130 std::cout << "sizeof rtree: " << sizeof(RT) << std::endl;
131
132 for (;;)
133 {
134 std::vector<V> result;
135 result.reserve(100);
136 B result_one;
137
138 // packing test
139 {
140 clock_t::time_point start = clock_t::now();
141
142 RT t(values.begin(), values.end());
143
144 dur_t time = clock_t::now() - start;
145 std::cout << time << " - pack " << values_count /*<< '\n'*/;
146
147 std::cout << (bgi::detail::rtree::utilities::are_levels_ok(t) ? " ok" : " NOK")
148 << (bgi::detail::rtree::utilities::are_boxes_ok(t) ? " ok\n" : "NOK\n");
149
150 {
151 clock_t::time_point start = clock_t::now();
152 size_t temp = 0;
153 for (size_t i = 0 ; i < queries_count ; ++i )
154 {
155 float x = coords[i].first;
156 float y = coords[i].second;
157 result.clear();
158 t.query(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))), std::back_inserter(result));
159 temp += result.size();
160 }
161 dur_t time = clock_t::now() - start;
162 std::cout << time << " - query(B) " << queries_count << " found " << temp << '\n';
163 }
164 }
165
166 RT t;
167
168 // inserting test
169 {
170 clock_t::time_point start = clock_t::now();
171 t.insert(values);
172 dur_t time = clock_t::now() - start;
173 std::cout << time << " - insert " << values_count /*<< '\n'*/;
174
175 std::cout << (bgi::detail::rtree::utilities::are_levels_ok(t) ? " ok" : " NOK")
176 << (bgi::detail::rtree::utilities::are_boxes_ok(t) ? " ok\n" : "NOK\n");
177 }
178
179
180
181 {
182 clock_t::time_point start = clock_t::now();
183 size_t temp = 0;
184 for (size_t i = 0 ; i < queries_count ; ++i )
185 {
186 float x = coords[i].first;
187 float y = coords[i].second;
188 result.clear();
189 t.query(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))), std::back_inserter(result));
190 temp += result.size();
191 }
192 dur_t time = clock_t::now() - start;
193 std::cout << time << " - query(B) " << queries_count << " found " << temp << '\n';
194 }
195
196 {
197 clock_t::time_point start = clock_t::now();
198 size_t temp = 0;
199 for (size_t i = 0 ; i < queries_count ; ++i )
200 {
201 float x = coords[i].first;
202 float y = coords[i].second;
203 result.clear();
204 boost::copy(t | bgi::adaptors::queried(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
205 std::back_inserter(result));
206 temp += result.size();
207 }
208 dur_t time = clock_t::now() - start;
209 std::cout << time << " - range queried(B) " << queries_count << " found " << temp << '\n';
210 }
211
212 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
213 {
214 clock_t::time_point start = clock_t::now();
215 size_t temp = 0;
216 for (size_t i = 0 ; i < queries_count ; ++i )
217 {
218 float x = coords[i].first;
219 float y = coords[i].second;
220 result.clear();
221 std::copy(
222 t.qbegin_(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
223 t.qend_(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
224 std::back_inserter(result));
225 temp += result.size();
226 }
227 dur_t time = clock_t::now() - start;
228 std::cout << time << " - qbegin(B) qend(B) " << queries_count << " found " << temp << '\n';
229 }
230 {
231 clock_t::time_point start = clock_t::now();
232 size_t temp = 0;
233 for (size_t i = 0 ; i < queries_count ; ++i )
234 {
235 float x = coords[i].first;
236 float y = coords[i].second;
237 result.clear();
238 mycopy(
239 t.qbegin_(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
240 t.qend_(),
241 std::back_inserter(result));
242 temp += result.size();
243 }
244 dur_t time = clock_t::now() - start;
245 std::cout << time << " - qbegin(B) qend() " << queries_count << " found " << temp << '\n';
246 }
247 {
248 clock_t::time_point start = clock_t::now();
249 size_t temp = 0;
250 for (size_t i = 0 ; i < queries_count ; ++i )
251 {
252 float x = coords[i].first;
253 float y = coords[i].second;
254 result.clear();
255 boost::copy(
256 std::make_pair(
257 t.qbegin_(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10)))),
258 t.qend_(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))))
259 ), std::back_inserter(result));
260 temp += result.size();
261 }
262 dur_t time = clock_t::now() - start;
263 std::cout << time << " - range qbegin(B) qend(B)" << queries_count << " found " << temp << '\n';
264 }
265 #endif // BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
266
267 {
268 clock_t::time_point start = clock_t::now();
269 size_t temp = 0;
270 for (size_t i = 0 ; i < queries_count ; ++i )
271 {
272 float x = coords[i].first;
273 float y = coords[i].second;
274 result.clear();
275 RT::const_query_iterator first = t.qbegin(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))));
276 RT::const_query_iterator last = t.qend();
277 std::copy(first, last, std::back_inserter(result));
278 temp += result.size();
279 }
280 dur_t time = clock_t::now() - start;
281 std::cout << time << " - type-erased qbegin(B) qend() " << queries_count << " found " << temp << '\n';
282 }
283 {
284 clock_t::time_point start = clock_t::now();
285 size_t temp = 0;
286 for (size_t i = 0 ; i < queries_count ; ++i )
287 {
288 float x = coords[i].first;
289 float y = coords[i].second;
290 result.clear();
291 RT::const_query_iterator first = t.qbegin(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))));
292 RT::const_query_iterator last = t.qend();
293 boost::copy(std::make_pair(first, last), std::back_inserter(result));
294 temp += result.size();
295 }
296 dur_t time = clock_t::now() - start;
297 std::cout << time << " - range type-erased qbegin(B) qend() " << queries_count << " found " << temp << '\n';
298 }
299
300 #ifndef SEGMENT_INDEXABLE
301 {
302 clock_t::time_point start = clock_t::now();
303 size_t temp = 0;
304 for (size_t i = 0 ; i < queries_count / 2 ; ++i )
305 {
306 float x1 = coords[i].first;
307 float y1 = coords[i].second;
308 float x2 = coords[i+1].first;
309 float y2 = coords[i+1].second;
310 float x3 = coords[i+2].first;
311 float y3 = coords[i+2].second;
312 result.clear();
313 t.query(
314 bgi::intersects(B(P(x1 - 10, y1 - 10), P(x1 + 10, y1 + 10)))
315 &&
316 !bgi::within(B(P(x2 - 10, y2 - 10), P(x2 + 10, y2 + 10)))
317 &&
318 !bgi::covered_by(B(P(x3 - 10, y3 - 10), P(x3 + 10, y3 + 10)))
319 ,
320 std::back_inserter(result)
321 );
322 temp += result.size();
323 }
324 dur_t time = clock_t::now() - start;
325 std::cout << time << " - query(i && !w && !c) " << queries_count << " found " << temp << '\n';
326 }
327 #endif
328
329 result.clear();
330
331 {
332 clock_t::time_point start = clock_t::now();
333 size_t temp = 0;
334 for (size_t i = 0 ; i < nearest_queries_count ; ++i )
335 {
336 float x = coords[i].first + 100;
337 float y = coords[i].second + 100;
338 result.clear();
339 temp += t.query(bgi::nearest(P(x, y), neighbours_count), std::back_inserter(result));
340 }
341 dur_t time = clock_t::now() - start;
342 std::cout << time << " - query(nearest(P, " << neighbours_count << ")) " << nearest_queries_count << " found " << temp << '\n';
343 }
344
345 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
346 {
347 clock_t::time_point start = clock_t::now();
348 size_t temp = 0;
349 for (size_t i = 0 ; i < nearest_queries_count ; ++i )
350 {
351 float x = coords[i].first + 100;
352 float y = coords[i].second + 100;
353 result.clear();
354 std::copy(
355 t.qbegin_(bgi::nearest(P(x, y), neighbours_count)),
356 t.qend_(bgi::nearest(P(x, y), neighbours_count)),
357 std::back_inserter(result));
358 temp += result.size();
359 }
360 dur_t time = clock_t::now() - start;
361 std::cout << time << " - qbegin(nearest(P, " << neighbours_count << ")) qend(n) " << nearest_queries_count << " found " << temp << '\n';
362 }
363 {
364 clock_t::time_point start = clock_t::now();
365 size_t temp = 0;
366 for (size_t i = 0 ; i < nearest_queries_count ; ++i )
367 {
368 float x = coords[i].first + 100;
369 float y = coords[i].second + 100;
370 result.clear();
371 mycopy(
372 t.qbegin_(bgi::nearest(P(x, y), neighbours_count)),
373 t.qend_(),
374 std::back_inserter(result));
375 temp += result.size();
376 }
377 dur_t time = clock_t::now() - start;
378 std::cout << time << " - qbegin(nearest(P, " << neighbours_count << ")) qend() " << nearest_queries_count << " found " << temp << '\n';
379 }
380 #endif // BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
381
382 {
383 clock_t::time_point start = clock_t::now();
384 size_t temp = 0;
385 for (size_t i = 0 ; i < nearest_queries_count ; ++i )
386 {
387 float x = coords[i].first;
388 float y = coords[i].second;
389 result.clear();
390 RT::const_query_iterator first = t.qbegin(bgi::nearest(P(x, y), neighbours_count));
391 RT::const_query_iterator last = t.qend();
392 std::copy(first, last, std::back_inserter(result));
393 temp += result.size();
394 }
395 dur_t time = clock_t::now() - start;
396 std::cout << time << " - type-erased qbegin(nearest(P, " << neighbours_count << ")) qend() " << nearest_queries_count << " found " << temp << '\n';
397 }
398
399 #ifdef BOOST_GEOMETRY_INDEX_DETAIL_EXPERIMENTAL
400 #ifndef SEGMENT_INDEXABLE
401
402 {
403 LS ls;
404 ls.resize(6);
405
406 clock_t::time_point start = clock_t::now();
407 size_t temp = 0;
408 for (size_t i = 0 ; i < path_queries_count ; ++i )
409 {
410 float x = coords[i].first;
411 float y = coords[i].second;
412 for ( int i = 0 ; i < 3 ; ++i )
413 {
414 float foo = i*max_val/300;
415 ls[2*i] = P(x, y+foo);
416 ls[2*i+1] = P(x+max_val/100, y+foo);
417 }
418 result.clear();
419 t.query(bgi::path(ls, path_values_count), std::back_inserter(result));
420 temp += result.size();
421 }
422 dur_t time = clock_t::now() - start;
423 std::cout << time << " - query(path(LS6, " << path_values_count << ")) " << path_queries_count << " found " << temp << '\n';
424 }
425
426 {
427 LS ls;
428 ls.resize(2);
429
430 clock_t::time_point start = clock_t::now();
431 size_t temp = 0;
432 for (size_t i = 0 ; i < path_queries_count2 ; ++i )
433 {
434 float x = coords[i].first;
435 float y = coords[i].second;
436 ls[0] = P(x, y);
437 ls[1] = P(x+max_val/100, y+max_val/100);
438 result.clear();
439 t.query(bgi::path(ls, path_values_count), std::back_inserter(result));
440 temp += result.size();
441 }
442 dur_t time = clock_t::now() - start;
443 std::cout << time << " - query(path(LS2, " << path_values_count << ")) " << path_queries_count2 << " found " << temp << '\n';
444 }
445
446 {
447 clock_t::time_point start = clock_t::now();
448 size_t temp = 0;
449 for (size_t i = 0 ; i < path_queries_count2 ; ++i )
450 {
451 float x = coords[i].first;
452 float y = coords[i].second;
453 S seg(P(x, y), P(x+max_val/100, y+max_val/100));
454 result.clear();
455 t.query(bgi::path(seg, path_values_count), std::back_inserter(result));
456 temp += result.size();
457 }
458 dur_t time = clock_t::now() - start;
459 std::cout << time << " - query(path(S, " << path_values_count << ")) " << path_queries_count2 << " found " << temp << '\n';
460 }
461 #endif
462 #endif
463 {
464 clock_t::time_point start = clock_t::now();
465 for (size_t i = 0 ; i < values_count / 10 ; ++i )
466 {
467 float x = coords[i].first;
468 float y = coords[i].second;
469
470 t.remove(generate_value<V>::apply(x, y));
471 }
472 dur_t time = clock_t::now() - start;
473 std::cout << time << " - remove " << values_count / 10 << '\n';
474
475 std::cout << (bgi::detail::rtree::utilities::are_boxes_ok(t) ? " boxes ok\n" : "boxes NOT ok\n");
476 }
477
478 std::cout << "------------------------------------------------\n";
479 }
480
481 return 0;
482 }
483