<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:(null)1="http://www.w3.org/TR/REC-html40" lang="en"><head><!--
Copyright 2009-2010 Intel Corporation
license banner
--><title>Boost Polygon Library: Polygon 90 Set Concept</title>
<meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" /><!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> --></head><body>
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
<tbody>
<tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
<div style="padding: 5px;" align="center"> <img src="images/boost.png" border="0" height="86" width="277" /><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;"> </a> </div>
<div style="margin: 5px;">
<h3 class="navbar">Contents</h3>
<ul>
<li><a href="index.htm">Boost.Polygon Main Page</a></li>
<li><a href="gtl_design_overview.htm">Design Overview</a></li>
<li><a href="gtl_isotropy.htm">Isotropy</a></li>
<li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
<li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
<li><a href="gtl_point_concept.htm">Point Concept</a></li>
<li><a href="gtl_segment_concept.htm">Segment Concept</a></li>
<li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
<li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
<li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
With Holes Concept</a></li>
<li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
<li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
With Holes Concept</a></li>
<li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
<li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
Holes Concept</a></li>
<li>Polygon 90 Set Concept</li>
<li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
Concept</a></li>
<li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
<li><a href="gtl_connectivity_extraction_90.htm">Connectivity
Extraction 90</a></li>
<li><a href="gtl_connectivity_extraction_45.htm">Connectivity
Extraction 45</a></li>
<li><a href="gtl_connectivity_extraction.htm">Connectivity
Extraction</a></li>
<li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
<li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
<li><a href="gtl_property_merge.htm">Property Merge</a></li>
<li><a href="voronoi_main.htm">Voronoi Main Page<br />
</a></li>
<li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br />
</li>
<li><a href="voronoi_builder.htm">Voronoi Builder</a></li>
<li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
</ul>
<h3 class="navbar">Other Resources</h3>
<ul>
<li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
<li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
Presentation</a></li>
<li><a href="analysis.htm">Performance Analysis</a></li>
<li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
<li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
<li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
<li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
Tutorial</a></li>
</ul>
</div>
<h3 class="navbar">Polygon Sponsor</h3>
<div style="padding: 5px;" align="center"> <img src="images/intlogo.gif" border="0" height="51" width="127" /><a title="www.adobe.com home page" href="http://www.adobe.com/" tabindex="2" style="border: medium none ;"> </a> </div>
</td>
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
<!-- End Header --><br />
<p>
</p>
<h1>Polygon 90 Set Concept</h1>
<p> </p>
<p>The polygon_90_set concept tag is <font face="Courier New">
polygon_90_set_concept</font></p>
<p> <font face="Times New Roman">The semantic of a
polygon_90_set is zero or more Manhattan geometry regions.</font></p>
<p> <font face="Times New Roman">The motivation for providing
the polygon_90_set_concept is that it is a very common special case of
planar geometry which afford the implementation of a variety of
optimizations on the general planar geometry algorithms.
Manhattan geometry processing by the polygon_90_set_concept can be 100X
faster than arbitrary angle polygon manipulation. Because the
performance benefits are so large and the special case is important
enough, the library provides these performance benefits for those
application domains that require them.</font></p>
<p>Users are recommended to use std::vector and std::list of user
defined polygons or library provided
polygon_90_set_data<coordinate_type> objects. Lists and
vectors of models of polygon_90_concept or
polygon_90_with_holes_concept or rectangle_concept are automatically
models of polygon_90_set_concept.</p>
<h2>Operators</h2>
<p>The return type of some operators is the <font face="Courier New">polygon_90_set_view</font> operator template
type. This type is itself a model of the polygon_90_set concept,
but furthermore can be used as an argument to the <font face="Courier New">polygon_90_set_data</font> constructor and
assignment operator. The operator template exists to eliminate
temp copies of intermediate results when Boolean operators are chained
together.</p>
<p>Operators are declared inside the namespace <font face="Courier New">boost::polygon::operators</font>.</p>
<table id="table3" border="1" width="100%">
<tbody>
<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 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().
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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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. 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&, 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. 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&, 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. 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&, 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. O( n log n)
runtime complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
</tbody>
</table>
<h2>Functions</h2>
<table id="table1" border="1" width="100%">
<tbody>
<tr>
<td width="586"><font face="Courier New">template
<typename T1, typename T2><br />
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. 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 />
bool <b>equivalence</b>(const T1& lvalue, const T2& rvalue) </font></td>
<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. 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 output_container_type, typename T><br />
void <b>get_rectangles</b>(output_container_type& output, <br />
const T& polygon_set)</font></td>
<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. 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 output_container_type, typename T><br />
void <b>get_max_rectangles</b>(output_container_type& output, <br />
const T& polygon_set)</font></td>
<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. Expected n log n runtime,
worst case quadratic rutnime.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template
<typename polygon_set_type><br />
void <b>clear</b>(polygon_set_type& polygon_set)</font></td>
<td>Makes the object empty of geometry.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template
<typename 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. 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 rectangle_type><br />
bool <b>extents</b>(rectangle_type& extents_rectangle, <br />
const T& polygon_set)</font></td>
<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. 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. 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>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. 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. 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. 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. 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. 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
low_bloating,<br />
unsigned_area_type
high_bloating)</font></td>
<td>Same as getting all the rectangles, bloating them and
putting them 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. 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, <br />
unsigned_area_type
west_bloating,<br />
unsigned_area_type
east_bloating,<br />
unsigned_area_type
south_bloating,<br />
unsigned_area_type
north_bloating)</font></td>
<td>Same as getting all the rectangles, bloating them and
putting them 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. 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, orientation_2d orient,<br />
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. 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, orientation_2d orient,<br />
unsigned_area_type low_shrinking,<br />
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. 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, direction_2d dir,<br />
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. 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, <br />
unsigned_area_type west_shrinking,<br />
unsigned_area_type east_shrinking,<br />
unsigned_area_type south_shrinking,<br />
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. 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>resize</b>(T& polygon_set, coord_type resizing)</font></td>
<td>Same as bloat if resizing is positive, same as shrink
if resizing is negative.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template
<typename T, typename coord_type><br />
T& <b>resize</b>(polygon_set_type& polygon_set, <br />
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. 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. 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, orientation_2d orient,<br />
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. 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, orientation_2d orient,<br />
unsigned_area_type low_bloating,<br />
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. 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, direction_2d dir,<br />
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. 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, <br />
unsigned_area_type west_bloating,<br />
unsigned_area_type east_bloating,<br />
unsigned_area_type south_bloating,<br />
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. 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. 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. 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. 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. 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). 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. 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>keep</b>(T& polygon_set, <br />
unsigned_area_type min_area,<br />
unsigned_area_type max_area,<br />
unsigned_area_type min_width,<br />
unsigned_area_type max_width,<br />
unsigned_area_type
min_height,<br />
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. O( n log n) runtime complexity and O(n) memory
wrt vertices + intersections. </td>
</tr>
</tbody>
</table>
<h1>Polygon 90 Set Data Object</h1>
<p> </p>
<p>The polygon 90 set data type encapsulates the internal data
format that serves as the input to the sweep-line algorithm that
implements polygon-clipping boolean operations. It also
internally keeps track of whether that data has been sorted or scanned
and maintains the invariant that when its flags indicate that the data
is sorted or scanned the data has not been changed to violate that
assumption. Using the Polygon 90 Set Data type directly can be
more efficient than using lists and vectors of polygons in the
functions above because of the invariants it can enforce which provide
the opportunity to maintain the data is sorted form rather than going
all the way out to polygons then resorting those vertices for a
subsequent operation.</p>
<p>The declaration of Polygon 90 Set Data is the following:</p>
<p><font face="Courier New">template <typename T><br />
class polygon_90_set_data;</font></p>
<p>The class is parameterized on the coordinate data type.
Algorithms that benefit from knowledge of the invariants enforced by
the class are implemented as member functions to provide them access to
information about those invariants. </p>
<h2>Member Functions</h2>
<table id="table2" border="1" width="100%">
<tbody>
<tr>
<td width="586"><font face="Courier New"><b>polygon_90_set_data</b>()</font></td>
<td>Default constructor. Scanning orientation
defaults to HORIZONTAL</td>
</tr>
<tr>
<td width="586"><font face="Courier New"><b>polygon_90_set_data</b>(orientation_2d
orient)</font></td>
<td>Construct with scanning orientation.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template
<typename iT><br />
<b>polygon_90_set_data</b>(orientation_2d orient, <br />
iT input_begin, iT input_end)</font></td>
<td>Construct with scanning orientation from an iterator
range of insertable objects.</td>
</tr>
<tr>
<td width="586"><font face="Courier New"> <b>polygon_90_set_data</b>(const
polygon_90_set_data& that)</font></td>
<td>Copy construct.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template
<typename l, typename r, typename op><br />
<b>polygon_90_set_data</b>(const
polygon_90_set_view<l,r,op>& t)</font></td>
<td>Copy construct from a Boolean operator template.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
<b>polygon_90_set_data</b>(orientation_2d orient, <br />
const polygon_90_set_data& that)</font></td>
<td>Construct with scanning orientation and copy from
another polygon set.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">polygon_90_set_data&
<br />
<b>operator=</b>(const polygon_90_set_data& that)</font></td>
<td>Assignment from another polygon set, may change
scanning orientation.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template
<typename l, typename r, typename op><br />
polygon_90_set_data& <br />
<b>operator=</b>(const polygon_90_set_view<l, r,
op>& that)</font></td>
<td>Assignment from a Boolean operator template.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template
<typename geometry_object><br />
polygon_90_set_data& <b>operator=</b>(const geometry_object&
geo)</font></td>
<td>Assignment from an insertable object.</td>
</tr>
<tr>
<td width="586"><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. 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. Linear wrt. inserted
vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
template <typename geometry_type><br />
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. Linear wrt.
inserted vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template
<typename output_container><br />
void <b>get</b>(output_container& output) const</font></td>
<td>Expects a standard container of geometry objects.
Will scan 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 not the duplicate of the first, and the number of
points is equal to the number of edges. O( n log n) runtime
complexity and O(n) memory wrt vertices + intersections.</td>
</tr>
<tr>
<td style="vertical-align: top;"><font face="Courier New">template
<typename output_container><br />
void <b>get</b>(output_container& output, size_t k) const</font></td>
<td style="vertical-align: top;">Expects a standard
container of geometry objects. Will scan and eliminate
overlaps. Converts polygon set geometry to objects of that type
and appends them to the container. The resulting polygons will
have at most k vertices. For Manhattan data k should be at least 4 .
Polygons will be 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. O( n log n) runtime
complexity and O(n) memory wrt vertices + intersections.<br />
</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template
<typename output_container><br />
void <b>get_polygons</b>(output_container& output) const</font></td>
<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 direction
of the scanline 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">template
<typename output_container><br />
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. 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 output_container><br />
void <b>get_rectangles</b>(output_container& output, <br />
orientation_2d slicing_orientation) const </font> </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. O( n log n) runtime complexity and O(n) memory
wrt vertices + intersections.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">
bool <b>operator==</b>(const polygon_90_set_data& p) const</font></td>
<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. 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">bool <b>operator!=</b>(const
polygon_90_set_data& p) const</font></td>
<td>Inverse logic of equivalence operator.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">void <b>clear</b>()</font></td>
<td>Make the polygon set empty. Note: does not
de-allocate memory. Use shrink to fit idiom and assign default
constructed polygon set to de-allocate.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">bool <b>empty</b>()
const </font> </td>
<td>Check whether the polygon set contains no
geometry. Will scan and eliminate overlaps because subtractive
regions might make the 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. Constant time.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">void <b>clean</b>()
const</font></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">template
<typename input_iterator_type><br />
void <b>set</b>(input_iterator_type input_begin, <br />
input_iterator_type
input_end, <br />
orientation_2d orient)
</font> </td>
<td>Overwrite geometry in polygon set with insertable
objects in the iterator range. Also sets the scanning orientation
to that specified.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template
<typename rectangle_type><br />
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. 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">polygon_90_set_data&<br />
<b>bloat</b>(unsigned_area_type west_bloating,<br />
unsigned_area_type east_bloating,<br />
unsigned_area_type south_bloating,<br />
unsigned_area_type north_bloating) </font></td>
<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. 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>shrink</b>(unsigned_area_type west_shrinking,<br />
unsigned_area_type east_shrinking,<br />
unsigned_area_type south_shrinking,<br />
unsigned_area_type north_shrinking)</font></td>
<td>Scans to eliminate overlaps and subtractive
regions. Inserts subtractiive rectangles of width specified by
bloating values to the 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. 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. 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>move</b>(coordinate_type x_delta, <br />
coordinate_type y_delta) </font> </td>
<td>Add x_delta to x values and y_delta to y values of
vertices stored within the polygon set. Linear wrt. vertices.</td>
</tr>
<tr>
<td width="586"><font face="Courier New">template
<typename transformation_type><br />
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. 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. 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> </p>
</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(). 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. 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. 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. 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. O( n log n) runtime complexity and O(n) memory wrt
vertices + intersections.</td>
</tr>
</tbody>
</table>
</td>
</tr>
<tr>
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> </td>
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
<table class="docinfo" id="table4" frame="void" rules="none">
<colgroup> <col class="docinfo-name" /><col class="docinfo-content" /> </colgroup> <tbody valign="top">
<tr>
<th class="docinfo-name">Copyright:</th>
<td>Copyright � Intel Corporation 2008-2010.</td>
</tr>
<tr class="field">
<th class="docinfo-name">License:</th>
<td class="field-body">Distributed under the Boost Software
License, Version 1.0. (See accompanying file <tt class="literal"> <span class="pre">LICENSE_1_0.txt</span></tt> or copy at <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
http://www.boost.org/LICENSE_1_0.txt</a>)</td>
</tr>
</tbody>
</table>
</td>
</tr>
</tbody>
</table>
</body></html>