libs/polygon/doc/gtl_polygon_90_set_concept.htm

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   2 <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><!--
   3     Copyright 2009-2010 Intel Corporation
   4     license banner
   5 --><title>Boost Polygon Library: Polygon 90 Set Concept</title>
   6
   7
   8
   9
  10   <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" /><!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> --></head><body>
  11 <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0">
  12   <tbody>
  13     <tr>
  14       <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
  15       <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>
  16       <div style="margin: 5px;">
  17       <h3 class="navbar">Contents</h3>
  18       <ul>
  19         <li><a href="index.htm">Boost.Polygon Main Page</a></li>
  20         <li><a href="gtl_design_overview.htm">Design Overview</a></li>
  21         <li><a href="gtl_isotropy.htm">Isotropy</a></li>
  22         <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
  23         <li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
  24         <li><a href="gtl_point_concept.htm">Point Concept</a></li>
  25         <li><a href="gtl_segment_concept.htm">Segment Concept</a></li>
  26         <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
  27         <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
  28         <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
  29 With Holes Concept</a></li>
  30         <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
  31         <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
  32 With Holes Concept</a></li>
  33         <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
  34         <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
  35 Holes Concept</a></li>
  36         <li>Polygon 90 Set Concept</li>
  37         <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
  38 Concept</a></li>
  39         <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
  40         <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
  41 Extraction 90</a></li>
  42         <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
  43 Extraction 45</a></li>
  44         <li><a href="gtl_connectivity_extraction.htm">Connectivity
  45 Extraction</a></li>
  46         <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
  47         <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
  48         <li><a href="gtl_property_merge.htm">Property Merge</a></li>
  49         <li><a href="voronoi_main.htm">Voronoi Main Page<br />
  50           </a></li>
  51         <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br />
  52         </li>
  53         <li><a href="voronoi_builder.htm">Voronoi Builder</a></li>
  54         <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
  55       </ul>
  56       <h3 class="navbar">Other Resources</h3>
  57       <ul>
  58         <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
  59         <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
  60 Presentation</a></li>
  61         <li><a href="analysis.htm">Performance Analysis</a></li>
  62         <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
  63         <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
  64         <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
  65         <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
  66 Tutorial</a></li>
  67       </ul>
  68       </div>
  69       <h3 class="navbar">Polygon Sponsor</h3>
  70       <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>
  71       </td>
  72       <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
  73 <!-- End Header --><br />
  74       <p>
  75       </p>
  76       <h1>Polygon 90 Set Concept</h1>
  77       <p> </p>
  78       <p>The polygon_90_set concept tag is <font face="Courier New">
  79 polygon_90_set_concept</font></p>
  80       <p> <font face="Times New Roman">The semantic of a
  81 polygon_90_set is zero or more Manhattan geometry regions.</font></p>
  82       <p> <font face="Times New Roman">The motivation for providing
  83 the polygon_90_set_concept is that it is a very common special case of
  84 planar geometry which afford the implementation of a variety of
  85 optimizations on the general planar geometry algorithms.&nbsp;
  86 Manhattan geometry processing by the polygon_90_set_concept can be 100X
  87 faster than arbitrary angle polygon manipulation.&nbsp; Because the
  88 performance benefits are so large and the special case is important
  89 enough, the library provides these performance benefits for those
  90 application domains that require them.</font></p>
  91       <p>Users are recommended to use std::vector and std::list of user
  92 defined polygons or library provided
  93 polygon_90_set_data&lt;coordinate_type&gt; objects.&nbsp; Lists and
  94 vectors of models of polygon_90_concept or
  95 polygon_90_with_holes_concept or rectangle_concept are automatically
  96 models of polygon_90_set_concept.</p>
  97       <h2>Operators</h2>
  98       <p>The return type of some operators is the <font face="Courier New">polygon_90_set_view</font> operator template
  99 type.&nbsp; This type is itself a model of the polygon_90_set concept,
 100 but furthermore can be used as an argument to the <font face="Courier New">polygon_90_set_data</font> constructor and
 101 assignment operator.&nbsp; The operator template exists to eliminate
 102 temp copies of intermediate results when Boolean operators are chained
 103 together.</p>
 104       <p>Operators are declared inside the namespace <font face="Courier New">boost::polygon::operators</font>.</p>
 105       <table id="table3" border="1" width="100%">
 106         <tbody>
 107           <tr>
 108             <td width="586"><font face="Courier New">template
 109 &lt;typename T1, typename T2&gt;<br />
 110 polygon_90_set_view <b>operator</b>|(const T1&amp; l, const T2&amp; r)</font></td>
 111             <td>Boolean OR operation (polygon set union).&nbsp; Accepts
 112 two objects that model polygon_90_set or one of its refinements.&nbsp;
 113 Returns an operator template that performs the operation on demand when
 114 chained or or nested in a library function call such as assign().&nbsp;
 115 O( n log n) runtime complexity and O(n) memory wrt vertices +
 116 intersections.</td>
 117           </tr>
 118           <tr>
 119             <td width="586"><font face="Courier New">template
 120 &lt;typename T1, typename T2&gt;<br />
 121 polygon_90_set_view <b>operator</b>+(const T1&amp; l, const T2&amp; r)</font></td>
 122             <td>Same as operator|.&nbsp; The plus sign is also used for
 123 OR operations in Boolean logic expressions.&nbsp; O( n log n) runtime
 124 complexity and O(n) memory wrt vertices + intersections.</td>
 125           </tr>
 126           <tr>
 127             <td width="586"><font face="Courier New">template
 128 &lt;typename T1, typename T2&gt;<br />
 129 polygon_90_set_view <b>operator</b>&amp;(const T1&amp; l, const
 130 T2&amp; r)</font></td>
 131             <td>Boolean AND operation (polygon set intersection).&nbsp;
 132 Accepts two objects that model polygon_90_set or one of its
 133 refinements.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 134 vertices + intersections.</td>
 135           </tr>
 136           <tr>
 137             <td width="586"><font face="Courier New">template
 138 &lt;typename T1, typename T2&gt;<br />
 139 polygon_90_set_view <b>operator</b>*(const T1&amp; l, const T2&amp; r)</font></td>
 140             <td>Same as operator&amp;.&nbsp; The multiplication symbol
 141 is also used for AND operations in Boolean logic expressions.&nbsp; O(
 142 n log n) runtime complexity and O(n) memory wrt vertices +
 143 intersections.</td>
 144           </tr>
 145           <tr>
 146             <td width="586"><font face="Courier New">template
 147 &lt;typename T1, typename T2&gt;<br />
 148 polygon_90_set_view <b>operator</b>^(const T1&amp; l, const T2&amp; r)</font></td>
 149             <td>Boolean XOR operation (polygon set
 150 disjoint-union).&nbsp; Accepts two objects that model polygon_90_set or
 151 one of its refinements.&nbsp; O( n log n) runtime complexity and O(n)
 152 memory wrt vertices + intersections.&nbsp; O( n log n) runtime
 153 complexity and O(n) memory wrt vertices + intersections.</td>
 154           </tr>
 155           <tr>
 156             <td width="586"><font face="Courier New">template
 157 &lt;typename T1, typename T2&gt;<br />
 158 polygon_90_set_view <b>operator</b>-(const T1&amp; l, const T2&amp; r)</font></td>
 159             <td>Boolean SUBTRACT operation (polygon set
 160 difference).&nbsp; Accepts two objects that model polygon_90_set or one
 161 of its refinements.&nbsp; O( n log n) runtime complexity and O(n)
 162 memory wrt vertices + intersections.</td>
 163           </tr>
 164           <tr>
 165             <td width="586"><font face="Courier New">template
 166 &lt;typename T1, typename T2&gt;<br />
 167 T1&amp; <b>operator</b>|=(const T1&amp; l, const T2&amp; r)</font></td>
 168             <td>Same as operator|, but with self assignment, left
 169 operand must model polygon_90_set and not one of it's
 170 refinements.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 171 vertices + intersections.</td>
 172           </tr>
 173           <tr>
 174             <td width="586"><font face="Courier New">template
 175 &lt;typename T1, typename T2&gt;<br />
 176 T1&amp; <b>operator</b>+=(T1&amp; l, const T2&amp; r)</font></td>
 177             <td>Same as operator+, but with self assignment, left
 178 operand must model polygon_90_set and not one of it's
 179 refinements.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 180 vertices + intersections.</td>
 181           </tr>
 182           <tr>
 183             <td width="586"><font face="Courier New">template
 184 &lt;typename T1, typename T2&gt;<br />
 185 T1&amp; <b>operator</b>&amp;=(const T1&amp; l, const T2&amp; r)</font></td>
 186             <td>Same as operator&amp;, but with self assignment, left
 187 operand must model polygon_90_set and not one of it's
 188 refinements.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 189 vertices + intersections.</td>
 190           </tr>
 191           <tr>
 192             <td width="586"><font face="Courier New">template
 193 &lt;typename T1, typename T2&gt;<br />
 194 T1&amp; <b>operator</b>*=(T1&amp; l, const T2&amp; r)</font></td>
 195             <td>Same as operator*, but with self assignment, left
 196 operand must model polygon_90_set and not one of it's
 197 refinements.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 198 vertices + intersections.</td>
 199           </tr>
 200           <tr>
 201             <td width="586"><font face="Courier New">template
 202 &lt;typename T1, typename T2&gt;<br />
 203 T1&amp; <b>operator</b>^=(const T1&amp; l, const T2&amp; r)</font></td>
 204             <td>Same as operator^, but with self assignment, left
 205 operand must model polygon_90_set and not one of it's
 206 refinements.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 207 vertices + intersections.</td>
 208           </tr>
 209           <tr>
 210             <td width="586"><font face="Courier New">template
 211 &lt;typename T1, typename T2&gt;<br />
 212 T1&amp; <b>operator</b>-=(T1&amp; l, const T2&amp; r)</font></td>
 213             <td>Same as operator-, but with self assignment, left
 214 operand must model polygon_90_set and not one of it's
 215 refinements.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 216 vertices + intersections.</td>
 217           </tr>
 218           <tr>
 219             <td width="586"><font face="Courier New">template
 220 &lt;typename T1&gt;<br />
 221 T1 <b>operator</b>+(const T1&amp;, coordinate_type bloating)</font></td>
 222             <td>Performs resize operation, inflating by bloating
 223 ammount.&nbsp; If negative the result is a shrink instead of
 224 bloat.&nbsp; Note: returns result by value.&nbsp; O( n log n) runtime
 225 complexity and O(n) memory wrt vertices + intersections.</td>
 226           </tr>
 227           <tr>
 228             <td width="586"><font face="Courier New">template
 229 &lt;typename T1, typename T2&gt;<br />
 230 T1 <b>operator</b>-(const T1&amp;, coordinate_type shrinking)</font></td>
 231             <td>Performs resize operation, deflating by bloating
 232 ammount.&nbsp; If negative the result is a bloat instead of
 233 shrink.&nbsp; Note: returns result by value.&nbsp; O( n log n) runtime
 234 complexity and O(n) memory wrt vertices + intersections.</td>
 235           </tr>
 236           <tr>
 237             <td width="586"><font face="Courier New">template
 238 &lt;typename T1, typename T2&gt;<br />
 239 T1&amp; <b>operator</b>+=(const T1&amp;, coordinate_type bloating)</font></td>
 240             <td>Performs resize operation, inflating by bloating
 241 ammount.&nbsp; If negative the result is a shrink instead of
 242 bloat.&nbsp; Returns reference to modified argument.&nbsp; O( n log n)
 243 runtime complexity and O(n) memory wrt vertices + intersections.</td>
 244           </tr>
 245           <tr>
 246             <td width="586"><font face="Courier New">template
 247 &lt;typename T1, typename T2&gt;<br />
 248 T1&amp; <b>operator</b>-=(const T1&amp;, coordinate_type shrinking)</font></td>
 249             <td>Performs resize operation, deflating by bloating
 250 ammount.&nbsp; If negative the result is a bloat instead of
 251 shrink.&nbsp; Returns reference to modified argument.&nbsp; O( n log n)
 252 runtime complexity and O(n) memory wrt vertices + intersections.</td>
 253           </tr>
 254         </tbody>
 255       </table>
 256       <h2>Functions</h2>
 257       <table id="table1" border="1" width="100%">
 258         <tbody>
 259           <tr>
 260             <td width="586"><font face="Courier New">template
 261 &lt;typename T1, typename T2&gt;<br />
 262 T1&amp; <b>assign</b>(T1&amp; lvalue, const T2&amp; rvalue)</font></td>
 263             <td>Eliminates overlaps in geometry and copies from an
 264 object that models polygon_90_set or any of its refinements into an
 265 object that models polygon_90_set.&nbsp; O( n log n) runtime complexity
 266 and O(n) memory wrt vertices + intersections.</td>
 267           </tr>
 268           <tr>
 269             <td width="586"><font face="Courier New">template
 270 &lt;typename T1, typename T2&gt;<br />
 271 bool <b>equivalence</b>(const T1&amp; lvalue, const T2&amp; rvalue) </font></td>
 272             <td>Returns true if an object that models polygon_90_set or
 273 one of its refinements covers the exact same geometric regions as
 274 another object that models polygon_90_set or one of its
 275 refinements.&nbsp; For example: two of polygon_90 objects.&nbsp; O( n
 276 log n) runtime complexity and O(n) memory wrt vertices + intersections.</td>
 277           </tr>
 278           <tr>
 279             <td width="586"><font face="Courier New">template
 280 &lt;typename output_container_type, typename T&gt;<br />
 281 void <b>get_rectangles</b>(output_container_type&amp; output, <br />
 282 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 283 const T&amp; polygon_set)</font></td>
 284             <td>Output container is expected to be a standard
 285 container.&nbsp; Slices geometry of an object that models
 286 polygon_90_set or one of its refinements into non overlapping
 287 rectangles and appends them to the output.&nbsp; O( n log n) runtime
 288 complexity and O(n) memory wrt vertices + intersections. </td>
 289           </tr>
 290           <tr>
 291             <td width="586"><font face="Courier New">template
 292 &lt;typename output_container_type, typename T&gt;<br />
 293 void <b>get_max_rectangles</b>(output_container_type&amp; output, <br />
 294 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 295 const T&amp; polygon_set)</font></td>
 296             <td>Output container is expected to be a standard
 297 container.&nbsp; Given an object that models polygon_90_set or one of
 298 its refinements finds all overlapping rectangles that are maximal in
 299 area and appends them to the output.&nbsp; Expected n log n runtime,
 300 worst case quadratic rutnime.</td>
 301           </tr>
 302           <tr>
 303             <td width="586"><font face="Courier New">template
 304 &lt;typename polygon_set_type&gt;<br />
 305 void <b>clear</b>(polygon_set_type&amp; polygon_set)</font></td>
 306             <td>Makes the object empty of geometry.</td>
 307           </tr>
 308           <tr>
 309             <td width="586"><font face="Courier New">template
 310 &lt;typename polygon_set_type&gt;<br />
 311 bool <b>empty</b>(const polygon_set_type&amp; polygon_set)</font></td>
 312             <td>Checks whether the object is empty of geometry.&nbsp;
 313 Polygons that are completely covered by holes will result in empty
 314 returning true.&nbsp; O( n log n) runtime complexity and O(n) memory
 315 wrt vertices + intersections. </td>
 316           </tr>
 317           <tr>
 318             <td width="586"><font face="Courier New">template
 319 &lt;typename T, typename rectangle_type&gt;<br />
 320 bool <b>extents</b>(rectangle_type&amp; extents_rectangle, <br />
 321 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 322 const T&amp; polygon_set)</font></td>
 323             <td>Computes bounding box of an object that models
 324 polygon_90_set and stores it in an object that models rectangle.&nbsp;
 325 If the polygon set is empty returns false.&nbsp; If there are holes
 326 outside of shells they do not contribute to the extents of the polygon
 327 set.&nbsp; O( n log n) runtime complexity and O(n) memory wrt vertices
 328 + intersections. </td>
 329           </tr>
 330           <tr>
 331             <td width="586"><font face="Courier New">template
 332 &lt;typename T&gt;<br />
 333 manhattan_area_type <b>area</b>(const T&amp; polygon_set)</font></td>
 334             <td>Computes the area covered by geometry in an object that
 335 models polygon_90_set.&nbsp; O( n log n) runtime complexity and O(n)
 336 memory wrt vertices + intersections. </td>
 337           </tr>
 338           <tr>
 339             <td width="586"><font face="Courier New">template
 340 &lt;typename T1, typename T2&gt;<br />
 341 T1&amp; <b>interact</b>(T1&amp; a, const T2&amp; b)</font></td>
 342             <td>Given an object that models polygon_90_set and an
 343 object that models polygon_90_set or one of its refinements, modifies a
 344 to retain only regions that overlap or touch regions in b.&nbsp; O( n
 345 log n) runtime complexity and O(n) memory wrt vertices + intersections.
 346             </td>
 347           </tr>
 348           <tr>
 349             <td width="586"><font face="Courier New">template
 350 &lt;typename T&gt;<br />
 351 T&amp; <b>self_intersect</b>(T&amp; polygon_set)</font></td>
 352             <td>Given an object that models polygon_90_set that has
 353 self overlapping regions, modifies the argument to contain only the
 354 regions of overlap.&nbsp; O( n log n) runtime complexity and O(n)
 355 memory wrt vertices + intersections. </td>
 356           </tr>
 357           <tr>
 358             <td width="586"><font face="Courier New">template
 359 &lt;typename T&gt;<br />
 360 T&amp; <b>self_xor</b>(T&amp; polygon_set)</font></td>
 361             <td>Given an object that models polygon_90_set that has
 362 self overlapping regions, modifies the argument to contain only the
 363 regions that do not overlap.&nbsp; O( n log n) runtime complexity and
 364 O(n) memory wrt vertices + intersections. </td>
 365           </tr>
 366           <tr>
 367             <td width="586"><font face="Courier New">template
 368 &lt;typename T&gt;<br />
 369 T&amp; <b>bloat</b>(T&amp; polygon_set, unsigned_area_type bloating)</font></td>
 370             <td>Same as getting all the rectangles, bloating them and
 371 putting them back.&nbsp; O( n log n) runtime complexity and O(n) memory
 372 wrt vertices + intersections. </td>
 373           </tr>
 374           <tr>
 375             <td width="586"><font face="Courier New">template
 376 &lt;typename T&gt;<br />
 377 T&amp; <b>bloat</b>(T&amp; polygon_set, orientation_2d orient,<br />
 378 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 379 bloating)</font></td>
 380             <td>Same as getting all the rectangles, bloating them and
 381 putting them back.&nbsp; O( n log n) runtime complexity and O(n) memory
 382 wrt vertices + intersections. </td>
 383           </tr>
 384           <tr>
 385             <td width="586"><font face="Courier New">template
 386 &lt;typename T&gt;<br />
 387 T&amp; <b>bloat</b>(T&amp; polygon_set, orientation_2d orient,<br />
 388 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 389 low_bloating,<br />
 390 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 391 high_bloating)</font></td>
 392             <td>Same as getting all the rectangles, bloating them and
 393 putting them back.&nbsp; O( n log n) runtime complexity and O(n) memory
 394 wrt vertices + intersections. </td>
 395           </tr>
 396           <tr>
 397             <td width="586"><font face="Courier New">template
 398 &lt;typename T&gt;<br />
 399 T&amp; <b>bloat</b>(T&amp; polygon_set, direction_2d dir,<br />
 400 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 401 bloating)</font></td>
 402             <td>Same as getting all the rectangles, bloating them and
 403 putting them back.&nbsp; O( n log n) runtime complexity and O(n) memory
 404 wrt vertices + intersections. </td>
 405           </tr>
 406           <tr>
 407             <td width="586"><font face="Courier New">template
 408 &lt;typename T&gt;<br />
 409 T&amp; <b>bloat</b>(T&amp; polygon_set, <br />
 410 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 411 west_bloating,<br />
 412 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 413 east_bloating,<br />
 414 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 415 south_bloating,<br />
 416 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 417 north_bloating)</font></td>
 418             <td>Same as getting all the rectangles, bloating them and
 419 putting them back.&nbsp; O( n log n) runtime complexity and O(n) memory
 420 wrt vertices + intersections. </td>
 421           </tr>
 422           <tr>
 423             <td width="586"><font face="Courier New">template
 424 &lt;typename T&gt;<br />
 425 T&amp; <b>shrink</b>(T&amp; polygon_set, unsigned_area_type shrinking)</font></td>
 426             <td>Same as getting all the rectangles of the inverse,
 427 bloating them and overwriting the polygon set with the resulting
 428 regions then negating.&nbsp; O( n log n) runtime complexity and O(n)
 429 memory wrt vertices + intersections. </td>
 430           </tr>
 431           <tr>
 432             <td width="586"><font face="Courier New">template
 433 &lt;typename T&gt;<br />
 434 T&amp; <b>shrink</b>(T&amp; polygon_set, orientation_2d orient,<br />
 435 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 436 unsigned_area_type shrinking)</font></td>
 437             <td>Same as getting all the rectangles of the inverse,
 438 bloating them and overwriting the polygon set with the resulting
 439 regions then negating.&nbsp; O( n log n) runtime complexity and O(n)
 440 memory wrt vertices + intersections. </td>
 441           </tr>
 442           <tr>
 443             <td width="586"><font face="Courier New">template
 444 &lt;typename T&gt;<br />
 445 T&amp; <b>shrink</b>(T&amp; polygon_set, orientation_2d orient,<br />
 446 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 447 unsigned_area_type low_shrinking,<br />
 448 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 449 unsigned_area_type high_shrinking)</font></td>
 450             <td>Same as getting all the rectangles of the inverse,
 451 bloating them and overwriting the polygon set with the resulting
 452 regions then negating.&nbsp; O( n log n) runtime complexity and O(n)
 453 memory wrt vertices + intersections. </td>
 454           </tr>
 455           <tr>
 456             <td width="586"><font face="Courier New">template
 457 &lt;typename T&gt;<br />
 458 T&amp; <b>shrink</b>(T&amp; polygon_set, direction_2d dir,<br />
 459 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 460 unsigned_area_type shrinking)</font></td>
 461             <td>Same as getting all the rectangles of the inverse,
 462 bloating them and overwriting the polygon set with the resulting
 463 regions then negating.&nbsp; O( n log n) runtime complexity and O(n)
 464 memory wrt vertices + intersections. </td>
 465           </tr>
 466           <tr>
 467             <td width="586"><font face="Courier New">template
 468 &lt;typename T&gt;<br />
 469 T&amp; <b>shrink</b>(T&amp; polygon_set, <br />
 470 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 471 unsigned_area_type west_shrinking,<br />
 472 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 473 unsigned_area_type east_shrinking,<br />
 474 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 475 unsigned_area_type south_shrinking,<br />
 476 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 477 unsigned_area_type north_shrinking)</font></td>
 478             <td>Same as getting all the rectangles of the inverse,
 479 bloating them and overwriting the polygon set with the resulting
 480 regions then negating.&nbsp; O( n log n) runtime complexity and O(n)
 481 memory wrt vertices + intersections. </td>
 482           </tr>
 483           <tr>
 484             <td width="586"><font face="Courier New">template
 485 &lt;typename T, typename coord_type&gt;<br />
 486 T&amp; <b>resize</b>(T&amp; polygon_set, coord_type resizing)</font></td>
 487             <td>Same as bloat if resizing is positive, same as shrink
 488 if resizing is negative.</td>
 489           </tr>
 490           <tr>
 491             <td width="586"><font face="Courier New">template
 492 &lt;typename T, typename coord_type&gt;<br />
 493 T&amp; <b>resize</b>(polygon_set_type&amp; polygon_set, <br />
 494 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; coord_type west,
 495 coord_type east, <br />
 496 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; coord_type
 497 south, coord_type north)</font></td>
 498             <td>Same as bloat if resizing is positive, same as shrink
 499 if resizing is negative.&nbsp; O( n log n) runtime complexity and O(n)
 500 memory wrt vertices + intersections. </td>
 501           </tr>
 502           <tr>
 503             <td width="586"><font face="Courier New">template
 504 &lt;typename T&gt;<br />
 505 T&amp; <b>grow_and</b>(T&amp; polygon_set, unsigned_area_type bloating)</font></td>
 506             <td>Same as bloating non-overlapping regions and then
 507 applying self intersect to retain only the overlaps introduced by the
 508 bloat.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 509 vertices + intersections. </td>
 510           </tr>
 511           <tr>
 512             <td width="586"><font face="Courier New">template
 513 &lt;typename T&gt;<br />
 514 T&amp; <b>grow_and</b>(T&amp; polygon_set, orientation_2d orient,<br />
 515 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 516 unsigned_area_type bloating)</font></td>
 517             <td>Same as bloating non-overlapping regions and then
 518 applying self intersect to retain only the overlaps introduced by the
 519 bloat.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 520 vertices + intersections. </td>
 521           </tr>
 522           <tr>
 523             <td width="586"><font face="Courier New">template
 524 &lt;typename T&gt;<br />
 525 T&amp; <b>grow_and</b>(T&amp; polygon_set, orientation_2d orient,<br />
 526 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 527 unsigned_area_type low_bloating,<br />
 528 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 529 unsigned_area_type high_bloating)</font></td>
 530             <td>Same as bloating non-overlapping regions and then
 531 applying self intersect to retain only the overlaps introduced by the
 532 bloat.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 533 vertices + intersections. </td>
 534           </tr>
 535           <tr>
 536             <td width="586"><font face="Courier New">template
 537 &lt;typename T&gt;<br />
 538 T&amp; <b>grow_and</b>(T&amp; polygon_set, direction_2d dir,<br />
 539 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 540 unsigned_area_type bloating)</font></td>
 541             <td>Same as bloating non-overlapping regions and then
 542 applying self intersect to retain only the overlaps introduced by the
 543 bloat.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 544 vertices + intersections. </td>
 545           </tr>
 546           <tr>
 547             <td width="586"><font face="Courier New">template
 548 &lt;typename T&gt;<br />
 549 T&amp; <b>grow_and</b>(T&amp; polygon_set, <br />
 550 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 551 unsigned_area_type west_bloating,<br />
 552 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 553 unsigned_area_type east_bloating,<br />
 554 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 555 unsigned_area_type south_bloating,<br />
 556 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 557 unsigned_area_type north_bloating)</font></td>
 558             <td>Same as bloating non-overlapping regions and then
 559 applying self intersect to retain only the overlaps introduced by the
 560 bloat.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 561 vertices + intersections. </td>
 562           </tr>
 563           <tr>
 564             <td width="586"><font face="Courier New">template
 565 &lt;typename T&gt;<br />
 566 T&amp; <b>scale_up</b>(T&amp; polygon_set, unsigned_area_type factor)</font></td>
 567             <td>Scales geometry up by unsigned factor.&nbsp; O( n log
 568 n) runtime complexity and O(n) memory wrt vertices + intersections. </td>
 569           </tr>
 570           <tr>
 571             <td width="586"><font face="Courier New">template
 572 &lt;typename T&gt;<br />
 573 T&amp; <b>scale_down</b>(T&amp; polygon_set, unsigned_area_type factor)</font></td>
 574             <td>Scales geometry down by unsigned factor.&nbsp; O( n log
 575 n) runtime complexity and O(n) memory wrt vertices + intersections. </td>
 576           </tr>
 577           <tr>
 578             <td width="586"><font face="Courier New">template
 579 &lt;typename T, typename scaling_type&gt;<br />
 580 T&amp; <b>scale</b>(polygon_set_type&amp; polygon_set, <br />
 581 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; const
 582 scaling_type&amp; scaling)</font></td>
 583             <td>Scales geometry by applying scaling.scale() on all
 584 vertices.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 585 vertices + intersections. </td>
 586           </tr>
 587           <tr>
 588             <td width="586"><font face="Courier New">template
 589 &lt;typename T, typename coord_type&gt;<br />
 590 T&amp; <b>move</b>(T&amp; polygon_set,<br />
 591 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; orientation_2d orient,
 592 coord_type displacement)</font></td>
 593             <td>Moves geometry by displacement amount in the
 594 orientation.&nbsp;&nbsp;&nbsp; O( n log n) runtime complexity and O(n)
 595 memory wrt vertices + intersections. </td>
 596           </tr>
 597           <tr>
 598             <td width="586"><font face="Courier New">template
 599 &lt;typename T, typename coord_type&gt;<br />
 600 T&amp; <b>move</b>(T&amp; polygon_set, coord_type x_displacement, <br />
 601 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; coord_type y_displacement)</font></td>
 602             <td>Moves the geometry by x_dispacement in x and
 603 y_displacement in y.&nbsp; Note: for consistency should be
 604 convolve(polygon_set, point).&nbsp; O( n log n) runtime complexity and
 605 O(n) memory wrt vertices + intersections. </td>
 606           </tr>
 607           <tr>
 608             <td width="586"><font face="Courier New">template
 609 &lt;typename T, typename transformation_type&gt;<br />
 610 T&amp; <b>transform</b>(T&amp; polygon_set,<br />
 611 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 612 const transformation_type&amp; transformation)</font></td>
 613             <td>Applies transformation.transform() on all
 614 vertices.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 615 vertices + intersections. </td>
 616           </tr>
 617           <tr>
 618             <td width="586"><font face="Courier New">template
 619 &lt;typename T&gt;<br />
 620 T&amp; <b>keep</b>(T&amp; polygon_set, <br />
 621 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type min_area,<br />
 622 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type max_area,<br />
 623 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type min_width,<br />
 624 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type max_width,<br />
 625 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 626 min_height,<br />
 627 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 628 max_height)</font></td>
 629             <td>Retains only regions that satisfy the min/max criteria
 630 in the argument list.&nbsp; Note: useful for visualization to cull too
 631 small polygons.&nbsp; O( n log n) runtime complexity and O(n) memory
 632 wrt vertices + intersections. </td>
 633           </tr>
 634         </tbody>
 635       </table>
 636       <h1>Polygon 90 Set Data Object</h1>
 637       <p> </p>
 638       <p>The polygon 90 set data type encapsulates the internal data
 639 format that serves as the input to the sweep-line algorithm that
 640 implements polygon-clipping boolean operations.&nbsp; It also
 641 internally keeps track of whether that data has been sorted or scanned
 642 and maintains the invariant that when its flags indicate that the data
 643 is sorted or scanned the data has not been changed to violate that
 644 assumption.&nbsp; Using the Polygon 90 Set Data type directly can be
 645 more efficient than using lists and vectors of polygons in the
 646 functions above because of the invariants it can enforce which provide
 647 the opportunity to maintain the data is sorted form rather than going
 648 all the way out to polygons then resorting those vertices for a
 649 subsequent operation.</p>
 650       <p>The declaration of Polygon 90 Set Data is the following:</p>
 651       <p><font face="Courier New">template &lt;typename T&gt;<br />
 652 class polygon_90_set_data;</font></p>
 653       <p>The class is parameterized on the coordinate data type.&nbsp;
 654 Algorithms that benefit from knowledge of the invariants enforced by
 655 the class are implemented as member functions to provide them access to
 656 information about those invariants.&nbsp; </p>
 657       <h2>Member Functions</h2>
 658       <table id="table2" border="1" width="100%">
 659         <tbody>
 660           <tr>
 661             <td width="586"><font face="Courier New"><b>polygon_90_set_data</b>()</font></td>
 662             <td>Default constructor.&nbsp; Scanning orientation
 663 defaults to HORIZONTAL</td>
 664           </tr>
 665           <tr>
 666             <td width="586"><font face="Courier New"><b>polygon_90_set_data</b>(orientation_2d
 667 orient)</font></td>
 668             <td>Construct with scanning orientation.</td>
 669           </tr>
 670           <tr>
 671             <td width="586"><font face="Courier New">template
 672 &lt;typename iT&gt;<br />
 673             <b>polygon_90_set_data</b>(orientation_2d orient, <br />
 674 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 675 iT input_begin, iT input_end)</font></td>
 676             <td>Construct with scanning orientation from an iterator
 677 range of insertable objects.</td>
 678           </tr>
 679           <tr>
 680             <td width="586"><font face="Courier New"> <b>polygon_90_set_data</b>(const
 681 polygon_90_set_data&amp; that)</font></td>
 682             <td>Copy construct.</td>
 683           </tr>
 684           <tr>
 685             <td width="586"><font face="Courier New">template
 686 &lt;typename l, typename r, typename op&gt;<br />
 687             <b>polygon_90_set_data</b>(const
 688 polygon_90_set_view&lt;l,r,op&gt;&amp; t)</font></td>
 689             <td>Copy construct from a Boolean operator template.</td>
 690           </tr>
 691           <tr>
 692             <td width="586"><font face="Courier New">
 693             <b>polygon_90_set_data</b>(orientation_2d orient, <br />
 694 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 695 const polygon_90_set_data&amp; that)</font></td>
 696             <td>Construct with scanning orientation and copy from
 697 another polygon set.</td>
 698           </tr>
 699           <tr>
 700             <td width="586"><font face="Courier New">polygon_90_set_data&amp;
 701             <br />
 702             <b>operator=</b>(const polygon_90_set_data&amp; that)</font></td>
 703             <td>Assignment from another polygon set, may change
 704 scanning orientation.</td>
 705           </tr>
 706           <tr>
 707             <td width="586"><font face="Courier New">template
 708 &lt;typename l, typename r, typename op&gt;<br />
 709 polygon_90_set_data&amp; <br />
 710             <b>operator=</b>(const polygon_90_set_view&lt;l, r,
 711 op&gt;&amp; that)</font></td>
 712             <td>Assignment from a Boolean operator template.</td>
 713           </tr>
 714           <tr>
 715             <td width="586"><font face="Courier New">template
 716 &lt;typename geometry_object&gt;<br />
 717 polygon_90_set_data&amp; <b>operator=</b>(const geometry_object&amp;
 718 geo)</font></td>
 719             <td>Assignment from an insertable object.</td>
 720           </tr>
 721           <tr>
 722             <td width="586"><font face="Courier New">
 723 template &lt;typename iT&gt;<br />
 724 void <b>insert</b>(iT input_begin, iT input_end)</font></td>
 725             <td>Insert objects of an iterator range.&nbsp; Linear wrt.
 726 inserted vertices.</td>
 727           </tr>
 728           <tr>
 729             <td width="586"><font face="Courier New">
 730 void <b>insert</b>(const polygon_90_set_data&amp; polygon_set)</font></td>
 731             <td>Insert a polygon set.&nbsp; Linear wrt. inserted
 732 vertices.</td>
 733           </tr>
 734           <tr>
 735             <td width="586"><font face="Courier New">
 736 template &lt;typename geometry_type&gt;<br />
 737 void <b>insert</b>(const geometry_type&amp; geometry_object, <br />
 738 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; bool
 739 is_hole = false)</font></td>
 740             <td>Insert a geometry object, if is_hole is true then the
 741 inserted region is subtractive rather than additive.&nbsp; Linear wrt.
 742 inserted vertices.</td>
 743           </tr>
 744           <tr>
 745             <td width="586"><font face="Courier New">template
 746 &lt;typename output_container&gt;<br />
 747 void <b>get</b>(output_container&amp; output) const</font></td>
 748             <td>Expects a standard container of geometry objects.&nbsp;
 749 Will scan and eliminate overlaps.&nbsp; Converts polygon set geometry
 750 to objects of that type and appends them to the container.&nbsp;
 751 Polygons will be output with counterclockwise winding, hole polygons
 752 will be output with clockwise winding.&nbsp; The last vertex of an
 753 output polygon is not the duplicate of the first, and the number of
 754 points is equal to the number of edges.&nbsp; O( n log n) runtime
 755 complexity and O(n) memory wrt vertices + intersections.</td>
 756           </tr>
 757           <tr>
 758             <td style="vertical-align: top;"><font face="Courier New">template
 759 &lt;typename output_container&gt;<br />
 760 void <b>get</b>(output_container&amp; output, size_t k) const</font></td>
 761             <td style="vertical-align: top;">Expects a standard
 762 container of geometry objects.&nbsp; Will scan and eliminate
 763 overlaps.&nbsp; Converts polygon set geometry to objects of that type
 764 and appends them to the container.&nbsp; The resulting polygons will
 765 have at most k vertices. For Manhattan data k should be at least 4 .
 766 Polygons will be output with counterclockwise winding, hole polygons
 767 will be output with clockwise winding.&nbsp; The last vertex of an
 768 output polygon is not the duplicate of the first, and the number of
 769 points is equal to the number of edges.&nbsp; O( n log n) runtime
 770 complexity and O(n) memory wrt vertices + intersections.<br />
 771             </td>
 772           </tr>
 773 <tr>
 774             <td width="586"><font face="Courier New">template
 775 &lt;typename output_container&gt;<br />
 776 void <b>get_polygons</b>(output_container&amp; output) const</font></td>
 777             <td>Expects a standard container of polygon objects.&nbsp;
 778 Will scan and eliminate overlaps.&nbsp; Converts polygon set geometry
 779 to polygons and appends them to the container.&nbsp; Polygons will have
 780 holes fractured out to the outer boundary along the positive direction
 781 of the scanline orientation of the polygon set.&nbsp; O( n log n)
 782 runtime complexity and O(n) memory wrt vertices + intersections.</td>
 783           </tr>
 784           <tr>
 785             <td width="586"><font face="Courier New">template
 786 &lt;typename output_container&gt;<br />
 787 void <b>get_rectangles</b>(output_container&amp; output) const</font></td>
 788             <td>Expects a standard container of rectangle
 789 objects.&nbsp; Will scan and eliminate overlaps.&nbsp; Slices polygon
 790 set geometry to rectangles along the scanning orientation and appends
 791 them to the container.&nbsp; O( n log n) runtime complexity and O(n)
 792 memory wrt vertices + intersections.</td>
 793           </tr>
 794           <tr>
 795             <td width="586"><font face="Courier New">
 796 template &lt;typename output_container&gt;<br />
 797 void <b>get_rectangles</b>(output_container&amp; output, <br />
 798 &nbsp; orientation_2d slicing_orientation) const </font> </td>
 799             <td>Expects a standard container of rectangle
 800 objects.&nbsp; Will scan and eliminate overlaps.&nbsp; Slices polygon
 801 set geometry to rectangles along the given orientation and appends them
 802 to the container.&nbsp; O( n log n) runtime complexity and O(n) memory
 803 wrt vertices + intersections.</td>
 804           </tr>
 805           <tr>
 806             <td width="586"><font face="Courier New">
 807 bool <b>operator==</b>(const polygon_90_set_data&amp; p) const</font></td>
 808             <td>Once scanned the data representation of geometry within
 809 a polygon set is in a mathematically canonical form.&nbsp; Comparison
 810 between two sets is therefore a linear time operation once they are in
 811 the scanned state. Will scan and eliminate overlaps in both polygon
 812 sets.&nbsp; O( n log n) runtime complexity and O(n) memory wrt vertices
 813 + intersections the first time, linear subsequently.</td>
 814           </tr>
 815           <tr>
 816             <td width="586"><font face="Courier New">bool <b>operator!=</b>(const
 817 polygon_90_set_data&amp; p) const</font></td>
 818             <td>Inverse logic of equivalence operator.</td>
 819           </tr>
 820           <tr>
 821             <td width="586"><font face="Courier New">void <b>clear</b>()</font></td>
 822             <td>Make the polygon set empty.&nbsp; Note: does not
 823 de-allocate memory.&nbsp; Use shrink to fit idiom and assign default
 824 constructed polygon set to de-allocate.</td>
 825           </tr>
 826           <tr>
 827             <td width="586"><font face="Courier New">bool <b>empty</b>()
 828 const </font> </td>
 829             <td>Check whether the polygon set contains no
 830 geometry.&nbsp; Will scan and eliminate overlaps because subtractive
 831 regions might make the polygon set empty.&nbsp; O( n log n) runtime
 832 complexity and O(n) memory wrt vertices + intersections the first time,
 833 linear subsequently.</td>
 834           </tr>
 835           <tr>
 836             <td width="586"><font face="Courier New">orientation_2d <b>orient</b>()
 837 const</font></td>
 838             <td>Get the scanning orientation.&nbsp; Depending on the
 839 data it is sometimes more efficient to scan in a specific
 840 orientation.&nbsp; This is particularly true of Manhattan geometry
 841 data.&nbsp; Constant time.</td>
 842           </tr>
 843           <tr>
 844             <td width="586"><font face="Courier New">void <b>clean</b>()
 845 const</font></td>
 846             <td>Scan and eliminate overlaps.&nbsp; O( n log n) runtime
 847 complexity and O(n) memory wrt vertices + intersections the first time,
 848 constant time subsequently.</td>
 849           </tr>
 850           <tr>
 851             <td width="586"><font face="Courier New">template
 852 &lt;typename input_iterator_type&gt;<br />
 853 void <b>set</b>(input_iterator_type input_begin, <br />
 854 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; input_iterator_type
 855 input_end, <br />
 856 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; orientation_2d orient)
 857             </font> </td>
 858             <td>Overwrite geometry in polygon set with insertable
 859 objects in the iterator range.&nbsp; Also sets the scanning orientation
 860 to that specified.</td>
 861           </tr>
 862           <tr>
 863             <td width="586"><font face="Courier New">template
 864 &lt;typename rectangle_type&gt;<br />
 865 bool <b>extents</b>(rectangle_type&amp; extents_rectangle) const</font></td>
 866             <td>Given an object that models rectangle, scans and
 867 eliminates overlaps in the polygon set because subtractive regions may
 868 alter its extents then computes the bounding box and assigns it to
 869 extents_rectangle.&nbsp; O( n log n) runtime complexity and O(n) memory
 870 wrt vertices + intersections the first time, linear subsequently.</td>
 871           </tr>
 872           <tr>
 873             <td width="586"><font face="Courier New">polygon_90_set_data&amp;<br />
 874             <b>bloat</b>(unsigned_area_type west_bloating,<br />
 875 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 876 unsigned_area_type east_bloating,<br />
 877 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 878 unsigned_area_type south_bloating,<br />
 879 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 880 unsigned_area_type north_bloating) </font></td>
 881             <td>Scans to eliminate overlaps and subtractive
 882 regions.&nbsp; Inserts rectangles of width specified by bloating values
 883 to the indicated side of geometry within the polygon set and fills
 884 corners with rectangles of the length and width specified for the
 885 adjacent sides.&nbsp; O( n log n) runtime complexity and O(n) memory
 886 wrt vertices + intersections.</td>
 887           </tr>
 888           <tr>
 889             <td width="586"><font face="Courier New">polygon_90_set_data&amp;<br />
 890             <b>shrink</b>(unsigned_area_type west_shrinking,<br />
 891 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 892 unsigned_area_type east_shrinking,<br />
 893 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 894 unsigned_area_type south_shrinking,<br />
 895 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 896 unsigned_area_type north_shrinking)</font></td>
 897             <td>Scans to eliminate overlaps and subtractive
 898 regions.&nbsp; Inserts subtractiive rectangles of width specified by
 899 bloating values to the indicated side of geometry within the polygon
 900 set and subtractive rectangle at convex corners of the length and width
 901 specified for the adjacent sides.&nbsp; Scans to eliminate overlapping
 902 subtractive regions.&nbsp; O( n log n) runtime complexity and O(n)
 903 memory wrt vertices + intersections.</td>
 904           </tr>
 905           <tr>
 906             <td width="586"><font face="Courier New">polygon_90_set_data&amp;<br />
 907             <b>resize</b>(coordinate_type west, coordinate_type east, <br />
 908 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; coordinate_type south,
 909 coordinate_type north)</font></td>
 910             <td>Call bloat or shrink or shrink then bloat depending on
 911 whether the resizing values are positive or negative.&nbsp; O( n log n)
 912 runtime complexity and O(n) memory wrt vertices + intersections.</td>
 913           </tr>
 914           <tr>
 915             <td width="586"><font face="Courier New">polygon_90_set_data&amp;
 916             <b>move</b>(coordinate_type x_delta, <br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 917 coordinate_type y_delta) </font> </td>
 918             <td>Add x_delta to x values and y_delta to y values of
 919 vertices stored within the polygon set.&nbsp; Linear wrt. vertices.</td>
 920           </tr>
 921           <tr>
 922             <td width="586"><font face="Courier New">template
 923 &lt;typename transformation_type&gt;<br />
 924 polygon_90_set_data&amp; <br />
 925             <b>transform</b>(const transformation_type&amp;
 926 transformation) </font> </td>
 927             <td>Applies transformation.transform() on vertices stored
 928 within the polygon set.&nbsp; Linear wrt. vertices.</td>
 929           </tr>
 930           <tr>
 931             <td width="586"><font face="Courier New">polygon_90_set_data&amp;
 932             <b>scale_up</b>(unsigned_area_type factor)</font></td>
 933             <td>Scales vertices stored within the polygon set up by
 934 factor.&nbsp; Linear wrt. vertices.</td>
 935           </tr>
 936           <tr>
 937             <td width="586">
 938             <p><font face="Courier New">polygon_90_set_data&amp; <b>scale_down</b>(unsigned_area_type
 939 factor)</font>&nbsp;</p>
 940             </td>
 941             <td>Scales vertices stored within the polygon set down by
 942 factor.&nbsp; Linear wrt. vertices.</td>
 943           </tr>
 944           <tr>
 945             <td width="586"><font face="Courier New">template
 946 &lt;typename scaling_type&gt;<br />
 947 polygon_90_set_data&amp;<br />
 948             <b>scale</b>(const
 949 anisotropic_scale_factor&lt;scaling_type&gt;&amp; f)</font></td>
 950             <td>Scales vertices stored within the polygon set by
 951 applying f.scale().&nbsp; Linear wrt. vertices.</td>
 952           </tr>
 953           <tr>
 954             <td width="586"><font face="Courier New">polygon_90_set_data&amp;
 955             <b>scale</b>(double factor) </font></td>
 956             <td>Scales vertices stored within the polygon set by
 957 floating point factor.&nbsp; Linear wrt. vertices.</td>
 958           </tr>
 959           <tr>
 960             <td width="586"><font face="Courier New">polygon_90_set_data&amp;
 961             <b>self_xor</b>()</font></td>
 962             <td>Retain only non-overlapping regions of geometry within
 963 polygon set.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 964 vertices + intersections.</td>
 965           </tr>
 966           <tr>
 967             <td width="586"><font face="Courier New">polygon_90_set_data&amp;
 968             <b>self_intersect</b>()</font></td>
 969             <td>Retain only overlapping regions of geometry within a
 970 polygon set.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 971 vertices + intersections.</td>
 972           </tr>
 973           <tr>
 974             <td width="586"><font face="Courier New">polygon_90_set_data&amp;<br />
 975             <b>interact</b>(const polygon_90_set_data&amp; that)</font></td>
 976             <td>Retain only regions that touch or overlap regions in
 977 argument.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 978 vertices + intersections.</td>
 979           </tr>
 980         </tbody>
 981       </table>
 982       </td>
 983     </tr>
 984     <tr>
 985       <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> &nbsp;</td>
 986       <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
 987       <table class="docinfo" id="table4" frame="void" rules="none">
 988         <colgroup> <col class="docinfo-name" /><col class="docinfo-content" /> </colgroup> <tbody valign="top">
 989           <tr>
 990             <th class="docinfo-name">Copyright:</th>
 991             <td>Copyright © Intel Corporation 2008-2010.</td>
 992           </tr>
 993           <tr class="field">
 994             <th class="docinfo-name">License:</th>
 995             <td class="field-body">Distributed under the Boost Software
 996 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">
 997 http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 998           </tr>
 999         </tbody>
1000       </table>
1001       </td>
1002     </tr>
1003   </tbody>
1004 </table>
1005
1006 </body></html>