|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r61140 - sandbox/gtl/doc
From: lucanus.j.simonson_at_[hidden]
Date: 2010-04-07 17:04:46
Author: ljsimons
Date: 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
New Revision: 61140
URL: http://svn.boost.org/trac/boost/changeset/61140
Log:
updating docs
Text files modified:
sandbox/gtl/doc/gtl_connectivity_extraction.htm | 6
sandbox/gtl/doc/gtl_connectivity_extraction_45.htm | 6
sandbox/gtl/doc/gtl_connectivity_extraction_90.htm | 6
sandbox/gtl/doc/gtl_coordinate_concept.htm | 15 +
sandbox/gtl/doc/gtl_design_overview.htm | 9
sandbox/gtl/doc/gtl_interval_concept.htm | 6
sandbox/gtl/doc/gtl_isotropy.htm | 8
sandbox/gtl/doc/gtl_point_3d_concept.htm | 6
sandbox/gtl/doc/gtl_point_concept.htm | 6
sandbox/gtl/doc/gtl_polygon_45_concept.htm | 32 ++--
sandbox/gtl/doc/gtl_polygon_45_set_concept.htm | 188 ++++++++++++++++++++----------
sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm | 6
sandbox/gtl/doc/gtl_polygon_90_concept.htm | 32 ++--
sandbox/gtl/doc/gtl_polygon_90_set_concept.htm | 239 +++++++++++++++++++++++++++------------
sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm | 6
sandbox/gtl/doc/gtl_polygon_concept.htm | 31 ++--
sandbox/gtl/doc/gtl_polygon_set_concept.htm | 158 ++++++++++++++++++--------
sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm | 6
sandbox/gtl/doc/gtl_property_merge.htm | 13 +-
sandbox/gtl/doc/gtl_property_merge_45.htm | 12 +-
sandbox/gtl/doc/gtl_property_merge_90.htm | 12 +-
sandbox/gtl/doc/gtl_rectangle_concept.htm | 6
sandbox/gtl/doc/index.htm | 49 +++++--
23 files changed, 551 insertions(+), 307 deletions(-)
Modified: sandbox/gtl/doc/gtl_connectivity_extraction.htm
==============================================================================
--- sandbox/gtl/doc/gtl_connectivity_extraction.htm (original)
+++ sandbox/gtl/doc/gtl_connectivity_extraction.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
Modified: sandbox/gtl/doc/gtl_connectivity_extraction_45.htm
==============================================================================
--- sandbox/gtl/doc/gtl_connectivity_extraction_45.htm (original)
+++ sandbox/gtl/doc/gtl_connectivity_extraction_45.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
Modified: sandbox/gtl/doc/gtl_connectivity_extraction_90.htm
==============================================================================
--- sandbox/gtl/doc/gtl_connectivity_extraction_90.htm (original)
+++ sandbox/gtl/doc/gtl_connectivity_extraction_90.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
Modified: sandbox/gtl/doc/gtl_coordinate_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_coordinate_concept.htm (original)
+++ sandbox/gtl/doc/gtl_coordinate_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
@@ -107,7 +107,14 @@
coordinates.<p>
Note: older versions of the stl define a fully generic distance(T, T) function
for computing the difference between two iterators. We were forced to name
-our distance function euclidean_distance to avoid name collision.<tr>
+our distance function euclidean_distance to avoid name collision.<p>
+The
+<a href="http://www.mentor.com/products/esl/high_level_synthesis/ac_datatypes">
+Algorithmic C</a> ac_int<128> is an example of a user defined coordinate data
+type that satisfies the coordinate concept. In general a data type should
+define std::numeric_limits and be integer-like. Floating point coordinate
+types are not supported by all the algorithms and generally not suitable for use
+with the library at present.<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%">
Modified: sandbox/gtl/doc/gtl_design_overview.htm
==============================================================================
--- sandbox/gtl/doc/gtl_design_overview.htm (original)
+++ sandbox/gtl/doc/gtl_design_overview.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,8 +15,8 @@
<div style="margin: 5px;">
<h3 class="navbar">Contents</h3>
<ul>
- <li>Polygon Library Main Page</li>
- <li>Polygon Library Design Overview</li>
+ <li>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +44,7 @@
<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>
@@ -105,8 +106,8 @@
by the library to overload generic functions means no matching function is found
by the compiler in cases where no overload is provided.</p>
<p>
-<font face="Courier New">error: no matching function for call to 'gtl::assign(gtl::rectangle_data<int>&,
-gtl::polygon_data<int>&)'</font></p>
+<font face="Courier New">error: no matching function for call to 'assign(rectangle_data<int>&,
+polygon_data<int>&)'</font></p>
<p>Associated with each concept is a traits struct that generally must be
specialized for a given data type to provide the concept mapping between the
interfaces of the data type and the expected behaviors of an object of that type
Modified: sandbox/gtl/doc/gtl_interval_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_interval_concept.htm (original)
+++ sandbox/gtl/doc/gtl_interval_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
Modified: sandbox/gtl/doc/gtl_isotropy.htm
==============================================================================
--- sandbox/gtl/doc/gtl_isotropy.htm (original)
+++ sandbox/gtl/doc/gtl_isotropy.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
@@ -76,7 +76,7 @@
called isotropy. In such situations it is convenient to parameterize
direction or orientation and write code that is invariant to the direction or
orientation in which it is applied. To do this effectively we provide an
-internally consistent set of isotropic data types in GTL to represent program
+internally consistent set of isotropic data types to represent program
data that describes orientations and directions. These data types are:</p>
<ul>
<li>direction_1d - has one of the following 2 states: LOW, HIGH </li>
Modified: sandbox/gtl/doc/gtl_point_3d_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_point_3d_concept.htm (original)
+++ sandbox/gtl/doc/gtl_point_3d_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
Modified: sandbox/gtl/doc/gtl_point_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_point_concept.htm (original)
+++ sandbox/gtl/doc/gtl_point_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
Modified: sandbox/gtl/doc/gtl_polygon_45_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_45_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_45_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
@@ -186,14 +186,14 @@
point, returns true
if the polygon contains the point. If the consider_touch
flag is true will return true if the point lies along the boundary of
- the polygon.</td>
+ the polygon. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">// get the center coordinate<br>
template <typename T, typename point_type><br>
void <b>center</b>(point_type& p, const T& polygon)</font></td>
<td>Sets object that models point to the center point of the bounding
- box of an object that models polygon_45.</td>
+ box of an object that models polygon_45. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T,
@@ -201,57 +201,59 @@
bool <b>extents</b>(rectangle_type& bbox, const T& polygon)</font></td>
<td>Sets object that models rectangle to the bounding box of an object
that models polygon_45 and returns true. Returns false and leaves
- bbox unchanged if polygon is empty.</td>
+ bbox unchanged if polygon is empty. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
area_type <b>area</b>(const T& polygon)</font></td>
<td>Returns the area of an object
- that models polygon_45.</td>
+ that models polygon_45. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
direction_1d <b>winding</b>(const T& polygon)</font></td>
<td>Returns the winding direction of an object
- that models polygon_45, LOW == CLOCKWISE, HIGH = COUNTERCLOCKWISE.</td>
+ that models polygon_45, LOW == CLOCKWISE, HIGH = COUNTERCLOCKWISE.
+ Complexity depends upon winding trait.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
coordinate_distance <b>perimeter</b>(const T& polygon)</font></td>
<td>Returns the perimeter length of an object
- that models polygon_45.</td>
+ that models polygon_45. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T,
typename transform_type><br>
T& <b>transform</b>(T& polygon, const transform_type&)</font></td>
<td>Applies transform() on the vertices of polygon and sets the polygon to that described by the result of
- transforming its vertices.</td>
+ transforming its vertices. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>scale_up</b>(T& polygon, unsigned_area_type factor)</font></td>
<td>Scales up coordinate of an object that models
- polygon_45 by unsigned factor.</td>
+ polygon_45 by unsigned factor. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>scale_down</b>(T& polygon, unsigned_area_type factor)</font></td>
<td>Scales down coordinates of an object that models
- polygon_45 by unsigned factor.</td>
+ polygon_45 by unsigned factor. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, scaling_type><br>
T& <b>scale</b>(T& rectangle, double scaling) </font></td>
<td>Scales coordinates of an object that models polygon_45 by floating
- point factor.</td>
+ point factor. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>move</b>(T& polygon, orientation_2d,<br>
coordinate_difference displacement)</font></td>
<td>Adds displacement value to coordinate indicated by orientation_2d of
- vertices of an object that models polygon_45 .</td>
+ vertices of an object that models polygon_45. Linear wrt.
+ vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename polygon_type, typename point_type><br>
@@ -259,7 +261,7 @@
const point_type& point)</font></td>
<td>Convolves coordinate values of point with vertices of an
- object that models polygon_45.</td>
+ object that models polygon_45. Linear wrt. vertices.</td>
</tr>
</table>
<h1>Polygon 45 Data</h1>
Modified: sandbox/gtl/doc/gtl_polygon_45_set_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_45_set_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_45_set_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
@@ -114,91 +114,106 @@
<td>Boolean OR operation (polygon set union). Accepts two objects
that model polygon_45_set or one of its refinements. Returns an
operator template that performs the operation on demand when chained or
- or nested in a library function call such as assign().</td>
+ or nested in a library function call such as assign(). O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_45_set_view <b>operator</b>+(const T1& l, const T2& r)</font></td>
<td>Same as operator|. The plus sign is also used for OR
- operations in Boolean logic expressions.</td>
+ operations in Boolean logic expressions. O( n log n) runtime
+ complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_45_set_view <b>operator</b>&(const T1& l, const T2& r)</font></td>
<td>Boolean AND operation (polygon set intersection). Accepts two
- objects that model polygon_45_set or one of its refinements.</td>
+ objects that model polygon_45_set or one of its refinements. O( n
+ log n) runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_45_set_view <b>operator</b>*(const T1& l, const T2& r)</font></td>
<td>Same as operator&. The multiplication symbol is also used for
- AND operations in Boolean logic expressions.</td>
+ AND operations in Boolean logic expressions. O( n log n) runtime
+ complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_45_set_view <b>operator</b>^(const T1& l, const T2& r)</font></td>
<td>Boolean XOR operation (polygon set disjoint-union). Accepts
- two objects that model polygon_45_set or one of its refinements.</td>
+ two objects that model polygon_45_set or one of its refinements.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_45_set_view <b>operator</b>-(const T1& l, const T2& r)</font></td>
<td>Boolean SUBTRACT operation (polygon set difference). Accepts
- two objects that model polygon_45_set or one of its refinements.</td>
+ two objects that model polygon_45_set or one of its refinements.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>|=(const T1& l, const T2& r)</font></td>
<td>Same as operator|, but with self assignment, left operand must model
- polygon_45_set and not one of it's refinements.</td>
+ polygon_45_set and not one of it's refinements. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>+=(T1& l, const T2& r)</font></td>
<td>Same as operator+, but with self assignment, left operand must model
- polygon_45_set and not one of it's refinements.</td>
+ polygon_45_set and not one of it's refinements. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>&=(const T1& l, const T2& r)</font></td>
<td>Same as operator&, but with self assignment, left operand must model
- polygon_45_set and not one of it's refinements.</td>
+ polygon_45_set and not one of it's refinements. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>*=(T1& l, const T2& r)</font></td>
<td>Same as operator*, but with self assignment, left operand must model
- polygon_45_set and not one of it's refinements.</td>
+ polygon_45_set and not one of it's refinements. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>^=(const T1& l, const T2& r)</font></td>
<td>Same as operator^, but with self assignment, left operand must model
- polygon_45_set and not one of it's refinements.</td>
+ polygon_45_set and not one of it's refinements. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>-=(T1& l, const T2& r)</font></td>
<td>Same as operator-, but with self assignment, left operand must model
- polygon_45_set and not one of it's refinements.</td>
+ polygon_45_set and not one of it's refinements. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1><br>
T1 <b>operator</b>+(const T1&, coordinate_type bloating)</font></td>
<td>Performs resize operation, inflating by bloating ammount. If
negative the result is a shrink instead of bloat. Note: returns
- result by value.</td>
+ result by value. O( n log n) runtime complexity and O(n) memory
+ wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -206,7 +221,8 @@
T1 <b>operator</b>-(const T1&, coordinate_type shrinking)</font></td>
<td>Performs resize operation, deflating by bloating ammount. If
negative the result is a bloat instead of shrink. Note: returns
- result by value.</td>
+ result by value. O( n log n) runtime complexity and O(n) memory
+ wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -214,7 +230,8 @@
T1& <b>operator</b>+=(const T1&, coordinate_type bloating)</font></td>
<td>Performs resize operation, inflating by bloating ammount. If
negative the result is a shrink instead of bloat. Returns
- reference to modified argument.</td>
+ reference to modified argument. O( n log n) runtime complexity and
+ O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -222,7 +239,8 @@
T1& <b>operator</b>-=(const T1&, coordinate_type shrinking)</font></td>
<td>Performs resize operation, deflating by bloating ammount. If
negative the result is a bloat instead of shrink. Returns
- reference to modified argument.</td>
+ reference to modified argument. O( n log n) runtime complexity and
+ O(n) memory wrt vertices + intersections.</td>
</tr>
</table>
<h2>Functions</h2>
@@ -233,7 +251,8 @@
T1& <b>assign</b>(T1& lvalue, const T2& rvalue)</font></td>
<td>Eliminates overlaps in geometry and copies from an object that
models polygon_45_set or any of its refinements into an object that
- models polygon_45_set</td>
+ models polygon_45_set. O( n log n) runtime complexity and O(n)
+ memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -242,7 +261,8 @@
<td>Returns true if an object that models polygon_45_set or one of its
refinements covers the exact same geometric regions as another object
that models polygon_45_set or one of its refinements. For example:
- two of polygon_45 objects.</td>
+ two of polygon_45 objects. O( n log n) runtime complexity and O(n)
+ memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename
@@ -255,7 +275,8 @@
refinements into non overlapping trapezoids along a vertical slicing
orientation and appends them to the
output, which must have a value type that models polygon_45,
- polygon_45_with_holes, polygon or polygon_with_holes. </td>
+ polygon_45_with_holes, polygon or polygon_with_holes. O( n
+ log n) runtime complexity and O(n) memory wrt vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename
@@ -268,7 +289,8 @@
refinements into non overlapping trapezoids along a the specified slicing
orientation and appends them to the
output, which must have a value type that models polygon_45,
- polygon_45_with_holes, polygon or polygon_with_holes. </td>
+ polygon_45_with_holes, polygon or polygon_with_holes. O( n
+ log n) runtime complexity and O(n) memory wrt vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename
@@ -281,7 +303,8 @@
polygon_set_type><br>
bool <b>empty</b>(const polygon_set_type& polygon_set)</font></td>
<td>Checks whether the object is empty of geometry. Polygons that
- are completely covered by holes will result in empty returning true.</td>
+ are completely covered by holes will result in empty returning true.
+ O( n log n) runtime complexity and O(n) memory wrt vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, typename
@@ -292,13 +315,15 @@
<td>Computes bounding box of an object that models polygon_45_set and
stores it in an object that models rectangle. If the polygon set
is empty returns false. If there are holes outside of shells they
- do not contribute to the extents of the polygon set.</td>
+ do not contribute to the extents of the polygon set. O( n
+ log n) runtime complexity and O(n) memory wrt vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
area_type <b>area</b>(const T& polygon_set)</font></td>
<td>Computes the area covered by geometry in an object that models
- polygon_45_set</td>
+ polygon_45_set. O( n log n) runtime complexity and O(n)
+ memory wrt vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -306,32 +331,38 @@
T1& <b>interact</b>(T1& a, const T2& b)</font></td>
<td>Given an object that models polygon_45_set and an object that models
polygon_45_set or one of its refinements, modifies a to retain only
- regions that overlap or touch regions in b.</td>
+ regions that overlap or touch regions in b. O( n log n)
+ runtime complexity and O(n) memory wrt vertices plus intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>self_intersect</b>(T& polygon_set)</font></td>
<td>Given an object that models polygon_45_set that has self overlapping
- regions, modifies the argument to contain only the regions of overlap.</td>
+ regions, modifies the argument to contain only the regions of overlap.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>self_xor</b>(T& polygon_set)</font></td>
<td>Given an object that models polygon_45_set that has self overlapping
regions, modifies the argument to contain only the regions that do not
- overlap.</td>
+ overlap. O( n log n) runtime complexity and O(n) memory wrt
+ vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>bloat</b>(T& polygon_set, unsigned_area_type bloating)</font></td>
<td>Same as getting all the polygons, bloating them and putting them
- back.</td>
+ back. O( n log n) runtime complexity and O(n) memory wrt vertices
+ + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>shrink</b>(T& polygon_set, unsigned_area_type shrinking)</font></td>
<td>Same as getting all the polygons, shrinking them and overwriting
- the polygon set with the resulting regions.</td>
+ the polygon set with the resulting regions. O( n log n) runtime
+ complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, typename
@@ -343,39 +374,46 @@
negative. RoundingOption is an enum that controls snapping of
non-integer results of resizing 45 degree edges. CornerOption is
an enum that controls how corner filling is performed.
- polygon_45_set_data.hpp defines these enums.</td>
+ polygon_45_set_data.hpp defines these enums. O( n log n) runtime
+ complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>grow_and</b>(T& polygon_set, unsigned_area_type bloating)</font></td>
<td>Same as bloating non-overlapping regions and then applying self
- intersect to retain only the overlaps introduced by the bloat.</td>
+ intersect to retain only the overlaps introduced by the bloat. O(
+ n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>scale_up</b>(T& polygon_set, unsigned_area_type factor)</font></td>
- <td>Scales geometry up by unsigned factor..</td>
+ <td>Scales geometry up by unsigned factor. O( n log n) runtime
+ complexity and O(n) memory wrt vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>scale_down</b>(T& polygon_set, unsigned_area_type factor)</font></td>
<td>Scales geometry down by unsigned factor. Snaps 45 degree edges
back to 45 degrees after division truncation leads to small changes in
- angle.</td>
+ angle. O( n log n) runtime complexity and O(n) memory wrt
+ vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, typename scaling_type><br>
T& <b>scale</b>(polygon_set_type& polygon_set, double scaling)</font></td>
<td>Scales geometry by multiplying by floating point factor.
Snaps 45 degree edges back to 45 degrees after truncation of fractional
- results of multiply leads to small changes in angle.</td>
+ results of multiply leads to small changes in angle. O( n log n)
+ runtime complexity and O(n) memory wrt vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, typename transformation_type><br>
T& <b>transform</b>(T& polygon_set,<br>
const
transformation_type& transformation)</font></td>
- <td>Applies transformation.transform() on all vertices.</td>
+ <td>Applies transformation.transform() on all vertices. O( n log
+ n) runtime complexity and O(n) memory wrt vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
@@ -388,7 +426,8 @@
unsigned_area_type max_height)</font></td>
<td>Retains only regions that satisfy the min/max criteria in the
argument list. Note: useful for visualization to cull too small
- polygons.</td>
+ polygons. O( n log n) runtime complexity and O(n) memory wrt
+ vertices.</td>
</tr>
</table>
<h1>Polygon 45 Set Data Object</h1>
@@ -460,14 +499,15 @@
template <typename iT><br>
void <b>insert</b>(iT input_begin, iT input_end, <br> bool is_hole = false)</font></td>
<td>Insert objects of an iterator range. If is_hole is true
- inserts subtractive regions.</td>
+ inserts subtractive regions. Linear wrt the number of vertices
+ added.</td>
</tr>
<tr>
<td width="586">
<font face="Courier New">
void <b>insert</b>(const polygon_45_set_data& polygon_set, <br> bool is_hole
= false)</font></td>
- <td>Insert a polygon set.</td>
+ <td>Insert a polygon set. Linear wrt the number of vertices added.</td>
</tr>
<tr>
<td width="586">
@@ -476,7 +516,8 @@
void <b>insert</b>(const geometry_type& geometry_object, <br> bool is_hole
= false)</font></td>
<td>Insert a geometry object, if is_hole is true then the inserted
- region is subtractive rather than additive.</td>
+ region is subtractive rather than additive. Linear wrt the number
+ of vertices added.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -486,9 +527,10 @@
and eliminate overlaps. Converts polygon set geometry to objects
of that type and appends them to the container. Polygons will be
output with counterclockwise winding, hole polygons will be output with
- clockwise winding. The last vertex of an output polygon is the
+ clockwise winding. The last vertex of an output polygon is not the
duplicate of the first, and the number of points is equal to the number
- of edges plus 1.</td>
+ of edges. O(n log n) runtime and O(n) memory wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -497,7 +539,8 @@
<td>Expects a standard container of polygon objects. Will scan and
eliminate overlaps. Converts polygon set geometry to polygons and
appends them to the container. Polygons will have holes fractured
- out to the outer boundary along the positive y direction.</td>
+ out to the outer boundary along the positive y direction. O(n log
+ n) runtime and O(n) memory wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -505,7 +548,8 @@
void <b>get_polygons_with_holes</b>(output_container& o) const</font></td>
<td>Expects a standard container of polygon with holes objects. Will scan and
eliminate overlaps. Converts polygon set geometry to polygons and
- appends them to the container.</td>
+ appends them to the container. O(n log n) runtime and O(n) memory
+ wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -513,7 +557,8 @@
void <b>get_trapezoids</b>(output_container& output) const</font></td>
<td>Expects a standard container of polygon objects. Will scan
and eliminate overlaps. Slices polygon set geometry to trapezoids
- vertically and appends them to the container.</td>
+ vertically and appends them to the container. O(n log n) runtime
+ and O(n) memory wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586">
@@ -524,7 +569,8 @@
</td>
<td>Expects a standard container of polygon objects. Will scan
and eliminate overlaps. Slices polygon set geometry to trapezoids
- along the given orientation and appends them to the container.</td>
+ along the given orientation and appends them to the container. O(n
+ log n) runtime and O(n) memory wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586">
@@ -533,7 +579,9 @@
<td>Once scanned the data representation of geometry within a polygon
set is in a mathematically canonical form. Comparison between two
sets is therefore a linear time operation once they are in the scanned
- state. Will scan and eliminate overlaps in both polygon sets. </td>
+ state. Will scan and eliminate overlaps in both polygon sets. O(n
+ log n) runtime and O(n) memory wrt. vertices + intersections the first
+ time and linear runtime and constant memory subsequently. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -551,17 +599,22 @@
</td>
<td>Check whether the polygon set contains no geometry. Will scan
and eliminate overlaps because subtractive regions might make the
- polygon set empty.</td>
+ polygon set empty. O(n log n) runtime and O(n) memory wrt.
+ vertices + intersections the first time and linear runtime and constant
+ memory subsequently. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">bool <b>is_manhattan</b>()
const</font></td>
<td>Returns in constant time the information about whether the geometry
- contains only Manhattan (axis-parallel rectilinear) edges.</td>
+ contains only Manhattan (axis-parallel rectilinear) edges.
+ Constant time.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">void <b>clean</b>() const</font></td>
- <td>Scan and eliminate overlaps.</td>
+ <td>Scan and eliminate overlaps. O(n log n) runtime and O(n)
+ memory wrt. vertices + intersections the first time and linear runtime
+ and constant memory subsequently. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -577,7 +630,9 @@
bool <b>extents</b>(rectangle_type& extents_rectangle) const</font></td>
<td>Given an object that models rectangle, scans and eliminates overlaps
in the polygon set because subtractive regions may alter its extents
- then computes the bounding box and assigns it to extents_rectangle.</td>
+ then computes the bounding box and assigns it to extents_rectangle.
+ O(n log n) runtime and O(n) memory wrt. vertices the first time and
+ linear runtime and constant memory subsequently. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -589,7 +644,8 @@
negative. RoundingOption is an enum that controls snapping of
non-integer results of resizing 45 degree edges. CornerOption is
an enum that controls how corner filling is performed.
- polygon_45_set_data.hpp defines these enums.</td>
+ polygon_45_set_data.hpp defines these enums. O(n log n) runtime
+ and O(n) memory wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -597,54 +653,60 @@
polygon_45_set_data& <br><b>transform</b>(const transformation_type& transformation) </font>
</td>
<td>Applies transformation.transform() on vertices stored within the
- polygon set.</td>
+ polygon set. O(n log n) runtime and O(n) memory wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
polygon_45_set_data& <b>scale_up</b>(unsigned_area_type factor)</font></td>
- <td>Scales vertices stored within the polygon set up by factor.</td>
+ <td>Scales vertices stored within the polygon set up by factor.
+ Linear wrt vertices.</td>
</tr>
<tr>
<td width="586">
<font face="Courier New">polygon_45_set_data& <b>scale_down</b>(unsigned_area_type
factor)</font> </td>
- <td>Scales vertices stored within the polygon set down by factor.</td>
+ <td>Scales vertices stored within the polygon set down by factor.
+ Linear wrt vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">polygon_45_set_data& <b>scale</b>(double factor) </font></td>
<td>Scales vertices stored within the polygon set by floating point
- factor.</td>
+ factor. Linear wrt vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">polygon_45_set_data& <b>self_xor</b>()</font></td>
- <td>Retain only non-overlapping regions of geometry within polygon set.</td>
+ <td>Retain only non-overlapping regions of geometry within polygon set.
+ O(n log n) runtime and O(n) memory wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">polygon_45_set_data& <b>self_intersect</b>()</font></td>
- <td>Retain only overlapping regions of geometry within a polygon set.</td>
+ <td>Retain only overlapping regions of geometry within a polygon set.
+ O(n log n) runtime and O(n) memory wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">bool <b>has_error_data</b>()
const </font></td>
<td>Returns true if non-integer intersections resulted in small
- artifacts in the output of a boolean.</td>
+ artifacts in the output of a boolean. Constant time.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">std::size_t <b>error_count</b>()
const</font></td>
<td>Returns the number of artifacts that may potentially be present in
- the output due to non-integer intersections.</td>
+ the output due to non-integer intersections. Constant time.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">void <b>get_error_data</b>(polygon_45_set_data&
p) const</font></td>
<td>Populates the input polygon set with 1x1 unit squares that bound the
error that may be present in the output due to non-integer
- intersections.</td>
+ intersections. Linear wrt. vertices of error data.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">polygon_45_set_data& <b>self_intersect</b>()</font></td>
- <td>Retain only overlapping regions of geometry within a polygon set.</td>
+ <td>Retain only overlapping regions of geometry within a polygon set.
+ O(n log n) runtime and O(n) memory wrt. vertices + intersections.</td>
</tr>
</table>
<tr>
Modified: sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_45_with_holes_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
Modified: sandbox/gtl/doc/gtl_polygon_90_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_90_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_90_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
@@ -194,14 +194,14 @@
point, returns true
if the polygon contains the point. If the consider_touch
flag is true will return true if the point lies along the boundary of
- the polygon.</td>
+ the polygon. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">// get the center coordinate<br>
template <typename T, typename point_type><br>
void <b>center</b>(point_type& p, const T& polygon)</font></td>
<td>Sets object that models point to the center point of the bounding
- box of an object that models polygon_90.</td>
+ box of an object that models polygon_90. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T,
@@ -209,57 +209,59 @@
bool <b>extents</b>(rectangle_type& bbox, const T& polygon)</font></td>
<td>Sets object that models rectangle to the bounding box of an object
that models polygon_90 and returns true. Returns false and leaves
- bbox unchanged if polygon is empty.</td>
+ bbox unchanged if polygon is empty. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
manhattan_area_type <b>area</b>(const T& polygon)</font></td>
<td>Returns the area of an object
- that models polygon_90.</td>
+ that models polygon_90. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
direction_1d <b>winding</b>(const T& polygon)</font></td>
<td>Returns the winding direction of an object
- that models polygon_90, LOW == CLOCKWISE, HIGH = COUNTERCLOCKWISE.</td>
+ that models polygon_90, LOW == CLOCKWISE, HIGH = COUNTERCLOCKWISE.
+ Complexity depends upon winding trait.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
coordinate_difference <b>perimeter</b>(const T& polygon)</font></td>
<td>Returns the perimeter length of an object
- that models polygon_90.</td>
+ that models polygon_90. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T,
typename transform_type><br>
T& <b>transform</b>(T& polygon, const transform_type&)</font></td>
<td>Applies transform() on the vertices of polygon and sets the polygon to that described by the result of
- transforming its vertices.</td>
+ transforming its vertices. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>scale_up</b>(T& polygon, unsigned_area_type factor)</font></td>
<td>Scales up coordinate of an object that models
- polygon_90 by unsigned factor.</td>
+ polygon_90 by unsigned factor. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>scale_down</b>(T& polygon, unsigned_area_type factor)</font></td>
<td>Scales down coordinates of an object that models
- polygon_90 by unsigned factor.</td>
+ polygon_90 by unsigned factor. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, scaling_type><br>
T& <b>scale</b>(T& rectangle, double scaling) </font></td>
<td>Scales coordinates of an object that models polygon_90 by floating
- point factor.</td>
+ point factor. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>move</b>(T& polygon, orientation_2d,<br>
coordinate_difference displacement)</font></td>
<td>Adds displacement value to coordinate indicated by orientation_2d of
- vertices of an object that models polygon_90 .</td>
+ vertices of an object that models polygon_90 . Linear wrt.
+ vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename polygon_type, typename point_type><br>
@@ -267,7 +269,7 @@
const point_type& point)</font></td>
<td>Convolves coordinate values of point with vertices of an
- object that models polygon_90.</td>
+ object that models polygon_90. Linear wrt. vertices.</td>
</tr>
</table>
<h1>Polygon 90 Data</h1>
Modified: sandbox/gtl/doc/gtl_polygon_90_set_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_90_set_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_90_set_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
@@ -93,91 +93,107 @@
<td>Boolean OR operation (polygon set union). Accepts two objects
that model polygon_90_set or one of its refinements. Returns an
operator template that performs the operation on demand when chained or
- or nested in a library function call such as assign().</td>
+ or nested in a library function call such as assign(). O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_90_set_view <b>operator</b>+(const T1& l, const T2& r)</font></td>
<td>Same as operator|. The plus sign is also used for OR
- operations in Boolean logic expressions.</td>
+ operations in Boolean logic expressions. O( n log n) runtime
+ complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_90_set_view <b>operator</b>&(const T1& l, const T2& r)</font></td>
<td>Boolean AND operation (polygon set intersection). Accepts two
- objects that model polygon_90_set or one of its refinements.</td>
+ objects that model polygon_90_set or one of its refinements. O( n
+ log n) runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_90_set_view <b>operator</b>*(const T1& l, const T2& r)</font></td>
<td>Same as operator&. The multiplication symbol is also used for
- AND operations in Boolean logic expressions.</td>
+ AND operations in Boolean logic expressions. O( n log n) runtime
+ complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_90_set_view <b>operator</b>^(const T1& l, const T2& r)</font></td>
<td>Boolean XOR operation (polygon set disjoint-union). Accepts
- two objects that model polygon_90_set or one of its refinements.</td>
+ two objects that model polygon_90_set or one of its refinements.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections. O( n log n) runtime complexity and O(n) memory wrt
+ vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_90_set_view <b>operator</b>-(const T1& l, const T2& r)</font></td>
<td>Boolean SUBTRACT operation (polygon set difference). Accepts
- two objects that model polygon_90_set or one of its refinements.</td>
+ two objects that model polygon_90_set or one of its refinements.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>|=(const T1& l, const T2& r)</font></td>
<td>Same as operator|, but with self assignment, left operand must model
- polygon_90_set and not one of it's refinements.</td>
+ polygon_90_set and not one of it's refinements. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>+=(T1& l, const T2& r)</font></td>
<td>Same as operator+, but with self assignment, left operand must model
- polygon_90_set and not one of it's refinements.</td>
+ polygon_90_set and not one of it's refinements. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>&=(const T1& l, const T2& r)</font></td>
<td>Same as operator&, but with self assignment, left operand must model
- polygon_90_set and not one of it's refinements.</td>
+ polygon_90_set and not one of it's refinements. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>*=(T1& l, const T2& r)</font></td>
<td>Same as operator*, but with self assignment, left operand must model
- polygon_90_set and not one of it's refinements.</td>
+ polygon_90_set and not one of it's refinements. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>^=(const T1& l, const T2& r)</font></td>
<td>Same as operator^, but with self assignment, left operand must model
- polygon_90_set and not one of it's refinements.</td>
+ polygon_90_set and not one of it's refinements. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>-=(T1& l, const T2& r)</font></td>
<td>Same as operator-, but with self assignment, left operand must model
- polygon_90_set and not one of it's refinements.</td>
+ polygon_90_set and not one of it's refinements. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1><br>
T1 <b>operator</b>+(const T1&, coordinate_type bloating)</font></td>
<td>Performs resize operation, inflating by bloating ammount. If
negative the result is a shrink instead of bloat. Note: returns
- result by value.</td>
+ result by value. O( n log n) runtime complexity and O(n) memory
+ wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -185,7 +201,8 @@
T1 <b>operator</b>-(const T1&, coordinate_type shrinking)</font></td>
<td>Performs resize operation, deflating by bloating ammount. If
negative the result is a bloat instead of shrink. Note: returns
- result by value.</td>
+ result by value. O( n log n) runtime complexity and O(n) memory
+ wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -193,7 +210,8 @@
T1& <b>operator</b>+=(const T1&, coordinate_type bloating)</font></td>
<td>Performs resize operation, inflating by bloating ammount. If
negative the result is a shrink instead of bloat. Returns
- reference to modified argument.</td>
+ reference to modified argument. O( n log n) runtime complexity and
+ O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -201,7 +219,8 @@
T1& <b>operator</b>-=(const T1&, coordinate_type shrinking)</font></td>
<td>Performs resize operation, deflating by bloating ammount. If
negative the result is a bloat instead of shrink. Returns
- reference to modified argument.</td>
+ reference to modified argument. O( n log n) runtime complexity and
+ O(n) memory wrt vertices + intersections.</td>
</tr>
</table>
<h2>Functions</h2>
@@ -212,7 +231,8 @@
T1& <b>assign</b>(T1& lvalue, const T2& rvalue)</font></td>
<td>Eliminates overlaps in geometry and copies from an object that
models polygon_90_set or any of its refinements into an object that
- models polygon_90_set</td>
+ models polygon_90_set. O( n log n) runtime complexity and O(n)
+ memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -221,7 +241,8 @@
<td>Returns true if an object that models polygon_90_set or one of its
refinements covers the exact same geometric regions as another object
that models polygon_90_set or one of its refinements. For example:
- two of polygon_90 objects.</td>
+ two of polygon_90 objects. O( n log n) runtime complexity and O(n)
+ memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename
@@ -232,7 +253,8 @@
<td>Output container is expected to be a standard container.
Slices geometry of an object that models polygon_90_set or one of its
refinements into non overlapping rectangles and appends them to the
- output. </td>
+ output. O( n log n) runtime complexity and O(n) memory wrt
+ vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename
@@ -243,7 +265,7 @@
<td>Output container is expected to be a standard container. Given
an object that models polygon_90_set or one of its refinements finds all
overlapping rectangles that are maximal in area and appends them to the
- output. </td>
+ output. Expected n log n runtime, worst case quadratic rutnime.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename
@@ -256,7 +278,9 @@
polygon_set_type><br>
bool <b>empty</b>(const polygon_set_type& polygon_set)</font></td>
<td>Checks whether the object is empty of geometry. Polygons that
- are completely covered by holes will result in empty returning true.</td>
+ are completely covered by holes will result in empty returning true.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, typename
@@ -267,13 +291,15 @@
<td>Computes bounding box of an object that models polygon_90_set and
stores it in an object that models rectangle. If the polygon set
is empty returns false. If there are holes outside of shells they
- do not contribute to the extents of the polygon set.</td>
+ do not contribute to the extents of the polygon set. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
manhattan_area_type <b>area</b>(const T& polygon_set)</font></td>
<td>Computes the area covered by geometry in an object that models
- polygon_90_set</td>
+ polygon_90_set. O( n log n) runtime complexity and O(n) memory wrt
+ vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -281,33 +307,39 @@
T1& <b>interact</b>(T1& a, const T2& b)</font></td>
<td>Given an object that models polygon_90_set and an object that models
polygon_90_set or one of its refinements, modifies a to retain only
- regions that overlap or touch regions in b.</td>
+ regions that overlap or touch regions in b. O( n log n) runtime
+ complexity and O(n) memory wrt vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>self_intersect</b>(T& polygon_set)</font></td>
<td>Given an object that models polygon_90_set that has self overlapping
- regions, modifies the argument to contain only the regions of overlap.</td>
+ regions, modifies the argument to contain only the regions of overlap.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>self_xor</b>(T& polygon_set)</font></td>
<td>Given an object that models polygon_90_set that has self overlapping
regions, modifies the argument to contain only the regions that do not
- overlap.</td>
+ overlap. O( n log n) runtime complexity and O(n) memory wrt
+ vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>bloat</b>(T& polygon_set, unsigned_area_type bloating)</font></td>
<td>Same as getting all the rectangles, bloating them and putting them
- back.</td>
+ back. O( n log n) runtime complexity and O(n) memory wrt vertices
+ + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>bloat</b>(T& polygon_set, orientation_2d orient,<br>
unsigned_area_type bloating)</font></td>
<td>Same as getting all the rectangles, bloating them and putting them
- back.</td>
+ back. O( n log n) runtime complexity and O(n) memory wrt vertices
+ + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
@@ -316,14 +348,16 @@
unsigned_area_type
high_bloating)</font></td>
<td>Same as getting all the rectangles, bloating them and putting them
- back.</td>
+ back. O( n log n) runtime complexity and O(n) memory wrt vertices
+ + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>bloat</b>(T& polygon_set, direction_2d dir,<br>
unsigned_area_type bloating)</font></td>
<td>Same as getting all the rectangles, bloating them and putting them
- back.</td>
+ back. O( n log n) runtime complexity and O(n) memory wrt vertices
+ + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
@@ -337,13 +371,15 @@
unsigned_area_type
north_bloating)</font></td>
<td>Same as getting all the rectangles, bloating them and putting them
- back.</td>
+ back. O( n log n) runtime complexity and O(n) memory wrt vertices
+ + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>shrink</b>(T& polygon_set, unsigned_area_type shrinking)</font></td>
<td>Same as getting all the rectangles of the inverse, bloating them and overwriting
- the polygon set with the resulting regions then negating.</td>
+ the polygon set with the resulting regions then negating. O( n log
+ n) runtime complexity and O(n) memory wrt vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
@@ -351,7 +387,8 @@
unsigned_area_type
shrinking)</font></td>
<td>Same as getting all the rectangles of the inverse, bloating them and overwriting
- the polygon set with the resulting regions then negating.</td>
+ the polygon set with the resulting regions then negating. O( n log
+ n) runtime complexity and O(n) memory wrt vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
@@ -361,7 +398,8 @@
unsigned_area_type
high_shrinking)</font></td>
<td>Same as getting all the rectangles of the inverse, bloating them and overwriting
- the polygon set with the resulting regions then negating.</td>
+ the polygon set with the resulting regions then negating. O( n log
+ n) runtime complexity and O(n) memory wrt vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
@@ -369,7 +407,8 @@
unsigned_area_type
shrinking)</font></td>
<td>Same as getting all the rectangles of the inverse, bloating them and overwriting
- the polygon set with the resulting regions then negating.</td>
+ the polygon set with the resulting regions then negating. O( n log
+ n) runtime complexity and O(n) memory wrt vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
@@ -383,7 +422,8 @@
unsigned_area_type
north_shrinking)</font></td>
<td>Same as getting all the rectangles of the inverse, bloating them and overwriting
- the polygon set with the resulting regions then negating.</td>
+ the polygon set with the resulting regions then negating. O( n log
+ n) runtime complexity and O(n) memory wrt vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, typename
@@ -399,13 +439,16 @@
coord_type west, coord_type east,
<br> coord_type south, coord_type north)</font></td>
<td>Same as bloat if resizing is positive, same as shrink if resizing is
- negative.</td>
+ negative. O( n log n) runtime complexity and O(n) memory wrt
+ vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>grow_and</b>(T& polygon_set, unsigned_area_type bloating)</font></td>
<td>Same as bloating non-overlapping regions and then applying self
- intersect to retain only the overlaps introduced by the bloat.</td>
+ intersect to retain only the overlaps introduced by the bloat. O(
+ n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
@@ -413,7 +456,9 @@
unsigned_area_type bloating)</font></td>
<td>Same as bloating non-overlapping regions and then applying self
- intersect to retain only the overlaps introduced by the bloat.</td>
+ intersect to retain only the overlaps introduced by the bloat. O(
+ n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
@@ -423,7 +468,9 @@
unsigned_area_type high_bloating)</font></td>
<td>Same as bloating non-overlapping regions and then applying self
- intersect to retain only the overlaps introduced by the bloat.</td>
+ intersect to retain only the overlaps introduced by the bloat. O(
+ n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
@@ -431,7 +478,9 @@
unsigned_area_type bloating)</font></td>
<td>Same as bloating non-overlapping regions and then applying self
- intersect to retain only the overlaps introduced by the bloat.</td>
+ intersect to retain only the overlaps introduced by the bloat. O(
+ n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
@@ -445,44 +494,54 @@
unsigned_area_type north_bloating)</font></td>
<td>Same as bloating non-overlapping regions and then applying self
- intersect to retain only the overlaps introduced by the bloat.</td>
+ intersect to retain only the overlaps introduced by the bloat. O(
+ n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>scale_up</b>(T& polygon_set, unsigned_area_type factor)</font></td>
- <td>Scales geometry up by unsigned factor..</td>
+ <td>Scales geometry up by unsigned factor. O( n log n) runtime
+ complexity and O(n) memory wrt vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>scale_down</b>(T& polygon_set, unsigned_area_type factor)</font></td>
- <td>Scales geometry down by unsigned factor.</td>
+ <td>Scales geometry down by unsigned factor. O( n log n) runtime
+ complexity and O(n) memory wrt vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, typename scaling_type><br>
T& <b>scale</b>(polygon_set_type& polygon_set, <br>
const scaling_type& scaling)</font></td>
- <td>Scales geometry by applying scaling.scale() on all vertices.</td>
+ <td>Scales geometry by applying scaling.scale() on all vertices.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, typename coord_type><br>
T& <b>move</b>(T& polygon_set,<br>
orientation_2d orient, coord_type
displacement)</font></td>
- <td>Moves geometry by displacement amount in the orientation</td>
+ <td>Moves geometry by displacement amount in the orientation.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, typename coord_type><br>
T& <b>move</b>(T& polygon_set, coord_type x_displacement, <br>
coord_type y_displacement)</font></td>
<td>Moves the geometry by x_dispacement in x and y_displacement in y.
- Note: for consistency should be convolve(polygon_set, point)</td>
+ Note: for consistency should be convolve(polygon_set, point). O( n
+ log n) runtime complexity and O(n) memory wrt vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, typename transformation_type><br>
T& <b>transform</b>(T& polygon_set,<br>
const
transformation_type& transformation)</font></td>
- <td>Applies transformation.transform() on all vertices.</td>
+ <td>Applies transformation.transform() on all vertices. O( n log
+ n) runtime complexity and O(n) memory wrt vertices + intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
@@ -495,7 +554,8 @@
unsigned_area_type max_height)</font></td>
<td>Retains only regions that satisfy the min/max criteria in the
argument list. Note: useful for visualization to cull too small
- polygons.</td>
+ polygons. O( n log n) runtime complexity and O(n) memory wrt
+ vertices + intersections. </td>
</tr>
</table>
<h1>Polygon 90 Set Data Object</h1>
@@ -580,13 +640,14 @@
<font face="Courier New">
template <typename iT><br>
void <b>insert</b>(iT input_begin, iT input_end)</font></td>
- <td>Insert objects of an iterator range.</td>
+ <td>Insert objects of an iterator range. Linear wrt. inserted
+ vertices.</td>
</tr>
<tr>
<td width="586">
<font face="Courier New">
void <b>insert</b>(const polygon_90_set_data& polygon_set)</font></td>
- <td>Insert a polygon set.</td>
+ <td>Insert a polygon set. Linear wrt. inserted vertices.</td>
</tr>
<tr>
<td width="586">
@@ -595,7 +656,8 @@
void <b>insert</b>(const geometry_type& geometry_object, <br> bool is_hole
= false)</font></td>
<td>Insert a geometry object, if is_hole is true then the inserted
- region is subtractive rather than additive.</td>
+ region is subtractive rather than additive. Linear wrt. inserted
+ vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -607,7 +669,8 @@
output with counterclockwise winding, hole polygons will be output with
clockwise winding. The last vertex of an output polygon is not the
duplicate of the first, and the number of points is equal to the number
- of edges.</td>
+ of edges. O( n log n) runtime complexity and O(n) memory wrt
+ vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -617,7 +680,8 @@
eliminate overlaps. Converts polygon set geometry to polygons and
appends them to the container. Polygons will have holes fractured
out to the outer boundary along the positive direction of the scanline
- orientation of the polygon set.</td>
+ orientation of the polygon set. O( n log n) runtime complexity and
+ O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -625,7 +689,9 @@
void <b>get_rectangles</b>(output_container& output) const</font></td>
<td>Expects a standard container of rectangle objects. Will scan
and eliminate overlaps. Slices polygon set geometry to rectangles
- along the scanning orientation and appends them to the container.</td>
+ along the scanning orientation and appends them to the container.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586">
@@ -636,7 +702,9 @@
</td>
<td>Expects a standard container of rectangle objects. Will scan
and eliminate overlaps. Slices polygon set geometry to rectangles
- along the given orientation and appends them to the container.</td>
+ along the given orientation and appends them to the container. O(
+ n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586">
@@ -645,7 +713,9 @@
<td>Once scanned the data representation of geometry within a polygon
set is in a mathematically canonical form. Comparison between two
sets is therefore a linear time operation once they are in the scanned
- state. Will scan and eliminate overlaps in both polygon sets. </td>
+ state. Will scan and eliminate overlaps in both polygon sets. O( n
+ log n) runtime complexity and O(n) memory wrt vertices + intersections
+ the first time, linear subsequently.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -663,17 +733,20 @@
</td>
<td>Check whether the polygon set contains no geometry. Will scan
and eliminate overlaps because subtractive regions might make the
- polygon set empty.</td>
+ polygon set empty. O( n log n) runtime complexity and O(n) memory
+ wrt vertices + intersections the first time, linear subsequently.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">orientation_2d <b>orient</b>() const</font></td>
<td>Get the scanning orientation. Depending on the data it is
sometimes more efficient to scan in a specific orientation. This
- is particularly true of Manhattan geometry data.</td>
+ is particularly true of Manhattan geometry data. Constant time.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">void <b>clean</b>() const</font></td>
- <td>Scan and eliminate overlaps.</td>
+ <td>Scan and eliminate overlaps. O( n log n) runtime complexity
+ and O(n) memory wrt vertices + intersections the first time, constant
+ time subsequently.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -691,7 +764,9 @@
bool <b>extents</b>(rectangle_type& extents_rectangle) const</font></td>
<td>Given an object that models rectangle, scans and eliminates overlaps
in the polygon set because subtractive regions may alter its extents
- then computes the bounding box and assigns it to extents_rectangle.</td>
+ then computes the bounding box and assigns it to extents_rectangle.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections the first time, linear subsequently.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -706,7 +781,8 @@
<td>Scans to eliminate overlaps and subtractive regions. Inserts
rectangles of width specified by bloating values to the indicated side
of geometry within the polygon set and fills corners with rectangles of
- the length and width specified for the adjacent sides.</td>
+ the length and width specified for the adjacent sides. O( n log n)
+ runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -723,14 +799,16 @@
indicated side of geometry within the polygon set and subtractive
rectangle at convex corners of the length and width specified for the
adjacent sides. Scans to eliminate overlapping subtractive
- regions.</td>
+ regions. O( n log n) runtime complexity and O(n) memory wrt
+ vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
polygon_90_set_data&<br>
<b>resize</b>(coordinate_type west, coordinate_type east, <br> coordinate_type south, coordinate_type north)</font></td>
<td>Call bloat or shrink or shrink then bloat depending on whether the
- resizing values are positive or negative.</td>
+ resizing values are positive or negative. O( n log n) runtime
+ complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -738,7 +816,7 @@
y_delta) </font>
</td>
<td>Add x_delta to x values and y_delta to y values of vertices stored
- within the polygon set.</td>
+ within the polygon set. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -746,42 +824,51 @@
polygon_90_set_data& <br><b>transform</b>(const transformation_type& transformation) </font>
</td>
<td>Applies transformation.transform() on vertices stored within the
- polygon set.</td>
+ polygon set. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
polygon_90_set_data& <b>scale_up</b>(unsigned_area_type factor)</font></td>
- <td>Scales vertices stored within the polygon set up by factor.</td>
+ <td>Scales vertices stored within the polygon set up by factor.
+ Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586">
<p><font face="Courier New">polygon_90_set_data& <b>scale_down</b>(unsigned_area_type
factor)</font> </td>
- <td>Scales vertices stored within the polygon set down by factor.</td>
+ <td>Scales vertices stored within the polygon set down by factor.
+ Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
template <typename scaling_type><br>
polygon_90_set_data&<br> <b>scale</b>(const anisotropic_scale_factor<scaling_type>&
f)</font></td>
- <td>Scales vertices stored within the polygon set by applying f.scale().</td>
+ <td>Scales vertices stored within the polygon set by applying f.scale().
+ Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">polygon_90_set_data& <b>scale</b>(double factor) </font></td>
<td>Scales vertices stored within the polygon set by floating point
- factor.</td>
+ factor. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">polygon_90_set_data& <b>self_xor</b>()</font></td>
- <td>Retain only non-overlapping regions of geometry within polygon set.</td>
+ <td>Retain only non-overlapping regions of geometry within polygon set.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">polygon_90_set_data& <b>self_intersect</b>()</font></td>
- <td>Retain only overlapping regions of geometry within a polygon set.</td>
+ <td>Retain only overlapping regions of geometry within a polygon set.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">polygon_90_set_data&<br> <b>interact</b>(const polygon_90_set_data& that)</font></td>
- <td>Retain only regions that touch or overlap regions in argument.</td>
+ <td>Retain only regions that touch or overlap regions in argument.
+ O( n log n) runtime complexity and O(n) memory wrt vertices +
+ intersections.</td>
</tr>
</table>
<tr>
Modified: sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_90_with_holes_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
Modified: sandbox/gtl/doc/gtl_polygon_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
@@ -188,14 +188,14 @@
point, returns true
if the polygon contains the point. If the consider_touch
flag is true will return true if the point lies along the boundary of
- the polygon.</td>
+ the polygon. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">// get the center coordinate<br>
template <typename T, typename point_type><br>
void <b>center</b>(point_type& p, const T& polygon)</font></td>
<td>Sets object that models point to the center point of the bounding
- box of an object that models polygon.</td>
+ box of an object that models polygon. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T,
@@ -203,57 +203,58 @@
bool <b>extents</b>(rectangle_type& bbox, const T& polygon)</font></td>
<td>Sets object that models rectangle to the bounding box of an object
that models polygon and returns true. Returns false and leaves
- bbox unchanged if polygon is empty.</td>
+ bbox unchanged if polygon is empty. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
area_type <b>area</b>(const T& polygon)</font></td>
<td>Returns the area of an object
- that models polygon.</td>
+ that models polygon. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
direction_1d <b>winding</b>(const T& polygon)</font></td>
<td>Returns the winding direction of an object
- that models polygon, LOW == CLOCKWISE, HIGH = COUNTERCLOCKWISE.</td>
+ that models polygon, LOW == CLOCKWISE, HIGH = COUNTERCLOCKWISE.
+ Complexity depends upon winding trait.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
coordinate_distance <b>perimeter</b>(const T& polygon)</font></td>
<td>Returns the perimeter length of an object
- that models polygon.</td>
+ that models polygon. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T,
typename transform_type><br>
T& <b>transform</b>(T& polygon, const transform_type&)</font></td>
<td>Applies transform() on the vertices of polygon and sets the polygon to that described by the result of
- transforming its vertices.</td>
+ transforming its vertices. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>scale_up</b>(T& polygon, unsigned_area_type factor)</font></td>
<td>Scales up coordinate of an object that models
- polygon by unsigned factor.</td>
+ polygon by unsigned factor. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>scale_down</b>(T& polygon, unsigned_area_type factor)</font></td>
<td>Scales down coordinates of an object that models
- polygon by unsigned factor.</td>
+ polygon by unsigned factor. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, scaling_type><br>
T& <b>scale</b>(T& rectangle, double scaling) </font></td>
<td>Scales coordinates of an object that models polygon by floating
- point factor.</td>
+ point factor. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>move</b>(T& polygon, orientation_2d,<br>
coordinate_difference displacement)</font></td>
<td>Adds displacement value to coordinate indicated by orientation_2d of
- vertices of an object that models polygon .</td>
+ vertices of an object that models polygon . Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename polygon_type, typename point_type><br>
@@ -261,7 +262,7 @@
const point_type& point)</font></td>
<td>Convolves coordinate values of point with vertices of an
- object that models polygon.</td>
+ object that models polygon. Linear wrt. vertices.</td>
</tr>
</table>
<h1>Polygon Data</h1>
Modified: sandbox/gtl/doc/gtl_polygon_set_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_set_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_set_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
@@ -110,91 +110,108 @@
<td>Boolean OR operation (polygon set union). Accepts two objects
that model polygon_set or one of its refinements. Returns an
operator template that performs the operation on demand when chained or
- or nested in a library function call such as assign().</td>
+ or nested in a library function call such as assign(). Expected n
+ log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_set_view <b>operator</b>+(const T1& l, const T2& r)</font></td>
<td>Same as operator|. The plus sign is also used for OR
- operations in Boolean logic expressions.</td>
+ operations in Boolean logic expressions. Expected n log n runtime,
+ worst case quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_set_view <b>operator</b>&(const T1& l, const T2& r)</font></td>
<td>Boolean AND operation (polygon set intersection). Accepts two
- objects that model polygon_set or one of its refinements.</td>
+ objects that model polygon_set or one of its refinements. Expected
+ n log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_set_view <b>operator</b>*(const T1& l, const T2& r)</font></td>
<td>Same as operator&. The multiplication symbol is also used for
- AND operations in Boolean logic expressions.</td>
+ AND operations in Boolean logic expressions. Expected n log n
+ runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_set_view <b>operator</b>^(const T1& l, const T2& r)</font></td>
<td>Boolean XOR operation (polygon set disjoint-union). Accepts
- two objects that model polygon_set or one of its refinements.</td>
+ two objects that model polygon_set or one of its refinements.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
polygon_set_view <b>operator</b>-(const T1& l, const T2& r)</font></td>
<td>Boolean SUBTRACT operation (polygon set difference). Accepts
- two objects that model polygon_set or one of its refinements.</td>
+ two objects that model polygon_set or one of its refinements.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>|=(const T1& l, const T2& r)</font></td>
<td>Same as operator|, but with self assignment, left operand must model
- polygon_set and not one of it's refinements.</td>
+ polygon_set and not one of it's refinements. Expected n log n
+ runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>+=(T1& l, const T2& r)</font></td>
<td>Same as operator+, but with self assignment, left operand must model
- polygon_set and not one of it's refinements.</td>
+ polygon_set and not one of it's refinements. Expected n log n
+ runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>&=(const T1& l, const T2& r)</font></td>
<td>Same as operator&, but with self assignment, left operand must model
- polygon_set and not one of it's refinements.</td>
+ polygon_set and not one of it's refinements. Expected n log n
+ runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>*=(T1& l, const T2& r)</font></td>
<td>Same as operator*, but with self assignment, left operand must model
- polygon_set and not one of it's refinements.</td>
+ polygon_set and not one of it's refinements. Expected n log n
+ runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>^=(const T1& l, const T2& r)</font></td>
<td>Same as operator^, but with self assignment, left operand must model
- polygon_set and not one of it's refinements.</td>
+ polygon_set and not one of it's refinements. Expected n log n
+ runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
T2><br>
T1& <b>operator</b>-=(T1& l, const T2& r)</font></td>
<td>Same as operator-, but with self assignment, left operand must model
- polygon_set and not one of it's refinements.</td>
+ polygon_set and not one of it's refinements. Expected n log n
+ runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1><br>
T1 <b>operator</b>+(const T1&, coordinate_type bloating)</font></td>
<td>Performs resize operation, inflating by bloating ammount. If
negative the result is a shrink instead of bloat. Note: returns
- result by value.</td>
+ result by value. Expected n log n runtime, worst case quadratic
+ runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -202,7 +219,8 @@
T1 <b>operator</b>-(const T1&, coordinate_type shrinking)</font></td>
<td>Performs resize operation, deflating by bloating ammount. If
negative the result is a bloat instead of shrink. Note: returns
- result by value.</td>
+ result by value. Expected n log n runtime, worst case quadratic
+ runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -210,7 +228,8 @@
T1& <b>operator</b>+=(const T1&, coordinate_type bloating)</font></td>
<td>Performs resize operation, inflating by bloating ammount. If
negative the result is a shrink instead of bloat. Returns
- reference to modified argument.</td>
+ reference to modified argument. Expected n log n runtime, worst
+ case quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -218,7 +237,8 @@
T1& <b>operator</b>-=(const T1&, coordinate_type shrinking)</font></td>
<td>Performs resize operation, deflating by bloating ammount. If
negative the result is a bloat instead of shrink. Returns
- reference to modified argument.</td>
+ reference to modified argument. Expected n log n runtime, worst
+ case quadratic runtime wrt. vertices + intersections.</td>
</tr>
</table>
<h2>Functions</h2>
@@ -229,7 +249,8 @@
T1& <b>assign</b>(T1& lvalue, const T2& rvalue)</font></td>
<td>Eliminates overlaps in geometry and copies from an object that
models polygon_set or any of its refinements into an object that
- models polygon_set</td>
+ models polygon_set. Expected n log n runtime, worst case quadratic
+ runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T1, typename
@@ -238,7 +259,8 @@
<td>Returns true if an object that models polygon_set or one of its
refinements covers the exact same geometric regions as another object
that models polygon_set or one of its refinements. For example:
- two of polygon objects.</td>
+ two of polygon objects. Expected n log n runtime, worst case
+ quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename
@@ -250,7 +272,9 @@
Slices geometry of an object that models polygon_set or one of its
refinements into non overlapping trapezoids along a vertical slicing
orientation and appends them to the
- output, which must have a value type that models polygon or polygon_with_holes. </td>
+ output, which must have a value type that models polygon or polygon_with_holes.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename
@@ -262,7 +286,9 @@
Slices geometry of an object that models polygon_set or one of its
refinements into non overlapping trapezoids along a the specified slicing
orientation and appends them to the
- output, which must have a value type that models polygon or polygon_with_holes. </td>
+ output, which must have a value type that models polygon or polygon_with_holes.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename
@@ -275,7 +301,9 @@
polygon_set_type><br>
bool <b>empty</b>(const polygon_set_type& polygon_set)</font></td>
<td>Checks whether the object is empty of geometry. Polygons that
- are completely covered by holes will result in empty returning true.</td>
+ are completely covered by holes will result in empty returning true.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, typename
@@ -286,25 +314,30 @@
<td>Computes bounding box of an object that models polygon_set and
stores it in an object that models rectangle. If the polygon set
is empty returns false. If there are holes outside of shells they
- do not contribute to the extents of the polygon set.</td>
+ do not contribute to the extents of the polygon set. Expected n
+ log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
area_type <b>area</b>(const T& polygon_set)</font></td>
<td>Computes the area covered by geometry in an object that models
- polygon_set</td>
+ polygon_set. Expected n log n runtime, worst case quadratic
+ runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>bloat</b>(T& polygon_set, unsigned_area_type bloating)</font></td>
<td>Same as getting all the polygons, bloating them and putting them
- back.</td>
+ back. Expected n log n runtime, worst case quadratic runtime wrt.
+ vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>shrink</b>(T& polygon_set, unsigned_area_type shrinking)</font></td>
<td>Same as getting all the polygons, shrinking them and overwriting
- the polygon set with the resulting regions.</td>
+ the polygon set with the resulting regions. Expected n log n
+ runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, typename
@@ -318,24 +351,29 @@
by default, segmented circular arcs are inserted if corner_fill_arc is
true. num_circle_segments specifies number of segments to
introduce on a full circle when filling acute angle corners with
- circular arcs.</td>
+ circular arcs. Expected n log n runtime, worst case quadratic
+ runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>scale_up</b>(T& polygon_set, unsigned_area_type factor)</font></td>
- <td>Scales geometry up by unsigned factor..</td>
+ <td>Scales geometry up by unsigned factor. Expected n log n
+ runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
T& <b>scale_down</b>(T& polygon_set, unsigned_area_type factor)</font></td>
- <td>Scales geometry down by unsigned factor. </td>
+ <td>Scales geometry down by unsigned factor. Expected n log n
+ runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T, typename transformation_type><br>
T& <b>transform</b>(T& polygon_set,<br>
const
transformation_type& transformation)</font></td>
- <td>Applies transformation.transform() on all vertices.</td>
+ <td>Applies transformation.transform() on all vertices. Expected n
+ log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template <typename T><br>
@@ -348,7 +386,8 @@
unsigned_area_type max_height)</font></td>
<td>Retains only regions that satisfy the min/max criteria in the
argument list. Note: useful for visualization to cull too small
- polygons.</td>
+ polygons. Expected n log n runtime, worst case quadratic runtime
+ wrt. vertices + intersections.</td>
</tr>
</table>
<h1>Polygon Set Data Object</h1>
@@ -422,13 +461,14 @@
<font face="Courier New">
template <typename iT><br>
void <b>insert</b>(iT input_begin, iT input_end)</font></td>
- <td>Insert objects of an iterator range.</td>
+ <td>Insert objects of an iterator range. Linear wrt vertices
+ inserted.</td>
</tr>
<tr>
<td width="586">
<font face="Courier New">
void <b>insert</b>(const polygon_set_data& polygon_set)</font></td>
- <td>Insert a polygon set.</td>
+ <td>Insert a polygon set. Linear wrt vertices inserted.</td>
</tr>
<tr>
<td width="586">
@@ -437,7 +477,8 @@
void <b>insert</b>(const geometry_type& geometry_object, <br> bool is_hole
= false)</font></td>
<td>Insert a geometry object, if is_hole is true then the inserted
- region is subtractive rather than additive.</td>
+ region is subtractive rather than additive. Linear wrt vertices
+ inserted.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -452,7 +493,9 @@
to the number of edges plus 1. If required by the output data
type, polygons will have holes fractured out to the outer boundary along
the positive y direction and off grid intersections on the outer
- boundary introduced by this fracture will be truncated downward.</td>
+ boundary introduced by this fracture will be truncated downward.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -460,7 +503,8 @@
void <b>get_trapezoids</b>(output_container& output) const</font></td>
<td>Expects a standard container of polygon objects. Will scan
and eliminate overlaps. Slices polygon set geometry to trapezoids
- vertically and appends them to the container.</td>
+ vertically and appends them to the container. Expected n log n
+ runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586">
@@ -471,7 +515,9 @@
</td>
<td>Expects a standard container of polygon objects. Will scan
and eliminate overlaps. Slices polygon set geometry to trapezoids
- along the given orientation and appends them to the container.</td>
+ along the given orientation and appends them to the container.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586">
@@ -480,7 +526,9 @@
<td>Once scanned the data representation of geometry within a polygon
set is in a mathematically canonical form. Comparison between two
sets is therefore a linear time operation once they are in the scanned
- state. Will scan and eliminate overlaps in both polygon sets. </td>
+ state. Will scan and eliminate overlaps in both polygon sets.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections. </td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -498,11 +546,14 @@
</td>
<td>Check whether the polygon set contains no geometry. Will scan
and eliminate overlaps because subtractive regions might make the
- polygon set empty.</td>
+ polygon set empty. Expected n log n runtime, worst case quadratic
+ runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">void <b>clean</b>() const</font></td>
- <td>Scan and eliminate overlaps.</td>
+ <td>Scan and eliminate overlaps. Expected n log n runtime, worst
+ case quadratic runtime wrt. vertices + intersections the first time,
+ constant time subsequently.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -518,7 +569,9 @@
bool <b>extents</b>(rectangle_type& extents_rectangle) const</font></td>
<td>Given an object that models rectangle, scans and eliminates overlaps
in the polygon set because subtractive regions may alter its extents
- then computes the bounding box and assigns it to extents_rectangle.</td>
+ then computes the bounding box and assigns it to extents_rectangle.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections the first time, linear subsequently.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -532,7 +585,9 @@
true. num_circle_segments specifies number of segments to
introduce on a full circle when filling acute angle corners with
circular arcs. Specifying zero for num_circle_segments results in
- only a single segment being inserted at acute corners.</td>
+ only a single segment being inserted at acute corners. Expected n
+ log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
@@ -540,25 +595,32 @@
polygon_set_data& <br><b>transform</b>(const transformation_type& transformation) </font>
</td>
<td>Applies transformation.transform() on vertices stored within the
- polygon set.</td>
+ polygon set. Expected n log n runtime, worst case quadratic
+ runtime wrt. vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
polygon_set_data& <b>scale_up</b>(unsigned_area_type factor)</font></td>
- <td>Scales vertices stored within the polygon set up by factor.</td>
+ <td>Scales vertices stored within the polygon set up by factor.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586">
<font face="Courier New">polygon_set_data& <b>scale_down</b>(unsigned_area_type
factor)</font> </td>
- <td>Scales vertices stored within the polygon set down by factor.</td>
+ <td>Scales vertices stored within the polygon set down by factor.
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
template <typename scaling_type><br>
polygon_set_data&<br> <b>scale</b>(const scaling_type&
f)</font></td>
- <td>Scales vertices stored within the polygon set by applying f.scale().</td>
+ <td>Scales vertices stored within the polygon set by applying f.scale().
+ Expected n log n runtime, worst case quadratic runtime wrt. vertices +
+ intersections.</td>
</tr>
</table>
<tr>
Modified: sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm (original)
+++ sandbox/gtl/doc/gtl_polygon_with_holes_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
Modified: sandbox/gtl/doc/gtl_property_merge.htm
==============================================================================
--- sandbox/gtl/doc/gtl_property_merge.htm (original)
+++ sandbox/gtl/doc/gtl_property_merge.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
@@ -93,7 +93,7 @@
const property_type& property)</font></td>
<td>I<font face="Times New Roman">nsert a polygon set with an associated
- property.</font></td>
+ property.</font> Linear wrt vertices inserted.</td>
</tr>
<tr>
<td width="586">
@@ -103,7 +103,7 @@
const property_type& property)</font></td>
<td>Insert a geometry object that is a refinement of polygon set with an
- associated property.</td>
+ associated property. Linear wrt vertices inserted.</td>
</tr>
<tr>
<td width="586">
@@ -112,7 +112,8 @@
void <b>merge</b>(result_type& result)</font></td>
<td>Accepts a container object that conforms to the expectations defined
above. Performs property merge and populates the container
- object.</td>
+ object. Expected n log n runtime, worst case quadratic runtime wrt.
+ vertices + intersections.</td>
</tr>
</table>
<tr>
Modified: sandbox/gtl/doc/gtl_property_merge_45.htm
==============================================================================
--- sandbox/gtl/doc/gtl_property_merge_45.htm (original)
+++ sandbox/gtl/doc/gtl_property_merge_45.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
@@ -93,7 +93,7 @@
const property_type& property)</font></td>
<td>I<font face="Times New Roman">nsert a polygon set with an associated
- property.</font></td>
+ property.</font> Linear wrt vertices inserted.</td>
</tr>
<tr>
<td width="586">
@@ -103,7 +103,7 @@
const property_type& property)</font></td>
<td>Insert a geometry object that is a refinement of polygon 45 set with
- an associated property.</td>
+ an associated property. Linear wrt vertices inserted.</td>
</tr>
<tr>
<td width="586">
@@ -112,7 +112,7 @@
void <b>merge</b>(result_type& result)</font></td>
<td>Accepts a container object that conforms to the expectations defined
above. Performs property merge and populates the container
- object.</td>
+ object. O(n log n) runtime wrt. vertices + intersections.</td>
</tr>
</table>
<tr>
Modified: sandbox/gtl/doc/gtl_property_merge_90.htm
==============================================================================
--- sandbox/gtl/doc/gtl_property_merge_90.htm (original)
+++ sandbox/gtl/doc/gtl_property_merge_90.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
@@ -93,7 +93,7 @@
const property_type& property)</font></td>
<td>I<font face="Times New Roman">nsert a polygon set with an associated
- property.</font></td>
+ property.</font> Linear wrt vertices inserted.</td>
</tr>
<tr>
<td width="586">
@@ -103,7 +103,7 @@
const property_type& property)</font></td>
<td>Insert a geometry object that is a refinement of polygon 90 set with
- an associated property.</td>
+ an associated property. Linear wrt vertices inserted.</td>
</tr>
<tr>
<td width="586">
@@ -112,7 +112,7 @@
void <b>merge</b>(result_type& result)</font></td>
<td>Accepts a container object that conforms to the expectations defined
above. Performs property merge and populates the container
- object.</td>
+ object. O(n log n) runtime wrt. vertices + intersections.</td>
</tr>
</table>
<tr>
Modified: sandbox/gtl/doc/gtl_rectangle_concept.htm
==============================================================================
--- sandbox/gtl/doc/gtl_rectangle_concept.htm (original)
+++ sandbox/gtl/doc/gtl_rectangle_concept.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -44,6 +43,7 @@
<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>
Modified: sandbox/gtl/doc/index.htm
==============================================================================
--- sandbox/gtl/doc/index.htm (original)
+++ sandbox/gtl/doc/index.htm 2010-04-07 17:04:43 EDT (Wed, 07 Apr 2010)
@@ -15,9 +15,8 @@
<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>Boost.Polygon Main Page</li>
+ <li>Design Overview</li>
<li>Isotropy</li>
<li>Coordinate Concept</li>
<li>Interval Concept</li>
@@ -45,6 +44,7 @@
<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>
@@ -59,8 +59,8 @@
<br>
<p>
-</p><h1>THE BOOST POLYGON LIBRARY</h1>
-<p>The boost polygon library provides algorithms focused on manipulating planar
+</p><h1>THE BOOST.POLYGON LIBRARY</h1>
+<p>The Boost.Polygon library provides algorithms focused on manipulating planar
polygon geometry data. Specific algorithms provided are the polygon set
operations (intersection, union, difference, disjoint-union) and related
algorithms such as polygon connectivity graph extraction, offsetting and map-overlay.
@@ -69,23 +69,31 @@
These so-called Boolean algorithms are of significant interest in GIS (Geospatial Information
Systems), VLSI CAD as well al other fields of CAD, and many more application
areas, and providing them is the primary focus of this library. The
-polygon library is not intended to cover all of computational geometry in its
-scope, and provides a set of capabilities for working with coordinates, points,
-intervals and rectangles that are needed to support implementing and interacting
-with polygon data structures and algorithms. Specifically, 3d and
-non-Cartesian/non-planar geometry is outside of the scope of the polygon
-library.</p><img border="0" src="images/hand.png" width="837" height="277"><p>
+Boost.Polygon library is not intended to cover all of computational
+geometry in its scope, and provides a set of capabilities for working with
+coordinates, points, intervals and rectangles that are needed to support
+implementing and interacting with polygon data structures and algorithms. </p><img border="0" src="images/hand.png" width="837" height="277"><p>
+The coordinate data type is a template parameter of all data types and
+algorithms provided by the library, and is expected to be integral.
+Floating point coordinate data types are not supported by the algorithms
+implemented in the library due to the fact that the achieving floating point
+robustness implies a different set of algorithms and generally platform specific
+assumptions about floating point representations.
For additional detailed discussion of the library and its implementation
including benchmark comparisons with other open source alternatives please see
the paper and
<a href="GTL_boostcon_draft03.htm">presentation</a> from
-boostcon 2009. </p>
+boostcon 2009 as well as a detailed
+analysis of the runtime complexity of
+the library's core algorithms. </p>
<p>The design philosophy behind the polygon library was to create an API for
invoking the library algorithms it provides on user geometry data types that is maximally
intuitive, minimally error-prone and easy to integrate into pre-existing
applications. C++-concepts based template meta-programming combined with
generic operator overloading meets these design goals without sacrificing the
-runtime or memory efficiency of the underlying algorithms. This API makes
+runtime or memory efficiency of the underlying algorithms. The API is
+intended to demonstrate what could be achieved with ease by a C++-concepts based
+library interface, but is implemented based on current language features. This API makes
the following code snippet that operates on non-library geometry types possible:</p>
<p:colorscheme
colors="#ffffff,#000000,#808080,#000000,#bbe0e3,#333399,#009999,#99cc00"/>
@@ -132,7 +140,7 @@
it, and the description is not much clearer than the code itself.
Functions are named for what they do, or are overloads of C++ operators that make it
easy to infer from reading the code what to expect from it. Operators are
-contained in the namespace <font face="Courier New">boost::polgyon::operators</font>
+contained in the namespace <font face="Courier New">boost::polygon::operators</font>
so that they can be used outside the <font face="Courier New">boost::polygon</font>
namespace without bringing in the entire <font face="Courier New">boost::polygon</font>
namespace. Following the
@@ -176,6 +184,17 @@
</ul>
+<p>We would like to thank: Thomas Klimpel, Frank Mori Hess, Barend Gehrels,
+Andreas Fabri, Jeffrey Hellrung, Tim Keitt, Markus Werle, Paul A. Bristow,
+Robert Stewart, Mathias Gaunard, Michael Fawcett, Steven Watanabe, Joachim
+Faulhaber, John Bytheway, Sebastian Redl, Mika Heiskanen, John Phillips, Kai
+Benndorf, Hartmut Kaiser, Arash Partow, Maurizio Vitale, Brandon Kohn, David
+Abrahams, Gordon Woodhull, Daniel James, John Maddock, Tom Brinkman, Bo Persson,
+Mateusz Loskot, Christian Henning, Jean-Sebastien Stoezel, for providing
+feedback and or formal review of the library as part of the boost submission
+process and Fernando Cacciola for graciously serving as review manager.</p>
+
+
<table class="docinfo" rules="none" frame="void" id="table1">
<colgroup>
<col class="docinfo-name"><col class="docinfo-content">
@@ -183,7 +202,7 @@
<tbody vAlign="top">
<tr>
<th class="docinfo-name">Copyright:</th>
- <td>Copyright © Intel Corporation 2008-2009.</td>
+ <td>Copyright © Intel Corporation 2008-2010.</td>
</tr>
<tr class="field">
<th class="docinfo-name">License:</th>
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk