libs/polygon/benchmark/voronoi_benchmark_points.cpp
// 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;
}