devn00b
/
EQ2EMu


			
				
					
						
						
							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.&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.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.&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>