1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
|
// Boost.Polygon library voronoi_benchmark.cpp file
// Copyright Andrii Sydorchuk 2010-2012.
// Distributed under 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)
// See http://www.boost.org for updates, documentation, and revision history.
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <fstream>
#include <numeric>
#include <vector>
#include <utility>
#include <boost/random/mersenne_twister.hpp>
#include <boost/timer/timer.hpp>
typedef boost::int32_t int32;
using boost::timer::cpu_times;
using boost::timer::nanosecond_type;
// Include for the Boost.Polygon Voronoi library.
#include <boost/polygon/voronoi.hpp>
typedef boost::polygon::default_voronoi_builder VB_BOOST;
typedef boost::polygon::voronoi_diagram<double> VD_BOOST;
// Includes for the CGAL library.
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel CGAL_KERNEL;
typedef CGAL::Delaunay_triangulation_2<CGAL_KERNEL> DT_CGAL;
typedef CGAL_KERNEL::Point_2 POINT_CGAL;
// Includes for the S-Hull library.
#include <s_hull.h>
const int RANDOM_SEED = 27;
const int NUM_TESTS = 6;
const int NUM_POINTS[] = {10, 100, 1000, 10000, 100000, 1000000};
const int NUM_RUNS[] = {100000, 10000, 1000, 100, 10, 1};
std::ofstream bf("benchmark_points.txt",
std::ios_base::out | std::ios_base::app);
boost::timer::cpu_timer timer;
void format_line(int num_points, int num_tests, double time_per_test) {
bf << "| " << std::setw(16) << num_points << " ";
bf << "| " << std::setw(15) << num_tests << " ";
bf << "| " << std::setw(17) << time_per_test << " ";
bf << "|" << std::endl;
}
double get_elapsed_secs() {
cpu_times elapsed_times(timer.elapsed());
return 1E-9 * static_cast<double>(
elapsed_times.system + elapsed_times.user);
}
void run_boost_voronoi_test() {
boost::mt19937 gen(RANDOM_SEED);
bf << "Boost.Polygon Voronoi Diagram of Points:\n";
for (int i = 0; i < NUM_TESTS; ++i) {
timer.start();
for (int j = 0; j < NUM_RUNS[i]; ++j) {
VB_BOOST vb;
VD_BOOST vd;
for (int k = 0; k < NUM_POINTS[i]; ++k) {
int32 x = static_cast<int32>(gen());
int32 y = static_cast<int32>(gen());
vb.insert_point(x, y);
}
vb.construct(&vd);
}
double time_per_test = get_elapsed_secs() / NUM_RUNS[i];
format_line(NUM_POINTS[i], NUM_RUNS[i], time_per_test);
}
bf << "\n";
}
void run_cgal_delaunay_test() {
boost::mt19937 gen(RANDOM_SEED);
bf << "CGAL Delaunay Triangulation of Points:\n";
for (int i = 0; i < NUM_TESTS; ++i) {
timer.start();
for (int j = 0; j < NUM_RUNS[i]; ++j) {
DT_CGAL dt;
std::vector<POINT_CGAL> points;
for (int k = 0; k < NUM_POINTS[i]; ++k) {
int32 x = static_cast<int32>(gen());
int32 y = static_cast<int32>(gen());
points.push_back(POINT_CGAL(x, y));
}
// CGAL's implementation sorts points along
// the Hilbert curve implicitly to improve
// spatial ordering of the input geometries.
dt.insert(points.begin(), points.end());
}
double time_per_test = get_elapsed_secs() / NUM_RUNS[i];
format_line(NUM_POINTS[i], NUM_RUNS[i], time_per_test);
}
bf << "\n";
}
void run_shull_delaunay_test() {
boost::mt19937 gen(RANDOM_SEED);
bf << "S-Hull Delaunay Triangulation of Points:\n";
// This value is required by S-Hull as it doesn't seem to support properly
// coordinates with the absolute value higher than 100.
float koef = 100.0 / (1 << 16) / (1 << 15);
for (int i = 0; i < NUM_TESTS; ++i) {
timer.start();
for (int j = 0; j < NUM_RUNS[i]; ++j) {
// S-Hull doesn't deal properly with duplicates so we need
// to eliminate them before running the algorithm.
std::vector< pair<int32, int32> > upts;
std::vector<Shx> pts;
std::vector<Triad> triads;
Shx pt;
for (int k = 0; k < NUM_POINTS[i]; ++k) {
int32 x = static_cast<int32>(gen());
int32 y = static_cast<int32>(gen());
upts.push_back(std::make_pair(x, y));
}
// Absolutely the same code is used by the Boost.Polygon Voronoi library.
std::sort(upts.begin(), upts.end());
upts.erase(std::unique(upts.begin(), upts.end()), upts.end());
for (int k = 0; k < upts.size(); ++k) {
pt.r = koef * upts[k].first;
pt.c = koef * upts[k].second;
pt.id = k;
pts.push_back(pt);
}
s_hull_del_ray2(pts, triads);
}
double time_per_test = get_elapsed_secs() / NUM_RUNS[i];
format_line(NUM_POINTS[i], NUM_RUNS[i], time_per_test);
}
bf << "\n";
}
int main() {
bf << std::setiosflags(std::ios::right | std::ios::fixed)
<< std::setprecision(6);
run_boost_voronoi_test();
run_cgal_delaunay_test();
run_shull_delaunay_test();
bf.close();
return 0;
}
|
