libs/polygon/doc/voronoi_benchmark.htm

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2 <html><head>
   3
   4
   5
   6   <meta http-equiv="Content-Language" content="en-us">
   7   <meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Voronoi Benchmark</title></head><body>
   8 <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
   9   <tbody>
  10     <tr>
  11       <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  12       <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>
  13       <div style="margin: 5px;">
  14       <h3 class="navbar">Contents</h3>
  15       <ul>
  16         <li><a href="index.htm">Boost.Polygon Main Page</a></li>
  17         <li><a href="gtl_design_overview.htm">Design Overview</a></li>
  18         <li><a href="gtl_isotropy.htm">Isotropy</a></li>
  19         <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
  20         <li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
  21         <li><a href="gtl_point_concept.htm">Point Concept</a></li>
  22         <li><a href="gtl_segment_concept.htm">Segment Concept</a></li>
  23         <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
  24         <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
  25         <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
  26 With Holes Concept</a></li>
  27         <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
  28         <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
  29 With Holes Concept</a></li>
  30         <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
  31         <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
  32 Holes Concept</a></li>
  33         <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
  34 Concept</a></li>
  35         <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
  36 Concept</a></li>
  37         <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
  38         <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
  39 Extraction 90</a></li>
  40         <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
  41 Extraction 45</a></li>
  42         <li><a href="gtl_connectivity_extraction.htm">Connectivity
  43 Extraction</a></li>
  44         <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
  45         <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
  46         <li><a href="gtl_property_merge.htm">Property Merge</a></li>
  47         <li><a href="voronoi_main.htm">Voronoi Main Page<br>
  48           </a></li>
  49         <li>Voronoi Benchmark<br>
  50         </li>
  51         <li><a href="voronoi_builder.htm">Voronoi Builder</a></li>
  52         <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
  53       </ul>
  54       <h3 class="navbar">Other Resources</h3>
  55       <ul>
  56         <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
  57         <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
  58 Presentation</a></li>
  59         <li><a href="analysis.htm">Performance Analysis</a></li>
  60         <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
  61         <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
  62         <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
  63         <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
  64 Tutorial</a></li>
  65       </ul>
  66       </div>
  67       <h3 class="navbar">Polygon Sponsor</h3>
  68       <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>
  69       </td>
  70       <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"><!-- End Header --> <br>
  71       <h1>Voronoi Benchmark</h1>
  72       <h2>Benchmark Details</h2>
  73 From the topological perspective Delaunay triangulation is a dual
  74 data structure to the Voronoi diagram, thus libraries that provide
  75 Delaunay triangulation construction routines were also included into
  76 the benchmark. However, from the computation perspective Voronoi
  77 diagram contains more information as it embeds information regarding
  78 the coordinates of the centers of the inscribed circles tangent to the
  79 three or more input geometries.<br>
  80
  81
  82 The benchmark consists of the two parts:<br>
  83       <ol>
  84 <li>construction of the Voronoi diagram / Delaunay triangulation of a set of
  85 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
  86 random non-intersecting
  87 segments uniformly distributed over 32-bit integer grid (<a href="../benchmark/voronoi_benchmark_segments.cpp">voronoi_benchmark_segments.cpp</a>).</li>
  88       </ol>
  89
  90
  91
  92       <h2>Libraries</h2>
  93       <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
  94         <tbody>
  95           <tr>
  96             <td style="vertical-align: top;"><span style="font-weight: bold;">Library</span><br>
  97             </td>
  98             <td style="vertical-align: top; font-weight: bold;">Boost.Polygon<br>
  99             </td>
 100             <td style="vertical-align: top; font-weight: bold;">CGAL<br>
 101             </td>
 102             <td style="vertical-align: top; font-weight: bold;">SHull<br>
 103             </td>
 104           </tr>
 105           <tr>
 106             <td style="vertical-align: top;">Official page<br>
 107             </td>
 108             <td style="vertical-align: top;">www.boost.org/libs/polygon&#8206;<br>
 109             </td>
 110             <td style="vertical-align: top;">http://www.cgal.org<br>
 111             </td>
 112             <td style="vertical-align: top;">http://www.s-hull.org<br>
 113             </td>
 114           </tr>
 115           <tr>
 116             <td style="vertical-align: top;">Algorithm<br>
 117             </td>
 118             <td style="vertical-align: top;">sweep-line<br>
 119             </td>
 120             <td style="vertical-align: top;">incremental<br>
 121             </td>
 122             <td style="vertical-align: top;">sweep-hull<br>
 123             </td>
 124           </tr>
 125           <tr>
 126             <td style="vertical-align: top;">Supported input geometries<br>
 127             </td>
 128             <td style="vertical-align: top;">points and segments<br>
 129             </td>
 130             <td style="vertical-align: top;">points and segments<br>
 131             </td>
 132             <td style="vertical-align: top;">points<br>
 133             </td>
 134           </tr>
 135           <tr>
 136             <td style="vertical-align: top;">Output data structure<br>
 137             </td>
 138             <td style="vertical-align: top;">Voronoi diagram<br>
 139             </td>
 140             <td style="vertical-align: top;">Delaunay triangulation<br>
 141             </td>
 142             <td style="vertical-align: top;">Delaunay triangulation<br>
 143             </td>
 144           </tr>
 145           <tr>
 146             <td style="vertical-align: top;">Complexity<br>
 147             </td>
 148             <td style="vertical-align: top;">O(N log N)<br>
 149             </td>
 150             <td style="vertical-align: top;">O(N log N)</td>
 151             <td style="vertical-align: top;">O(N log N)</td>
 152           </tr>
 153           <tr>
 154             <td style="vertical-align: top;">Memory usage<br>
 155             </td>
 156             <td style="vertical-align: top;">O(N)<br>
 157             </td>
 158             <td style="vertical-align: top;">O(N)<br>
 159             </td>
 160             <td style="vertical-align: top;">O(N)<br>
 161             </td>
 162           </tr>
 163           <tr>
 164             <td style="vertical-align: top;">Robustness policies<br>
 165             </td>
 166             <td style="vertical-align: top;">lazy arithmetic, exact predicates, topology analysis<br>
 167             </td>
 168             <td style="vertical-align: top;">lazy arithmetic, exact predicates, topology analysis<br>
 169             </td>
 170             <td style="vertical-align: top;">non-robust<br>
 171             </td>
 172           </tr>
 173           <tr>
 174             <td style="vertical-align: top;">Output coordinates precision<br>
 175             </td>
 176             <td style="vertical-align: top;">128 machine epsilon<br>
 177             </td>
 178             <td style="vertical-align: top;">no output coordinates<br>
 179             </td>
 180             <td style="vertical-align: top;">no output coordinates<br>
 181             </td>
 182           </tr>
 183           <tr>
 184             <td style="vertical-align: top;">External dependencies<br>
 185             </td>
 186             <td style="vertical-align: top;">No<br>
 187             </td>
 188             <td style="vertical-align: top;">Boost, GMP, MPFR<br>
 189             </td>
 190             <td style="vertical-align: top;">No<br>
 191             </td>
 192           </tr>
 193         </tbody>
 194       </table>
 195       <br>
 196
 197 The other known libraries (<a href="https://github.com/aewallin/openvoronoi">OpenVoronoi</a>,
 198       <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>
 199 <ul>
 200         <ul>
 201
 202
 203
 204
 205
 206
 207
 208         </ul>
 209
 210
 211         <ul>
 212
 213
 214         </ul>
 215
 216       </ul>
 217       <h2>System Configuration<br>
 218       </h2>
 219
 220
 221 Hardware: Intel i5-7600 2.8 GHz, 16GiB RAM.<br>
 222 OS: Ubuntu 13.04 64-bit.<br>
 223 Compiler: GCC 4.7.3.<br>
 224 Libraries and dependencies: Boost 1.54.0, CGAL-4.3-beta1, GMP 5.1.4, MPFR 3.1.2, S-Hull.<br>
 225       <h2>Benchmark Results</h2>
 226       <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>
 227
 228       <table style="text-align: left; width: 100%; margin-left: auto; margin-right: auto;" border="1" cellpadding="2" cellspacing="2">
 229         <tbody>
 230           <tr>
 231             <td colspan="2" rowspan="1" style="vertical-align: top; text-align: center;">Test specification<br>
 232             </td>
 233             <td colspan="6" rowspan="1" style="vertical-align: top; text-align: center;">Average construction
 234 time (in secs)<br>
 235             </td>
 236           </tr>
 237           <tr>
 238             <td style="vertical-align: top; text-align: center;">Number
 239 of Points<br>
 240             </td>
 241             <td style="vertical-align: top; text-align: center;">Number
 242 of Runs<br>
 243             </td>
 244
 245
 246
 247             <td style="vertical-align: top; text-align: center;">Boost
 248 Linux-64<br>
 249             </td>
 250             <td style="vertical-align: top; text-align: center;">CGAL
 251 Linux-64<br>
 252             </td>
 253             <td style="vertical-align: top; text-align: center;">S-Hull
 254 Linux-64<br>
 255             </td>
 256           </tr>
 257
 258           <tr>
 259             <td style="vertical-align: top; text-align: right;">100<br>
 260             </td>
 261             <td style="vertical-align: top; text-align: right;">10000<br>
 262             </td>
 263
 264
 265
 266             <td style="vertical-align: top; text-align: right;">0.000206<br>
 267             </td>
 268             <td style="vertical-align: top; text-align: right;">&nbsp;0.000073<br>
 269             </td>
 270             <td style="vertical-align: top; text-align: right;">0.000243<br>
 271             </td>
 272           </tr>
 273           <tr>
 274             <td style="vertical-align: top; text-align: right;">1000<br>
 275             </td>
 276             <td style="vertical-align: top; text-align: right;">1000<br>
 277             </td>
 278
 279
 280
 281             <td style="vertical-align: top; text-align: right;">0.002250<br>
 282             </td>
 283             <td style="vertical-align: top; text-align: right;">0.000753<br>
 284             </td>
 285             <td style="vertical-align: top; text-align: right;">0.002184<br>
 286             </td>
 287           </tr>
 288           <tr>
 289             <td style="vertical-align: top; text-align: right;">10000<br>
 290             </td>
 291             <td style="vertical-align: top; text-align: right;">100<br>
 292             </td>
 293
 294
 295
 296             <td style="vertical-align: top; text-align: right;">0.024100<br>
 297             </td>
 298             <td style="vertical-align: top; text-align: right;">0.007917<br>
 299             </td>
 300             <td style="vertical-align: top; text-align: right;">0.030552<br>
 301             </td>
 302           </tr>
 303           <tr>
 304             <td style="vertical-align: top; text-align: right;">100000<br>
 305             </td>
 306             <td style="vertical-align: top; text-align: right;">10<br>
 307             </td>
 308
 309
 310
 311             <td style="vertical-align: top; text-align: right;">0.292000<br>
 312             </td>
 313             <td style="vertical-align: top; text-align: right;">0.084336<br>
 314             </td>
 315             <td style="vertical-align: top; text-align: right;">0.451913<br>
 316             </td>
 317           </tr>
 318           <tr>
 319             <td style="vertical-align: top; text-align: right;">1000000<br>
 320             </td>
 321             <td style="vertical-align: top; text-align: right;">1<br>
 322             </td>
 323
 324
 325
 326             <td style="vertical-align: top; text-align: right;">3.470000<br>
 327             </td>
 328             <td style="vertical-align: top; text-align: right;">0.902300<br>
 329             </td>
 330             <td style="vertical-align: top; text-align: right;">6.603814<br>
 331             </td>
 332           </tr>
 333         </tbody>
 334       </table>
 335       <br>
 336 <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>
 337
 338       <table style="text-align: left; width: 100%;" border="1" cellpadding="2" cellspacing="2">
 339         <tbody>
 340           <tr>
 341             <td colspan="2" rowspan="1" style="vertical-align: top; text-align: center;">Test specification<br>
 342             </td>
 343             <td colspan="4" rowspan="1" style="vertical-align: top; text-align: center;">Average construction
 344 time (in secs)</td>
 345           </tr>
 346           <tr>
 347             <td style="vertical-align: top; text-align: center;">Number
 348 of Segments<br>
 349             </td>
 350             <td style="vertical-align: top; text-align: center;">Number
 351 of Runs<br>
 352             </td>
 353
 354
 355             <td style="vertical-align: top; text-align: center;">Boost
 356 Linux-64<br>
 357             </td>
 358             <td style="vertical-align: top; text-align: center;">CGAL
 359 Linux-64<br>
 360             </td>
 361           </tr>
 362
 363           <tr>
 364             <td style="vertical-align: top; text-align: right;">100<br>
 365             </td>
 366             <td style="vertical-align: top; text-align: right;">10000<br>
 367             </td>
 368
 369
 370             <td style="vertical-align: top; text-align: right;">0.002284<br>
 371             </td>
 372             <td style="vertical-align: top; text-align: right;">0.002985<br>
 373             </td>
 374           </tr>
 375           <tr>
 376             <td style="vertical-align: top; text-align: right;">1000<br>
 377             </td>
 378             <td style="vertical-align: top; text-align: right;">1000<br>
 379             </td>
 380
 381
 382             <td style="vertical-align: top; text-align: right;">0.023240<br>
 383             </td>
 384             <td style="vertical-align: top; text-align: right;">0.032180<br>
 385             </td>
 386           </tr>
 387           <tr>
 388             <td style="vertical-align: top; text-align: right;">10000<br>
 389             </td>
 390             <td style="vertical-align: top; text-align: right;">100<br>
 391             </td>
 392
 393
 394             <td style="vertical-align: top; text-align: right;">&nbsp;0.237700<br>
 395             </td>
 396             <td style="vertical-align: top; text-align: right;">0.337400<br>
 397             </td>
 398           </tr>
 399           <tr>
 400             <td style="vertical-align: top; text-align: right;">100000<br>
 401             </td>
 402             <td style="vertical-align: top; text-align: right;">10<br>
 403             </td>
 404
 405
 406             <td style="vertical-align: top; text-align: right;">2.488000<br>
 407             </td>
 408             <td style="vertical-align: top; text-align: right;">3.633000<br>
 409             </td>
 410           </tr>
 411           <tr>
 412             <td style="vertical-align: top; text-align: right;">1000000<br>
 413             </td>
 414             <td style="vertical-align: top; text-align: right;">1<br>
 415             </td>
 416
 417
 418             <td style="vertical-align: top; text-align: right;">25.00000<br>
 419             </td>
 420             <td style="vertical-align: top; text-align: right;">39.090000<br>
 421             </td>
 422           </tr>
 423         </tbody>
 424       </table>
 425       <br><span style="font-weight: bold;"></span></td>
 426     </tr>
 427     <tr>
 428       <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">&nbsp;</td>
 429       <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
 430       <table class="docinfo" id="table2" frame="void" rules="none">
 431         <colgroup> <col class="docinfo-name"><col class="docinfo-content"> </colgroup> <tbody valign="top">
 432           <tr>
 433             <th class="docinfo-name">Copyright:</th>
 434             <td>Copyright © Andrii Sydorchuk 2010-2012.</td>
 435           </tr>
 436           <tr class="field">
 437             <th class="docinfo-name">License:</th>
 438             <td class="field-body">Distributed under the Boost Software
 439 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">
 440 http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 441           </tr>
 442         </tbody>
 443       </table>
 444       </td>
 445     </tr>
 446   </tbody>
 447 </table>
 448
 449 </body></html>