Subject: [Boost-commit] svn:boost r86189 - in trunk/libs/polygon: benchmark/benchmark_results benchmark/benchmark_results/plots doc
From: sydorchuk.andriy_at_[hidden]
Date: 2013-10-06 19:59:52
Author: asydorchuk
Date: 2013-10-06 19:59:52 EDT (Sun, 06 Oct 2013)
New Revision: 86189
URL: http://svn.boost.org/trac/boost/changeset/86189
Log:
Polygon: rerunning benchmarks; updating benchmark documentation pages.
Added:
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points.png (contents, props changed)
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments.png (contents, props changed)
Deleted:
trunk/libs/polygon/benchmark/benchmark_results/benchmark_points.txt
trunk/libs/polygon/benchmark/benchmark_results/benchmark_segments.txt
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_10.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_100.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_1000.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_10000.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_100000.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_1000000.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_all.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_memory.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_10.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_100.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_1000.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_10000.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_100000.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_1000000.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_all.png
trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_memory.png
Text files modified:
/dev/null | 60 ---
/dev/null | 44 --
trunk/libs/polygon/doc/voronoi_benchmark.htm | 601 +++++++++++++++------------------------
trunk/libs/polygon/doc/voronoi_builder.htm | 127 ++-----
trunk/libs/polygon/doc/voronoi_main.htm | 112 ++----
5 files changed, 314 insertions(+), 630 deletions(-)
Deleted: trunk/libs/polygon/benchmark/benchmark_results/benchmark_points.txt
==============================================================================
--- trunk/libs/polygon/benchmark/benchmark_results/benchmark_points.txt 2013-10-06 19:59:52 EDT (Sun, 06 Oct 2013) (r86188)
+++ /dev/null 00:00:00 1970 (deleted)
@@ -1,60 +0,0 @@
-System: CPU i5-7600 2.8 GHz, 4Gb RAM.
-OS: Windows 7 Professional 32 bit.
-Compiler: MSVC-9.0.
-
-Boost.Polygon Voronoi of Points:
-| Number of points | Number of tests | Time per one test |
-| 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:
-| Number of points | Number of tests | Time per one test |
-| 10 | 100000 | 0.000116 |
-| 100 | 10000 | 0.002649 |
-| 1000 | 1000 | 0.039140 |
-| 10000 | 100 | 0.684090 |
-| 100000 | 10 | 16.904600 |
-| 1000000 | 1 | 566.056000 |
-
-S-Hull Triangulation of Points:
-| 10 | 100000 | 0.000043 |
-| 100 | 10000 | 0.000521 |
-| 1000 | 1000 | 0.007125 |
-| 10000 | 100 | 0.091640 |
-| 100000 | 10 | 1.218000 |
-| 1000000 | 1 | 15.394000 |
-
-System: CPU i5-7600 2.8 GHz, 4Gb RAM.
-OS: Ubuntu 11.10 64 bit.
-Compiler: gcc 4.6.1.
-
-Boost.Polygon Voronoi of Points:
-| Number of points | Number of tests | Time per one test |
-| 10 | 100000 | 0.000013 |
-| 100 | 10000 | 0.000192 |
-| 1000 | 1000 | 0.002130 |
-| 10000 | 100 | 0.022900 |
-| 100000 | 10 | 0.274000 |
-| 1000000 | 1 | 3.290000 |
-
-CGAL Triangulation of Points:
-| Number of points | Number of tests | Time per one test |
-| 10 | 100000 | 0.000052 |
-| 100 | 10000 | 0.001150 |
-| 1000 | 1000 | 0.016680 |
-| 10000 | 100 | 0.297900 |
-| 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 |
-
Deleted: trunk/libs/polygon/benchmark/benchmark_results/benchmark_segments.txt
==============================================================================
--- trunk/libs/polygon/benchmark/benchmark_results/benchmark_segments.txt 2013-10-06 19:59:52 EDT (Sun, 06 Oct 2013) (r86188)
+++ /dev/null 00:00:00 1970 (deleted)
@@ -1,44 +0,0 @@
-System: CPU i5-7600 2.8 GHz, 4Gb RAM.
-OS: Windows 7 Professional 32 bit.
-Compiler: MSVC-9.0.
-
-Boost.Polygon Voronoi of Segments:
-| Number of points | Number of tests | Time per one test |
-| 10 | 100000 | 0.000290 |
-| 100 | 10000 | 0.003655 |
-| 1000 | 1000 | 0.038158 |
-| 10000 | 100 | 0.389470 |
-| 100000 | 10 | 4.031300 |
-| 1000000 | 1 | 40.912000 |
-
-CGAL Triangulation of Segments:
-| Number of points | Number of tests | Time per one test |
-| 10 | 100000 | 0.001047 |
-| 100 | 10000 | 0.014812 |
-| 1000 | 1000 | 0.177315 |
-| 10000 | 100 | 2.561340 |
-| 100000 | 10 | 49.314600 |
-| 1000000 | 1 | 1640.830000 |
-
-System: CPU i5-7600 2.8 GHz, 4Gb RAM.
-OS: Ubuntu 11.10 64 bit.
-Compiler: gcc 4.6.1.
-
-Boost.Polygon Voronoi of Segments:
-| Number of points | Number of tests | Time per one test |
-| 10 | 100000 | 0.000165 |
-| 100 | 10000 | 0.002006 |
-| 1000 | 1000 | 0.020440 |
-| 10000 | 100 | 0.209700 |
-| 100000 | 10 | 2.228000 |
-| 1000000 | 1 | 22.250000 |
-
-CGAL Triangulation of Segments:
-| Number of points | Number of tests | Time per one test |
-| 10 | 100000 | 0.000483 |
-| 100 | 10000 | 0.007006 |
-| 1000 | 1000 | 0.084000 |
-| 10000 | 100 | 1.191900 |
-| 100000 | 10 | 23.538000 |
-| 1000000 | 1 | 856.650000 |
-
Added: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_10.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_100.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_1000.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_10000.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_100000.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_1000000.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_all.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_points_memory.png
==============================================================================
Binary file. No diff available.
Added: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_10.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_100.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_1000.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_10000.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_100000.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_1000000.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_all.png
==============================================================================
Binary file. No diff available.
Deleted: trunk/libs/polygon/benchmark/benchmark_results/plots/benchmark_segments_memory.png
==============================================================================
Binary file. No diff available.
Modified: trunk/libs/polygon/doc/voronoi_benchmark.htm
Modified: trunk/libs/polygon/doc/voronoi_builder.htm
Modified: trunk/libs/polygon/doc/voronoi_main.htm
==============================================================================
--- trunk/libs/polygon/doc/voronoi_benchmark.htm Sun Oct 6 17:56:25 2013 (r86188)
+++ trunk/libs/polygon/doc/voronoi_benchmark.htm 2013-10-06 19:59:52 EDT (Sun, 06 Oct 2013) (r86189)
@@ -1,22 +1,15 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html>
-<head>
+<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>
-</head>
-<body>
-<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0"
- cellpadding="0" cellspacing="0">
+ <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">
- <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>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <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>
<ul>
@@ -72,313 +65,282 @@
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
- <div style="padding: 5px;" align="center"> <img
- src="images/intlogo.gif" border="0" height="51" width="127"><a
- title="www.adobe.com home page" tabindex="2"
- style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
+ <div style="padding: 5px;" align="center"> <img src="images/intlogo.gif" border="0" height="51" width="127"><a title="www.adobe.com home page" tabindex="2" style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
</td>
- <td
- style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
- valign="top" width="100%"><!-- End Header --> <br>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header --> <br>
<h1>Voronoi Benchmark</h1>
-There are not many known Voronoi libraries that are capable to satisfy
-the
-following set of conditions:<br>
- <ul>
- <li>could handle input data sets of points and segments<br>
- </li>
- <li>give exact warranties about the algorithm robustness and
-output topology<br>
- </li>
- <li>compute coordinates of the output geometries within the
-fixed relative precision<br>
- </li>
- </ul>
-Below is the list of libraries included in this benchmark sorted by the
-number of conditions each of them satisfies:<br>
- <ul>
- <li>Boost.Polygon Voronoi - satisfies all the conditions above,
-implements sweep-line algorithm.<br>
- </li>
- <li>CGAL - satisfies the first two conditions, implements
-incremental algorithm. CGAL is a well-known
-library in the computational geometry area, especially for its
-robustness.<br>
- </li>
- <li>S-Hull
-- doesn't satisfy any of the above conditions. S-Hull is a non-robust
-implementation of the sweep-hull algorithm used to construct Delaunay
-triangulation of a set of points.<br>
- </li>
- </ul>
-At the moment this benchmark includes only two robust implementations:
-Boost.Polygon Voronoi and CGAL. Thus we are considering comparison of
-those two to be of the most interest. <br>
- <br>
-Other libraries (OpenVoronoi,
- Triangle)
-would be added to this benchmark
-incrementally (we are open for suggestions).<br>
- <h2>Important<br>
- </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
-diagram. Thus there are problems where the CGAL's incremental approach
-would
-be still more vital than the sweep-line algorithm (e.g. input sites are
-inserted as a live stream
-data).<br>
- <h2>Voronoi Benchmark Details<br>
- </h2>
+ <h2>Benchmark Details</h2>
+From the topological perspective Delaunay triangulation is a dual
+data structure to the Voronoi diagram, thus libraries that provide
+Delaunay triangulation construction routines were also included into
+the benchmark. However, from the computation perspective Voronoi
+diagram contains more information as it embeds information regarding
+the coordinates of the centers of the inscribed circles tangent to the
+three or more input geometries.<br>
+
+
The benchmark consists of the two parts:<br>
- <ul>
- <li>The first one constructs the Voronoi diagram of a set of
-random points (<a href="../benchmark/voronoi_benchmark_points.cpp"><span
- style="text-decoration: underline;">voronoi_benchmark_points.cpp</span></a>)</li>
- <li>The second one constructs the Voronoi diagram of a set of
-random
-segments (voronoi_benchmark_segments.cpp)</li>
- </ul>
-Below we list important benchmark details that should be considered
-while reviewing its results:<br>
- <ul>
- <li>We ensure that input data sets are the same for all
-libraries by initializing random generator with the same seed</li>
- <li>We ensure that input data sets that consist of segments
-don't contain intersections using Boost.Polygon functionality</li>
- <li>S-Hull's implementation doesn't process duplicate points
-properly, thus those are eliminated before the algorithm execution
-explicitly (Boost.Polygon Voronoi and CGAL do that implicitly) <br>
- </li>
- <li>There is no Voronoi diagram data structure in CGAL/S-Hull.
-That's why we use the segment Delaunay graph which is topologically
-dual to the Voronoi diagram</li>
- <li>CGAL's and S-Hull's output Delaunay triangulation doesn't
-contain information
-about coordinates of the Voronoi vertices. We didn't include time to
-compute Voronoi vertices and memory
-storage required for those in this benchmark.<br>
- </li>
- <li>Both Boost.Polygon Voronoi and CGAL process each input
-segment
-as 3 input objects (segment itself and its endpoints), thus the running
-time and memory usage for Voronoi of segments would be at
-least 3 times
-slower than for Voronoi of points</li>
- </ul>
-The benchmark was executed on the following two system configurations:<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">
+ <ol>
+<li>construction of the Voronoi diagram / Delaunay triangulation of a set of
+random points uniformly distributed over 32-bit integer grid (voronoi_benchmark_points.cpp)</li><li>construction of the Voronoi diagram / Delaunay triangulation of a set of
+random non-intersecting
+segments uniformly distributed over 32-bit integer grid (voronoi_benchmark_segments.cpp).</li>
+ </ol>
+
+
+
+ <h2>Libraries</h2>
+ <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 style="vertical-align: top;"><span style="font-weight: bold;">Library</span><br>
</td>
- <td colspan="6" rowspan="1"
- style="vertical-align: top; text-align: center;">Average construction
-time (in secs)<br>
+ <td style="vertical-align: top; font-weight: bold;">Boost.Polygon<br>
+ </td>
+ <td style="vertical-align: top; font-weight: bold;">CGAL<br>
+ </td>
+ <td style="vertical-align: top; font-weight: bold;">SHull<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; text-align: center;">Number
-of Points<br>
+ <td style="vertical-align: top;">Official page<br>
</td>
- <td style="vertical-align: top; text-align: center;">Number
-of Runs<br>
+ <td style="vertical-align: top;">www.boost.org/libs/polygon‎<br>
</td>
- <td style="vertical-align: top; text-align: center;">Boost
-Win-32<br>
+ <td style="vertical-align: top;">http://www.cgal.org
</td>
- <td style="vertical-align: top; text-align: center;">CGAL
-Win-32<br>
+ <td style="vertical-align: top;">http://www.s-hull.org
</td>
- <td style="vertical-align: top; text-align: center;">S-Hull
-Win-32<br>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">Algorithm<br>
</td>
- <td style="vertical-align: top; text-align: center;">Boost
-Linux-64<br>
+ <td style="vertical-align: top;">sweep-line<br>
</td>
- <td style="vertical-align: top; text-align: center;">CGAL
-Linux-64<br>
+ <td style="vertical-align: top;">incremental<br>
</td>
- <td style="vertical-align: top; text-align: center;">S-Hull
-Linux-64<br>
+ <td style="vertical-align: top;">sweep-hull<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; text-align: right;">10<br>
+ <td style="vertical-align: top;">Supported input geometries<br>
</td>
- <td style="vertical-align: top; text-align: right;">100000<br>
+ <td style="vertical-align: top;">points and segments<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.000027<br>
+ <td style="vertical-align: top;">points and segments<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.000116<br>
+ <td style="vertical-align: top;">points<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.000043<br>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">Output data structure<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.000013<br>
+ <td style="vertical-align: top;">Voronoi diagram<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.000052<br>
+ <td style="vertical-align: top;">Delaunay triangulation<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.000012<br>
+ <td style="vertical-align: top;">Delaunay triangulation<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; text-align: right;">100<br>
+ <td style="vertical-align: top;">Complexity<br>
</td>
- <td style="vertical-align: top; text-align: right;">10000<br>
+ <td style="vertical-align: top;">O(N log N)<br>
+ </td>
+ <td style="vertical-align: top;">O(N log N)</td>
+ <td style="vertical-align: top;">O(N log N)</td>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">Memory usage<br>
+ </td>
+ <td style="vertical-align: top;">O(N)<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.000392<br>
+ <td style="vertical-align: top;">O(N)<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.002649<br>
+ <td style="vertical-align: top;">O(N)<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.000521<br>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">Robustness policies<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.000192<br>
+ <td style="vertical-align: top;">lazy arithmetic, exact predicates, topology analysis<br>
</td>
- <td style="vertical-align: top; text-align: right;"> 0.001150<br>
+ <td style="vertical-align: top;">lazy arithmetic, exact predicates, topology analysis<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.000139<br>
+ <td style="vertical-align: top;">non-robust<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; text-align: right;">1000<br>
+ <td style="vertical-align: top;">Output coordinates precision<br>
</td>
- <td style="vertical-align: top; text-align: right;">1000<br>
+ <td style="vertical-align: top;">128 machine epsilon<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.004541<br>
+ <td style="vertical-align: top;">no output coordinates<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.039140<br>
+ <td style="vertical-align: top;">no output coordinates<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.007125<br>
+ </tr>
+ <tr>
+ <td style="vertical-align: top;">External dependencies<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.002130<br>
+ <td style="vertical-align: top;">No<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.016680<br>
+ <td style="vertical-align: top;">Boost, GMP, MPFR<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.002010<br>
+ <td style="vertical-align: top;">No<br>
</td>
</tr>
+ </tbody>
+ </table>
+ <br>
+
+The other known libraries (OpenVoronoi,
+ Triangle, Vroni) will be considered for the inclusion into the benchmark in the future.<br>
+<ul>
+ <ul>
+
+
+
+
+
+
+
+ </ul>
+
+
+ <ul>
+
+
+ </ul>
+
+ </ul>
+ <h2>System Configuration<br>
+ </h2>
+
+
+Hardware: Intel i5-7600 2.8 GHz, 16GiB RAM.<br>
+OS: Ubuntu 13.04 64-bit.<br>
+Compiler: GCC 4.7.3.<br>
+Libraries and dependencies: Boost 1.54.0, CGAL-4.3-beta1, GMP 5.1.4, MPFR 3.1.2, S-Hull.<br>
+ <h2>Benchmark Results</h2>
+ <h3>Random Points Benchmark</h3><img style="border: 1px solid ; width: 500px; height: 350px;" alt="Benchmark Points Chart" src="../benchmark/benchmark_results/plots/benchmark_points.png"><br>
+
+ <table style="text-align: left; width: 100%; margin-left: auto; margin-right: auto;" border="1" cellpadding="2" cellspacing="2">
+ <tbody>
<tr>
- <td style="vertical-align: top; text-align: right;">10000<br>
- </td>
- <td style="vertical-align: top; text-align: right;">100<br>
+ <td colspan="2" rowspan="1" style="vertical-align: top; text-align: center;">Test specification<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.047540<br>
+ <td colspan="6" rowspan="1" style="vertical-align: top; text-align: center;">Average construction
+time (in secs)<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.684090<br>
+ </tr>
+ <tr>
+ <td style="vertical-align: top; text-align: center;">Number
+of Points<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.091640<br>
+ <td style="vertical-align: top; text-align: center;">Number
+of Runs<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.022900<br>
+
+
+
+ <td style="vertical-align: top; text-align: center;">Boost
+Linux-64<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.297900<br>
+ <td style="vertical-align: top; text-align: center;">CGAL
+Linux-64<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.028300<br>
+ <td style="vertical-align: top; text-align: center;">S-Hull
+Linux-64<br>
</td>
</tr>
+
<tr>
- <td style="vertical-align: top; text-align: right;">100000<br>
+ <td style="vertical-align: top; text-align: right;">100<br>
</td>
- <td style="vertical-align: top; text-align: right;">10<br>
+ <td style="vertical-align: top; text-align: right;">10000<br>
+ </td>
+
+
+
+ <td style="vertical-align: top; text-align: right;">0.000206<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.530200<br>
+ <td style="vertical-align: top; text-align: right;"> 0.000073<br>
</td>
- <td style="vertical-align: top; text-align: right;"> 16.904600<br>
+ <td style="vertical-align: top; text-align: right;">0.000243<br>
</td>
- <td style="vertical-align: top; text-align: right;">1.218000<br>
+ </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.274000<br>
+
+
+
+ <td style="vertical-align: top; text-align: right;">0.002250<br>
</td>
- <td style="vertical-align: top; text-align: right;">8.047000<br>
+ <td style="vertical-align: top; text-align: right;">0.000753<br>
</td>
- <td style="vertical-align: top; text-align: right;">0.432000<br>
+ <td style="vertical-align: top; text-align: right;">0.002184<br>
</td>
</tr>
<tr>
- <td style="vertical-align: top; text-align: right;">1000000<br>
+ <td style="vertical-align: top; text-align: right;">10000<br>
</td>
- <td style="vertical-align: top; text-align: right;">1<br>
+ <td style="vertical-align: top; text-align: right;">100<br>
</td>
- <td style="vertical-align: top; text-align: right;">5.882000<br>
+
+
+
+ <td style="vertical-align: top; text-align: right;">0.024100<br>
</td>
- <td style="vertical-align: top; text-align: right;">566.056000<br>
+ <td style="vertical-align: top; text-align: right;">0.007917<br>
</td>
- <td style="vertical-align: top; text-align: right;">15.394000<br>
+ <td style="vertical-align: top; text-align: right;">0.030552<br>
</td>
- <td style="vertical-align: top; text-align: right;">3.290000<br>
+ </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;">315.740000<br>
+
+
+
+ <td style="vertical-align: top; text-align: right;">0.292000<br>
</td>
- <td style="vertical-align: top; text-align: right;">6.350000<br>
+ <td style="vertical-align: top; text-align: right;">0.084336<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.451913<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="images/benchmark_points_10.png"></td>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_points_100.png"></td>
- </tr>
- <tr>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_points_1000.png"></td>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_points_10000.png"></td>
- </tr>
- <tr>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_points_100000.png"></td>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_points_1000000.png"></td>
- </tr>
- <tr>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_points_memory.png"><br>
- </td>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_points_all.png"><br>
+ <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;">3.470000<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">0.902300<br>
+ </td>
+ <td style="vertical-align: top; text-align: right;">6.603814<br>
</td>
</tr>
</tbody>
</table>
- <h3>Random Segments Benchmark</h3>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
+ <br>
+<h3>Random Segments Benchmark</h3><img style="border: 1px solid ; width: 500px; height: 350px;" alt="Benchmark Segment Chart" src="../benchmark/benchmark_results/plots/benchmark_segments.png"><br>
+
+ <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 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
+ <td colspan="4" rowspan="1" style="vertical-align: top; text-align: center;">Average construction
time (in secs)</td>
</tr>
<tr>
@@ -388,12 +350,8 @@
<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>
@@ -401,32 +359,17 @@
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 style="vertical-align: top; text-align: right;">0.002284<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 style="vertical-align: top; text-align: right;">0.002985<br>
</td>
</tr>
<tr>
@@ -434,13 +377,11 @@
</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 style="vertical-align: top; text-align: right;">0.023240<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 style="vertical-align: top; text-align: right;">0.032180<br>
</td>
</tr>
<tr>
@@ -448,13 +389,11 @@
</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 style="vertical-align: top; text-align: right;"> 0.237700<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 style="vertical-align: top; text-align: right;">0.337400<br>
</td>
</tr>
<tr>
@@ -462,13 +401,11 @@
</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 style="vertical-align: top; text-align: right;">2.488000<br>
</td>
- <td style="vertical-align: top; text-align: right;">23.538000<br>
+ <td style="vertical-align: top; text-align: right;">3.633000<br>
</td>
</tr>
<tr>
@@ -476,99 +413,22 @@
</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 style="vertical-align: top; text-align: right;">25.00000<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="images/benchmark_segments_10.png"></td>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_segments_100.png"></td>
- </tr>
- <tr>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_segments_1000.png"></td>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_segments_10000.png"></td>
- </tr>
- <tr>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_segments_100000.png"></td>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_segments_1000000.png"></td>
- </tr>
- <tr>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_segments_memory.png"><br>
- </td>
- <td style="vertical-align: top;"><img
- style="width: 500px; height: 300px;" alt=""
- src="images/benchmark_segments_all.png"><br>
+ <td style="vertical-align: top; text-align: right;">39.090000<br>
</td>
</tr>
</tbody>
</table>
- <span style="font-weight: bold;"></span>
- <h2>Voronoi Benchmark Summary</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. 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).<br>
- </li>
- <li>Logarithmic execution time shows that Boost.Polygon Voronoi
-and S-Hull
-have clear N*log(N) complexity, while this doesn't seem to be true for
-CGAL (at least for large input data sets).<br>
- </li>
- <li>Boost.Polygon Voronoi computes coordinates of the output
-Voronoi vertices within 64 machine epsilon precision. There are no such
-warranties for the CGAL library.<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>
- </td>
+ <br><span style="font-weight: bold;"></span></td>
</tr>
<tr>
- <td style="background-color: rgb(238, 238, 238);" nowrap="1"
- valign="top"> </td>
- <td
- style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
- valign="top" width="100%">
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </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">
+ <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
<tr>
<th class="docinfo-name">Copyright:</th>
<td>Copyright © Andrii Sydorchuk 2010-2012.</td>
@@ -576,10 +436,7 @@
<tr class="field">
<th class="docinfo-name">License:</th>
<td class="field-body">Distributed under the Boost Software
-License, Version 1.0. (See accompanying file <tt class="literal"><span
- class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
- class="reference" target="_top"
- href="http://www.boost.org/LICENSE_1_0.txt">
+License, Version 1.0. (See accompanying file <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
http://www.boost.org/LICENSE_1_0.txt>)</td>
</tr>
</tbody>
@@ -588,5 +445,5 @@
</tr>
</tbody>
</table>
-</body>
-</html>
+
+</body></html>
\ No newline at end of file
==============================================================================
--- trunk/libs/polygon/doc/voronoi_builder.htm Sun Oct 6 17:56:25 2013 (r86188)
+++ trunk/libs/polygon/doc/voronoi_builder.htm 2013-10-06 19:59:52 EDT (Sun, 06 Oct 2013) (r86189)
@@ -1,22 +1,14 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html>
-<head>
+<html><head>
+
+
<meta http-equiv="Content-Language" content="en-us">
- <meta http-equiv="Content-Type"
- content="text/html; charset=windows-1252">
- <title>Voronoi Builder</title>
-</head>
-<body>
-<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0"
- cellpadding="0" cellspacing="0">
+ <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Builder</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">
- <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>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <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>
<ul>
@@ -70,20 +62,14 @@
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
- <div style="padding: 5px;" align="center"> <img
- src="images/intlogo.gif" border="0" height="51" width="127"><a
- title="www.adobe.com home page" tabindex="2"
- style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
+ <div style="padding: 5px;" align="center"> <img src="images/intlogo.gif" border="0" height="51" width="127"><a title="www.adobe.com home page" tabindex="2" style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
</td>
- <td
- style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
- valign="top" width="100%"><!-- End Header --> <br>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header --> <br>
<h1>Voronoi Builder </h1>
The Voronoi builder is the event generator structure, that implements
the <a href="http://en.wikipedia.org/wiki/Sweep_line_algorithm">sweepline
algorithm</a>,
-scanning 2D space and spawning the two types of events: <a
- href="http://www.ams.org/samplings/feature-column/fcarc-voronoi">site
+scanning 2D space and spawning the two types of events: <a href="http://www.ams.org/samplings/feature-column/fcarc-voronoi">site
events and circle events</a>. Each event is reported to the output data
structure builder.
The structure shares Voronoi name, as the events generated by it
@@ -112,35 +98,28 @@
the Boost.Polygon library:<br>
<br>
<span style="font-family: Courier New,Courier,monospace;">#include
-<voronoi_builder.hpp></span><br
- style="font-family: Courier New,Courier,monospace;">
+<voronoi_builder.hpp></span><br style="font-family: Courier New,Courier,monospace;">
<span style="font-family: Courier New,Courier,monospace;">#include
<voronoi_diagram.hpp></span><br>
<h2>Declaration</h2>
Header: boost/polygon/voronoi_builder.hpp<br>
<br>
- <font face="Courier New"> <span
- style="font-family: 'Courier New',Courier,monospace;">template
-<typename T,</span><br
- style="font-family: 'Courier New',Courier,monospace;">
+ <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">template
+<typename T,</span><br style="font-family: 'Courier New',Courier,monospace;">
<span style="font-family: 'Courier New',Courier,monospace;">
-typename CTT = detail::voronoi_ctype_traits<T>,</span><br
- style="font-family: 'Courier New',Courier,monospace;">
+typename CTT = detail::voronoi_ctype_traits<T>,</span><br style="font-family: 'Courier New',Courier,monospace;">
<span style="font-family: 'Courier New',Courier,monospace;">
-typename VP = detail::voronoi_predicates<CTT> ></span><br
- style="font-family: 'Courier New',Courier,monospace;">
+typename VP = detail::voronoi_predicates<CTT> ></span><br style="font-family: 'Courier New',Courier,monospace;">
<span style="font-family: 'Courier New',Courier,monospace;">class
voronoi_builder;</span><br>
<br>
<span style="font-family: 'Courier New',Courier,monospace;">T</span></font>
- specifies the coordinate type of the input geometries (points and
segments).<br>
- <font face="Courier New"> <span
- style="font-family: 'Courier New',Courier,monospace;">CTT</span></font>
+ <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">CTT</span></font>
- defines the input/output coordinate type traits used by the Voronoi
predicates (VP).<br>
- <font face="Courier New"> <span
- style="font-family: 'Courier New',Courier,monospace;">VP</span></font>
+ <font face="Courier New"> <span style="font-family: 'Courier New',Courier,monospace;">VP</span></font>
- the predicate kernel, that contains robust and
efficient predicates and functors.<br>
The Voronoi builder data structure is ready to use from the box with
@@ -152,25 +131,19 @@
defined by the coordinate type traits satisfy the requirements
explained at the end of this page. In case
those
-requirements are not satisfied,<font face="Courier New"><span
- style="font-family: 'Courier New',Courier,monospace;"></span></font>
+requirements are not satisfied,<font face="Courier New"><span style="font-family: 'Courier New',Courier,monospace;"></span></font>
the proper predicate kernel
-implementation is required.<span
- style="font-family: Courier New,Courier,monospace;"></span><br>
+implementation is required.<span style="font-family: Courier New,Courier,monospace;"></span><br>
<h2>Member Functions</h2>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td style="font-family: 'Courier New',Courier,monospace;"><span
- style="font-weight: bold;">voronoi_builder</span>()</td>
+ <td style="font-family: 'Courier New',Courier,monospace;"><span style="font-weight: bold;">voronoi_builder</span>()</td>
<td width="693">Default
constructor.</td>
</tr>
<tr>
- <td><span
- style="font-family: Courier New,Courier,monospace;">size_t <span
- style="font-weight: bold;">insert_point</span>(const int_type& x,<br>
+ <td><span style="font-family: Courier New,Courier,monospace;">size_t <span style="font-weight: bold;">insert_point</span>(const int_type& x,<br>
const int_type& y)</span> </td>
<td>Inserts a point object with
@@ -178,9 +151,7 @@
Returns index of the inserted point. </td>
</tr>
<tr>
- <td><span
- style="font-family: Courier New,Courier,monospace;">size_t <span
- style="font-weight: bold;">insert_segment</span>(const int_type&
+ <td><span style="font-family: Courier New,Courier,monospace;">size_t <span style="font-weight: bold;">insert_segment</span>(const int_type&
x1,<br>
const int_type& y1,<br>
@@ -201,7 +172,8 @@
algorithm over the set of inserted geometries and generates site and
circle events to the OUTPUT data structure. It's the responsibility of
the
-output data structure to process them. </td>
+output data structure to process them. Complexity: O(N * log N), where N is the total number of input points and segments.<br>
+ </td>
</tr>
<tr>
<td style="font-family: 'Courier New',Courier,monospace;">void
@@ -216,8 +188,7 @@
<p>The library provides the default coordinate type traits
specialization for the
32-bit signed integer type:</p>
- <font style="font-family: 'Courier New',Courier,monospace;"
- face="Courier New">
+ <font style="font-family: 'Courier New',Courier,monospace;" face="Courier New">
<p>template <typename T><br>
struct voronoi_ctype_traits;<br>
<br>
@@ -244,33 +215,28 @@
of traits (the assumption is made that input geometries have
X-bit signed integer coordinate type):<br>
<br>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
- <td
- style="font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_type
+ <td style="font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_type
</td>
<td style="vertical-align: top;">At least X-bit signed
integer type. </td>
</tr>
<tr>
- <td
- style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_x2_type
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">int_x2_type
</td>
<td style="vertical-align: top;">At least 2X-bit signed
integer type. </td>
</tr>
<tr>
- <td
- style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">uint_x2_type
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">uint_x2_type
</td>
<td style="vertical-align: top;">At least 2X-bit unsigned
integer type. </td>
</tr>
<tr>
- <td
- style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">big_int_type
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">big_int_type
</td>
<td style="vertical-align: top;">At least 8X-bit signed
integer type if input dataset contains only points.<br>
@@ -278,40 +244,35 @@
segments. </td>
</tr>
<tr>
- <td
- style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">fpt_type
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">fpt_type
</td>
<td style="vertical-align: top;">IEEE-754 floating point
type, with mantissa at least (X+16) bits and exponent able to handle
32X-bit unsigned integer type. </td>
</tr>
<tr>
- <td
- style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">efpt_type
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">efpt_type
</td>
<td style="vertical-align: top;">IEEE-754 floating point
type, with mantissa at least (X+16) bits and exponent able to handle
64X-bit unsigned integer type. </td>
</tr>
<tr>
- <td
- style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">ulp_cmp_type
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">ulp_cmp_type
</td>
<td style="vertical-align: top;">Ulp comparison structure,
that checks if two fpt_type values are within the given ulp range
(relative error range). </td>
</tr>
<tr>
- <td
- style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_fpt_converter_type
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_fpt_converter_type
</td>
<td style="vertical-align: top;">Type converter structure,
that converts any of the integer types above plus efpt_type to the
fpt_type using operator(). </td>
</tr>
<tr>
- <td
- style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_efpt_converter_type
+ <td style="vertical-align: top; font-family: 'Courier New',Courier,monospace; font-weight: bold;">to_efpt_converter_type
</td>
<td style="vertical-align: top;">Type converter structure,
that converts any of the integer types above to the efpt_type using
@@ -346,12 +307,9 @@
</tr>
<tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1"> </td>
- <td
- style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
- valign="top" width="100%">
+ <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">
+ <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
<tr>
<th class="docinfo-name">Copyright:</th>
<td>Copyright © Andrii Sydorchuk 2010-2013.</td>
@@ -359,10 +317,7 @@
<tr class="field">
<th class="docinfo-name">License:</th>
<td class="field-body">Distributed under the Boost Software
-License, Version 1.0. (See accompanying file <tt class="literal"><span
- class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
- class="reference" target="_top"
- href="http://www.boost.org/LICENSE_1_0.txt">
+License, Version 1.0. (See accompanying file <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
http://www.boost.org/LICENSE_1_0.txt>)</td>
</tr>
</tbody>
@@ -371,5 +326,5 @@
</tr>
</tbody>
</table>
-</body>
-</html>
+
+</body></html>
\ No newline at end of file
==============================================================================
--- trunk/libs/polygon/doc/voronoi_main.htm Sun Oct 6 17:56:25 2013 (r86188)
+++ trunk/libs/polygon/doc/voronoi_main.htm 2013-10-06 19:59:52 EDT (Sun, 06 Oct 2013) (r86189)
@@ -1,26 +1,20 @@
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
-<html>
-<head>
+<html><head>
+
+
+
<meta http-equiv="Content-Language" content="en-us">
- <meta http-equiv="Content-Type"
- content="text/html; charset=windows-1252">
- <title>Voronoi Main</title>
+ <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Main</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">
- <meta http-equiv="content-type" content="text/html; charset=utf-8">
-</head>
-<body>
-<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0"
- cellpadding="0" cellspacing="0">
+ <meta http-equiv="content-type" content="text/html; charset=utf-8"></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">
- <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>
+ <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
+ <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>
<ul>
@@ -74,17 +68,11 @@
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
- <div style="padding: 5px;" align="center"> <img
- src="images/intlogo.gif" border="0" height="51" width="127"><a
- title="www.adobe.com home page" tabindex="2"
- style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
+ <div style="padding: 5px;" align="center"> <img src="images/intlogo.gif" border="0" height="51" width="127"><a title="www.adobe.com home page" tabindex="2" style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
</td>
- <td
- style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
- valign="top" width="100%"><!-- End Header --> <br>
+ <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header --> <br>
<h1>THE BOOST.POLYGON VORONOI LIBRARY </h1>
- <img style="width: 900px; height: 300px;" alt=""
- src="images/voronoi3.png"><br>
+ <img style="width: 900px; height: 300px;" alt="" src="images/voronoi3.png"><br>
The Voronoi extension of the Boost.Polygon library provides
functionality to construct a <a href="voronoi_diagram.htm">Voronoi
diagram</a>
@@ -101,11 +89,13 @@
While the first restriction is permanent (it
allows to give the exact warranties about the output precision and
algorithm execution flow),
-the second one may be resolved using the Boost.Polygon <a
- href="gtl_segment_concept.htm">segment utils</a>.
+the second one may be resolved using the Boost.Polygon segment utils.
The strong sides of the
library and main benefits comparing to the other implementations are
-discussed in the following paragraphs.<span style="font-weight: bold;"></span><br>
+discussed in the following paragraphs.<br>
+ <br>
+Voronoi diagram construction complexity: O(N * logN), memory usage
+O(N), where N is the total number of input points and segments.<span style="font-weight: bold;"></span><br>
<h2>Fully Functional with Segments</h2>
There are just a few implementations of the Voronoi diagram
construction
@@ -154,8 +144,7 @@
geometries can be increased simply by using a floating-point type with
the larger mantissa. The practical point of this statements is
explained in the following table:<br>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
<td style="vertical-align: top;">Output Coordinate Type </td>
@@ -196,10 +185,8 @@
</tbody>
</table>
Detailed description of the absolute and relative errors evaluation can
-be found in the article: <a
- href="http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html">"What
-Every Computer Scientist Should Know About Floating-Point Arithmetic"</a><a
- href="http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html"></a>.<br>
+be found in the article: <a href="http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html">"What
+Every Computer Scientist Should Know About Floating-Point Arithmetic"</a>.<br>
<br>
During the finalization step the implementation unites the Voronoi
vertices
@@ -218,14 +205,12 @@
micrometres or the size of a bacteria) will be considered
equal and united.<br>
<h2>Simple Interface </h2>
-The boost/polygon/<a
- href="../../../boost/polygon/voronoi.hpp">voronoi.hpp</a>
+The boost/polygon/<a href="../../../boost/polygon/voronoi.hpp">voronoi.hpp</a>
library header defines the following static functions to integrate the
Voronoi library
functionality with the Boost.Polygon interfaces:<br>
<br>
- <table style="text-align: left; width: 100%;" border="1"
- cellpadding="2" cellspacing="2">
+ <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
<tbody>
<tr>
<td style="font-family: Courier New,Courier,monospace;">template
@@ -282,19 +267,22 @@
VD *vd) </td>
<td>Constructs the Voronoi diagram of a set of points.<br>
-Corresponding point type should model the point concept. </td>
+Corresponding point type should model the point concept.<br>
+Complexity: O(N * log N), memory usage: O(N), where N is the total number of input points.<br>
+ </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">template
<typename SegmentIterator, typename VD><br>
void <span style="font-weight: bold;">construct_voronoi</span>(SegmentIterator
-first,<br>
-
+first,<br>
SegmentIterator last,<br>
VD *vd) </td>
<td>Constructs the Voronoi diagram of a set of segments.<br>
-Corresponding segment type should model the segment concept. </td>
+Corresponding segment type should model the segment concept.<br>
+Complexity: O(N * log N), memory usage: O(N), where N is the total number of input segments.<br>
+ </td>
</tr>
<tr>
<td style="font-family: Courier New,Courier,monospace;">template
@@ -303,8 +291,7 @@
SegmentIterator,<br>
typename VD><br>
void <span style="font-weight: bold;">construct_voronoi</span>(PointIterator
-p_first,<br>
-
+p_first,<br>
PointIterator p_last,<br>
SegmentIterator s_first,<br>
@@ -315,7 +302,9 @@
<td>Constructs the Voronoi
diagram of a set of points and segments.<br>
Corresponding point type should model the point concept.<br>
-Corresponding segment type should model the segment concept. </td>
+Corresponding segment type should model the segment concept.<br>
+Complexity: O(N* log N), memory usage: O(N), where N is the total number of input points and segments.<br>
+</td>
</tr>
</tbody>
</table>
@@ -336,14 +325,12 @@
output geometries and efficiently traverse
the
Voronoi graph.
-More details on those topics are covered in the <a
- href="voronoi_basic_tutorial.htm">basic Voronoi tutorial</a>. Advanced
+More details on those topics are covered in the basic Voronoi tutorial. Advanced
usage of the library with the configuration of the coordinate
types is explained in the <a href="voronoi_advanced_tutorial.htm">advanced
Voronoi tutorial</a>.
The library allows users to implement their own Voronoi diagram /
-Delaunay triangulation construction routines based on the <a
- href="voronoi_builder.htm">Voronoi builder API</a>.<br>
+Delaunay triangulation construction routines based on the Voronoi builder API.<br>
<h2>No Third Party Dependencies </h2>
The Voronoi extension of the Boost.Polygon library doesn't depend on
any 3rd party code
@@ -354,12 +341,10 @@
part of the implementation. The library is fast to compile (3 public
and 4 private heades), has strong cohesion between its components and
is clearly modularized from the rest of the Boost.Polygon library, with
-the optional integration through the <a
- href="../../../boost/polygon/voronoi.hpp">voronoi.hpp</a> header.<br>
+the optional integration through the voronoi.hpp header.<br>
<h2>Extensible for the User Provided Coordinate Types</h2>
The implementation is coordinate type agnostic. As long
-as the user provided types satisfy the set of the requirements of the <a
- href="voronoi_builder.htm">Voronoi builder</a> coordinate type traits,
+as the user provided types satisfy the set of the requirements of the Voronoi builder coordinate type traits,
no additional
changes
are needed
@@ -441,21 +426,15 @@
his/her PC. Upon the community request, more documentation on the
theoretical aspects of the implementation will be published.
The
-authors would like to acknowledge the Steven Fortune's article <span
- style="font-family: Arial,Helvetica,sans-serif;"><span
- style="font-weight: bold;"></span></span>"<a
- href="http://dl.acm.org/citation.cfm?id=10549">A Sweepline algorithm
+authors would like to acknowledge the Steven Fortune's article <span style="font-family: Arial,Helvetica,sans-serif;"><span style="font-weight: bold;"></span></span>"<a href="http://dl.acm.org/citation.cfm?id=10549">A Sweepline algorithm
for Voronoi diagrams</a>", that covers fundamental ideas of the
current implementation. </td>
</tr>
<tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1"> </td>
- <td
- style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
- valign="top" width="100%">
+ <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">
+ <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
<tr>
<th class="docinfo-name">Copyright:</th>
<td>Copyright © Andrii Sydorchuk 2010-2013.</td>
@@ -463,10 +442,7 @@
<tr class="field">
<th class="docinfo-name">License:</th>
<td class="field-body">Distributed under the Boost Software
-License, Version 1.0. (See accompanying file <tt class="literal"><span
- class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
- class="reference" target="_top"
- href="http://www.boost.org/LICENSE_1_0.txt">
+License, Version 1.0. (See accompanying file <tt class="literal"><span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
http://www.boost.org/LICENSE_1_0.txt>)</td>
</tr>
</tbody>
@@ -475,5 +451,5 @@
</tr>
</tbody>
</table>
-</body>
-</html>
+
+</body></html>
\ No newline at end of file