libs/polygon/doc/gtl_polygon_45_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"
   3  xmlns:v="urn:schemas-microsoft-com:vml"
   4  xmlns:o="urn:schemas-microsoft-com:office:office"
   5  xmlns:(null)1="http://www.w3.org/TR/REC-html40" lang="en">
   6 <head>
   7 <!--
   8     Copyright 2009-2010 Intel Corporation
   9     license banner
  10 -->
  11   <title>Boost Polygon Library: Polygon 45 Set Concept</title>
  12   <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" />
  13 <!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> -->
  14 </head>
  15 <body>
  16 <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0"
  17  cellpadding="0" cellspacing="0">
  18   <tbody>
  19     <tr>
  20       <td style="background-color: rgb(238, 238, 238);" nowrap="1"
  21  valign="top">
  22       <div style="padding: 5px;" align="center"> <img
  23  src="images/boost.png" border="0" height="86" width="277" /><a
  24  title="www.boost.org home page" href="http://www.boost.org/"
  25  tabindex="2" style="border: medium none ;"> </a> </div>
  26       <div style="margin: 5px;">
  27       <h3 class="navbar">Contents</h3>
  28       <ul>
  29         <li><a href="index.htm">Boost.Polygon Main Page</a></li>
  30         <li><a href="gtl_design_overview.htm">Design Overview</a></li>
  31         <li><a href="gtl_isotropy.htm">Isotropy</a></li>
  32         <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
  33         <li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
  34         <li><a href="gtl_point_concept.htm">Point Concept</a></li>
  35         <li><a href="gtl_segment_concept.htm">Segment Concept</a></li>
  36         <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
  37         <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
  38         <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
  39 With Holes Concept</a></li>
  40         <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
  41         <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
  42 With Holes Concept</a></li>
  43         <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
  44         <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
  45 Holes Concept</a></li>
  46         <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
  47 Concept</a></li>
  48         <li>Polygon 45 Set Concept</li>
  49         <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
  50         <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
  51 Extraction 90</a></li>
  52         <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
  53 Extraction 45</a></li>
  54         <li><a href="gtl_connectivity_extraction.htm">Connectivity
  55 Extraction</a></li>
  56         <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
  57         <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
  58         <li><a href="gtl_property_merge.htm">Property Merge</a></li>
  59         <li><a href="voronoi_main.htm">Voronoi Main Page<br />
  60           </a></li>
  61         <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br />
  62         </li>
  63         <li><a href="voronoi_builder.htm">Voronoi Builder</a></li>
  64         <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
  65       </ul>
  66       <h3 class="navbar">Other Resources</h3>
  67       <ul>
  68         <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
  69         <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
  70 Presentation</a></li>
  71         <li><a href="analysis.htm">Performance Analysis</a></li>
  72         <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
  73         <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
  74         <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
  75         <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
  76 Tutorial</a></li>
  77       </ul>
  78       </div>
  79       <h3 class="navbar">Polygon Sponsor</h3>
  80       <div style="padding: 5px;" align="center"> <img
  81  src="images/intlogo.gif" border="0" height="51" width="127" /><a
  82  title="www.adobe.com home page" href="http://www.adobe.com/"
  83  tabindex="2" style="border: medium none ;"> </a> </div>
  84       </td>
  85       <td
  86  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
  87  valign="top" width="100%">
  88 <!-- End Header --><br />
  89       <p>
  90       </p>
  91       <h1>Polygon 45 Set Concept</h1>
  92       <p> </p>
  93       <p>The polygon_45_set concept tag is <font face="Courier New">
  94 polygon_45_set_concept</font></p>
  95       <p> <font face="Times New Roman">The semantic of a
  96 polygon_45_set is zero or more geometry regions which have angles at
  97 the vertices that are multiples of 45-degrees relative to the
  98 coordinate axis.&nbsp; A Polygon 45 Set Concept makes no sense in
  99 floating point, but currently does not provide a static assert to
 100 prevent it from being used with floating point coordinates.&nbsp; The
 101 result of such use is undefined.&nbsp; When the intersection of two 45
 102 degree edges results in a vertex that is off the integer grid that case
 103 is handled by inserting a unit length edge between the two 45 degree
 104 edges near the off grid intersection point.&nbsp; In the case that data
 105 represented contains no 45-degree angles and is Manhattan a runtime
 106 check will default to the Manhattan algorithm.&nbsp; The results of
 107 which are identical to what the 45-degree algorithm would do, but
 108 obtained more efficiently.</font></p>
 109       <p> <font face="Times New Roman">The motivation for providing
 110 the polygon_45_set is to extend the special case of Manhattan geometry
 111 capability of the library to encompass the slightly less common, but
 112 still important special case of geometry that is described by angles
 113 that are multiples of 45-degress with respect to the coordinate
 114 axis.&nbsp; This simplifies the implementation of geometry algorithms
 115 and affords many opportunities for optimization.&nbsp; 45-degree
 116 algorithms can be 50X faster than arbitrary angle algorithms and are
 117 required to provide a complete feature set that meets the performance
 118 requirements of application domains in which Manhattan and 45-degree
 119 geometry are a common special case.</font></p>
 120       <p>Users are recommended to use std::vector and std::list of user
 121 defined polygons or library provided
 122 polygon_45_set_data&lt;coordinate_type&gt; objects.&nbsp; Lists and
 123 vectors of models of polygon_45_concept or
 124 polygon_45_with_holes_concept are automatically models of
 125 polygon_45_set_concept.</p>
 126       <p>An object that is a model of <font face="Courier New">
 127 polygon_45_set_concept</font> can be viewed as a model of <font
 128  face="Courier New">
 129 polygon_90_set_concept</font> if it is determined at runtime to conform
 130 to the restriction that all edges are axis-parallel.&nbsp; This concept
 131 casting is accomplished through the <font face="Courier New">view_as&lt;&gt;()</font>
 132 function.</p>
 133       <p><font face="Courier New">view_as&lt;polygon_90_set_concept&gt;(polygon_set_object)</font></p>
 134       <p>The return value of <font face="Courier New">view_as&lt;&gt;()</font>
 135 can be passed into any interface that expects an object of the
 136 conceptual type specified in its template parameter.&nbsp; Polygon sets
 137 cannot be viewed as single polygons or rectangles since it generally
 138 cannot be known whether a polygon set contains only a single polygon
 139 without converting to polygons.</p>
 140       <h2>Operators</h2>
 141       <p>The return type of some operators is the <font
 142  face="Courier New">polygon_45_set_view</font> operator template
 143 type.&nbsp; This type is itself a model of the polygon 90 set concept,
 144 but furthermore can be used as an argument to the <font
 145  face="Courier New">polygon_45_set_data</font> constructor and
 146 assignment operator.&nbsp; The operator template exists to eliminate
 147 temp copies of intermediate results when Boolean operators are chained
 148 together.</p>
 149       <p>Operators are declared inside the namespace <font
 150  face="Courier New">boost::polygon::operators</font>.</p>
 151       <table id="table5" border="1" width="100%">
 152         <tbody>
 153           <tr>
 154             <td width="586"><font face="Courier New">template
 155 &lt;typename T1, typename T2&gt;<br />
 156 polygon_45_set_view <b>operator</b>|(const T1&amp; l, const T2&amp; r)</font></td>
 157             <td>Boolean OR operation (polygon set union).&nbsp; Accepts
 158 two objects that model polygon_45_set or one of its refinements.&nbsp;
 159 Returns an operator template that performs the operation on demand when
 160 chained or or nested in a library function call such as assign().&nbsp;
 161 O( n log n) runtime complexity and O(n) memory wrt vertices +
 162 intersections.</td>
 163           </tr>
 164           <tr>
 165             <td width="586"><font face="Courier New">template
 166 &lt;typename T1, typename T2&gt;<br />
 167 polygon_45_set_view <b>operator</b>+(const T1&amp; l, const T2&amp; r)</font></td>
 168             <td>Same as operator|.&nbsp; The plus sign is also used for
 169 OR operations in Boolean logic expressions.&nbsp; O( n log n) runtime
 170 complexity and O(n) memory wrt vertices + intersections.</td>
 171           </tr>
 172           <tr>
 173             <td width="586"><font face="Courier New">template
 174 &lt;typename T1, typename T2&gt;<br />
 175 polygon_45_set_view <b>operator</b>&amp;(const T1&amp; l, const
 176 T2&amp; r)</font></td>
 177             <td>Boolean AND operation (polygon set intersection).&nbsp;
 178 Accepts two objects that model polygon_45_set or one of its
 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 polygon_45_set_view <b>operator</b>*(const T1&amp; l, const T2&amp; r)</font></td>
 186             <td>Same as operator&amp;.&nbsp; The multiplication symbol
 187 is also used for AND operations in Boolean logic expressions.&nbsp; O(
 188 n log n) runtime complexity and O(n) memory wrt vertices +
 189 intersections.</td>
 190           </tr>
 191           <tr>
 192             <td width="586"><font face="Courier New">template
 193 &lt;typename T1, typename T2&gt;<br />
 194 polygon_45_set_view <b>operator</b>^(const T1&amp; l, const T2&amp; r)</font></td>
 195             <td>Boolean XOR operation (polygon set
 196 disjoint-union).&nbsp; Accepts two objects that model polygon_45_set or
 197 one of its refinements.&nbsp; O( n log n) runtime complexity and O(n)
 198 memory wrt 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 polygon_45_set_view <b>operator</b>-(const T1&amp; l, const T2&amp; r)</font></td>
 204             <td>Boolean SUBTRACT operation (polygon set
 205 difference).&nbsp; Accepts two objects that model polygon_45_set or one
 206 of its refinements.&nbsp; O( n log n) runtime complexity and O(n)
 207 memory wrt 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>|=(const T1&amp; l, const T2&amp; r)</font></td>
 213             <td>Same as operator|, but with self assignment, left
 214 operand must model polygon_45_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, typename T2&gt;<br />
 221 T1&amp; <b>operator</b>+=(T1&amp; l, const T2&amp; r)</font></td>
 222             <td>Same as operator+, but with self assignment, left
 223 operand must model polygon_45_set and not one of it's
 224 refinements.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 225 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&amp; <b>operator</b>&amp;=(const T1&amp; l, const T2&amp; r)</font></td>
 231             <td>Same as operator&amp;, but with self assignment, left
 232 operand must model polygon_45_set and not one of it's
 233 refinements.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 234 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>*=(T1&amp; l, const T2&amp; r)</font></td>
 240             <td>Same as operator*, but with self assignment, left
 241 operand must model polygon_45_set and not one of it's
 242 refinements.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 243 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; l, const T2&amp; r)</font></td>
 249             <td>Same as operator^, but with self assignment, left
 250 operand must model polygon_45_set and not one of it's
 251 refinements.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 252 vertices + intersections.</td>
 253           </tr>
 254           <tr>
 255             <td width="586"><font face="Courier New">template
 256 &lt;typename T1, typename T2&gt;<br />
 257 T1&amp; <b>operator</b>-=(T1&amp; l, const T2&amp; r)</font></td>
 258             <td>Same as operator-, but with self assignment, left
 259 operand must model polygon_45_set and not one of it's
 260 refinements.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 261 vertices + intersections.</td>
 262           </tr>
 263           <tr>
 264             <td width="586"><font face="Courier New">template
 265 &lt;typename T1&gt;<br />
 266 T1 <b>operator</b>+(const T1&amp;, coordinate_type bloating)</font></td>
 267             <td>Performs resize operation, inflating by bloating
 268 ammount.&nbsp; If negative the result is a shrink instead of
 269 bloat.&nbsp; Note: returns result by value.&nbsp; O( n log n) runtime
 270 complexity and O(n) memory wrt vertices + intersections.</td>
 271           </tr>
 272           <tr>
 273             <td width="586"><font face="Courier New">template
 274 &lt;typename T1, typename T2&gt;<br />
 275 T1 <b>operator</b>-(const T1&amp;, coordinate_type shrinking)</font></td>
 276             <td>Performs resize operation, deflating by bloating
 277 ammount.&nbsp; If negative the result is a bloat instead of
 278 shrink.&nbsp; Note: returns result by value.&nbsp; O( n log n) runtime
 279 complexity and O(n) memory wrt vertices + intersections.</td>
 280           </tr>
 281           <tr>
 282             <td width="586"><font face="Courier New">template
 283 &lt;typename T1, typename T2&gt;<br />
 284 T1&amp; <b>operator</b>+=(const T1&amp;, coordinate_type bloating)</font></td>
 285             <td>Performs resize operation, inflating by bloating
 286 ammount.&nbsp; If negative the result is a shrink instead of
 287 bloat.&nbsp; Returns reference to modified argument.&nbsp; O( n log n)
 288 runtime 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 T1, typename T2&gt;<br />
 293 T1&amp; <b>operator</b>-=(const T1&amp;, coordinate_type shrinking)</font></td>
 294             <td>Performs resize operation, deflating by bloating
 295 ammount.&nbsp; If negative the result is a bloat instead of
 296 shrink.&nbsp; Returns reference to modified argument.&nbsp; O( n log n)
 297 runtime complexity and O(n) memory wrt vertices + intersections.</td>
 298           </tr>
 299         </tbody>
 300       </table>
 301       <h2>Functions</h2>
 302       <table id="table3" border="1" width="100%">
 303         <tbody>
 304           <tr>
 305             <td width="586"><font face="Courier New">template
 306 &lt;typename T1, typename T2&gt;<br />
 307 T1&amp; <b>assign</b>(T1&amp; lvalue, const T2&amp; rvalue)</font></td>
 308             <td>Eliminates overlaps in geometry and copies from an
 309 object that models polygon_45_set or any of its refinements into an
 310 object that models polygon_45_set.&nbsp; O( n log n) runtime complexity
 311 and O(n) memory wrt vertices + intersections.</td>
 312           </tr>
 313           <tr>
 314             <td width="586"><font face="Courier New">template
 315 &lt;typename T1, typename T2&gt;<br />
 316 bool <b>equivalence</b>(const T1&amp; lvalue, const T2&amp; rvalue) </font></td>
 317             <td>Returns true if an object that models polygon_45_set or
 318 one of its refinements covers the exact same geometric regions as
 319 another object that models polygon_45_set or one of its
 320 refinements.&nbsp; For example: two of polygon_45 objects.&nbsp; O( n
 321 log n) runtime complexity and O(n) memory wrt vertices + intersections.</td>
 322           </tr>
 323           <tr>
 324             <td width="586"><font face="Courier New">template
 325 &lt;typename output_container_type, typename T&gt;<br />
 326 void <b>get_trapezoids</b>(output_container_type&amp; output, <br />
 327 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 328 const T&amp; polygon_set)</font></td>
 329             <td>Output container is expected to be a standard
 330 container.&nbsp; Slices geometry of an object that models
 331 polygon_45_set or one of its refinements into non overlapping
 332 trapezoids along a vertical slicing orientation and appends them to the
 333 output, which must have a value type that models polygon_45,
 334 polygon_45_with_holes, polygon or polygon_with_holes.&nbsp;&nbsp; O( n
 335 log n) runtime complexity and O(n) memory wrt vertices.</td>
 336           </tr>
 337           <tr>
 338             <td width="586"><font face="Courier New">template
 339 &lt;typename output_container_type, typename T&gt;<br />
 340 void <b>get_trapezoids</b>(output_container_type&amp; output, <br />
 341 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 342 const T&amp; polygon_set,<br />
 343 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 344 orientation_2d orient)</font></td>
 345             <td>Output container is expected to be a standard
 346 container.&nbsp; Slices geometry of an object that models
 347 polygon_45_set or one of its refinements into non overlapping
 348 trapezoids along a the specified slicing orientation and appends them
 349 to the output, which must have a value type that models polygon_45,
 350 polygon_45_with_holes, polygon or polygon_with_holes.&nbsp;&nbsp; O( n
 351 log n) runtime complexity and O(n) memory wrt vertices.</td>
 352           </tr>
 353           <tr>
 354             <td width="586"><font face="Courier New">template
 355 &lt;typename polygon_set_type&gt;<br />
 356 void <b>clear</b>(polygon_set_type&amp; polygon_set)</font></td>
 357             <td>Makes the object empty of geometry.</td>
 358           </tr>
 359           <tr>
 360             <td width="586"><font face="Courier New">template
 361 &lt;typename polygon_set_type&gt;<br />
 362 bool <b>empty</b>(const polygon_set_type&amp; polygon_set)</font></td>
 363             <td>Checks whether the object is empty of geometry.&nbsp;
 364 Polygons that are completely covered by holes will result in empty
 365 returning true.&nbsp;&nbsp; O( n log n) runtime complexity and O(n)
 366 memory wrt vertices.</td>
 367           </tr>
 368           <tr>
 369             <td width="586"><font face="Courier New">template
 370 &lt;typename T, typename rectangle_type&gt;<br />
 371 bool <b>extents</b>(rectangle_type&amp; extents_rectangle, <br />
 372 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 373 const T&amp; polygon_set)</font></td>
 374             <td>Computes bounding box of an object that models
 375 polygon_45_set and stores it in an object that models rectangle.&nbsp;
 376 If the polygon set is empty returns false.&nbsp; If there are holes
 377 outside of shells they do not contribute to the extents of the polygon
 378 set.&nbsp;&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 379 vertices.</td>
 380           </tr>
 381           <tr>
 382             <td width="586"><font face="Courier New">template
 383 &lt;typename T&gt;<br />
 384 area_type <b>area</b>(const T&amp; polygon_set)</font></td>
 385             <td>Computes the area covered by geometry in an object that
 386 models polygon_45_set.&nbsp;&nbsp; O( n log n) runtime complexity and
 387 O(n) memory wrt vertices.</td>
 388           </tr>
 389           <tr>
 390             <td width="586"><font face="Courier New">template
 391 &lt;typename T1, typename T2&gt;<br />
 392 T1&amp; <b>interact</b>(T1&amp; a, const T2&amp; b)</font></td>
 393             <td>Given an object that models polygon_45_set and an
 394 object that models polygon_45_set or one of its refinements, modifies a
 395 to retain only regions that overlap or touch regions in b.&nbsp;&nbsp;
 396 O( n log n) runtime complexity and O(n) memory wrt vertices plus
 397 intersections.</td>
 398           </tr>
 399           <tr>
 400             <td width="586"><font face="Courier New">template
 401 &lt;typename T&gt;<br />
 402 T&amp; <b>self_intersect</b>(T&amp; polygon_set)</font></td>
 403             <td>Given an object that models polygon_45_set that has
 404 self overlapping regions, modifies the argument to contain only the
 405 regions of overlap.&nbsp; O( n log n) runtime complexity and O(n)
 406 memory wrt vertices + intersections.</td>
 407           </tr>
 408           <tr>
 409             <td width="586"><font face="Courier New">template
 410 &lt;typename T&gt;<br />
 411 T&amp; <b>self_xor</b>(T&amp; polygon_set)</font></td>
 412             <td>Given an object that models polygon_45_set that has
 413 self overlapping regions, modifies the argument to contain only the
 414 regions that do not overlap.&nbsp; O( n log n) runtime complexity and
 415 O(n) memory wrt vertices + intersections.</td>
 416           </tr>
 417           <tr>
 418             <td width="586"><font face="Courier New">template
 419 &lt;typename T&gt;<br />
 420 T&amp; <b>bloat</b>(T&amp; polygon_set, unsigned_area_type bloating)</font></td>
 421             <td>Same as getting all the polygons, bloating them and
 422 putting them back.&nbsp; O( n log n) runtime complexity and O(n) memory
 423 wrt vertices + intersections.</td>
 424           </tr>
 425           <tr>
 426             <td width="586"><font face="Courier New">template
 427 &lt;typename T&gt;<br />
 428 T&amp; <b>shrink</b>(T&amp; polygon_set, unsigned_area_type shrinking)</font></td>
 429             <td>Same as getting all the polygons, shrinking them and
 430 overwriting the polygon set with the resulting regions.&nbsp; O( n log
 431 n) runtime complexity and O(n) memory wrt vertices + intersections.</td>
 432           </tr>
 433           <tr>
 434             <td width="586"><font face="Courier New">template
 435 &lt;typename T, typename coord_type&gt;<br />
 436 T&amp; <b>resize</b>(T&amp; polygon_set, coord_type resizing,<br />
 437 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; RoundingOption
 438 rounding = CLOSEST, <br />
 439 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; CornerOption
 440 corner = INTERSECTION)</font></td>
 441             <td>Same as bloat if resizing is positive, same as shrink
 442 if resizing is negative.&nbsp; RoundingOption is an enum that controls
 443 snapping of non-integer results of resizing 45 degree edges.&nbsp;
 444 CornerOption is an enum that controls how corner filling is
 445 performed.&nbsp; polygon_45_set_data.hpp defines these enums.&nbsp; O(
 446 n log n) runtime complexity and O(n) memory wrt vertices +
 447 intersections.</td>
 448           </tr>
 449           <tr>
 450             <td width="586"><font face="Courier New">template
 451 &lt;typename T&gt;<br />
 452 T&amp; <b>grow_and</b>(T&amp; polygon_set, unsigned_area_type bloating)</font></td>
 453             <td>Same as bloating non-overlapping regions and then
 454 applying self intersect to retain only the overlaps introduced by the
 455 bloat.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 456 vertices + intersections.</td>
 457           </tr>
 458           <tr>
 459             <td width="586"><font face="Courier New">template
 460 &lt;typename T&gt;<br />
 461 T&amp; <b>scale_up</b>(T&amp; polygon_set, unsigned_area_type factor)</font></td>
 462             <td>Scales geometry up by unsigned factor.&nbsp; O( n log
 463 n) runtime complexity and O(n) memory wrt vertices.</td>
 464           </tr>
 465           <tr>
 466             <td width="586"><font face="Courier New">template
 467 &lt;typename T&gt;<br />
 468 T&amp; <b>scale_down</b>(T&amp; polygon_set, unsigned_area_type factor)</font></td>
 469             <td>Scales geometry down by unsigned factor.&nbsp; Snaps 45
 470 degree edges back to 45 degrees after division truncation leads to
 471 small changes in angle.&nbsp; O( n log n) runtime complexity and O(n)
 472 memory wrt vertices.</td>
 473           </tr>
 474           <tr>
 475             <td width="586"><font face="Courier New">template
 476 &lt;typename T, typename scaling_type&gt;<br />
 477 T&amp; <b>scale</b>(polygon_set_type&amp; polygon_set, double scaling)</font></td>
 478             <td>Scales geometry by multiplying by floating point
 479 factor.&nbsp;&nbsp; Snaps 45 degree edges back to 45 degrees after
 480 truncation of fractional results of multiply leads to small changes in
 481 angle.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 482 vertices.</td>
 483           </tr>
 484           <tr>
 485             <td width="586"><font face="Courier New">template
 486 &lt;typename T, typename transformation_type&gt;<br />
 487 T&amp; <b>transform</b>(T&amp; polygon_set,<br />
 488 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 489 const transformation_type&amp; transformation)</font></td>
 490             <td>Applies transformation.transform() on all
 491 vertices.&nbsp; O( n log n) runtime complexity and O(n) memory wrt
 492 vertices.</td>
 493           </tr>
 494           <tr>
 495             <td width="586"><font face="Courier New">template
 496 &lt;typename T&gt;<br />
 497 T&amp; <b>keep</b>(T&amp; polygon_set, <br />
 498 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type min_area,<br />
 499 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type max_area,<br />
 500 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type min_width,<br />
 501 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type max_width,<br />
 502 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 503 min_height,<br />
 504 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 505 max_height)</font></td>
 506             <td>Retains only regions that satisfy the min/max criteria
 507 in the argument list.&nbsp; Note: useful for visualization to cull too
 508 small polygons.&nbsp; O( n log n) runtime complexity and O(n) memory
 509 wrt vertices.</td>
 510           </tr>
 511         </tbody>
 512       </table>
 513       <h1>Polygon 45 Set Data Object</h1>
 514       <p> </p>
 515       <p>The polygon 45 set data type encapsulates the internal data
 516 format that serves as the input to the sweep-line algorithm that
 517 implements polygon-clipping Boolean operations.&nbsp; It also
 518 internally keeps track of whether that data has been sorted or scanned
 519 and maintains the invariant that when its flags indicate that the data
 520 is sorted or scanned the data has not been changed to violate that
 521 assumption.&nbsp; Using the Polygon 45 Set Data type directly can be
 522 more efficient than using lists and vectors of polygons in the
 523 functions above because of the invariants it can enforce which provide
 524 the opportunity to maintain the data is sorted form rather than going
 525 all the way out to polygons then resorting those vertices for a
 526 subsequent operation.</p>
 527       <p>The declaration of Polygon 45 Set Data is the following:</p>
 528       <p><font face="Courier New">template &lt;typename T&gt;<br />
 529 class polygon_45_set_data;</font></p>
 530       <p>The class is parameterized on the coordinate data type.&nbsp;
 531 Algorithms that benefit from knowledge of the invariants enforced by
 532 the class are implemented as member functions to provide them access to
 533 information about those invariants.&nbsp; </p>
 534       <h2>Member Functions</h2>
 535       <table id="table4" border="1" width="100%">
 536         <tbody>
 537           <tr>
 538             <td width="586"><font face="Courier New"><b>polygon_45_set_data</b>()</font></td>
 539             <td>Default constructor. </td>
 540           </tr>
 541           <tr>
 542             <td width="586"><font face="Courier New">template
 543 &lt;typename iT&gt;<br />
 544             <b>polygon_45_set_data</b>(iT input_begin, iT input_end)</font></td>
 545             <td>Construct from an iterator range of insertable objects.</td>
 546           </tr>
 547           <tr>
 548             <td width="586"><font face="Courier New"> <b>polygon_45_set_data</b>(const
 549 polygon_45_set_data&amp; that)</font></td>
 550             <td>Copy construct.</td>
 551           </tr>
 552           <tr>
 553             <td width="586"><font face="Courier New">template
 554 &lt;typename l, typename r, typename op&gt;<br />
 555             <b>polygon_45_set_data</b>(const
 556 polygon_45_set_view&lt;l,r,op&gt;&amp; t)</font></td>
 557             <td>Copy construct from a Boolean operator template.</td>
 558           </tr>
 559           <tr>
 560             <td width="586"><font face="Courier New">polygon_45_set_data&amp;
 561             <br />
 562             <b>operator=</b>(const polygon_45_set_data&amp; that)</font></td>
 563             <td>Assignment from another polygon set, may change
 564 scanning orientation.</td>
 565           </tr>
 566           <tr>
 567             <td width="586"><font face="Courier New">template
 568 &lt;typename l, typename r, typename op&gt;<br />
 569 polygon_45_set_data&amp; <br />
 570             <b>operator=</b>(const polygon_45_set_view&lt;l, r,
 571 op&gt;&amp; that)</font></td>
 572             <td>Assignment from a Boolean operator template.</td>
 573           </tr>
 574           <tr>
 575             <td width="586"><font face="Courier New">template
 576 &lt;typename geometry_object&gt;<br />
 577 polygon_45_set_data&amp; <b>operator=</b>(const geometry_object&amp;
 578 geo)</font></td>
 579             <td>Assignment from an insertable object.</td>
 580           </tr>
 581           <tr>
 582             <td width="586"><font face="Courier New">
 583 template &lt;typename iT&gt;<br />
 584 void <b>insert</b>(iT input_begin, iT input_end, <br />
 585 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; bool
 586 is_hole = false)</font></td>
 587             <td>Insert objects of an iterator range.&nbsp; If is_hole
 588 is true inserts subtractive regions.&nbsp; Linear wrt the number of
 589 vertices added.</td>
 590           </tr>
 591           <tr>
 592             <td width="586"><font face="Courier New">
 593 void <b>insert</b>(const polygon_45_set_data&amp; polygon_set, <br />
 594 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; bool
 595 is_hole = false)</font></td>
 596             <td>Insert a polygon set.&nbsp; Linear wrt the number of
 597 vertices added.</td>
 598           </tr>
 599           <tr>
 600             <td width="586"><font face="Courier New">
 601 template &lt;typename geometry_type&gt;<br />
 602 void <b>insert</b>(const geometry_type&amp; geometry_object, <br />
 603 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; bool
 604 is_hole = false)</font></td>
 605             <td>Insert a geometry object, if is_hole is true then the
 606 inserted region is subtractive rather than additive.&nbsp; Linear wrt
 607 the number of vertices added.</td>
 608           </tr>
 609           <tr>
 610             <td width="586"><font face="Courier New">template
 611 &lt;typename output_container&gt;<br />
 612 void <b>get</b>(output_container&amp; output) const</font></td>
 613             <td>Expects a standard container of geometry objects.&nbsp;
 614 Will scan and eliminate overlaps.&nbsp; Converts polygon set geometry
 615 to objects of that type and appends them to the container.&nbsp;
 616 Polygons will be output with counterclockwise winding, hole polygons
 617 will be output with clockwise winding.&nbsp; The last vertex of an
 618 output polygon is not the duplicate of the first, and the number of
 619 points is equal to the number of edges.&nbsp; O(n log n) runtime and
 620 O(n) memory wrt. vertices + intersections.</td>
 621           </tr>
 622           <tr>
 623             <td width="586"><font face="Courier New">template
 624 &lt;typename output_container&gt;<br />
 625 void <b>get_polygons</b>(output_container&amp; output) const</font></td>
 626             <td>Expects a standard container of polygon objects.&nbsp;
 627 Will scan and eliminate overlaps.&nbsp; Converts polygon set geometry
 628 to polygons and appends them to the container.&nbsp; Polygons will have
 629 holes fractured out to the outer boundary along the positive y
 630 direction.&nbsp; O(n log n) runtime and O(n) memory wrt. vertices +
 631 intersections.</td>
 632           </tr>
 633           <tr>
 634             <td width="586"><font face="Courier New">template
 635 &lt;typename output_container&gt;<br />
 636 void <b>get_polygons_with_holes</b>(output_container&amp; o) const</font></td>
 637             <td>Expects a standard container of polygon with holes
 638 objects.&nbsp; Will scan and eliminate overlaps.&nbsp; Converts polygon
 639 set geometry to polygons and appends them to the container.&nbsp; O(n
 640 log n) runtime and O(n) memory wrt. vertices + intersections.</td>
 641           </tr>
 642           <tr>
 643             <td width="586"><font face="Courier New">template
 644 &lt;typename output_container&gt;<br />
 645 void <b>get_trapezoids</b>(output_container&amp; output) const</font></td>
 646             <td>Expects a standard container of polygon objects.&nbsp;
 647 Will scan and eliminate overlaps.&nbsp; Slices polygon set geometry to
 648 trapezoids vertically and appends them to the container.&nbsp; O(n log
 649 n) runtime and O(n) memory wrt. vertices + intersections.</td>
 650           </tr>
 651           <tr>
 652             <td width="586"><font face="Courier New">
 653 template &lt;typename output_container&gt;<br />
 654 void <b>get_trapezoids</b>(output_container&amp; output, <br />
 655 &nbsp; orientation_2d slicing_orientation) const </font> </td>
 656             <td>Expects a standard container of polygon objects.&nbsp;
 657 Will scan and eliminate overlaps.&nbsp; Slices polygon set geometry to
 658 trapezoids along the given orientation and appends them to the
 659 container.&nbsp; O(n log n) runtime and O(n) memory wrt. vertices +
 660 intersections.</td>
 661           </tr>
 662           <tr>
 663             <td width="586"><font face="Courier New">
 664 bool <b>operator==</b>(const polygon_45_set_data&amp; p) const</font></td>
 665             <td>Once scanned the data representation of geometry within
 666 a polygon set is in a mathematically canonical form.&nbsp; Comparison
 667 between two sets is therefore a linear time operation once they are in
 668 the scanned state. Will scan and eliminate overlaps in both polygon
 669 sets.&nbsp; O(n log n) runtime and O(n) memory wrt. vertices +
 670 intersections the first time and linear runtime and constant memory
 671 subsequently.&nbsp; </td>
 672           </tr>
 673           <tr>
 674             <td width="586"><font face="Courier New">bool <b>operator!=</b>(const
 675 polygon_45_set_data&amp; p) const</font></td>
 676             <td>Inverse logic of equivalence operator.</td>
 677           </tr>
 678           <tr>
 679             <td width="586"><font face="Courier New">void <b>clear</b>()</font></td>
 680             <td>Make the polygon set empty.&nbsp; Note: does not
 681 de-allocate memory.&nbsp; Use shrink to fit idiom and assign default
 682 constructed polygon set to de-allocate.</td>
 683           </tr>
 684           <tr>
 685             <td width="586"><font face="Courier New">bool <b>empty</b>()
 686 const </font> </td>
 687             <td>Check whether the polygon set contains no
 688 geometry.&nbsp; Will scan and eliminate overlaps because subtractive
 689 regions might make the polygon set empty.&nbsp; O(n log n) runtime and
 690 O(n) memory wrt. vertices + intersections the first time and linear
 691 runtime and constant memory subsequently.&nbsp; </td>
 692           </tr>
 693           <tr>
 694             <td width="586"><font face="Courier New">bool <b>is_manhattan</b>()
 695 const</font></td>
 696             <td>Returns in constant time the information about whether
 697 the geometry contains only Manhattan (axis-parallel rectilinear)
 698 edges.&nbsp; Constant time.</td>
 699           </tr>
 700           <tr>
 701             <td width="586"><font face="Courier New">void <b>clean</b>()
 702 const</font></td>
 703             <td>Scan and eliminate overlaps.&nbsp; O(n log n) runtime
 704 and O(n) memory wrt. vertices + intersections the first time and linear
 705 runtime and constant memory subsequently.&nbsp; </td>
 706           </tr>
 707           <tr>
 708             <td width="586"><font face="Courier New">template
 709 &lt;typename input_iterator_type&gt;<br />
 710 void <b>set</b>(input_iterator_type input_begin, <br />
 711 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; input_iterator_type
 712 input_end) </font> </td>
 713             <td>Overwrite geometry in polygon set with insertable
 714 objects in the iterator range.&nbsp; </td>
 715           </tr>
 716           <tr>
 717             <td width="586"><font face="Courier New">template
 718 &lt;typename rectangle_type&gt;<br />
 719 bool <b>extents</b>(rectangle_type&amp; extents_rectangle) const</font></td>
 720             <td>Given an object that models rectangle, scans and
 721 eliminates overlaps in the polygon set because subtractive regions may
 722 alter its extents then computes the bounding box and assigns it to
 723 extents_rectangle.&nbsp; O(n log n) runtime and O(n) memory wrt.
 724 vertices the first time and linear runtime and constant memory
 725 subsequently.&nbsp; </td>
 726           </tr>
 727           <tr>
 728             <td width="586"><font face="Courier New">polygon_45_set_data&amp;<br />
 729             <b>resize</b>(coord_type resizing,<br />
 730 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; RoundingOption rounding = CLOSEST,
 731             <br />
 732 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; CornerOption corner = INTERSECTION)</font></td>
 733             <td>Same as bloat if resizing is positive, same as shrink
 734 if resizing is negative.&nbsp; RoundingOption is an enum that controls
 735 snapping of non-integer results of resizing 45 degree edges.&nbsp;
 736 CornerOption is an enum that controls how corner filling is
 737 performed.&nbsp; polygon_45_set_data.hpp defines these enums.&nbsp; O(n
 738 log n) runtime and O(n) memory wrt. vertices + intersections.</td>
 739           </tr>
 740           <tr>
 741             <td width="586"><font face="Courier New">template
 742 &lt;typename transformation_type&gt;<br />
 743 polygon_45_set_data&amp; <br />
 744             <b>transform</b>(const transformation_type&amp;
 745 transformation) </font> </td>
 746             <td>Applies transformation.transform() on vertices stored
 747 within the polygon set.&nbsp; O(n log n) runtime and O(n) memory wrt.
 748 vertices + intersections.</td>
 749           </tr>
 750           <tr>
 751             <td width="586"><font face="Courier New">polygon_45_set_data&amp;
 752             <b>scale_up</b>(unsigned_area_type factor)</font></td>
 753             <td>Scales vertices stored within the polygon set up by
 754 factor.&nbsp; Linear wrt vertices.</td>
 755           </tr>
 756           <tr>
 757             <td width="586"><font face="Courier New">polygon_45_set_data&amp;
 758             <b>scale_down</b>(unsigned_area_type factor)</font>&nbsp;</td>
 759             <td>Scales vertices stored within the polygon set down by
 760 factor.&nbsp; Linear wrt vertices.</td>
 761           </tr>
 762           <tr>
 763             <td width="586"><font face="Courier New">polygon_45_set_data&amp;
 764             <b>scale</b>(double factor) </font></td>
 765             <td>Scales vertices stored within the polygon set by
 766 floating point factor.&nbsp; Linear wrt vertices.</td>
 767           </tr>
 768           <tr>
 769             <td width="586"><font face="Courier New">polygon_45_set_data&amp;
 770             <b>self_xor</b>()</font></td>
 771             <td>Retain only non-overlapping regions of geometry within
 772 polygon set.&nbsp; O(n log n) runtime and O(n) memory wrt. vertices +
 773 intersections.</td>
 774           </tr>
 775           <tr>
 776             <td width="586"><font face="Courier New">polygon_45_set_data&amp;
 777             <b>self_intersect</b>()</font></td>
 778             <td>Retain only overlapping regions of geometry within a
 779 polygon set.&nbsp; O(n log n) runtime and O(n) memory wrt. vertices +
 780 intersections.</td>
 781           </tr>
 782           <tr>
 783             <td width="586"><font face="Courier New">bool <b>has_error_data</b>()
 784 const </font></td>
 785             <td>Returns true if non-integer intersections resulted in
 786 small artifacts in the output of a boolean.&nbsp; Constant time.</td>
 787           </tr>
 788           <tr>
 789             <td width="586"><font face="Courier New">std::size_t <b>error_count</b>()
 790 const</font></td>
 791             <td>Returns the number of artifacts that may potentially be
 792 present in the output due to non-integer intersections.&nbsp; Constant
 793 time.</td>
 794           </tr>
 795           <tr>
 796             <td width="586"><font face="Courier New">void <b>get_error_data</b>(polygon_45_set_data&amp;
 797 p) const</font></td>
 798             <td>Populates the input polygon set with 1x1 unit squares
 799 that bound the error that may be present in the output due to
 800 non-integer intersections.&nbsp; Linear wrt. vertices of error data.</td>
 801           </tr>
 802           <tr>
 803             <td width="586"><font face="Courier New">polygon_45_set_data&amp;
 804             <b>self_intersect</b>()</font></td>
 805             <td>Retain only overlapping regions of geometry within a
 806 polygon set.&nbsp; O(n log n) runtime and O(n) memory wrt. vertices +
 807 intersections.</td>
 808           </tr>
 809         </tbody>
 810       </table>
 811       </td>
 812     </tr>
 813     <tr>
 814       <td style="background-color: rgb(238, 238, 238);" nowrap="1"
 815  valign="top"> &nbsp;</td>
 816       <td
 817  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
 818  valign="top" width="100%">
 819       <table class="docinfo" id="table6" frame="void" rules="none">
 820         <colgroup> <col class="docinfo-name" /><col
 821  class="docinfo-content" /> </colgroup> <tbody valign="top">
 822           <tr>
 823             <th class="docinfo-name">Copyright:</th>
 824             <td>Copyright © Intel Corporation 2008-2010.</td>
 825           </tr>
 826           <tr class="field">
 827             <th class="docinfo-name">License:</th>
 828             <td class="field-body">Distributed under the Boost Software
 829 License, Version 1.0. (See accompanying file <tt class="literal"> <span
 830  class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
 831  class="reference" target="_top"
 832  href="http://www.boost.org/LICENSE_1_0.txt">
 833 http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 834           </tr>
 835         </tbody>
 836       </table>
 837       </td>
 838     </tr>
 839   </tbody>
 840 </table>
 841 </body>
 842 </html>