123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203 |
- <!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" />
- <!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> -->
- </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" 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">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</a> </li>
- <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a></li>
- <li><a href="voronoi_builder.htm">Voronoi Builder</a><br />
- </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>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>
- <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" href="http://www.adobe.com/"
- tabindex="2" style="border: medium none ;"> </a> </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 src="images/perf_graph.PNG" border="0" height="414"
- width="391" />
- <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.man.ac.uk/~toby/gpc/">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
- 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>
- <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.</p>
- </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="table1" 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 © 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>
- </tbody>
- </table>
- </td>
- </tr>
- </tbody>
- </table>
- </body>
- </html>
|