123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151 |
- // 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;
- }
|