libs/geometry/index/example/benchmark.cpp

   1 // Boost.Geometry Index
   2 // Additional tests
   3
   4 // Copyright (c) 2011-2013 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
  12 #include <boost/geometry.hpp>
  13 #include <boost/geometry/index/rtree.hpp>
  14
  15 #include <boost/chrono.hpp>
  16 #include <boost/foreach.hpp>
  17 #include <boost/random.hpp>
  18
  19 int main()
  20 {
  21     namespace bg = boost::geometry;
  22     namespace bgi = bg::index;
  23     typedef boost::chrono::thread_clock clock_t;
  24     typedef boost::chrono::duration<float> dur_t;
  25
  26     size_t values_count = 1000000;
  27     size_t queries_count = 100000;
  28     size_t nearest_queries_count = 10000;
  29     unsigned neighbours_count = 10;
  30
  31     std::vector< std::pair<float, float> > coords;
  32
  33     //randomize values
  34     {
  35         boost::mt19937 rng;
  36         //rng.seed(static_cast<unsigned int>(std::time(0)));
  37         float max_val = static_cast<float>(values_count / 2);
  38         boost::uniform_real<float> range(-max_val, max_val);
  39         boost::variate_generator<boost::mt19937&, boost::uniform_real<float> > rnd(rng, range);
  40
  41         coords.reserve(values_count);
  42
  43         std::cout << "randomizing data\n";
  44         for ( size_t i = 0 ; i < values_count ; ++i )
  45         {
  46             coords.push_back(std::make_pair(rnd(), rnd()));
  47         }
  48         std::cout << "randomized\n";
  49     }
  50
  51     typedef bg::model::point<double, 2, bg::cs::cartesian> P;
  52     typedef bg::model::box<P> B;
  53     typedef bgi::rtree<B, bgi::linear<16, 4> > RT;
  54     //typedef bgi::rtree<B, bgi::quadratic<8, 3> > RT;
  55     //typedef bgi::rtree<B, bgi::rstar<8, 3> > RT;
  56
  57     std::cout << "sizeof rtree: " << sizeof(RT) << std::endl;
  58
  59     for (;;)
  60     {
  61         RT t;
  62
  63         // inserting test
  64         {
  65             clock_t::time_point start = clock_t::now();
  66             for (size_t i = 0 ; i < values_count ; ++i )
  67             {
  68                 float x = coords[i].first;
  69                 float y = coords[i].second;
  70                 B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
  71
  72                 t.insert(b);
  73             }
  74             dur_t time = clock_t::now() - start;
  75             std::cout << time << " - insert " << values_count << '\n';
  76         }
  77
  78         std::vector<B> result;
  79         result.reserve(100);
  80         B result_one;
  81
  82         {
  83             clock_t::time_point start = clock_t::now();
  84             size_t temp = 0;
  85             for (size_t i = 0 ; i < queries_count ; ++i )
  86             {
  87                 float x = coords[i].first;
  88                 float y = coords[i].second;
  89                 result.clear();
  90                 t.query(bgi::intersects(B(P(x - 10, y - 10), P(x + 10, y + 10))), std::back_inserter(result));
  91                 temp += result.size();
  92             }
  93             dur_t time = clock_t::now() - start;
  94             std::cout << time << " - query(B) " << queries_count << " found " << temp << '\n';
  95         }
  96
  97         {
  98             clock_t::time_point start = clock_t::now();
  99             size_t temp = 0;
 100             for (size_t i = 0 ; i < queries_count / 2 ; ++i )
 101             {
 102                 float x1 = coords[i].first;
 103                 float y1 = coords[i].second;
 104                 float x2 = coords[i+1].first;
 105                 float y2 = coords[i+1].second;
 106                 float x3 = coords[i+2].first;
 107                 float y3 = coords[i+2].second;
 108                 result.clear();
 109                 t.query(
 110                     bgi::intersects(B(P(x1 - 10, y1 - 10), P(x1 + 10, y1 + 10)))
 111                     &&
 112                     !bgi::within(B(P(x2 - 10, y2 - 10), P(x2 + 10, y2 + 10)))
 113                     &&
 114                     !bgi::overlaps(B(P(x3 - 10, y3 - 10), P(x3 + 10, y3 + 10)))
 115                     ,
 116                     std::back_inserter(result)
 117                     );
 118                 temp += result.size();
 119             }
 120             dur_t time = clock_t::now() - start;
 121             std::cout << time << " - query(i && !w && !o) " << queries_count << " found " << temp << '\n';
 122         }
 123
 124         result.clear();
 125
 126         {
 127             clock_t::time_point start = clock_t::now();
 128             size_t temp = 0;
 129             for (size_t i = 0 ; i < nearest_queries_count ; ++i )
 130             {
 131                 float x = coords[i].first + 100;
 132                 float y = coords[i].second + 100;
 133                 result.clear();
 134                 temp += t.query(bgi::nearest(P(x, y), neighbours_count), std::back_inserter(result));
 135             }
 136             dur_t time = clock_t::now() - start;
 137             std::cout << time << " - query(nearest(P, " << neighbours_count << ")) " << nearest_queries_count << " found " << temp << '\n';
 138         }
 139
 140         {
 141             clock_t::time_point start = clock_t::now();
 142             for (size_t i = 0 ; i < values_count / 10 ; ++i )
 143             {
 144                 float x = coords[i].first;
 145                 float y = coords[i].second;
 146                 B b(P(x - 0.5f, y - 0.5f), P(x + 0.5f, y + 0.5f));
 147
 148                 t.remove(b);
 149             }
 150             dur_t time = clock_t::now() - start;
 151             std::cout << time << " - remove " << values_count / 10 << '\n';
 152         }
 153
 154         std::cout << "------------------------------------------------\n";
 155     }
 156
 157     return 0;
 158 }