| <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
| <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"><head><!-- |
| Copyright 2009-2010 Intel Corporation |
| license banner |
| --> |
| <title>Boost Polygon Library: Performance Analysis</title> |
| <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1"> |
| <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 border="0" src="images/boost.png" width="277" height="86"><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;"> |
| </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">Polygon |
| Library 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_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> |
| </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>Performance Analysis</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> |
| </ul> |
| </div> |
| <h3 class="navbar">Polygon Sponsor</h3> |
| <div style="padding: 5px;" align="center"> |
| <img border="0" src="images/intlogo.gif" width="127" height="51"> |
| </div> |
| </td> |
| <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"> |
| |
| <!-- End Header --> |
| |
| <br> |
| <p> |
| </p><h1>Polygon Set Algorithms Analysis</h1> |
| <p>Most non-trivial algorithms in the Boost.Polygon library are |
| instantiations of generic sweep-line algorithms that provide the capability to |
| perform Manhattan and 45-degree line segment intersection, n-layer map overlay, |
| connectivity graph extraction and clipping/Booleans. These algorithms have O(n log n) |
| runtime complexity for n equal to input vertices plus intersection vertices. The |
| arbitrary angle line segment intersection algorithm is not implemented as a |
| sweep-line due to complications related to achieving numerical robustness. |
| The general line segment intersection algorithm is implemented as an recursive |
| adaptive heuristic divide and conquer in the y dimension followed by sorting |
| line segments in each subdivision by x coordinates and scanning left to right. |
| By one-dimensional decomposition of the problem space in both x and y the |
| algorithm approximates the optimal O(n log n) Bentley-Ottmann line segment intersection |
| runtime complexity in the common case. Specific examples of inputs that |
| defeat one dimensional decomposition of the problem space can result in |
| pathological quadratic runtime complexity to which the Bentley-Ottmann algorithm |
| is immune.</p> |
| <p>Below is shown a log-log plot of runtime versus input size for inputs that |
| increase quadratically in size. The inputs were generated by |
| pseudo-randomly distributing small axis-parallel rectangles within a square area |
| proportional the the number of rectangles specified for each trial. In |
| this way the probability of intersections being produced remains constant as the |
| input size grows. Because intersection vertices are expected to be a |
| constant factor of input vertices we can examine runtime complexity in terms of |
| input vertices. The operation performed was a union (Boolean OR) of the |
| input rectangles by each of the Manhattan, 45-degree and arbitrary angle |
| Booleans algorithms, which are labeled "boolean 90", "boolean 45" and "boolean". |
| Also shown in the plot is the performance of the arbitrary angle Booleans |
| algorithm as prior to the addition of divide and conquer recursive subdivision, |
| which was described in the <a href="GTL_boostcon2009.pdf">paper</a> |
| <a href="GTL_boostcon_draft03.pdf">presented</a> at |
| <a href="http://www.boostcon.com/home">boostcon</a> 2009. Finally, the |
| time required to sort the input points is shown as a common reference for O(n log n) |
| runtime to put the data into context.</p><img border="0" src="images/perf_graph.PNG" width="391" height="414"><p> |
| We can see in the log-log plot that sorting and the three Booleans algorithms |
| provided by the Boost.Polygon library have nearly 45 degree "linear" |
| scaling with empirical exponents just slightly larger than 1.0 and can be |
| observed to scale proportional to O(n log n) for |
| these inputs. The "old boolean" algorithm presented at boostcon 2009 |
| exhibits scaling close to the expected O(n<sup><font size="2">1.5</font></sup>) |
| scaling. Because the speedup provided by the divide and conquer approach |
| is algorithmic, the 10X potential performance improvement alluded to in the paper is |
| realized at inputs of 200,000 rectangles and larger. Even for small inputs |
| of 2K rectangles the algorithm is 2X faster and now can be expected to be |
| roughly as fast as <a href="http://www.cs.manchester.ac.uk/~toby/alan/software/">GPC</a> at small scales, |
| while algorithmically faster at large scales.</p> |
| <p> |
| |
| |
| From the plot we can compare the constant factor performance of the various |
| Booleans algorithms with the runtime of std::sort as a baseline for O(n log n) |
| algorithms. If you consider sort to be one unit of O(n log n) algorithmic |
| work we can see that Manhattan Booleans cost roughly five units of O(n log n) |
| work, 45-degree Booleans cost roughly |
| |
| |
| </body>ten units of O(n log n) work and arbitrary angle Booleans cost roughly |
| seventy units of O(n log n) work. Sorting the input vertices is the first |
| step in a Booleans algorithm and therefore provides a hard lower bound for the |
| runtime of an optimal Booleans algorithm.<p> |
| |
| |
| One final thing to note about performance of the arbitrary angle Booleans |
| algorithm is that the use of <a href="http://gmplib.org">GMP</a> |
| infinite precision rational data type for numerically robust |
| computations can be employed by including boost/polygon/gmp_override.hpp and linking |
| to lgmpxx and lgmp. This provides |
| 100% assurance that the algorithm will succeed and produce an output snapped to |
| the integer grid with a minimum of one integer grid of error on polygon |
| boundaries upon which intersection points are introduced. However, the |
| infinite precision data type is never used for predicates (see the boostcon |
| presentation or paper for description of robust predicates) and is only used for |
| constructions of intersection coordinate values in the very rare case that long |
| double computation of the intersection of two line segments fails to produce an |
| intersection point within one integer unit of both line segments. This |
| means that there is effectively no runtime penalty for the use of infinite |
| precision to ensure 100% robustness. Most inputs will process through the |
| algorithm without ever resorting to GMP.<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" rules="none" frame="void" id="table1"> |
| <colgroup> |
| <col class="docinfo-name"><col class="docinfo-content"> |
| </colgroup> |
| <tbody vAlign="top"> |
| <tr> |
| <th class="docinfo-name">Copyright:</th> |
| <td>Copyright © Intel Corporation 2008-2010.</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> |
| </table> |
| |
| </html> |