204 lines
10 KiB
HTML
204 lines
10 KiB
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.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 <20> 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>
|