|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r77819 - in sandbox/gtl: doc libs/polygon/benchmark/benchmark_results/plots
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-07 13:31:02
Author: asydorchuk
Date: 2012-04-07 13:31:00 EDT (Sat, 07 Apr 2012)
New Revision: 77819
URL: http://svn.boost.org/trac/boost/changeset/77819
Log:
Finalizing benchmark documentation page. Updating plots.
Binary files modified:
sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_10.png
sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_100.png
sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_1000.png
sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_10000.png
sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_100000.png
sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_1000000.png
sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_10.png
sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_100.png
sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_1000.png
sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_10000.png
sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_100000.png
sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_1000000.png
Text files modified:
sandbox/gtl/doc/voronoi_benchmark.htm | 328 +++++++++++++++++++++++++++++++++++++++
sandbox/gtl/doc/voronoi_main.htm | 20 +
2 files changed, 339 insertions(+), 9 deletions(-)
Modified: sandbox/gtl/doc/voronoi_benchmark.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_benchmark.htm (original)
+++ sandbox/gtl/doc/voronoi_benchmark.htm 2012-04-07 13:31:00 EDT (Sat, 07 Apr 2012)
@@ -14,6 +14,9 @@
+
+
+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title></head><body>
@@ -89,8 +92,329 @@
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header -->
<br>
<p></p>
- <h1>Voronoi Benchmark<br>
- </h1></td>
+ <h1>Voronoi Benchmark</h1>There are not many known Voronoi libraries that are capable to satisfy following set of conditions:<br>
+ <ul>
+ <li>could handle both point and segment input geometries;</li>
+ <li>give exact warranties about algorithm robustness and output topology;<br>
+ </li>
+ <li>compute output geometries within precision of the output coordinate type.</li>
+ </ul>
+Apart from Boost.Polygon Voronoi we managed to find just one library that meets those requirements: CGAL
+(while it is clearly defined in CGAL documentation that it's capable to
+handle the first two items, we didn't find any clear specification on
+the third item). Taking into account that CGAL is well-known in
+computational geometry area it should be clear why it is the main
+target of this benchmark comparison. Other libraries (OpenVoronoi, QHull), that at least
+partially satisfy above requirements would be added to this benchmark
+incrementally (we are open for suggestions).<br>
+
+ <h2>Voronoi Benchmark Details<br>
+
+ </h2>
+
+The benchmark consists of two parts. The first one constructs Voronoi diagram of a set of random points (voronoi_benchmark_points.cpp), the second one constructs Voronoi diagram of a set of random segments (voronoi_benchmark_segments.cpp).
+We ensure that input data sets are the same for both libraries by
+initializing random generator with the same seed. There is also one
+important detail to admit about Voronoi of segments: both Boost and
+CGAL implementation consider each segment as 3 input objects (segment
+itself and its endpoints), thus the running time one may expect would
+be at least three times slower for Voronoi of segments comparing to
+Voronoi of points.<br>
+ <br>
+The benchmark was executed on the following two systems:<br>
+ <br>
+Hardware: Intel i5-7600 2.8 GHz, 4GiB RAM.<br>
+OS: Windows 7 Professional 32-bit.<br>
+Libraries: Boost 1.48.0, CGAL-4.0.<br>
+ <br>
+Hardware: Intel i5-7600 2.8 GHz, 4GiB RAM.<br>
+
+OS: Ubuntu 11.10 64-bit.<br>
+
+Libraries: Boost 1.48.0, CGAL-4.0, GMP 5.0.4, MPFR 3.1.0 + cumulative patch.<br>
+
+ <h2>Voronoi Benchmark Results</h2>
+
+
+
+ <h3>Random Points Benchmark</h3>
+
+ <table style="text-align: left; width: 100%; margin-left: auto; margin-right: auto;" border="1" cellpadding="2" cellspacing="2">
+ <tbody>
+ <tr>
+ <td colspan="2" rowspan="1" style="vertical-align: top; text-align: center;">Test specification<br>
+ </td>
+ <td colspan="4" rowspan="1" style="vertical-align: top; text-align: center;">Average construction time (in secs)<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: center;">Number of Points<br>
+ </td>
+ <td style="vertical-align: top; text-align: center;">Number of Runs<br>
+ </td>
+ <td style="vertical-align: top; text-align: center;">Boost Win-32<br>
+ </td>
+ <td style="vertical-align: top; text-align: center;">CGAL Win-32<br>
+ </td>
+ <td style="vertical-align: top; text-align: center;">Boost Linux-64<br>
+ </td>
+ <td style="vertical-align: top; text-align: center;">CGAL Linux-64<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: right;">10<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">100000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.000027<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.000116<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.000013<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.000052<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: right;">100<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">10000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.000392<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.002649<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.000192<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;"> 0.001150<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: right;">1000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">1000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.004541<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.039140<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.002130<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.016680<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: right;">10000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">100<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.047540<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.684090<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.022900<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.297900<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: right;">100000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">10<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.530200<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;"> 16.904600<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.274000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">8.047000<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: right;">1000000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">1<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">5.882000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">566.056000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">3.290000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">315.740000<br>
+ </td>
+ </tr>
+ </tbody>
+ </table>
+ <br>
+ <table style="text-align: left;" border="1" cellpadding="2" cellspacing="2">
+ <tbody>
+ <tr>
+ <td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_points_10.png"></td>
+ <td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_points_100.png"></td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_points_1000.png"></td>
+ <td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_points_10000.png"></td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_points_100000.png"></td>
+ <td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_points_1000000.png"></td>
+ </tr>
+ </tbody>
+ </table>
+
+
+ <h3>Random Segments Benchmark</h3>
+
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
+ <tbody>
+ <tr>
+ <td colspan="2" rowspan="1" style="vertical-align: top; text-align: center;">Test specification<br>
+ </td>
+ <td colspan="4" rowspan="1" style="vertical-align: top; text-align: center;">Average construction time (in secs)</td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: center;">Number of Segments<br>
+ </td>
+ <td style="vertical-align: top; text-align: center;">Number of Runs<br>
+ </td>
+ <td style="vertical-align: top; text-align: center;">Boost Win-32<br>
+ </td>
+ <td style="vertical-align: top; text-align: center;">CGAL Win-32<br>
+ </td>
+ <td style="vertical-align: top; text-align: center;">Boost Linux-64<br>
+ </td>
+ <td style="vertical-align: top; text-align: center;">CGAL Linux-64<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: right;">10<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">100000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.000290<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.001047<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.000165<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.000483<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: right;">100<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">10000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.003655<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.014812<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.002006<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.007006<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: right;">1000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">1000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.038158<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.177315<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.020440<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.084000<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: right;">10000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">100<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.389470<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">2.561340<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;"> 0.209700<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">1.191900<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: right;">100000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">10<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">4.031300<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">49.314600<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">2.228000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">23.538000<br>
+ </td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: right;">1000000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">1<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">40.912000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">1640.830000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">22.250000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">856.650000<br>
+ </td>
+ </tr>
+ </tbody>
+ </table>
+ <br>
+ <table style="text-align: left;" border="1" cellpadding="2" cellspacing="2">
+ <tbody>
+ <tr>
+ <td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_10.png"></td>
+ <td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_100.png"></td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_1000.png"></td>
+ <td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_10000.png"></td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_100000.png"></td>
+ <td style="vertical-align: top;"><img style="width: 500px; height: 300px;" alt="" src="../libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_1000000.png"></td>
+ </tr>
+ </tbody>
+ </table>
+<span style="font-weight: bold;"></span>
+ <h2>Voronoi Benchmark Conclusions<br>
+
+ </h2>
+
+
+The main conclusions for the benchmark results above are following:<br>
+ <ul>
+ <li>There is no input size range were CGAL would outperform Boost.Polygon Voronoi.<br>
+ </li>
+ <li>Boost.Polygon Voronoi of points is 4 times faster for small
+input data sets (10 points) and this factor grows up to 100 for large
+input data sets (1000000 points).</li>
+ <li>Boost.Polygon Voronoi of segments is 3 times faster for
+small input data sets (10 segments) and this factor grows up to 40 for
+large input data sets (1000000 segments).</li>
+ <li>Boost.Polygon
+Voronoi is capable to construct Voronoi of 10000 points or 1000
+segments in 0.02 seconds. This allows to produce real time frame rate
+for those quantities.</li>
+
+ </ul>
+ <span style="font-weight: bold;"></span></td>
</tr>
<tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
Modified: sandbox/gtl/doc/voronoi_main.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_main.htm (original)
+++ sandbox/gtl/doc/voronoi_main.htm 2012-04-07 13:31:00 EDT (Sat, 07 Apr 2012)
@@ -33,6 +33,8 @@
+
+
<meta http-equiv="Content-Language" content="en-us">
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Contents</title><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta http-equiv="content-type" content="text/html; charset=utf-8"><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body>
@@ -119,9 +121,14 @@
</h1><img style="width: 900px; height: 300px;" alt="" src="images/voronoi3.png"><br>
The Boost.Polygon Voronoi library provides functionality to construct Voronoi diagrams
of a set of points and segments in 2D space with the following set of
-limitations: 1) coordinates of input points and endpoints of segments
-should be of integer type; 2) input segments should not intersect
-except their endpoints. While the first restriction is permanent (it
+limitations:<br>
+ <ul>
+ <li>coordinates of input points and endpoints of segments
+should be of integer type;</li>
+ <li>input segments should not intersect
+except their endpoints.</li>
+ </ul>
+While the first restriction is permanent (it
allows to give warranties for algorithm output precision and execution),
the second one may be resolved using Boost.Polygon functionality.
Strong sides of the
@@ -146,7 +153,7 @@
issues, numeric stability issues. Voronoi implementation avoids the
first type of issues using pure STL data structure, thus you won't find
any operator new in the code. The second category of problems is
-resolved using multiprecision-precision geometric predicates.
+resolved using multiprecision geometric predicates.
Even for commercial implementations usage of such predicates usually
results in huge performance slowdown. Here is another strong side of
Voronoi: we avoid multiprecision computations in 95% of cases using
@@ -254,7 +261,7 @@
<br>
Isn't that simple? The library also provides clear interfaces to associate user data with output geometries, efficiently traverse Voronoi graph and utilities to visualize output primitives (e.g. discretization of parabolic edges, clipping of linear edges). More details on those is covered in the basic Voronoi tutorial. Advanced usage of the library with configuration of the coordinate types is explained in the advanced Voronoi tutorial.<br>
<br>
- <h2>No Third-party Dependencies<br>
+ <h2>No Third Party Dependencies<br>
</h2>
Yes, the library doesn't depend on any 3rd party code. Even more than
that there is only one dependency on Boost library: boost/cstdint.hpp.
@@ -278,7 +285,6 @@
</h2>
Below one may find list of main directions for the future development of the library.<br>
- <br>
High-priority tasks that already have approximate implementation plan (some of those may be proposed as future GSoC projects):<br>
<ul>
<li>Implementing Delaunay triangulation data structure.<br>
@@ -290,7 +296,7 @@
of this data structure is to automatically filter Voronoi edges that
belong to those areas.</li>
<li>Implementing data structure built on top of Voronoi diagram that allows to execute nearest neighbor queries in O(log N) time.<br>
-Note: this would be sort of kd-tree data structure built on top of bounding rectangles around Voronoi cells.</li>
+Note: there should be r-tree data structure available soon in the Boost libraries.</li>
<li>Providing interface to retrieve convex hull of a set of
points and segments from Voronoi builder once the Voronoi diagram is
Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_10.png
==============================================================================
Binary files. No diff available.
Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_100.png
==============================================================================
Binary files. No diff available.
Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_1000.png
==============================================================================
Binary files. No diff available.
Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_10000.png
==============================================================================
Binary files. No diff available.
Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_100000.png
==============================================================================
Binary files. No diff available.
Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_1000000.png
==============================================================================
Binary files. No diff available.
Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_10.png
==============================================================================
Binary files. No diff available.
Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_100.png
==============================================================================
Binary files. No diff available.
Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_1000.png
==============================================================================
Binary files. No diff available.
Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_10000.png
==============================================================================
Binary files. No diff available.
Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_100000.png
==============================================================================
Binary files. No diff available.
Modified: sandbox/gtl/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_1000000.png
==============================================================================
Binary files. No diff available.
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk