libs/polygon/benchmark/voronoi_benchmark.cpp

   1 // Boost.Polygon library voronoi_benchmark.cpp file
   2
   3 //          Copyright Andrii Sydorchuk 2010-2012.
   4 // Distributed under the Boost Software License, Version 1.0.
   5 //    (See accompanying file LICENSE_1_0.txt or copy at
   6 //          http://www.boost.org/LICENSE_1_0.txt)
   7
   8 // See http://www.boost.org for updates, documentation, and revision history.
   9
  10 #include <algorithm>
  11 #include <iomanip>
  12 #include <iostream>
  13 #include <fstream>
  14 #include <list>
  15 #include <numeric>
  16 #include <vector>
  17
  18 #define BOOST_TEST_MODULE benchmark_test
  19 #include <boost/mpl/list.hpp>
  20 #include <boost/random/mersenne_twister.hpp>
  21 #include <boost/test/test_case_template.hpp>
  22 #include <boost/timer.hpp>
  23
  24 #include <boost/polygon/polygon.hpp>
  25 #include <boost/polygon/voronoi.hpp>
  26 using boost::polygon::point_data;
  27 using boost::polygon::segment_data;
  28 using boost::polygon::voronoi_diagram;
  29
  30 typedef boost::mpl::list<int> test_types;
  31 const char *BENCHMARK_FILE = "voronoi_benchmark.txt";
  32 const char *POINT_INPUT_FILE = "input_data/voronoi_point.txt";
  33 const char *SEGMENT_INPUT_FILE = "input_data/voronoi_segment.txt";
  34 const int POINT_RUNS = 10;
  35 const int SEGMENT_RUNS = 10;
  36
  37 boost::mt19937 gen(static_cast<unsigned int>(time(NULL)));
  38 boost::timer timer;
  39
  40 BOOST_AUTO_TEST_CASE_TEMPLATE(benchmark_test_random, T, test_types) {
  41     typedef T coordinate_type;
  42     typedef point_data<coordinate_type> point_type;
  43     voronoi_diagram<double> test_output;
  44
  45     std::ofstream bench_file(BENCHMARK_FILE, std::ios_base::out | std::ios_base::app);
  46     bench_file << "Voronoi Benchmark Test (time in seconds):" << std::endl;
  47     bench_file << "| Number of points | Number of tests | Time per one test |" << std::endl;
  48     bench_file << std::setiosflags(std::ios::right | std::ios::fixed) << std::setprecision(6);
  49     int max_points = 100000;
  50     std::vector<point_type> points;
  51     coordinate_type x, y;
  52     for (int num_points = 10; num_points <= max_points; num_points *= 10) {
  53         points.resize(num_points);
  54         timer.restart();
  55         int num_tests = max_points / num_points;
  56         for (int cur = 0; cur < num_tests; cur++) {
  57             test_output.clear();
  58             for (int cur_point = 0; cur_point < num_points; cur_point++) {
  59                 x = static_cast<coordinate_type>(gen());
  60                 y = static_cast<coordinate_type>(gen());
  61                 points[cur_point] = point_type(x, y);
  62             }
  63             construct_voronoi(points.begin(), points.end(), &test_output);
  64         }
  65         double elapsed_time = timer.elapsed();
  66         double time_per_test = elapsed_time / num_tests;
  67
  68         bench_file << "| " << std::setw(16) << num_points << " ";
  69         bench_file << "| " << std::setw(15) << num_tests << " ";
  70         bench_file << "| " << std::setw(17) << time_per_test << " ";
  71         bench_file << "| " << std::endl;
  72     }
  73     bench_file.close();
  74 }
  75
  76 BOOST_AUTO_TEST_CASE_TEMPLATE(benchmark_test_points, T, test_types) {
  77     typedef T coordinate_type;
  78     typedef point_data<coordinate_type> point_type;
  79
  80     std::vector<point_type> points;
  81     {
  82         std::ifstream input_file(POINT_INPUT_FILE);
  83         int num_points;
  84         coordinate_type x, y;
  85         input_file >> num_points;
  86         points.reserve(num_points);
  87         for (int i = 0; i < num_points; ++i) {
  88             input_file >> x >> y;
  89             points.push_back(point_type(x, y));
  90         }
  91         input_file.close();
  92     }
  93
  94     std::vector<double> periods;
  95     {
  96         for (int i = 0; i < POINT_RUNS; ++i) {
  97             voronoi_diagram<double> test_output;
  98             timer.restart();
  99             construct_voronoi(points.begin(), points.end(), &test_output);
 100             periods.push_back(timer.elapsed());
 101         }
 102     }
 103     std::sort(periods.begin(), periods.end());
 104     // Using olympic system to evaluate average time.
 105     double elapsed_time =
 106         std::accumulate(periods.begin() + 2, periods.end() - 2, 0.0);
 107     elapsed_time /= (periods.size() - 4);
 108
 109     std::ofstream bench_file(
 110         BENCHMARK_FILE, std::ios_base::out | std::ios_base::app);
 111     bench_file << std::setiosflags(std::ios::right | std::ios::fixed) << std::setprecision(6);
 112     bench_file << "Static test of " << points.size() << " points: " << elapsed_time << std::endl;
 113     bench_file.close();
 114 }
 115
 116 BOOST_AUTO_TEST_CASE_TEMPLATE(benchmark_test_segments, T, test_types) {
 117     typedef T coordinate_type;
 118     typedef point_data<coordinate_type> point_type;
 119     typedef segment_data<coordinate_type> segment_type;
 120
 121     std::vector<segment_type> segments;
 122     {
 123         std::ifstream input_file(SEGMENT_INPUT_FILE);
 124         int num_segments;
 125         coordinate_type x0, y0, x1, y1;
 126         input_file >> num_segments;
 127         segments.reserve(num_segments);
 128         for (int i = 0; i < num_segments; ++i) {
 129             input_file >> x0 >> y0 >> x1 >> y1;
 130             point_type p0(x0, y0), p1(x1, y1);
 131             segments.push_back(segment_type(p0, p1));
 132         }
 133         input_file.close();
 134     }
 135
 136     std::vector<double> periods;
 137     {
 138         for (int i = 0; i < SEGMENT_RUNS; ++i) {
 139             voronoi_diagram<double> test_output;
 140             timer.restart();
 141             construct_voronoi(segments.begin(), segments.end(), &test_output);
 142             periods.push_back(timer.elapsed());
 143         }
 144     }
 145     std::sort(periods.begin(), periods.end());
 146     // Using olympic system to evaluate average time.
 147     double elapsed_time =
 148         std::accumulate(periods.begin() + 2, periods.end() - 2, 0.0);
 149     elapsed_time /= (periods.size() - 4);
 150
 151     std::ofstream bench_file(
 152         BENCHMARK_FILE, std::ios_base::out | std::ios_base::app);
 153     bench_file << std::setiosflags(std::ios::right | std::ios::fixed) << std::setprecision(6);
 154     bench_file << "Static test of " << segments.size() << " segments: " << elapsed_time << std::endl;
 155     bench_file.close();
 156 }