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 #include <iostream>
11 #include <vector>
12 #include <algorithm>
13
14 #include <boost/chrono.hpp>
15 #include <boost/foreach.hpp>
16 #include <boost/random.hpp>
17
18 #include <boost/geometry.hpp>
19 #include <boost/geometry/index/rtree.hpp>
20 #include <boost/geometry/geometries/geometries.hpp>
21
22 #include <boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp>
23 #include <boost/geometry/index/detail/rtree/utilities/are_counts_ok.hpp>
24 #include <boost/geometry/index/detail/rtree/utilities/are_levels_ok.hpp>
25
26 namespace bg = boost::geometry;
27 namespace bgi = bg::index;
28
29 typedef bg::model::point<double, 2, bg::cs::cartesian> P;
30 typedef bg::model::box<P> B;
31 typedef bg::model::segment<P> S;
32 typedef P V;
33 //typedef B V;
34 //typedef S V;
35
36 template <typename V>
37 struct generate_value {};
38
39 template <>
40 struct generate_value<B>
41 {
applygenerate_value42 static inline B apply(float x, float y) { return B(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f)); }
43 };
44
45 template <>
46 struct generate_value<S>
47 {
applygenerate_value48 static inline S apply(float x, float y) { return S(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f)); }
49 };
50
51 template <>
52 struct generate_value<P>
53 {
applygenerate_value54 static inline P apply(float x, float y) { return P(x, y); }
55 };
56
57 template <typename RT>
test_queries(RT const & t,std::vector<std::pair<float,float>> const & coords,size_t queries_count)58 void test_queries(RT const& t, std::vector< std::pair<float, float> > const& coords, size_t queries_count)
59 {
60 typedef boost::chrono::thread_clock clock_t;
61 typedef boost::chrono::duration<float> dur_t;
62
63 std::vector<V> result;
64 result.reserve(100);
65
66 clock_t::time_point start = clock_t::now();
67 size_t temp = 0;
68 for (size_t i = 0 ; i < queries_count ; ++i )
69 {
70 float x = coords[i].first;
71 float y = coords[i].second;
72 result.clear();
73 t.query(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))), std::back_inserter(result));
74 temp += result.size();
75 }
76 dur_t time = clock_t::now() - start;
77 std::cout << time.count() << " " << temp << '\n';
78 }
79
80 //#define BOOST_GEOMETRY_INDEX_BENCHMARK_DEBUG
81
main()82 int main()
83 {
84 //typedef bgi::rtree<V, bgi::linear<4, 2> > RT;
85 //typedef bgi::rtree<V, bgi::linear<16, 4> > RT;
86 //typedef bgi::rtree<V, bgi::quadratic<4, 2> > RT;
87 typedef bgi::rtree<V, bgi::rstar<8, 2> > RT;
88
89 typedef boost::chrono::thread_clock clock_t;
90 typedef boost::chrono::duration<float> dur_t;
91
92 #ifndef BOOST_GEOMETRY_INDEX_BENCHMARK_DEBUG
93 size_t values_count = 1000000;
94 size_t queries_count = 100000;
95 size_t nearest_queries_count = 20000;
96 unsigned neighbours_count = 10;
97 size_t max_range_inserts = 10;
98 #else
99 size_t values_count = 10000;
100 size_t queries_count = 1000;
101 size_t nearest_queries_count = 100;
102 unsigned neighbours_count = 10;
103 size_t max_range_inserts = 10;
104 #endif
105
106 float max_val = static_cast<float>(values_count / 2);
107 std::vector< std::pair<float, float> > coords;
108 std::vector<V> values;
109
110 //randomize values
111 {
112 boost::mt19937 rng;
113 //rng.seed(static_cast<unsigned int>(std::time(0)));
114 boost::uniform_real<float> range(-max_val, max_val);
115 boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
116
117 coords.reserve(values_count);
118
119 std::cout << "randomizing data\n";
120 for ( size_t i = 0 ; i < values_count ; ++i )
121 {
122 float x = rnd();
123 float y = rnd();
124 coords.push_back(std::make_pair(x, y));
125 values.push_back(generate_value<V>::apply(x, y));
126 }
127 std::cout << "randomized\n";
128 }
129
130 for (;;)
131 {
132 // packing test
133 {
134 clock_t::time_point start = clock_t::now();
135
136 RT t(values.begin(), values.end());
137
138 BOOST_ASSERT(bgi::detail::rtree::utilities::are_boxes_ok(t));
139 BOOST_ASSERT(bgi::detail::rtree::utilities::are_counts_ok(t));
140 BOOST_ASSERT(bgi::detail::rtree::utilities::are_levels_ok(t));
141
142 dur_t time = clock_t::now() - start;
143 std::cout << "pack(" << values_count << ") - " << time.count() << ", ";
144
145 test_queries(t, coords, queries_count);
146 }
147
148 {
149 size_t n_per_max = values_count / max_range_inserts;
150
151 for ( size_t j = 0 ; j < max_range_inserts ; ++j )
152 {
153 clock_t::time_point start = clock_t::now();
154
155 RT t;
156
157 // perform j range-inserts
158 for ( size_t i = 0 ; i < j ; ++i )
159 {
160 t.insert(values.begin() + n_per_max * i,
161 values.begin() + (std::min)(n_per_max * (i + 1), values_count));
162 }
163
164 if ( !t.empty() )
165 {
166 BOOST_ASSERT(bgi::detail::rtree::utilities::are_boxes_ok(t));
167 BOOST_ASSERT(bgi::detail::rtree::utilities::are_counts_ok(t));
168 BOOST_ASSERT(bgi::detail::rtree::utilities::are_levels_ok(t));
169 }
170
171 // perform n-n/max_inserts*j inserts
172 size_t inserted_count = (std::min)(n_per_max*j, values_count);
173 for ( size_t i = inserted_count ; i < values_count ; ++i )
174 {
175 t.insert(values[i]);
176 }
177
178 if ( !t.empty() )
179 {
180 BOOST_ASSERT(bgi::detail::rtree::utilities::are_boxes_ok(t));
181 BOOST_ASSERT(bgi::detail::rtree::utilities::are_counts_ok(t));
182 BOOST_ASSERT(bgi::detail::rtree::utilities::are_levels_ok(t));
183 }
184
185 dur_t time = clock_t::now() - start;
186 std::cout << j << "*insert(N/" << max_range_inserts << ")+insert(" << (values_count - inserted_count) << ") - " << time.count() << ", ";
187
188 test_queries(t, coords, queries_count);
189 }
190 }
191
192 std::cout << "------------------------------------------------\n";
193 }
194
195 return 0;
196 }
197