ceph/src/boost/libs/polygon/doc/analysis.htm

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   2 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
   3 <head>
   4 <!--
   5     Copyright 2009-2010 Intel Corporation
   6     license banner
   7 -->
   8   <title>Boost Polygon Library: Performance Analysis</title>
   9   <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" />
  10 <!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> -->
  11 </head>
  12 <body>
  13 <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0"
  14  cellpadding="0" cellspacing="0">
  15   <tbody>
  16     <tr>
  17       <td style="background-color: rgb(238, 238, 238);" nowrap="1"
  18  valign="top">
  19       <div style="padding: 5px;" align="center"> <img
  20  src="images/boost.png" border="0" height="86" width="277" /><a
  21  title="www.boost.org home page" href="http://www.boost.org/"
  22  tabindex="2" style="border: medium none ;"> </a> </div>
  23       <div style="margin: 5px;">
  24       <h3 class="navbar">Contents</h3>
  25       <ul>
  26         <li><a href="index.htm">Boost.Polygon Main Page</a></li>
  27         <li><a href="gtl_design_overview.htm">Design Overview</a></li>
  28         <li><a href="gtl_isotropy.htm">Isotropy</a></li>
  29         <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
  30         <li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
  31         <li><a href="gtl_point_concept.htm">Point Concept</a></li>
  32         <li><a href="gtl_segment_concept.htm">Segment Concept</a></li>
  33         <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
  34         <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
  35         <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
  36 With Holes Concept</a></li>
  37         <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
  38         <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
  39 With Holes Concept</a></li>
  40         <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
  41         <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
  42 Holes Concept</a></li>
  43         <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
  44 Concept</a></li>
  45         <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
  46 Concept</a></li>
  47         <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
  48         <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
  49 Extraction 90</a></li>
  50         <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
  51 Extraction 45</a></li>
  52         <li><a href="gtl_connectivity_extraction.htm">Connectivity
  53 Extraction</a></li>
  54         <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
  55         <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
  56         <li><a href="gtl_property_merge.htm">Property Merge</a></li>
  57         <li><a href="voronoi_main.htm">Voronoi Main Page</a> </li>
  58         <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a></li>
  59         <li><a href="voronoi_builder.htm">Voronoi Builder</a><br />
  60         </li>
  61         <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
  62       </ul>
  63       <h3 class="navbar">Other Resources</h3>
  64       <ul>
  65         <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
  66         <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
  67 Presentation</a></li>
  68         <li>Performance Analysis</li>
  69         <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
  70         <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
  71         <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
  72         <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
  73 Tutorial</a></li>
  74       </ul>
  75       </div>
  76       <h3 class="navbar">Polygon Sponsor</h3>
  77       <div style="padding: 5px;" align="center"> <img
  78  src="images/intlogo.gif" border="0" height="51" width="127" /><a
  79  title="www.adobe.com home page" href="http://www.adobe.com/"
  80  tabindex="2" style="border: medium none ;"> </a> </div>
  81       </td>
  82       <td
  83  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
  84  valign="top" width="100%">
  85 <!-- End Header --><br />
  86       <p>
  87       </p>
  88       <h1>Polygon Set Algorithms Analysis</h1>
  89       <p>Most non-trivial algorithms in the Boost.Polygon library are
  90 instantiations of generic sweep-line algorithms that provide the
  91 capability to perform Manhattan and 45-degree line segment
  92 intersection, n-layer map overlay, connectivity graph extraction and
  93 clipping/Booleans.&nbsp; These algorithms have O(n log n) runtime
  94 complexity for n equal to input vertices plus intersection
  95 vertices.&nbsp; The arbitrary angle line segment intersection algorithm
  96 is not implemented as a sweep-line due to complications related to
  97 achieving numerical robustness.&nbsp; The general line segment
  98 intersection algorithm is implemented as an recursive adaptive
  99 heuristic divide and conquer in the y dimension followed by sorting
 100 line segments in each subdivision by x coordinates and scanning left to
 101 right.&nbsp; By one-dimensional decomposition of the problem space in
 102 both x and y the algorithm approximates the optimal O(n log n)
 103 Bentley-Ottmann line segment intersection runtime complexity in the
 104 common case.&nbsp; Specific examples of inputs that defeat one
 105 dimensional decomposition of the problem space can result in
 106 pathological quadratic runtime complexity to which the Bentley-Ottmann
 107 algorithm is immune.</p>
 108       <p>Below is shown a log-log plot of runtime versus input size for
 109 inputs that increase quadratically in size.&nbsp; The inputs were
 110 generated by pseudo-randomly distributing small axis-parallel
 111 rectangles within a square area proportional the the number of
 112 rectangles specified for each trial.&nbsp; In this way the probability
 113 of intersections being produced remains constant as the input size
 114 grows.&nbsp; Because intersection vertices are expected to be a
 115 constant factor of input vertices we can examine runtime complexity in
 116 terms of input vertices.&nbsp; The operation performed was a union
 117 (Boolean OR) of the input rectangles by each of the Manhattan,
 118 45-degree and arbitrary angle Booleans algorithms, which are labeled
 119 "boolean 90", "boolean 45" and "boolean".&nbsp; Also shown in the plot
 120 is the performance of the arbitrary angle Booleans algorithm as prior
 121 to the addition of divide and conquer recursive subdivision, which was
 122 described in the <a href="GTL_boostcon2009.pdf">paper</a> <a
 123  href="GTL_boostcon_draft03.pdf">presented</a> at
 124       <a href="http://www.boostcon.com/home">boostcon</a> 2009.&nbsp;
 125 Finally, the time required to sort the input points is shown as a
 126 common reference for O(n log n) runtime to put the data into context.</p>
 127       <img src="images/perf_graph.PNG" border="0" height="414"
 128  width="391" />
 129       <p>We can see in the log-log plot that sorting and the three
 130 Booleans algorithms provided by the Boost.Polygon library have nearly
 131 45 degree "linear" scaling with empirical exponents just slightly
 132 larger than 1.0 and can be observed to scale proportional to O(n log n)
 133 for these inputs.&nbsp; The "old boolean" algorithm presented at
 134 boostcon 2009 exhibits scaling close to the expected O(n<sup><font
 135  size="2">1.5</font></sup>) scaling.&nbsp; Because the speedup provided
 136 by the divide and conquer approach is algorithmic, the 10X potential
 137 performance improvement alluded to in the paper is realized at inputs
 138 of 200,000 rectangles and larger.&nbsp; Even for small inputs of 2K
 139 rectangles the algorithm is 2X faster and now can be expected to be
 140 roughly as fast as <a
 141  href="http://www.cs.manchester.ac.uk/%7Etoby/alan/software/">GPC</a>
 142 at small scales, while algorithmically faster at large scales.</p>
 143       <p>
 144 From the plot we can compare the constant factor performance of the
 145 various Booleans algorithms with the runtime of std::sort as a baseline
 146 for O(n log n) algorithms.&nbsp; If you consider sort to be one unit of
 147 O(n log n) algorithmic work we can see that Manhattan Booleans cost
 148 roughly five units of O(n log n) work, 45-degree&nbsp; Booleans cost
 149 roughly
 150 ten units of O(n log n) work and arbitrary angle Booleans cost roughly
 151 seventy units of O(n log n) work.&nbsp; Sorting the input vertices is
 152 the first step in a Booleans algorithm and therefore provides a hard
 153 lower bound for the runtime of an optimal Booleans algorithm.</p>
 154       <p>One final thing to note about performance of the arbitrary
 155 angle Booleans algorithm is that the use of <a href="http://gmplib.org">GMP</a>
 156 infinite precision rational data type for numerically robust
 157 computations can be employed by including
 158 boost/polygon/gmp_override.hpp and linking to lgmpxx and lgmp.&nbsp;
 159 This provides 100% assurance that the algorithm will succeed and
 160 produce an output snapped to the integer grid with a minimum of one
 161 integer grid of error on polygon boundaries upon which intersection
 162 points are introduced.&nbsp; However, the infinite precision data type
 163 is never used for predicates (see the boostcon presentation or paper
 164 for description of robust predicates) and is only used for
 165 constructions of intersection coordinate values in the very rare case
 166 that long double computation of the intersection of two line segments
 167 fails to produce an intersection point within one integer unit of both
 168 line segments.&nbsp; This means that there is effectively no runtime
 169 penalty for the use of infinite precision to ensure 100%
 170 robustness.&nbsp; Most inputs will process through the algorithm
 171 without ever resorting to GMP.</p>
 172       </td>
 173     </tr>
 174     <tr>
 175       <td style="background-color: rgb(238, 238, 238);" nowrap="1"
 176  valign="top"> &nbsp;</td>
 177       <td
 178  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
 179  valign="top" width="100%">
 180       <table class="docinfo" id="table1" frame="void" rules="none">
 181         <colgroup> <col class="docinfo-name" /><col
 182  class="docinfo-content" /> </colgroup> <tbody valign="top">
 183           <tr>
 184             <th class="docinfo-name">Copyright:</th>
 185             <td>Copyright © Intel Corporation 2008-2010.</td>
 186           </tr>
 187           <tr class="field">
 188             <th class="docinfo-name">License:</th>
 189             <td class="field-body">Distributed under the Boost Software
 190 License, Version 1.0. (See accompanying file <tt class="literal"> <span
 191  class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
 192  class="reference" target="_top"
 193  href="http://www.boost.org/LICENSE_1_0.txt">
 194 http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 195           </tr>
 196         </tbody>
 197       </table>
 198       </td>
 199     </tr>
 200   </tbody>
 201 </table>
 202 </body>
 203 </html>