Subject: [Boost-commit] svn:boost r61141 - in sandbox/gtl/doc: . images
From: lucanus.j.simonson_at_[hidden]
Date: 2010-04-07 17:05:53
Author: ljsimons
Date: 2010-04-07 17:05:52 EDT (Wed, 07 Apr 2010)
New Revision: 61141
URL: http://svn.boost.org/trac/boost/changeset/61141
Log:
updating docs
Added:
sandbox/gtl/doc/analysis.htm (contents, props changed)
sandbox/gtl/doc/images/perf_graph.PNG (contents, props changed)
Added: sandbox/gtl/doc/analysis.htm
==============================================================================
--- (empty file)
+++ sandbox/gtl/doc/analysis.htm 2010-04-07 17:05:52 EDT (Wed, 07 Apr 2010)
@@ -0,0 +1,145 @@
+<!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"> -->
+<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>Polygon Library Main Page</li>
+ <li><a href="gtl_design_overview.htm">Polygon
+ Library Design Overview</a></li>
+ <li>Isotropy</li>
+ <li>Coordinate Concept</li>
+ <li>Interval Concept</li>
+ <li>
+ Point Concept</li>
+ <li>Rectangle Concept</li>
+ <li>Polygon 90 Concept</li>
+ <li>Polygon 90 With Holes Concept</li>
+ <li>Polygon 45 Concept</li>
+ <li>Polygon 45 With Holes Concept</li>
+ <li>Polygon Concept</li>
+ <li>Polygon With Holes Concept</li>
+ <li>Polygon 90 Set Concept</li>
+ <li>Polygon 45 Set Concept</li>
+ <li>Polygon Set Concept</li>
+ <li>Connectivity Extraction 90</li>
+ <li>Connectivity Extraction 45</li>
+ <li>Connectivity Extraction</li>
+ <li>Property Merge 90</li>
+ <li>Property Merge 45</li>
+ <li>Property Merge</li>
+ </ul>
+ <h3 class="navbar">Other Resources</h3>
+ <ul>
+ <li>GTL Boostcon 2009 Paper</li>
+ <li><a href="GTL_boostcon_draft03.htm">GTL Boostcon 2009
+ Presentation</a></li>
+ <li>Performance Analysis</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"><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 paper
+presented at
+boostcon 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 GPC 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 GMP
+ 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%">
+
+ </html>
\ No newline at end of file
Added: sandbox/gtl/doc/images/perf_graph.PNG
==============================================================================
Binary file. No diff available.