[Boost-commit] svn:boost r85795 - trunk/libs/polygon/benchmark

Subject: [Boost-commit] svn:boost r85795 - trunk/libs/polygon/benchmark
From: sydorchuk.andriy_at_[hidden]
Date: 2013-09-19 16:48:25

Author: asydorchuk
Date: 2013-09-19 16:48:25 EDT (Thu, 19 Sep 2013)
New Revision: 85795
URL: http://svn.boost.org/trac/boost/changeset/85795

Log:
Polygon: updating CGAL portion of Voronoi segment benchmark.

Text files modified: 
   trunk/libs/polygon/benchmark/voronoi_benchmark_segments.cpp |    97 +++++++++++++++++++++++++-------------- 
   1 files changed, 61 insertions(+), 36 deletions(-)

Modified: trunk/libs/polygon/benchmark/voronoi_benchmark_segments.cpp
==============================================================================
--- trunk/libs/polygon/benchmark/voronoi_benchmark_segments.cpp	Thu Sep 19 16:27:08 2013	(r85794)
+++ trunk/libs/polygon/benchmark/voronoi_benchmark_segments.cpp	2013-09-19 16:48:25 EDT (Thu, 19 Sep 2013)	(r85795)
@@ -16,26 +16,24 @@
 #include <utility>
 
 #include <boost/random/mersenne_twister.hpp>
-#include <boost/timer.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::voronoi_diagram<double> VD_BOOST;
 
 // Includes for the CGAL library.
-#include <CGAL/Quotient.h>
-#include <CGAL/MP_Float.h>
 #include <CGAL/Simple_cartesian.h>
 #include <CGAL/Segment_Delaunay_graph_filtered_traits_2.h>
 #include <CGAL/Segment_Delaunay_graph_2.h>
-typedef CGAL::Quotient<CGAL::MP_Float> ENT;
-typedef CGAL::Simple_cartesian<double> CK;
-typedef CGAL::Simple_cartesian<ENT> EK;
-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 CGAL::Simple_cartesian<double> K;
+typedef CGAL::Segment_Delaunay_graph_filtered_traits_without_intersections_2<K> GT;
+typedef CGAL::Segment_Delaunay_graph_2<GT>  SDT_CGAL;
 typedef SDT_CGAL::Point_2 Point_CGAL;
 typedef SDT_CGAL::Site_2 Site_CGAL;
 
@@ -51,7 +49,7 @@
 const int NUM_RUNS[] = {100000, 10000, 1000, 100, 10, 1};
 std::ofstream bf("benchmark_segments.txt",
                  std::ios_base::out | std::ios_base::app);
-boost::timer timer;
+boost::timer::cpu_timer timer;
 
 void format_line(int num_points, int num_tests, double time_per_test) {
   bf << "| " << std::setw(16) << num_points << " ";
@@ -60,7 +58,13 @@
   bf << "|" << std::endl;
 }
 
-void clean_segment_set(std::vector<SEGMENT_POLYGON> &data) {
+double get_elapsed_secs() {
+  cpu_times elapsed_times(timer.elapsed());
+  return 1E-9 * static_cast<double>(
+      elapsed_times.system + elapsed_times.user);
+}
+
+void clean_segment_set(std::vector<SEGMENT_POLYGON>* data) {
   typedef int32 Unit;
   typedef boost::polygon::scanline_base<Unit>::Point Point;
   typedef boost::polygon::scanline_base<Unit>::half_edge half_edge;
@@ -68,9 +72,9 @@
   std::vector<std::pair<half_edge, segment_id> > half_edges;
   std::vector<std::pair<half_edge, segment_id> > half_edges_out;
   segment_id id = 0;
-  half_edges.reserve(data.size());
-  for (std::vector<SEGMENT_POLYGON>::iterator it = data.begin();
-       it != data.end(); ++it) {
+  half_edges.reserve(data->size());
+  for (std::vector<SEGMENT_POLYGON>::iterator it = data->begin();
+       it != data->end(); ++it) {
     POINT_POLYGON l = it->low();
     POINT_POLYGON h = it->high();
     half_edges.push_back(std::make_pair(half_edge(l, h), id++));
@@ -85,19 +89,19 @@
     id = half_edges_out[i].second;
     POINT_POLYGON l = half_edges_out[i].first.first;
     POINT_POLYGON h = half_edges_out[i].first.second;
-    SEGMENT_POLYGON orig_seg = data[id];
+    SEGMENT_POLYGON orig_seg = data->at(id);
     if (orig_seg.high() < orig_seg.low())
       std::swap(l, h);
     result.push_back(SEGMENT_POLYGON(l, h));
   }
-  std::swap(result, data);
+  std::swap(result, *data);
 }
 
 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();
+    timer.start();
     for (int j = 0; j < NUM_RUNS[i]; ++j) {
       SSD_POLYGON ssd;
       for (int k = 0; k < NUM_SEGMENTS[i]; ++k) {
@@ -108,18 +112,18 @@
         ssd.push_back(SEGMENT_POLYGON(
             POINT_POLYGON(x1, y1), POINT_POLYGON(x1 + dx, y1 + dy)));
       }
-      clean_segment_set(ssd);
+      clean_segment_set(&ssd);
     }
-    running_times.push_back(timer.elapsed());
+    running_times.push_back(get_elapsed_secs());
   }
   return running_times;
 }
 
-void run_voronoi_test(const std::vector<double> &running_times) {
+void run_boost_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();
+    timer.start();
     for (int j = 0; j < NUM_RUNS[i]; ++j) {
       SSD_POLYGON ssd;
       VD_BOOST vd;
@@ -129,22 +133,24 @@
         int32 dx = (gen() & 1023) + 1;
         int32 dy = (gen() & 1023) + 1;
         ssd.push_back(SEGMENT_POLYGON(
-            POINT_POLYGON(x1, y1), POINT_POLYGON(x1 + dx, y1 + dy)));
+            POINT_POLYGON(x1, y1),
+            POINT_POLYGON(x1 + dx, y1 + dy)));
       }
-      clean_segment_set(ssd);
+      clean_segment_set(&ssd);
       boost::polygon::construct_voronoi(ssd.begin(), ssd.end(), &vd);
     }
-    double time_per_test = (timer.elapsed() - running_times[i]) / NUM_RUNS[i];
+    double time_per_test =
+        (get_elapsed_secs() - 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) {
+void run_cgal_delaunay_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();
+    timer.start();
     for (int j = 0; j < NUM_RUNS[i]; ++j) {
       SSD_POLYGON ssd;
       for (int k = 0; k < NUM_SEGMENTS[i]; ++k) {
@@ -152,18 +158,37 @@
         int32 y1 = gen();
         int32 dx = (gen() & 1023) + 1;
         int32 dy = (gen() & 1023) + 1;
-        ssd.push_back(SEGMENT_POLYGON(POINT_POLYGON(x1, y1),
-                                   POINT_POLYGON(x1 + dx, y1 + dy)));
+        ssd.push_back(SEGMENT_POLYGON(
+            POINT_POLYGON(x1, y1),
+            POINT_POLYGON(x1 + dx, y1 + dy)));
       }
-      clean_segment_set(ssd);
-      SDT_CGAL dt;
+      clean_segment_set(&ssd);
+
+      typedef std::vector<Point_CGAL> Points_container;
+      typedef std::vector<Points_container>::size_type Index_type;
+      typedef std::vector< std::pair<Index_type, Index_type> > Constraints_container;
+      Points_container points;
+      Constraints_container constraints;
+      points.reserve(ssd.size() * 2);
+      constraints.reserve(ssd.size());
       for (SSD_POLYGON::iterator 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())));
+        points.push_back(Point_CGAL(
+            boost::polygon::x(it->low()),
+            boost::polygon::y(it->low())));
+        points.push_back(Point_CGAL(
+            boost::polygon::x(it->high()),
+            boost::polygon::y(it->high())));
+        constraints.push_back(
+            std::make_pair(points.size() - 2, points.size() - 1));
       }
+
+      SDT_CGAL sdg;
+      sdg.insert_segments(
+          points.begin(), points.end(),
+          constraints.begin(), constraints.end());
     }
-    double time_per_test = (timer.elapsed() - running_times[i]) / NUM_RUNS[i];
+    double time_per_test =
+        (get_elapsed_secs() - running_times[i]) / NUM_RUNS[i];
     format_line(NUM_SEGMENTS[i], NUM_RUNS[i], time_per_test);
   }
   bf << "\n";
@@ -173,8 +198,8 @@
   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);
+  run_boost_voronoi_test(running_times);
+  run_cgal_delaunay_test(running_times);
   bf.close();
   return 0;
 }