ceph/src/boost/libs/polygon/doc/gtl_polygon_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 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><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
  49 Concept</a></li>
  50         <li>Polygon Set Concept</li>
  51         <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
  52 Extraction 90</a></li>
  53         <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
  54 Extraction 45</a></li>
  55         <li><a href="gtl_connectivity_extraction.htm">Connectivity
  56 Extraction</a></li>
  57         <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
  58         <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
  59         <li><a href="gtl_property_merge.htm">Property Merge</a></li>
  60         <li><a href="voronoi_main.htm">Voronoi Main Page<br />
  61           </a></li>
  62         <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br />
  63         </li>
  64         <li><a href="voronoi_builder.htm">Voronoi Builder</a></li>
  65         <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
  66       </ul>
  67       <h3 class="navbar">Other Resources</h3>
  68       <ul>
  69         <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
  70         <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
  71 Presentation</a></li>
  72         <li><a href="analysis.htm">Performance Analysis</a></li>
  73         <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
  74         <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
  75         <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
  76         <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
  77 Tutorial</a></li>
  78       </ul>
  79       </div>
  80       <h3 class="navbar">Polygon Sponsor</h3>
  81       <div style="padding: 5px;" align="center"> <img
  82  src="images/intlogo.gif" border="0" height="51" width="127" /><a
  83  title="www.adobe.com home page" href="http://www.adobe.com/"
  84  tabindex="2" style="border: medium none ;"> </a> </div>
  85       </td>
  86       <td
  87  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
  88  valign="top" width="100%">
  89 <!-- End Header --><br />
  90       <p>
  91       </p>
  92       <h1>Polygon Set Concept</h1>
  93       <p> </p>
  94       <p>The polygon_set concept tag is <font face="Courier New">
  95 polygon_set_concept</font></p>
  96       <p> <font face="Times New Roman">The semantic of a polygon_set
  97 is zero or more geometry regions.&nbsp; A Polygon Set Concept may be
  98 defined with floating point coordinates, but a snap rounding distance
  99 of one integer unit will still be applied, furthermore, geometry
 100 outside the domain where one integer unit is sufficient to provide
 101 robustness may lead to undefined behavior in algorithms.&nbsp; It is
 102 recommended to use integer coordinates for robust operations.&nbsp; In
 103 the case that data represented contains only Manhattan geometry a
 104 runtime check will default to the Manhattan algorithm.&nbsp; The
 105 results of which are identical to what the general algorithm would do,
 106 but obtained more efficiently.&nbsp; In the case that the data
 107 represented contains only Manhattan and 45-degree geometry a runtime
 108 check will default to the faster 45-degree algorithm.&nbsp; The results
 109 of which may differ slight from what the general algorithm would do
 110 because non-integer intersections will be handled differently.</font></p>
 111       <p>Users are recommended to use std::vector and std::list of user
 112 defined polygons or library provided
 113 polygon_set_data&lt;coordinate_type&gt; objects.&nbsp; Lists and
 114 vectors of models of polygon_concept or polygon_with_holes_concept are
 115 automatically models of polygon_set_concept.</p>
 116       <p>Example code <a href="gtl_custom_polygon_set.htm">custom_polygon_set.cpp</a>
 117 demonstrates mapping a user defined class to the library
 118 polygon_set_concept</p>
 119       <p>An object that is a model of <font face="Courier New">
 120 polygon_set_concept</font> can be viewed as a model of <font
 121  face="Courier New">
 122 polygon_90_set_concept</font> or <font face="Courier New">
 123 polygon_45_set_concept</font> if it is determined at runtime to conform
 124 to the restrictions of those concepts.&nbsp; This concept casting is
 125 accomplished through the <font face="Courier New">view_as&lt;&gt;()</font>
 126 function.</p>
 127       <p><font face="Courier New">view_as&lt;polygon_90_set_concept&gt;(polygon_set_object)<br />
 128 view_as&lt;polygon_45_set_concept&gt;(polygon_set_object)</font></p>
 129       <p>The return value of <font face="Courier New">view_as&lt;&gt;()</font>
 130 can be passed into any interface that expects an object of the
 131 conceptual type specified in its template parameter.&nbsp; Polygon sets
 132 cannot be viewed as single polygons or rectangles since it generally
 133 cannot be known whether a polygon set contains only a single polygon
 134 without converting to polygons.</p>
 135       <h2>Operators</h2>
 136       <p>The return type of some operators is the <font
 137  face="Courier New">polygon_set_view</font> operator template
 138 type.&nbsp; This type is itself a model of the polygon 90 set concept,
 139 but furthermore can be used as an argument to the <font
 140  face="Courier New">polygon_set_data</font> constructor and assignment
 141 operator.&nbsp; The operator template exists to eliminate temp copies
 142 of intermediate results when Boolean operators are chained together.</p>
 143       <p>Operators are declared inside the namespace <font
 144  face="Courier New">boost::polygon::operators</font>.</p>
 145       <table id="table5" border="1" width="100%">
 146         <tbody>
 147           <tr>
 148             <td width="586"><font face="Courier New">template
 149 &lt;typename T1, typename T2&gt;<br />
 150 polygon_set_view <b>operator</b>|(const T1&amp; l, const T2&amp; r)</font></td>
 151             <td>Boolean OR operation (polygon set union).&nbsp; Accepts
 152 two objects that model polygon_set or one of its refinements.&nbsp;
 153 Returns an operator template that performs the operation on demand when
 154 chained or or nested in a library function call such as assign().&nbsp;
 155 Expected n log n runtime, worst case quadratic runtime wrt. vertices +
 156 intersections.</td>
 157           </tr>
 158           <tr>
 159             <td width="586"><font face="Courier New">template
 160 &lt;typename T1, typename T2&gt;<br />
 161 polygon_set_view <b>operator</b>+(const T1&amp; l, const T2&amp; r)</font></td>
 162             <td>Same as operator|.&nbsp; The plus sign is also used for
 163 OR operations in Boolean logic expressions.&nbsp; Expected n log n
 164 runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
 165           </tr>
 166           <tr>
 167             <td width="586"><font face="Courier New">template
 168 &lt;typename T1, typename T2&gt;<br />
 169 polygon_set_view <b>operator</b>&amp;(const T1&amp; l, const T2&amp; r)</font></td>
 170             <td>Boolean AND operation (polygon set intersection).&nbsp;
 171 Accepts two objects that model polygon_set or one of its
 172 refinements.&nbsp; Expected n log n runtime, worst case quadratic
 173 runtime wrt. vertices + intersections.</td>
 174           </tr>
 175           <tr>
 176             <td width="586"><font face="Courier New">template
 177 &lt;typename T1, typename T2&gt;<br />
 178 polygon_set_view <b>operator</b>*(const T1&amp; l, const T2&amp; r)</font></td>
 179             <td>Same as operator&amp;.&nbsp; The multiplication symbol
 180 is also used for AND operations in Boolean logic expressions.&nbsp;
 181 Expected n log n runtime, worst case quadratic runtime wrt. vertices +
 182 intersections.</td>
 183           </tr>
 184           <tr>
 185             <td width="586"><font face="Courier New">template
 186 &lt;typename T1, typename T2&gt;<br />
 187 polygon_set_view <b>operator</b>^(const T1&amp; l, const T2&amp; r)</font></td>
 188             <td>Boolean XOR operation (polygon set
 189 disjoint-union).&nbsp; Accepts two objects that model polygon_set or
 190 one of its refinements.&nbsp; Expected n log n runtime, worst case
 191 quadratic runtime wrt. vertices + intersections.</td>
 192           </tr>
 193           <tr>
 194             <td width="586"><font face="Courier New">template
 195 &lt;typename T1, typename T2&gt;<br />
 196 polygon_set_view <b>operator</b>-(const T1&amp; l, const T2&amp; r)</font></td>
 197             <td>Boolean SUBTRACT operation (polygon set
 198 difference).&nbsp; Accepts two objects that model polygon_set or one of
 199 its refinements.&nbsp; Expected n log n runtime, worst case quadratic
 200 runtime wrt. vertices + intersections.</td>
 201           </tr>
 202           <tr>
 203             <td width="586"><font face="Courier New">template
 204 &lt;typename T1, typename T2&gt;<br />
 205 T1&amp; <b>operator</b>|=(const T1&amp; l, const T2&amp; r)</font></td>
 206             <td>Same as operator|, but with self assignment, left
 207 operand must model polygon_set and not one of it's refinements.&nbsp;
 208 Expected n log n runtime, worst case quadratic runtime wrt. vertices +
 209 intersections.</td>
 210           </tr>
 211           <tr>
 212             <td width="586"><font face="Courier New">template
 213 &lt;typename T1, typename T2&gt;<br />
 214 T1&amp; <b>operator</b>+=(T1&amp; l, const T2&amp; r)</font></td>
 215             <td>Same as operator+, but with self assignment, left
 216 operand must model polygon_set and not one of it's refinements.&nbsp;
 217 Expected n log n runtime, worst case quadratic runtime wrt. vertices +
 218 intersections.</td>
 219           </tr>
 220           <tr>
 221             <td width="586"><font face="Courier New">template
 222 &lt;typename T1, typename T2&gt;<br />
 223 T1&amp; <b>operator</b>&amp;=(const T1&amp; l, const T2&amp; r)</font></td>
 224             <td>Same as operator&amp;, but with self assignment, left
 225 operand must model polygon_set and not one of it's refinements.&nbsp;
 226 Expected n log n runtime, worst case quadratic runtime wrt. vertices +
 227 intersections.</td>
 228           </tr>
 229           <tr>
 230             <td width="586"><font face="Courier New">template
 231 &lt;typename T1, typename T2&gt;<br />
 232 T1&amp; <b>operator</b>*=(T1&amp; l, const T2&amp; r)</font></td>
 233             <td>Same as operator*, but with self assignment, left
 234 operand must model polygon_set and not one of it's refinements.&nbsp;
 235 Expected n log n runtime, worst case quadratic runtime wrt. vertices +
 236 intersections.</td>
 237           </tr>
 238           <tr>
 239             <td width="586"><font face="Courier New">template
 240 &lt;typename T1, typename T2&gt;<br />
 241 T1&amp; <b>operator</b>^=(const T1&amp; l, const T2&amp; r)</font></td>
 242             <td>Same as operator^, but with self assignment, left
 243 operand must model polygon_set and not one of it's refinements.&nbsp;
 244 Expected n log n runtime, worst case quadratic runtime wrt. vertices +
 245 intersections.</td>
 246           </tr>
 247           <tr>
 248             <td width="586"><font face="Courier New">template
 249 &lt;typename T1, typename T2&gt;<br />
 250 T1&amp; <b>operator</b>-=(T1&amp; l, const T2&amp; r)</font></td>
 251             <td>Same as operator-, but with self assignment, left
 252 operand must model polygon_set and not one of it's refinements.&nbsp;
 253 Expected n log n runtime, worst case quadratic runtime wrt. vertices +
 254 intersections.</td>
 255           </tr>
 256           <tr>
 257             <td width="586"><font face="Courier New">template
 258 &lt;typename T1&gt;<br />
 259 T1 <b>operator</b>+(const T1&amp;, coordinate_type bloating)</font></td>
 260             <td>Performs resize operation, inflating by bloating
 261 ammount.&nbsp; If negative the result is a shrink instead of
 262 bloat.&nbsp; Note: returns result by value.&nbsp; Expected n log n
 263 runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
 264           </tr>
 265           <tr>
 266             <td width="586"><font face="Courier New">template
 267 &lt;typename T1, typename T2&gt;<br />
 268 T1 <b>operator</b>-(const T1&amp;, coordinate_type shrinking)</font></td>
 269             <td>Performs resize operation, deflating by bloating
 270 ammount.&nbsp; If negative the result is a bloat instead of
 271 shrink.&nbsp; Note: returns result by value.&nbsp; Expected n log n
 272 runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
 273           </tr>
 274           <tr>
 275             <td width="586"><font face="Courier New">template
 276 &lt;typename T1, typename T2&gt;<br />
 277 T1&amp; <b>operator</b>+=(const T1&amp;, coordinate_type bloating)</font></td>
 278             <td>Performs resize operation, inflating by bloating
 279 ammount.&nbsp; If negative the result is a shrink instead of
 280 bloat.&nbsp; Returns reference to modified argument.&nbsp; Expected n
 281 log n runtime, worst case quadratic runtime wrt. vertices +
 282 intersections.</td>
 283           </tr>
 284           <tr>
 285             <td width="586"><font face="Courier New">template
 286 &lt;typename T1, typename T2&gt;<br />
 287 T1&amp; <b>operator</b>-=(const T1&amp;, coordinate_type shrinking)</font></td>
 288             <td>Performs resize operation, deflating by bloating
 289 ammount.&nbsp; If negative the result is a bloat instead of
 290 shrink.&nbsp; Returns reference to modified argument.&nbsp; Expected n
 291 log n runtime, worst case quadratic runtime wrt. vertices +
 292 intersections.</td>
 293           </tr>
 294         </tbody>
 295       </table>
 296       <h2>Functions</h2>
 297       <table id="table6" border="1" width="100%">
 298         <tbody>
 299           <tr>
 300             <td width="586"><font face="Courier New">template
 301 &lt;typename T1, typename T2&gt;<br />
 302 T1&amp; <b>assign</b>(T1&amp; lvalue, const T2&amp; rvalue)</font></td>
 303             <td>Eliminates overlaps in geometry and copies from an
 304 object that models polygon_set or any of its refinements into an object
 305 that models polygon_set.&nbsp; Expected n log n runtime, worst case
 306 quadratic runtime wrt. vertices + intersections.</td>
 307           </tr>
 308           <tr>
 309             <td width="586"><font face="Courier New">template
 310 &lt;typename T1, typename T2&gt;<br />
 311 bool <b>equivalence</b>(const T1&amp; lvalue, const T2&amp; rvalue) </font></td>
 312             <td>Returns true if an object that models polygon_set or
 313 one of its refinements covers the exact same geometric regions as
 314 another object that models polygon_set or one of its refinements.&nbsp;
 315 For example: two of polygon objects.&nbsp; Expected n log n runtime,
 316 worst case quadratic runtime wrt. vertices + intersections.</td>
 317           </tr>
 318           <tr>
 319             <td width="586"><font face="Courier New">template
 320 &lt;typename output_container_type, typename T&gt;<br />
 321 void <b>get_trapezoids</b>(output_container_type&amp; output, <br />
 322 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 323 const T&amp; polygon_set)</font></td>
 324             <td>Output container is expected to be a standard
 325 container.&nbsp; Slices geometry of an object that models polygon_set
 326 or one of its refinements into non overlapping trapezoids along a
 327 vertical slicing orientation and appends them to the output, which must
 328 have a value type that models polygon or polygon_with_holes.&nbsp;
 329 Expected n log n runtime, worst case quadratic runtime wrt. vertices +
 330 intersections.</td>
 331           </tr>
 332           <tr>
 333             <td width="586"><font face="Courier New">template
 334 &lt;typename output_container_type, typename T&gt;<br />
 335 void <b>get_trapezoids</b>(output_container_type&amp; output, <br />
 336 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 337 const T&amp; polygon_set,<br />
 338 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 339 orientation_2d orient)</font></td>
 340             <td>Output container is expected to be a standard
 341 container.&nbsp; Slices geometry of an object that models polygon_set
 342 or one of its refinements into non overlapping trapezoids along a the
 343 specified slicing orientation and appends them to the output, which
 344 must have a value type that models polygon or polygon_with_holes.&nbsp;
 345 Expected n log n runtime, worst case quadratic runtime wrt. vertices +
 346 intersections.</td>
 347           </tr>
 348           <tr>
 349             <td width="586"><font face="Courier New">template
 350 &lt;typename polygon_set_type&gt;<br />
 351 void <b>clear</b>(polygon_set_type&amp; polygon_set)</font></td>
 352             <td>Makes the object empty of geometry.</td>
 353           </tr>
 354           <tr>
 355             <td width="586"><font face="Courier New">template
 356 &lt;typename polygon_set_type&gt;<br />
 357 bool <b>empty</b>(const polygon_set_type&amp; polygon_set)</font></td>
 358             <td>Checks whether the object is empty of geometry.&nbsp;
 359 Polygons that are completely covered by holes will result in empty
 360 returning true.&nbsp; Expected n log n runtime, worst case quadratic
 361 runtime wrt. vertices + intersections.</td>
 362           </tr>
 363           <tr>
 364             <td width="586"><font face="Courier New">template
 365 &lt;typename T, typename rectangle_type&gt;<br />
 366 bool <b>extents</b>(rectangle_type&amp; extents_rectangle, <br />
 367 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 368 const T&amp; polygon_set)</font></td>
 369             <td>Computes bounding box of an object that models
 370 polygon_set and stores it in an object that models rectangle.&nbsp; If
 371 the polygon set is empty returns false.&nbsp; If there are holes
 372 outside of shells they do not contribute to the extents of the polygon
 373 set.&nbsp; Expected n log n runtime, worst case quadratic runtime wrt.
 374 vertices + intersections.</td>
 375           </tr>
 376           <tr>
 377             <td width="586"><font face="Courier New">template
 378 &lt;typename T&gt;<br />
 379 area_type <b>area</b>(const T&amp; polygon_set)</font></td>
 380             <td>Computes the area covered by geometry in an object that
 381 models polygon_set.&nbsp; Expected n log n runtime, worst case
 382 quadratic runtime 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, unsigned_area_type bloating)</font></td>
 388             <td>Same as getting all the polygons, bloating them and
 389 putting them back.&nbsp; Expected n log n runtime, worst case quadratic
 390 runtime wrt. vertices + intersections.</td>
 391           </tr>
 392           <tr>
 393             <td width="586"><font face="Courier New">template
 394 &lt;typename T&gt;<br />
 395 T&amp; <b>shrink</b>(T&amp; polygon_set, unsigned_area_type shrinking)</font></td>
 396             <td>Same as getting all the polygons, shrinking them and
 397 overwriting the polygon set with the resulting regions.&nbsp; Expected
 398 n log n runtime, worst case quadratic runtime wrt. vertices +
 399 intersections.</td>
 400           </tr>
 401           <tr>
 402             <td width="586"><font face="Courier New">template
 403 &lt;typename T, typename coord_type&gt;<br />
 404 T&amp; <b>resize</b>(T&amp; polygon_set, coord_type resizing,<br />
 405 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; bool
 406 corner_fill_arc = false, <br />
 407 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned int
 408 num_circle_segments = 0)</font></td>
 409             <td>Same as bloat if resizing is positive, same as shrink
 410 if resizing is negative.&nbsp; Original topology at acute angle
 411 vertices is preserved by default, segmented circular arcs are inserted
 412 if corner_fill_arc is true.&nbsp; num_circle_segments specifies number
 413 of segments to introduce on a full circle when filling acute angle
 414 corners with circular arcs.&nbsp; Expected n log n runtime, worst case
 415 quadratic runtime 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>scale_up</b>(T&amp; polygon_set, unsigned_area_type factor)</font></td>
 421             <td>Scales geometry up by unsigned factor.&nbsp; Expected n
 422 log n runtime, worst case quadratic runtime wrt. vertices +
 423 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>scale_down</b>(T&amp; polygon_set, unsigned_area_type factor)</font></td>
 429             <td>Scales geometry down by unsigned factor.&nbsp; Expected
 430 n log n runtime, worst case quadratic runtime wrt. vertices +
 431 intersections.</td>
 432           </tr>
 433           <tr>
 434             <td width="586"><font face="Courier New">template
 435 &lt;typename T, typename transformation_type&gt;<br />
 436 T&amp; <b>transform</b>(T&amp; polygon_set,<br />
 437 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 438 const transformation_type&amp; transformation)</font></td>
 439             <td>Applies transformation.transform() on all
 440 vertices.&nbsp; Expected n log n runtime, worst case quadratic runtime
 441 wrt. vertices + intersections.</td>
 442           </tr>
 443           <tr>
 444             <td width="586"><font face="Courier New">template
 445 &lt;typename T&gt;<br />
 446 T&amp; <b>keep</b>(T&amp; polygon_set, <br />
 447 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type min_area,<br />
 448 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type max_area,<br />
 449 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type min_width,<br />
 450 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type max_width,<br />
 451 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 452 min_height,<br />
 453 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned_area_type
 454 max_height)</font></td>
 455             <td>Retains only regions that satisfy the min/max criteria
 456 in the argument list.&nbsp; Note: useful for visualization to cull too
 457 small polygons.&nbsp; Expected n log n runtime, worst case quadratic
 458 runtime wrt. vertices + intersections.</td>
 459           </tr>
 460         </tbody>
 461       </table>
 462       <h1>Polygon Set Data Object</h1>
 463       <p> </p>
 464       <p>The polygon set data type encapsulates the internal data
 465 format that serves as the input to the sweep-line algorithm that
 466 implements polygon-clipping Boolean operations.&nbsp; It also
 467 internally keeps track of whether that data has been sorted or scanned
 468 and maintains the invariant that when its flags indicate that the data
 469 is sorted or scanned the data has not been changed to violate that
 470 assumption.&nbsp; Using the Polygon Set Data type directly can be more
 471 efficient than using lists and vectors of polygons in the functions
 472 above because of the invariants it can enforce which provide the
 473 opportunity to maintain the data is sorted form rather than going all
 474 the way out to polygons then resorting those vertices for a subsequent
 475 operation.</p>
 476       <p>The declaration of Polygon Set Data is the following:</p>
 477       <p><font face="Courier New">template &lt;typename T&gt;<br />
 478 class polygon_set_data;</font></p>
 479       <p>The class is parameterized on the coordinate data type.&nbsp;
 480 Algorithms that benefit from knowledge of the invariants enforced by
 481 the class are implemented as member functions to provide them access to
 482 information about those invariants.&nbsp; </p>
 483       <p>Example code <a href="gtl_polygon_set_usage.htm">polygon_set_usage.cpp</a>
 484 demonstrates using the library provided polygon set data types and
 485 functions</p>
 486       <h2>Member Functions</h2>
 487       <table id="table7" border="1" width="100%">
 488         <tbody>
 489           <tr>
 490             <td width="586"><font face="Courier New"><b>polygon_set_data</b>()</font></td>
 491             <td>Default constructor. </td>
 492           </tr>
 493           <tr>
 494             <td width="586"><font face="Courier New">template
 495 &lt;typename iT&gt;<br />
 496             <b>polygon_set_data</b>(iT input_begin, iT input_end)</font></td>
 497             <td>Construct with scanning orientation from an iterator
 498 range of insertable objects.</td>
 499           </tr>
 500           <tr>
 501             <td width="586"><font face="Courier New"> <b>polygon_set_data</b>(const
 502 polygon_set_data&amp; that)</font></td>
 503             <td>Copy construct.</td>
 504           </tr>
 505           <tr>
 506             <td width="586"><font face="Courier New">template
 507 &lt;typename l, typename r, typename op&gt;<br />
 508             <b>polygon_set_data</b>(const
 509 polygon_set_view&lt;l,r,op&gt;&amp; t)</font></td>
 510             <td>Copy construct from a Boolean operator template.</td>
 511           </tr>
 512           <tr>
 513             <td width="586"><font face="Courier New">polygon_set_data&amp;
 514             <br />
 515             <b>operator=</b>(const polygon_set_data&amp; that)</font></td>
 516             <td>Assignment from another polygon set, may change
 517 scanning orientation.</td>
 518           </tr>
 519           <tr>
 520             <td width="586"><font face="Courier New">template
 521 &lt;typename l, typename r, typename op&gt;<br />
 522 polygon_set_data&amp; <br />
 523             <b>operator=</b>(const polygon_set_view&lt;l, r,
 524 op&gt;&amp; that)</font></td>
 525             <td>Assignment from a Boolean operator template.</td>
 526           </tr>
 527           <tr>
 528             <td width="586"><font face="Courier New">template
 529 &lt;typename geometry_object&gt;<br />
 530 polygon_set_data&amp; <b>operator=</b>(const geometry_object&amp; geo)</font></td>
 531             <td>Assignment from an insertable object.</td>
 532           </tr>
 533           <tr>
 534             <td width="586"><font face="Courier New">
 535 template &lt;typename iT&gt;<br />
 536 void <b>insert</b>(iT input_begin, iT input_end)</font></td>
 537             <td>Insert objects of an iterator range.&nbsp; Linear wrt
 538 vertices inserted.</td>
 539           </tr>
 540           <tr>
 541             <td width="586"><font face="Courier New">
 542 void <b>insert</b>(const polygon_set_data&amp; polygon_set)</font></td>
 543             <td>Insert a polygon set.&nbsp; Linear wrt vertices
 544 inserted.</td>
 545           </tr>
 546           <tr>
 547             <td width="586"><font face="Courier New">
 548 template &lt;typename geometry_type&gt;<br />
 549 void <b>insert</b>(const geometry_type&amp; geometry_object, <br />
 550 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; bool
 551 is_hole = false)</font></td>
 552             <td>Insert a geometry object, if is_hole is true then the
 553 inserted region is subtractive rather than additive.&nbsp; Linear wrt
 554 vertices inserted.</td>
 555           </tr>
 556           <tr>
 557             <td width="586"><font face="Courier New">template
 558 &lt;typename output_container&gt;<br />
 559 void <b>get</b>(output_container&amp; output) const</font></td>
 560             <td>Expects a standard container of polygons objects.&nbsp;
 561 Will scan and eliminate overlaps.&nbsp; Converts polygon set geometry
 562 to objects of the polygon type and appends them to the container.&nbsp;
 563 Polygons will be output with counterclockwise winding, hole polygons
 564 will be output with clockwise winding.&nbsp; The last vertex of an
 565 output polygon is the duplicate of the first, and the number of points
 566 is equal to the number of edges plus 1.&nbsp; If required by the output
 567 data type, polygons will have holes fractured out to the outer boundary
 568 along the positive y direction and off grid intersections on the outer
 569 boundary introduced by this fracture will be truncated downward.&nbsp;
 570 Expected n log n runtime, worst case quadratic runtime wrt. vertices +
 571 intersections.</td>
 572           </tr>
 573           <tr>
 574             <td width="586"><font face="Courier New">template
 575 &lt;typename output_container&gt;<br />
 576 void <b>get_trapezoids</b>(output_container&amp; output) const</font></td>
 577             <td>Expects a standard container of polygon objects.&nbsp;
 578 Will scan and eliminate overlaps.&nbsp; Slices polygon set geometry to
 579 trapezoids vertically and appends them to the container.&nbsp; Expected
 580 n log n runtime, worst case quadratic runtime wrt. vertices +
 581 intersections.</td>
 582           </tr>
 583           <tr>
 584             <td width="586"><font face="Courier New">
 585 template &lt;typename output_container&gt;<br />
 586 void <b>get_trapezoids</b>(output_container&amp; output, <br />
 587 &nbsp; orientation_2d slicing_orientation) const </font> </td>
 588             <td>Expects a standard container of polygon objects.&nbsp;
 589 Will scan and eliminate overlaps.&nbsp; Slices polygon set geometry to
 590 trapezoids along the given orientation and appends them to the
 591 container.&nbsp; Expected n log n runtime, worst case quadratic runtime
 592 wrt. vertices + intersections.</td>
 593           </tr>
 594           <tr>
 595             <td width="586"><font face="Courier New">
 596 bool <b>operator==</b>(const polygon_set_data&amp; p) const</font></td>
 597             <td>Once scanned the data representation of geometry within
 598 a polygon set is in a mathematically canonical form.&nbsp; Comparison
 599 between two sets is therefore a linear time operation once they are in
 600 the scanned state. Will scan and eliminate overlaps in both polygon
 601 sets.&nbsp; Expected n log n runtime, worst case quadratic runtime wrt.
 602 vertices + intersections.&nbsp; </td>
 603           </tr>
 604           <tr>
 605             <td width="586"><font face="Courier New">bool <b>operator!=</b>(const
 606 polygon_set_data&amp; p) const</font></td>
 607             <td>Inverse logic of equivalence operator.</td>
 608           </tr>
 609           <tr>
 610             <td width="586"><font face="Courier New">void <b>clear</b>()</font></td>
 611             <td>Make the polygon set empty.&nbsp; Note: does not
 612 de-allocate memory.&nbsp; Use shrink to fit idiom and assign default
 613 constructed polygon set to de-allocate.</td>
 614           </tr>
 615           <tr>
 616             <td width="586"><font face="Courier New">bool <b>empty</b>()
 617 const </font> </td>
 618             <td>Check whether the polygon set contains no
 619 geometry.&nbsp; Will scan and eliminate overlaps because subtractive
 620 regions might make the polygon set empty.&nbsp; Expected n log n
 621 runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
 622           </tr>
 623           <tr>
 624             <td width="586"><font face="Courier New">void <b>clean</b>()
 625 const</font></td>
 626             <td>Scan and eliminate overlaps.&nbsp; Expected n log n
 627 runtime, worst case quadratic runtime wrt. vertices + intersections the
 628 first time, constant time subsequently.</td>
 629           </tr>
 630           <tr>
 631             <td width="586"><font face="Courier New">template
 632 &lt;typename input_iterator_type&gt;<br />
 633 void <b>set</b>(input_iterator_type input_begin, <br />
 634 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; input_iterator_type
 635 input_end) </font> </td>
 636             <td>Overwrite geometry in polygon set with insertable
 637 objects in the iterator range. </td>
 638           </tr>
 639           <tr>
 640             <td width="586"><font face="Courier New">template
 641 &lt;typename rectangle_type&gt;<br />
 642 bool <b>extents</b>(rectangle_type&amp; extents_rectangle) const</font></td>
 643             <td>Given an object that models rectangle, scans and
 644 eliminates overlaps in the polygon set because subtractive regions may
 645 alter its extents then computes the bounding box and assigns it to
 646 extents_rectangle.&nbsp; Expected n log n runtime, worst case quadratic
 647 runtime wrt. vertices + intersections the first time, linear
 648 subsequently.</td>
 649           </tr>
 650           <tr>
 651             <td width="586"><font face="Courier New">polygon_set_data&amp;<br />
 652             <b>resize</b>(coord_type resizing,<br />
 653 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; bool corner_fill_arc = false, <br />
 654 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; unsigned int num_circle_segments =
 655 0)</font></td>
 656             <td>Inflates if resizing is positive, deflates if resizing
 657 is negative.&nbsp; Original topology at acute angle vertices is
 658 preserved by default, segmented circular arcs are inserted if
 659 corner_fill_arc is true.&nbsp; num_circle_segments specifies number of
 660 segments to introduce on a full circle when filling acute angle corners
 661 with circular arcs.&nbsp; Specifying zero for num_circle_segments
 662 results in only a single segment being inserted at acute corners.&nbsp;
 663 Expected n log n runtime, worst case quadratic runtime wrt. vertices +
 664 intersections.</td>
 665           </tr>
 666           <tr>
 667             <td width="586"><font face="Courier New">template
 668 &lt;typename transformation_type&gt;<br />
 669 polygon_set_data&amp; <br />
 670             <b>transform</b>(const transformation_type&amp;
 671 transformation) </font> </td>
 672             <td>Applies transformation.transform() on vertices stored
 673 within the polygon set.&nbsp; Expected n log n runtime, worst case
 674 quadratic runtime wrt. vertices + intersections.</td>
 675           </tr>
 676           <tr>
 677             <td width="586"><font face="Courier New">polygon_set_data&amp;
 678             <b>scale_up</b>(unsigned_area_type factor)</font></td>
 679             <td>Scales vertices stored within the polygon set up by
 680 factor.&nbsp; Expected n log n runtime, worst case quadratic runtime
 681 wrt. vertices + intersections.</td>
 682           </tr>
 683           <tr>
 684             <td width="586"><font face="Courier New">polygon_set_data&amp;
 685             <b>scale_down</b>(unsigned_area_type factor)</font>&nbsp;</td>
 686             <td>Scales vertices stored within the polygon set down by
 687 factor.&nbsp; Expected n log n runtime, worst case quadratic runtime
 688 wrt. vertices + intersections.</td>
 689           </tr>
 690           <tr>
 691             <td width="586"><font face="Courier New">template
 692 &lt;typename scaling_type&gt;<br />
 693 polygon_set_data&amp;<br />
 694             <b>scale</b>(const scaling_type&amp; f)</font></td>
 695             <td>Scales vertices stored within the polygon set by
 696 applying f.scale().&nbsp; Expected n log n runtime, worst case
 697 quadratic runtime wrt. vertices + intersections.</td>
 698           </tr>
 699         </tbody>
 700       </table>
 701       </td>
 702     </tr>
 703     <tr>
 704       <td style="background-color: rgb(238, 238, 238);" nowrap="1"
 705  valign="top"> &nbsp;</td>
 706       <td
 707  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
 708  valign="top" width="100%">
 709       <table class="docinfo" id="table8" frame="void" rules="none">
 710         <colgroup> <col class="docinfo-name" /><col
 711  class="docinfo-content" /> </colgroup> <tbody valign="top">
 712           <tr>
 713             <th class="docinfo-name">Copyright:</th>
 714             <td>Copyright © Intel Corporation 2008-2010.</td>
 715           </tr>
 716           <tr class="field">
 717             <th class="docinfo-name">License:</th>
 718             <td class="field-body">Distributed under the Boost Software
 719 License, Version 1.0. (See accompanying file <tt class="literal"> <span
 720  class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
 721  class="reference" target="_top"
 722  href="http://www.boost.org/LICENSE_1_0.txt">
 723 http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 724           </tr>
 725         </tbody>
 726       </table>
 727       </td>
 728     </tr>
 729   </tbody>
 730 </table>
 731 </body>
 732 </html>