123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196 |
- // Boost.Geometry Index
- // Additional tests
- // Copyright (c) 2011-2015 Adam Wulkiewicz, Lodz, Poland.
- // Use, modification and distribution is subject to the Boost Software License,
- // Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
- // http://www.boost.org/LICENSE_1_0.txt)
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <boost/chrono.hpp>
- #include <boost/foreach.hpp>
- #include <boost/random.hpp>
- #include <boost/geometry.hpp>
- #include <boost/geometry/index/rtree.hpp>
- #include <boost/geometry/geometries/geometries.hpp>
- #include <boost/geometry/index/detail/rtree/utilities/are_boxes_ok.hpp>
- #include <boost/geometry/index/detail/rtree/utilities/are_counts_ok.hpp>
- #include <boost/geometry/index/detail/rtree/utilities/are_levels_ok.hpp>
- namespace bg = boost::geometry;
- namespace bgi = bg::index;
- typedef bg::model::point<double, 2, bg::cs::cartesian> P;
- typedef bg::model::box<P> B;
- typedef bg::model::segment<P> S;
- typedef P V;
- //typedef B V;
- //typedef S V;
- template <typename V>
- struct generate_value {};
- template <>
- struct generate_value<B>
- {
- static inline B apply(float x, float y) { return B(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f)); }
- };
- template <>
- struct generate_value<S>
- {
- static inline S apply(float x, float y) { return S(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f)); }
- };
- template <>
- struct generate_value<P>
- {
- static inline P apply(float x, float y) { return P(x, y); }
- };
- template <typename RT>
- void test_queries(RT const& t, std::vector< std::pair<float, float> > const& coords, size_t queries_count)
- {
- typedef boost::chrono::thread_clock clock_t;
- typedef boost::chrono::duration<float> dur_t;
- std::vector<V> result;
- result.reserve(100);
- clock_t::time_point start = clock_t::now();
- size_t temp = 0;
- for (size_t i = 0 ; i < queries_count ; ++i )
- {
- float x = coords[i].first;
- float y = coords[i].second;
- result.clear();
- t.query(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))), std::back_inserter(result));
- temp += result.size();
- }
- dur_t time = clock_t::now() - start;
- std::cout << time.count() << " " << temp << '\n';
- }
- //#define BOOST_GEOMETRY_INDEX_BENCHMARK_DEBUG
- int main()
- {
- //typedef bgi::rtree<V, bgi::linear<4, 2> > RT;
- //typedef bgi::rtree<V, bgi::linear<16, 4> > RT;
- //typedef bgi::rtree<V, bgi::quadratic<4, 2> > RT;
- typedef bgi::rtree<V, bgi::rstar<8, 2> > RT;
- typedef boost::chrono::thread_clock clock_t;
- typedef boost::chrono::duration<float> dur_t;
- #ifndef BOOST_GEOMETRY_INDEX_BENCHMARK_DEBUG
- size_t values_count = 1000000;
- size_t queries_count = 100000;
- size_t nearest_queries_count = 20000;
- unsigned neighbours_count = 10;
- size_t max_range_inserts = 10;
- #else
- size_t values_count = 10000;
- size_t queries_count = 1000;
- size_t nearest_queries_count = 100;
- unsigned neighbours_count = 10;
- size_t max_range_inserts = 10;
- #endif
- float max_val = static_cast<float>(values_count / 2);
- std::vector< std::pair<float, float> > coords;
- std::vector<V> values;
- //randomize values
- {
- boost::mt19937 rng;
- //rng.seed(static_cast<unsigned int>(std::time(0)));
- boost::uniform_real<float> range(-max_val, max_val);
- boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
- coords.reserve(values_count);
- std::cout << "randomizing data\n";
- for ( size_t i = 0 ; i < values_count ; ++i )
- {
- float x = rnd();
- float y = rnd();
- coords.push_back(std::make_pair(x, y));
- values.push_back(generate_value<V>::apply(x, y));
- }
- std::cout << "randomized\n";
- }
- for (;;)
- {
- // packing test
- {
- clock_t::time_point start = clock_t::now();
- RT t(values.begin(), values.end());
- BOOST_ASSERT(bgi::detail::rtree::utilities::are_boxes_ok(t));
- BOOST_ASSERT(bgi::detail::rtree::utilities::are_counts_ok(t));
- BOOST_ASSERT(bgi::detail::rtree::utilities::are_levels_ok(t));
- dur_t time = clock_t::now() - start;
- std::cout << "pack(" << values_count << ") - " << time.count() << ", ";
- test_queries(t, coords, queries_count);
- }
- {
- size_t n_per_max = values_count / max_range_inserts;
- for ( size_t j = 0 ; j < max_range_inserts ; ++j )
- {
- clock_t::time_point start = clock_t::now();
- RT t;
- // perform j range-inserts
- for ( size_t i = 0 ; i < j ; ++i )
- {
- t.insert(values.begin() + n_per_max * i,
- values.begin() + (std::min)(n_per_max * (i + 1), values_count));
- }
- if ( !t.empty() )
- {
- BOOST_ASSERT(bgi::detail::rtree::utilities::are_boxes_ok(t));
- BOOST_ASSERT(bgi::detail::rtree::utilities::are_counts_ok(t));
- BOOST_ASSERT(bgi::detail::rtree::utilities::are_levels_ok(t));
- }
- // perform n-n/max_inserts*j inserts
- size_t inserted_count = (std::min)(n_per_max*j, values_count);
- for ( size_t i = inserted_count ; i < values_count ; ++i )
- {
- t.insert(values[i]);
- }
- if ( !t.empty() )
- {
- BOOST_ASSERT(bgi::detail::rtree::utilities::are_boxes_ok(t));
- BOOST_ASSERT(bgi::detail::rtree::utilities::are_counts_ok(t));
- BOOST_ASSERT(bgi::detail::rtree::utilities::are_levels_ok(t));
- }
- dur_t time = clock_t::now() - start;
- std::cout << j << "*insert(N/" << max_range_inserts << ")+insert(" << (values_count - inserted_count) << ") - " << time.count() << ", ";
- test_queries(t, coords, queries_count);
- }
- }
- std::cout << "------------------------------------------------\n";
- }
- return 0;
- }
|