[Boost-commit] svn:boost r77771 - sandbox/gtl/libs/polygon/benchmark

Subject: [Boost-commit] svn:boost r77771 - sandbox/gtl/libs/polygon/benchmark
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-04 19:10:36

Author: asydorchuk
Date: 2012-04-04 19:10:34 EDT (Wed, 04 Apr 2012)
New Revision: 77771
URL: http://svn.boost.org/trac/boost/changeset/77771

Log:
Adding Voronoi vs CGAL benchmarks.
Added:
   sandbox/gtl/libs/polygon/benchmark/Jamfile.v2   (contents, props changed)
   sandbox/gtl/libs/polygon/benchmark/benchmark_points.txt   (contents, props changed)
   sandbox/gtl/libs/polygon/benchmark/benchmark_segments.txt   (contents, props changed)
   sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_points.cpp   (contents, props changed)
   sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_segments.cpp   (contents, props changed)

Added: sandbox/gtl/libs/polygon/benchmark/Jamfile.v2
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/benchmark/Jamfile.v2	2012-04-04 19:10:34 EDT (Wed, 04 Apr 2012)
@@ -0,0 +1,37 @@
+#          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)
+
+import testing ;
+
+# It took five hours to configure CGAL.
+# If you want to run the benchmarks specify the following paths and
+# make sure that following libraries are compiled and do exist.
+# Good luck!
+path-constant CGAL_ROOT : "d:/Programming/CGAL-4.0" ;
+path-constant GMP_ROOT : "d:/Programming/CGAL-4.0/auxiliary/gmp" ;
+project polygon-test
+    :
+    requirements
+        <include>$(CGAL_ROOT)/include
+        <include>$(GMP_ROOT)/include
+	<library>$(BOOST_ROOT)/libs/thread/build//boost_thread
+	<library>$(BOOST_ROOT)/lib/libboost_thread-vc90-mt-1_48.lib
+        <library>$(GMP_ROOT)/lib/libgmp-10.lib
+        <library>$(GMP_ROOT)/lib/libmpfr-4.lib
+	<library>$(CGAL_ROOT)/lib/libCGAL-vc90-mt-4.0.lib
+	<library>$(CGAL_ROOT)/lib/libCGAL_Core-vc90-mt-4.0.lib
+    ;
+
+alias "benchmark-points"
+    :
+        [ run voronoi_benchmark_points.cpp ]
+    ;
+
+alias "benchmark-segments"
+    :
+        [ run voronoi_benchmark_segments.cpp ]
+    ;
+
+

Added: sandbox/gtl/libs/polygon/benchmark/benchmark_points.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/benchmark/benchmark_points.txt	2012-04-04 19:10:34 EDT (Wed, 04 Apr 2012)
@@ -0,0 +1,21 @@
+System: CPU i5-7600 2.8 GHz, 4Gb RAM.
+OS: Windows 7 Professional 32 bit.
+Compiler: MSVC-9.0.
+
+Boost.Polygon Voronoi of Points:
+|               10 |          100000 |          0.000027 |
+|              100 |           10000 |          0.000392 |
+|             1000 |            1000 |          0.004541 |
+|            10000 |             100 |          0.047540 |
+|           100000 |              10 |          0.530200 |
+|          1000000 |               1 |          5.882000 |
+
+CGAL Triangulation of Points:
+|               10 |          100000 |          0.000116 |
+|              100 |           10000 |          0.002649 |
+|             1000 |            1000 |          0.039140 |
+|            10000 |             100 |          0.684090 |
+|           100000 |              10 |         16.904600 |
+|          1000000 |               1 |        566.056000 |
+
+

Added: sandbox/gtl/libs/polygon/benchmark/benchmark_segments.txt
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/benchmark/benchmark_segments.txt	2012-04-04 19:10:34 EDT (Wed, 04 Apr 2012)
@@ -0,0 +1,17 @@
+System: CPU i5-7600 2.8 GHz, 4Gb RAM.
+OS: Windows 7 Professional 32 bit.
+Compiler: MSVC-9.0.
+
+Boost.Polygon Voronoi of Segments:
+|               10 |          100000 |          0.000272 |
+|              100 |           10000 |          0.003463 |
+|             1000 |            1000 |          0.035893 |
+|            10000 |             100 |          0.362920 |
+|           100000 |              10 |          3.742800 |
+
+CGAL Triangulation of Segments:
+|               10 |          100000 |          0.001020 |
+|              100 |           10000 |          0.014536 |
+|             1000 |            1000 |          0.174651 |
+|            10000 |             100 |          2.534000 |
+|           100000 |              10 |         49.125100 |

Added: sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_points.cpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_points.cpp	2012-04-04 19:10:34 EDT (Wed, 04 Apr 2012)
@@ -0,0 +1,99 @@
+// 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 <iomanip>
+#include <iostream>
+#include <fstream>
+#include <numeric>
+#include <vector>
+
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/timer.hpp>
+
+typedef boost::int32_t int32;
+
+// Include for 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 CGAL library.
+# include <CGAL/Quotient.h>
+# include <CGAL/MP_Float.h>
+typedef CGAL::Quotient<CGAL::MP_Float> ENT;
+#include <CGAL/Simple_cartesian.h>
+typedef CGAL::Simple_cartesian<double> CK;
+typedef CGAL::Simple_cartesian<ENT> EK;
+#include <CGAL/Segment_Delaunay_graph_filtered_traits_2.h>
+#include <CGAL/Segment_Delaunay_graph_2.h>
+typedef CGAL::Segment_Delaunay_graph_filtered_traits_2<
+    CK, CGAL::Field_with_sqrt_tag, EK, CGAL::Field_tag> Gt;
+typedef CGAL::Segment_Delaunay_graph_2<Gt> SDT_CGAL;
+typedef SDT_CGAL::Point_2 Point_CGAL;
+
+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 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;
+}
+
+void run_boost_test() {
+  boost::mt19937 gen(RANDOM_SEED);
+  bf << "Boost.Polygon Voronoi of Points:\n";
+  for (int i = 0; i < NUM_TESTS; ++i) {
+    timer.restart();
+    for (int j = 0; j < NUM_RUNS[i]; ++j) {
+      VB_BOOST vb;
+      VD_BOOST vd;
+      for (int k = 0; k < NUM_POINTS[i]; ++k) {
+        vb.insert_point(static_cast<int32>(gen()),
+                        static_cast<int32>(gen()));
+      }
+      vb.construct(&vd);
+    }
+    double time_per_test = timer.elapsed() / NUM_RUNS[i];
+    format_line(NUM_POINTS[i], NUM_RUNS[i], time_per_test);
+  }
+  bf << "\n";
+}
+
+void run_cgal_test() {
+  boost::mt19937 gen(RANDOM_SEED);
+  bf << "CGAL Triangulation of Points:\n";
+  for (int i = 0; i < NUM_TESTS; ++i) {
+    timer.restart();
+    for (int j = 0; j < NUM_RUNS[i]; ++j) {
+      SDT_CGAL dt;
+      for (int k = 0; k < NUM_POINTS[i]; ++k) {
+        dt.insert(Point_CGAL(static_cast<int32>(gen()),
+                             static_cast<int32>(gen())));
+      }
+    }
+    double time_per_test = timer.elapsed() / 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_test();
+  run_cgal_test();
+  bf.close();
+  return 0;
+}

Added: sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_segments.cpp
==============================================================================
--- (empty file)
+++ sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_segments.cpp	2012-04-04 19:10:34 EDT (Wed, 04 Apr 2012)
@@ -0,0 +1,143 @@
+// 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 <iomanip>
+#include <iostream>
+#include <fstream>
+#include <numeric>
+#include <vector>
+
+#include <boost/random/mersenne_twister.hpp>
+#include <boost/timer.hpp>
+
+typedef boost::int32_t int32;
+
+// Include for Boost.Polygon Voronoi library.
+#include <boost/polygon/voronoi.hpp>
+typedef boost::polygon::voronoi_diagram<double> VD_BOOST;
+
+// Includes for CGAL library.
+# include <CGAL/Quotient.h>
+# include <CGAL/MP_Float.h>
+typedef CGAL::Quotient<CGAL::MP_Float> ENT;
+#include <CGAL/Simple_cartesian.h>
+typedef CGAL::Simple_cartesian<double> CK;
+typedef CGAL::Simple_cartesian<ENT> EK;
+#include <CGAL/Segment_Delaunay_graph_filtered_traits_2.h>
+#include <CGAL/Segment_Delaunay_graph_2.h>
+typedef CGAL::Segment_Delaunay_graph_filtered_traits_2<
+    CK, CGAL::Field_with_sqrt_tag, EK, CGAL::Field_tag> Gt;
+typedef CGAL::Segment_Delaunay_graph_2<Gt> SDT_CGAL;
+typedef SDT_CGAL::Point_2 Point_CGAL;
+typedef SDT_CGAL::Site_2 Site_CGAL;
+
+// Include Boost.Polygon library.
+#include <boost/polygon/polygon.hpp>
+typedef boost::polygon::point_data<int32> POINT_POLYGON;
+typedef boost::polygon::directed_line_segment_data<int32> SEGMENT_POLYGON;
+typedef boost::polygon::directed_line_segment_set_data<int32> SSD_POLYGON;
+
+const int RANDOM_SEED = 27;
+const int NUM_TESTS = 5;
+const int NUM_SEGMENTS[] = {10, 100, 1000, 10000, 100000};
+const int NUM_RUNS[] = {100000, 10000, 1000, 100, 10};
+std::ofstream bf("benchmark_segments.txt", std::ios_base::out | std::ios_base::app);
+boost::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;
+}
+
+std::vector<double> get_intersection_runtime() {
+  std::vector<double> running_times;
+  boost::mt19937 gen(RANDOM_SEED);
+  for (int i = 0; i < NUM_TESTS; ++i) {
+    timer.restart();
+    for (int j = 0; j < NUM_RUNS[i]; ++j) {
+      SSD_POLYGON ssd;
+      for (int k = 0; k < NUM_SEGMENTS[i]; ++k) {
+        int32 x1 = gen();
+        int32 y1 = gen();
+        int32 dx = (gen() & 1023) + 1;
+        int32 dy = (gen() & 1023) + 1;
+        ssd.insert(SEGMENT_POLYGON(POINT_POLYGON(x1, y1),
+                                   POINT_POLYGON(x1 + dx, y1 + dy)));
+      }
+      ssd.clean();
+    }
+    double time_per_test = timer.elapsed() / NUM_RUNS[i];
+    running_times.push_back(timer.elapsed());
+  }
+  return running_times;
+}
+
+void run_voronoi_test(const std::vector<double> &running_times) {
+  boost::mt19937 gen(RANDOM_SEED);
+  bf << "Boost.Polygon Voronoi of Segments:\n";
+  for (int i = 0; i < NUM_TESTS; ++i) {
+    timer.restart();
+    for (int j = 0; j < NUM_RUNS[i]; ++j) {
+      SSD_POLYGON ssd;
+      VD_BOOST vd;
+      for (int k = 0; k < NUM_SEGMENTS[i]; ++k) {
+        int32 x1 = gen();
+        int32 y1 = gen();
+        int32 dx = (gen() & 1023) + 1;
+        int32 dy = (gen() & 1023) + 1;
+        ssd.insert(SEGMENT_POLYGON(POINT_POLYGON(x1, y1),
+                                   POINT_POLYGON(x1 + dx, y1 + dy)));
+      }
+      boost::polygon::construct_voronoi_segments(ssd, &vd);
+    }
+    double time_per_test = (timer.elapsed() - running_times[i]) / NUM_RUNS[i];
+    format_line(NUM_SEGMENTS[i], NUM_RUNS[i], time_per_test);
+  }
+  bf << "\n";
+}
+
+void run_cgal_test(const std::vector<double> &running_times) {
+  boost::mt19937 gen(RANDOM_SEED);
+  bf << "CGAL Triangulation of Segments:\n";
+  for (int i = 0; i < NUM_TESTS; ++i) {
+    timer.restart();
+    for (int j = 0; j < NUM_RUNS[i]; ++j) {
+      SSD_POLYGON ssd;
+      for (int k = 0; k < NUM_SEGMENTS[i]; ++k) {
+        int32 x1 = gen();
+        int32 y1 = gen();
+        int32 dx = (gen() & 1023) + 1;
+        int32 dy = (gen() & 1023) + 1;
+        ssd.insert(SEGMENT_POLYGON(POINT_POLYGON(x1, y1),
+                                   POINT_POLYGON(x1 + dx, y1 + dy)));
+      }
+      SDT_CGAL dt;
+      for (SSD_POLYGON::iterator_type it = ssd.begin(); it != ssd.end(); ++it) {
+        dt.insert(Site_CGAL::construct_site_2(
+          Point_CGAL(it->low().x(), it->low().y()),
+          Point_CGAL(it->high().x(), it->high().y())));
+      }
+    }
+    double time_per_test = (timer.elapsed() - running_times[i]) / NUM_RUNS[i];
+    format_line(NUM_SEGMENTS[i], NUM_RUNS[i], time_per_test);
+  }
+  bf << "\n";
+}
+
+int main() {
+  bf << std::setiosflags(std::ios::right | std::ios::fixed)
+     << std::setprecision(6);
+  std::vector<double> running_times = get_intersection_runtime();
+  run_voronoi_test(running_times);
+  run_cgal_test(running_times);
+  bf.close();
+  return 0;
+}