projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
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. These algorithms have O(n log n) runtime | |
| 94 | complexity for n equal to input vertices plus intersection | |
| 95 | vertices. The arbitrary angle line segment intersection algorithm | |
| 96 | is not implemented as a sweep-line due to complications related to | |
| 97 | achieving numerical robustness. 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. 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. 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. 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. In this way the probability | |
| 113 | of intersections being produced remains constant as the input size | |
| 114 | grows. 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. 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". 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. | |
| 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. 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. 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. 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. 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 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. 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. | |
| 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. 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. This means that there is effectively no runtime | |
| 169 | penalty for the use of infinite precision to ensure 100% | |
| 170 | robustness. 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"> </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 |