123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449 |
- <!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></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>
- <div style="margin: 5px;">
- <h3 class="navbar">Contents</h3>
- <ul>
- <li><a href="index.htm">Boost.Polygon Main Page</a></li>
- <li><a href="gtl_design_overview.htm">Design Overview</a></li>
- <li><a href="gtl_isotropy.htm">Isotropy</a></li>
- <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
- <li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
- <li><a href="gtl_point_concept.htm">Point Concept</a></li>
- <li><a href="gtl_segment_concept.htm">Segment Concept</a></li>
- <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
- <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
- <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
- With Holes Concept</a></li>
- <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
- <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
- With Holes Concept</a></li>
- <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
- <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
- Holes Concept</a></li>
- <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
- Concept</a></li>
- <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
- Concept</a></li>
- <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
- <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
- Extraction 90</a></li>
- <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
- Extraction 45</a></li>
- <li><a href="gtl_connectivity_extraction.htm">Connectivity
- Extraction</a></li>
- <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
- <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
- <li><a href="gtl_property_merge.htm">Property Merge</a></li>
- <li><a href="voronoi_main.htm">Voronoi Main Page<br>
- </a></li>
- <li>Voronoi Benchmark<br>
- </li>
- <li><a href="voronoi_builder.htm">Voronoi Builder</a></li>
- <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
- </ul>
- <h3 class="navbar">Other Resources</h3>
- <ul>
- <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
- <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
- Presentation</a></li>
- <li><a href="analysis.htm">Performance Analysis</a></li>
- <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
- <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
- <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
- <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
- Tutorial</a></li>
- </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>
- </td>
- <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header --> <br>
- <h1>Voronoi Benchmark</h1>
- <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>
- <ol>
- <li>construction of the Voronoi diagram / Delaunay triangulation of a set of
- random points uniformly distributed over 32-bit integer grid (<a href="../benchmark/voronoi_benchmark_points.cpp"><span style="text-decoration: underline;">voronoi_benchmark_points.cpp</span></a>)</li><li>construction of the Voronoi diagram / Delaunay triangulation of a set of
- random non-intersecting
- segments uniformly distributed over 32-bit integer grid (<a href="../benchmark/voronoi_benchmark_segments.cpp">voronoi_benchmark_segments.cpp</a>).</li>
- </ol>
- <h2>Libraries</h2>
- <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
- <tbody>
- <tr>
- <td style="vertical-align: top;"><span style="font-weight: bold;">Library</span><br>
- </td>
- <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;">Official page<br>
- </td>
- <td style="vertical-align: top;">www.boost.org/libs/polygon‎<br>
- </td>
- <td style="vertical-align: top;">http://www.cgal.org<br>
- </td>
- <td style="vertical-align: top;">http://www.s-hull.org<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top;">Algorithm<br>
- </td>
- <td style="vertical-align: top;">sweep-line<br>
- </td>
- <td style="vertical-align: top;">incremental<br>
- </td>
- <td style="vertical-align: top;">sweep-hull<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top;">Supported input geometries<br>
- </td>
- <td style="vertical-align: top;">points and segments<br>
- </td>
- <td style="vertical-align: top;">points and segments<br>
- </td>
- <td style="vertical-align: top;">points<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top;">Output data structure<br>
- </td>
- <td style="vertical-align: top;">Voronoi diagram<br>
- </td>
- <td style="vertical-align: top;">Delaunay triangulation<br>
- </td>
- <td style="vertical-align: top;">Delaunay triangulation<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top;">Complexity<br>
- </td>
- <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;">O(N)<br>
- </td>
- <td style="vertical-align: top;">O(N)<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top;">Robustness policies<br>
- </td>
- <td style="vertical-align: top;">lazy arithmetic, exact predicates, topology analysis<br>
- </td>
- <td style="vertical-align: top;">lazy arithmetic, exact predicates, topology analysis<br>
- </td>
- <td style="vertical-align: top;">non-robust<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top;">Output coordinates precision<br>
- </td>
- <td style="vertical-align: top;">128 machine epsilon<br>
- </td>
- <td style="vertical-align: top;">no output coordinates<br>
- </td>
- <td style="vertical-align: top;">no output coordinates<br>
- </td>
- </tr>
- <tr>
- <td style="vertical-align: top;">External dependencies<br>
- </td>
- <td style="vertical-align: top;">No<br>
- </td>
- <td style="vertical-align: top;">Boost, GMP, MPFR<br>
- </td>
- <td style="vertical-align: top;">No<br>
- </td>
- </tr>
- </tbody>
- </table>
- <br>
- The other known libraries (<a href="https://github.com/aewallin/openvoronoi">OpenVoronoi</a>,
- <a href="http://www.cs.cmu.edu/%7Equake/triangle.html">Triangle</a>, <a href="http://www.cosy.sbg.ac.at/%7Eheld/projects/vroni/vroni.html">Vroni</a>) 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 colspan="2" rowspan="1" style="vertical-align: top; text-align: center;">Test specification<br>
- </td>
- <td colspan="6" 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
- Linux-64<br>
- </td>
- <td style="vertical-align: top; text-align: center;">CGAL
- Linux-64<br>
- </td>
- <td style="vertical-align: top; text-align: center;">S-Hull
- Linux-64<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.000206<br>
- </td>
- <td style="vertical-align: top; text-align: right;"> 0.000073<br>
- </td>
- <td style="vertical-align: top; text-align: right;">0.000243<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.002250<br>
- </td>
- <td style="vertical-align: top; text-align: right;">0.000753<br>
- </td>
- <td style="vertical-align: top; text-align: right;">0.002184<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.024100<br>
- </td>
- <td style="vertical-align: top; text-align: right;">0.007917<br>
- </td>
- <td style="vertical-align: top; text-align: right;">0.030552<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.292000<br>
- </td>
- <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>
- <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;">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>
- <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>
- <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
- 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;">100<br>
- </td>
- <td style="vertical-align: top; text-align: right;">10000<br>
- </td>
-
-
- <td style="vertical-align: top; text-align: right;">0.002284<br>
- </td>
- <td style="vertical-align: top; text-align: right;">0.002985<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.023240<br>
- </td>
- <td style="vertical-align: top; text-align: right;">0.032180<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.237700<br>
- </td>
- <td style="vertical-align: top; text-align: right;">0.337400<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;">2.488000<br>
- </td>
- <td style="vertical-align: top; text-align: right;">3.633000<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;">25.00000<br>
- </td>
- <td style="vertical-align: top; text-align: right;">39.090000<br>
- </td>
- </tr>
- </tbody>
- </table>
- <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%">
- <table class="docinfo" id="table2" frame="void" rules="none">
- <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>
- </tr>
- <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">
- http://www.boost.org/LICENSE_1_0.txt</a>)</td>
- </tr>
- </tbody>
- </table>
- </td>
- </tr>
- </tbody>
- </table>
- </body></html>
|