boost/libs/polygon/doc/analysis.htm - nest-cam/4320010/boost - Git at Google

 <!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.&nbsp; These algorithms have O(n log n) runtime
 complexity for n equal to input vertices plus intersection
 vertices.&nbsp; The arbitrary angle line segment intersection algorithm
 is not implemented as a sweep-line due to complications related to
 achieving numerical robustness.&nbsp; 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.&nbsp; 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.&nbsp; 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.&nbsp; 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.&nbsp; In this way the probability
 of intersections being produced remains constant as the input size
 grows.&nbsp; Because intersection vertices are expected to be a
 constant factor of input vertices we can examine runtime complexity in
 terms of input vertices.&nbsp; 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".&nbsp; 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.&nbsp;
 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.&nbsp; 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.&nbsp; 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.&nbsp; 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/%7Etoby/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.&nbsp; 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&nbsp; 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.&nbsp; 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.&nbsp;
 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.&nbsp; 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.&nbsp; This means that there is effectively no runtime
 penalty for the use of infinite precision to ensure 100%
 robustness.&nbsp; 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"> &nbsp;</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>
	<!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.manchester.ac.uk/%7Etoby/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
	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>