Boost-Commit :

Date view	Thread view	Subject view	Author view

Subject: [Boost-commit] svn:boost r78003 - in sandbox/gtl: doc libs/polygon/benchmark/benchmark_results/plots
From: sydorchuk.andriy_at_[hidden]
Date: 2012-04-15 18:40:38

Next message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r78004 - sandbox/gtl/doc"
Previous message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r78002 - in sandbox/gtl/libs/polygon/benchmark: . benchmark_results"

Author: asydorchuk
Date: 2012-04-15 18:40:37 EDT (Sun, 15 Apr 2012)
New Revision: 78003
URL: http://svn.boost.org/trac/boost/changeset/78003

Log:
Adding S-Hull benchmark to the documentation.

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
Text files modified:
   sandbox/gtl/doc/voronoi_benchmark.htm | 98 ++++++++++++++++++++++++++++-----------
   sandbox/gtl/doc/voronoi_builder.htm | 24 +++++----
   2 files changed, 82 insertions(+), 40 deletions(-)

Modified: sandbox/gtl/doc/voronoi_benchmark.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_benchmark.htm (original)
+++ sandbox/gtl/doc/voronoi_benchmark.htm 2012-04-15 18:40:37 EDT (Sun, 15 Apr 2012)
@@ -1,19 +1,18 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html><head>
-
- <meta http-equiv="Content-Language" content="en-us">
+
+


- <meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
- <title>Voronoi Benchmark</title>
+ <meta http-equiv="Content-Language" content="en-us">


-</head><body>
+ <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Benchmark</title></head><body>
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">

 <tbody>
 <tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1">
 <div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277"><a title="www.boost.org home page" tabindex="2" style="border: medium none ;" href="http://www.boost.org/"> </a></div>
 <div style="margin: 5px;">
 <h3 class="navbar">Contents</h3>
@@ -88,21 +87,27 @@
 </li>
 <li>compute output geometries within precision of the output
coordinate type.</li>
+ </ul>Libraries included in the benchmark: 
+ <ul>
+ <li>Boost.Polygon Voronoi - satisfies all three items above. 
+ </li>
+ <li>CGAL - satisifes the first two items. CGAL is a well-known
+library in the computational geometry area, especially for its
+robustness.</li>
+ <li>S-Hull
+- doesn't satisfy any of the above items. S-Hull is a non-robust
+implementation of sweep-hull algorithm that constructs Delaunay
+triangulation of a set of points. 
+ </li>
 </ul>
-Apart from Boost.Polygon Voronoi we managed to find just one library
-that meets at least two of those requirements: CGAL
-(it is clearly defined in CGAL documentation that it's capable to
-handle the first two items, however there are no warranties on the
-output geometries precision). Taking into account that CGAL is
-well-known in the
-computational geometry area it should be clear why it is the main
-target of this benchmark comparison. Other libraries (OpenVoronoi, QHull, Triangle),
-that at least
-partially satisfy above requirements would be added to this benchmark
+There are only two robust imlementations in our benchmark:
+Boost.Polygon Voronoi and CGAL. Thus we are considering comparison of
+those two to be of the most interest. 
+ 
+Other libraries (OpenVoronoi, Triangle) would be added to this benchmark
incrementally (we are open for suggestions). 
 <h2>Important 
- </h2>
-While results of this benchmark show complete dominance of
+ </h2>While results of this benchmark show complete dominance of
the Boost.Polygon Voronoi over the CGAL Delaunay Graph implementation,
we would like to make it clear
that both libraries use different approach to construct Voronoi
@@ -140,10 +145,12 @@
as 3 input objects (segment itself and its endpoints), thus the running
time and memory usage for Voronoi of segments would be approximately at
least 3 times
-slower than for Voronoi of points; 
+slower than for Voronoi of points;</li>
+ <li>The S-Hull implementation doesn't process duplicate points properly, thus those are eliminated before the algorithm execution. 
 </li>
+
 </ul>
- 
+
The benchmark was executed on the following two system configurations: 
 
Hardware: Intel i5-7600 2.8 GHz, 4GiB RAM. 
@@ -161,7 +168,7 @@
 <tr>
 <td colspan="2" rowspan="1" style="vertical-align: top; text-align: center;">Test specification 
 </td>
- <td colspan="4" rowspan="1" style="vertical-align: top; text-align: center;">Average construction
+ <td colspan="6" rowspan="1" style="vertical-align: top; text-align: center;">Average construction
time (in secs) 
 </td>
 </tr>
@@ -178,12 +185,16 @@
 <td style="vertical-align: top; text-align: center;">CGAL
Win-32 
 </td>
- <td style="vertical-align: top; text-align: center;">Boost
+ <td style="vertical-align: top; text-align: center;">S-Hull Win-32 
+ </td>
+<td style="vertical-align: top; text-align: center;">Boost
Linux-64 
 </td>
 <td style="vertical-align: top; text-align: center;">CGAL
Linux-64 
+ </td><td style="vertical-align: top; text-align: center;">S-Hull Linux-64 
 </td>
+
 </tr>
 <tr>
 <td style="vertical-align: top; text-align: right;">10 
@@ -194,10 +205,14 @@
 </td>
 <td style="vertical-align: top; text-align: right;">0.000116 
 </td>
- <td style="vertical-align: top; text-align: right;">0.000013 
+ <td style="vertical-align: top; text-align: right;">0.000043 
+ </td>
+<td style="vertical-align: top; text-align: right;">0.000013 
 </td>
 <td style="vertical-align: top; text-align: right;">0.000052 
+ </td><td style="vertical-align: top; text-align: right;">0.000012 
 </td>
+
 </tr>
 <tr>
 <td style="vertical-align: top; text-align: right;">100 
@@ -208,10 +223,14 @@
 </td>
 <td style="vertical-align: top; text-align: right;">0.002649 
 </td>
- <td style="vertical-align: top; text-align: right;">0.000192 
+ <td style="vertical-align: top; text-align: right;">0.000521 
+ </td>
+<td style="vertical-align: top; text-align: right;">0.000192 
 </td>
 <td style="vertical-align: top; text-align: right;"> 0.001150 
+ </td><td style="vertical-align: top; text-align: right;">0.000139 
 </td>
+
 </tr>
 <tr>
 <td style="vertical-align: top; text-align: right;">1000 
@@ -222,10 +241,14 @@
 </td>
 <td style="vertical-align: top; text-align: right;">0.039140 
 </td>
- <td style="vertical-align: top; text-align: right;">0.002130 
+ <td style="vertical-align: top; text-align: right;">0.007125 
+ </td>
+<td style="vertical-align: top; text-align: right;">0.002130 
 </td>
 <td style="vertical-align: top; text-align: right;">0.016680 
+ </td><td style="vertical-align: top; text-align: right;">0.002010 
 </td>
+
 </tr>
 <tr>
 <td style="vertical-align: top; text-align: right;">10000 
@@ -236,10 +259,14 @@
 </td>
 <td style="vertical-align: top; text-align: right;">0.684090 
 </td>
- <td style="vertical-align: top; text-align: right;">0.022900 
+ <td style="vertical-align: top; text-align: right;">0.091640 
+ </td>
+<td style="vertical-align: top; text-align: right;">0.022900 
 </td>
 <td style="vertical-align: top; text-align: right;">0.297900 
+ </td><td style="vertical-align: top; text-align: right;">0.028300 
 </td>
+
 </tr>
 <tr>
 <td style="vertical-align: top; text-align: right;">100000 
@@ -250,10 +277,14 @@
 </td>
 <td style="vertical-align: top; text-align: right;"> 16.904600 
 </td>
- <td style="vertical-align: top; text-align: right;">0.274000 
+ <td style="vertical-align: top; text-align: right;">1.218000 
+ </td>
+<td style="vertical-align: top; text-align: right;">0.274000 
 </td>
 <td style="vertical-align: top; text-align: right;">8.047000 
+ </td><td style="vertical-align: top; text-align: right;">0.432000 
 </td>
+
 </tr>
 <tr>
 <td style="vertical-align: top; text-align: right;">1000000 
@@ -264,10 +295,14 @@
 </td>
 <td style="vertical-align: top; text-align: right;">566.056000 
 </td>
- <td style="vertical-align: top; text-align: right;">3.290000 
+ <td style="vertical-align: top; text-align: right;">15.394000 
+ </td>
+<td style="vertical-align: top; text-align: right;">3.290000 
 </td>
 <td style="vertical-align: top; text-align: right;">315.740000 
+ </td><td style="vertical-align: top; text-align: right;">6.350000 
 </td>
+
 </tr>
 </tbody>
 </table>
@@ -439,6 +474,11 @@
 <li>There is no input size range were CGAL would outperform
Boost.Polygon Voronoi. Even considering the fact that we didn't include
time it would take CGAL to compute coordinates of the Voronoi vertices.</li>
+ <li>The more interesting fact is that robust implementation of
+the Boost.Polygon Voronoi is faster than non-robust of
+S-Hull (except small input sets of around 100 points on Linux-64). 
+ </li>
+
 <li>Logarithmic execution time shows that Boost.Polygon Voronoi
has clear N*log(N) complexity, while this doesn't seem to be true for
CGAL (at least for large input data sets). 
@@ -461,7 +501,7 @@
 </td>
 </tr>
 <tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
+ <td style="background-color: rgb(238, 238, 238);" valign="top" nowrap="1"> </td>
 <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
 <table class="docinfo" id="table2" frame="void" rules="none">
 <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">

Modified: sandbox/gtl/doc/voronoi_builder.htm
==============================================================================
--- sandbox/gtl/doc/voronoi_builder.htm (original)
+++ sandbox/gtl/doc/voronoi_builder.htm 2012-04-15 18:40:37 EDT (Sun, 15 Apr 2012)
@@ -4,6 +4,7 @@

+

 <meta http-equiv="Content-Language" content="en-us">

@@ -88,8 +89,8 @@
The structure shares Voronoi name as the events generated by it
correspond to the Voronoi diagram edges and vertices, thus giving
enough information to construct the Voronoi diagram of a set of points
-and  linear segments. The requirements for the input/output
-coordinate types of
+and linear segments. The requirements for the input/output
+coordinate type of
the builder geometries are not the same as for the rest of the
Boost.Polygon library. The main differences are in the following: 
 <ul>
@@ -105,7 +106,7 @@
header to construct Voronoi diagram, however it's always possible to
use Voronoi builder explicitly, especially if the user wants to drop
the external dependencies such as MPL (metaprogramming library). So the
-following include set woudn't depend on any external headers even
+following include set woudn't depend on any heavy external headers (except STL and boost/cstdint.hpp), even
Boost.Polygon itself: 

 
@@ -116,7 +117,9 @@

 #include <voronoi_utils.hpp> 
 
- This also allows to build Voronoi construction APIs on top of the Voronoi builder data strcture. 
+ This
+also gives a way to build Voronoi construction API on top of the
+Voronoi builder data strcture for the other Boost libraries. 
 <h2>Declaration 
 </h2>

@@ -137,10 +140,10 @@
segments). 

 CTT
-- defines input/output coordinate types used by VP. 
+- defines input/output coordinate type used by VP. 

 VP
-- predicate kernel, that provides builder with the robust and
+- predicate kernel, that provides builder with robust and
efficient predicates and functors. 

The Voronoi builder data structure is ready to use from the box with
@@ -148,8 +151,8 @@
input coordinate range to the other integer types (e.g. 64-bit
integer), however this will also require manual set up of the
coordinate type traits. Default voronoi_predicates<CTT>
-structure provides correct predicates as soon as types defined by CTT
-satisfy the requirements explained in the end of this page. In case those
+structure provides correct and efficient predicates as soon as types defined by CTT
+satisfy the requirements explained at the end of this page. In case those
requirements are not satisfied for the user provided CTT,
proper VP
implementation is required. 
@@ -341,10 +344,9 @@
2048-bit (64 * 32) integers as they will overflow its exponent. On the
gcc compiler it's possible to use 80-bit long doubles for both fpt
types, however this is not supported by MSVC compiler.</li>
- <li>efpt_type and to_efpt_converter_type are not used to construct the
-Voronoi diagram of points (mocks will work fine).</li>
+ <li>efpt_type and to_efpt_converter_type are not used to construct Voronoi diagram of points (mocks will work fine).</li>
 <li>
-For an example of the user defined builder coordinate type traits
+For an example of the user defined coordinate type traits
see advanced Voronoi tutorial.</li>
 </ul>

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.

Next message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r78004 - sandbox/gtl/doc"
Previous message: sydorchuk.andriy_at_[hidden]: "[Boost-commit] svn:boost r78002 - in sandbox/gtl/libs/polygon/benchmark: . benchmark_results"

Date view	Thread view	Subject view	Author view

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