Subject: [Boost-commit] svn:boost r78001 - in sandbox/gtl/libs/polygon/benchmark: . benchmark_results
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-15 17:41:06
Author: asydorchuk
Date: 2012-04-15 17:41:06 EDT (Sun, 15 Apr 2012)
New Revision: 78001
URL: http://svn.boost.org/trac/boost/changeset/78001
Log:
Adding S-Hull to the benchmarks.
Text files modified:
sandbox/gtl/libs/polygon/benchmark/Jamfile.v2 | 3 ++
sandbox/gtl/libs/polygon/benchmark/benchmark_results/benchmark_points.txt | 8 +++++++
sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_points.cpp | 42 ++++++++++++++++++++++++++++++++++++++++
3 files changed, 53 insertions(+), 0 deletions(-)
Modified: sandbox/gtl/libs/polygon/benchmark/Jamfile.v2
==============================================================================
--- sandbox/gtl/libs/polygon/benchmark/Jamfile.v2 (original)
+++ sandbox/gtl/libs/polygon/benchmark/Jamfile.v2 2012-04-15 17:41:06 EDT (Sun, 15 Apr 2012)
@@ -25,12 +25,15 @@
# If follow official documentation of CGAL it takes 30 mins to
# set up properly CGAL and required libraries (GMP, MPFR).
path-constant CGAL_ROOT : "/home/slevin/Workspace/Libraries/CGAL" ;
+path-constant SHULL_ROOT : "/home/slevin/Workspace/Libraries/s_hull" ;
project benchmark
:
requirements
<include>$(CGAL_ROOT)/include
<library>$(CGAL_ROOT)/lib/libCGAL.so
<library>$(CGAL_ROOT)/lib/libCGAL_Core.so
+ <include>$(SHULL_ROOT)
+ <library>$(SHULL_ROOT)/s_hull.so
;
alias "benchmark-points"
Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_results/benchmark_points.txt
==============================================================================
--- sandbox/gtl/libs/polygon/benchmark/benchmark_results/benchmark_points.txt (original)
+++ sandbox/gtl/libs/polygon/benchmark/benchmark_results/benchmark_points.txt 2012-04-15 17:41:06 EDT (Sun, 15 Apr 2012)
@@ -42,3 +42,11 @@
| 100000 | 10 | 8.047000 |
| 1000000 | 1 | 315.740000 |
+S-Hull Triangulation of Points:
+| 10 | 100000 | 0.000012 |
+| 100 | 10000 | 0.000139 |
+| 1000 | 1000 | 0.002010 |
+| 10000 | 100 | 0.028300 |
+| 100000 | 10 | 0.432000 |
+| 1000000 | 1 | 6.350000 |
+
Modified: sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_points.cpp
==============================================================================
--- sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_points.cpp (original)
+++ sandbox/gtl/libs/polygon/benchmark/voronoi_benchmark_points.cpp 2012-04-15 17:41:06 EDT (Sun, 15 Apr 2012)
@@ -37,6 +37,9 @@
typedef CGAL::Segment_Delaunay_graph_2<Gt> SDT_CGAL;
typedef SDT_CGAL::Point_2 Point_CGAL;
+// Includes for 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};
@@ -87,11 +90,50 @@
bf << "\n";
}
+void run_shull_test() {
+ boost::mt19937 gen(RANDOM_SEED);
+ bf << "S-Hull Triangulation of Points:\n";
+ // This value is required by S-Hull as it doesn't seem to support properly
+ // coordinates with absolute value higher than 100.
+ float koef = 100.0 / (1 << 16) / (1 << 15);
+ for (int i = 0; i < NUM_TESTS; ++i) {
+ timer.restart();
+ 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.
+ 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 = 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();
+ run_shull_test();
bf.close();
return 0;
}