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 <numeric>
15 #include <vector>
16 #include <utility>
17 
18 #include <boost/random/mersenne_twister.hpp>
19 #include <boost/timer/timer.hpp>
20 
21 typedef boost::int32_t int32;
22 using boost::timer::cpu_times;
23 using boost::timer::nanosecond_type;
24 
25 // Include for the Boost.Polygon Voronoi library.
26 #include <boost/polygon/voronoi.hpp>
27 typedef boost::polygon::voronoi_diagram<double> VD_BOOST;
28 
29 // Includes for the CGAL library.
30 #include <CGAL/Simple_cartesian.h>
31 #include <CGAL/Segment_Delaunay_graph_filtered_traits_2.h>
32 #include <CGAL/Segment_Delaunay_graph_2.h>
33 
34 typedef CGAL::Simple_cartesian<double> K;
35 typedef CGAL::Segment_Delaunay_graph_filtered_traits_without_intersections_2<K> GT;
36 typedef CGAL::Segment_Delaunay_graph_2<GT>  SDT_CGAL;
37 typedef SDT_CGAL::Point_2 Point_CGAL;
38 typedef SDT_CGAL::Site_2 Site_CGAL;
39 
40 // Include for the Boost.Polygon library.
41 #include <boost/polygon/polygon.hpp>
42 typedef boost::polygon::point_data<int32> POINT_POLYGON;
43 typedef boost::polygon::segment_data<int32> SEGMENT_POLYGON;
44 typedef std::vector<SEGMENT_POLYGON> SSD_POLYGON;
45 
46 const int RANDOM_SEED = 27;
47 const int NUM_TESTS = 6;
48 const int NUM_SEGMENTS[] = {10, 100, 1000, 10000, 100000, 1000000};
49 const int NUM_RUNS[] = {100000, 10000, 1000, 100, 10, 1};
50 std::ofstream bf("benchmark_segments.txt",
51                  std::ios_base::out | std::ios_base::app);
52 boost::timer::cpu_timer timer;
53 
format_line(int num_points,int num_tests,double time_per_test)54 void format_line(int num_points, int num_tests, double time_per_test) {
55   bf << "| " << std::setw(16) << num_points << " ";
56   bf << "| " << std::setw(15) << num_tests << " ";
57   bf << "| " << std::setw(17) << time_per_test << " ";
58   bf << "|" << std::endl;
59 }
60 
get_elapsed_secs()61 double get_elapsed_secs() {
62   cpu_times elapsed_times(timer.elapsed());
63   return 1E-9 * static_cast<double>(
64       elapsed_times.system + elapsed_times.user);
65 }
66 
clean_segment_set(std::vector<SEGMENT_POLYGON> * data)67 void clean_segment_set(std::vector<SEGMENT_POLYGON>* data) {
68   typedef int32 Unit;
69   typedef boost::polygon::scanline_base<Unit>::Point Point;
70   typedef boost::polygon::scanline_base<Unit>::half_edge half_edge;
71   typedef int segment_id;
72   std::vector<std::pair<half_edge, segment_id> > half_edges;
73   std::vector<std::pair<half_edge, segment_id> > half_edges_out;
74   segment_id id = 0;
75   half_edges.reserve(data->size());
76   for (std::vector<SEGMENT_POLYGON>::iterator it = data->begin();
77        it != data->end(); ++it) {
78     POINT_POLYGON l = it->low();
79     POINT_POLYGON h = it->high();
80     half_edges.push_back(std::make_pair(half_edge(l, h), id++));
81   }
82   half_edges_out.reserve(half_edges.size());
83   // Apparently no need to pre-sort data when calling validate_scan.
84   boost::polygon::line_intersection<Unit>::validate_scan(
85       half_edges_out, half_edges.begin(), half_edges.end());
86   std::vector<SEGMENT_POLYGON> result;
87   result.reserve(half_edges_out.size());
88   for (std::size_t i = 0; i < half_edges_out.size(); ++i) {
89     id = half_edges_out[i].second;
90     POINT_POLYGON l = half_edges_out[i].first.first;
91     POINT_POLYGON h = half_edges_out[i].first.second;
92     SEGMENT_POLYGON orig_seg = data->at(id);
93     if (orig_seg.high() < orig_seg.low())
94       std::swap(l, h);
95     result.push_back(SEGMENT_POLYGON(l, h));
96   }
97   std::swap(result, *data);
98 }
99 
get_intersection_runtime()100 std::vector<double> get_intersection_runtime() {
101   std::vector<double> running_times;
102   boost::mt19937 gen(RANDOM_SEED);
103   for (int i = 0; i < NUM_TESTS; ++i) {
104     timer.start();
105     for (int j = 0; j < NUM_RUNS[i]; ++j) {
106       SSD_POLYGON ssd;
107       for (int k = 0; k < NUM_SEGMENTS[i]; ++k) {
108         int32 x1 = gen();
109         int32 y1 = gen();
110         int32 dx = (gen() & 1023) + 1;
111         int32 dy = (gen() & 1023) + 1;
112         ssd.push_back(SEGMENT_POLYGON(
113             POINT_POLYGON(x1, y1), POINT_POLYGON(x1 + dx, y1 + dy)));
114       }
115       clean_segment_set(&ssd);
116     }
117     running_times.push_back(get_elapsed_secs());
118   }
119   return running_times;
120 }
121 
run_boost_voronoi_test(const std::vector<double> & running_times)122 void run_boost_voronoi_test(const std::vector<double> &running_times) {
123   boost::mt19937 gen(RANDOM_SEED);
124   bf << "Boost.Polygon Voronoi of Segments:\n";
125   for (int i = 0; i < NUM_TESTS; ++i) {
126     timer.start();
127     for (int j = 0; j < NUM_RUNS[i]; ++j) {
128       SSD_POLYGON ssd;
129       VD_BOOST vd;
130       for (int k = 0; k < NUM_SEGMENTS[i]; ++k) {
131         int32 x1 = gen();
132         int32 y1 = gen();
133         int32 dx = (gen() & 1023) + 1;
134         int32 dy = (gen() & 1023) + 1;
135         ssd.push_back(SEGMENT_POLYGON(
136             POINT_POLYGON(x1, y1),
137             POINT_POLYGON(x1 + dx, y1 + dy)));
138       }
139       clean_segment_set(&ssd);
140       boost::polygon::construct_voronoi(ssd.begin(), ssd.end(), &vd);
141     }
142     double time_per_test =
143         (get_elapsed_secs() - running_times[i]) / NUM_RUNS[i];
144     format_line(NUM_SEGMENTS[i], NUM_RUNS[i], time_per_test);
145   }
146   bf << "\n";
147 }
148 
run_cgal_delaunay_test(const std::vector<double> & running_times)149 void run_cgal_delaunay_test(const std::vector<double> &running_times) {
150   boost::mt19937 gen(RANDOM_SEED);
151   bf << "CGAL Triangulation of Segments:\n";
152   for (int i = 0; i < NUM_TESTS; ++i) {
153     timer.start();
154     for (int j = 0; j < NUM_RUNS[i]; ++j) {
155       SSD_POLYGON ssd;
156       for (int k = 0; k < NUM_SEGMENTS[i]; ++k) {
157         int32 x1 = gen();
158         int32 y1 = gen();
159         int32 dx = (gen() & 1023) + 1;
160         int32 dy = (gen() & 1023) + 1;
161         ssd.push_back(SEGMENT_POLYGON(
162             POINT_POLYGON(x1, y1),
163             POINT_POLYGON(x1 + dx, y1 + dy)));
164       }
165       clean_segment_set(&ssd);
166 
167       typedef std::vector<Point_CGAL> Points_container;
168       typedef std::vector<Points_container>::size_type Index_type;
169       typedef std::vector< std::pair<Index_type, Index_type> > Constraints_container;
170       Points_container points;
171       Constraints_container constraints;
172       points.reserve(ssd.size() * 2);
173       constraints.reserve(ssd.size());
174       for (SSD_POLYGON::iterator it = ssd.begin(); it != ssd.end(); ++it) {
175         points.push_back(Point_CGAL(
176             boost::polygon::x(it->low()),
177             boost::polygon::y(it->low())));
178         points.push_back(Point_CGAL(
179             boost::polygon::x(it->high()),
180             boost::polygon::y(it->high())));
181         constraints.push_back(
182             std::make_pair(points.size() - 2, points.size() - 1));
183       }
184 
185       SDT_CGAL sdg;
186       sdg.insert_segments(
187           points.begin(), points.end(),
188           constraints.begin(), constraints.end());
189     }
190     double time_per_test =
191         (get_elapsed_secs() - running_times[i]) / NUM_RUNS[i];
192     format_line(NUM_SEGMENTS[i], NUM_RUNS[i], time_per_test);
193   }
194   bf << "\n";
195 }
196 
main()197 int main() {
198   bf << std::setiosflags(std::ios::right | std::ios::fixed)
199      << std::setprecision(6);
200   std::vector<double> running_times = get_intersection_runtime();
201   run_boost_voronoi_test(running_times);
202   run_cgal_delaunay_test(running_times);
203   bf.close();
204   return 0;
205 }
206