projects / ceph.git / blame
| Commit | Line | Data |
|---|---|---|
| 7c673cae FG |
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. | |
| 86 | Manhattan geometry processing by the polygon_90_set_concept can be 100X | |
| 87 | faster than arbitrary angle polygon manipulation. 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<coordinate_type> objects. 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. 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. 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 | <typename T1, typename T2><br /> | |
| 110 | polygon_90_set_view <b>operator</b>|(const T1& l, const T2& r)</font></td> | |
| 111 | <td>Boolean OR operation (polygon set union). Accepts | |
| 112 | two objects that model polygon_90_set or one of its refinements. | |
| 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(). | |
| 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 | <typename T1, typename T2><br /> | |
| 121 | polygon_90_set_view <b>operator</b>+(const T1& l, const T2& r)</font></td> | |
| 122 | <td>Same as operator|. The plus sign is also used for | |
| 123 | OR operations in Boolean logic expressions. 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 | <typename T1, typename T2><br /> | |
| 129 | polygon_90_set_view <b>operator</b>&(const T1& l, const | |
| 130 | T2& r)</font></td> | |
| 131 | <td>Boolean AND operation (polygon set intersection). | |
| 132 | Accepts two objects that model polygon_90_set or one of its | |
| 133 | refinements. 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 | <typename T1, typename T2><br /> | |
| 139 | polygon_90_set_view <b>operator</b>*(const T1& l, const T2& r)</font></td> | |
| 140 | <td>Same as operator&. The multiplication symbol | |
| 141 | is also used for AND operations in Boolean logic expressions. 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 | <typename T1, typename T2><br /> | |
| 148 | polygon_90_set_view <b>operator</b>^(const T1& l, const T2& r)</font></td> | |
| 149 | <td>Boolean XOR operation (polygon set | |
| 150 | disjoint-union). Accepts two objects that model polygon_90_set or | |
| 151 | one of its refinements. O( n log n) runtime complexity and O(n) | |
| 152 | memory wrt vertices + intersections. 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 | <typename T1, typename T2><br /> | |
| 158 | polygon_90_set_view <b>operator</b>-(const T1& l, const T2& r)</font></td> | |
| 159 | <td>Boolean SUBTRACT operation (polygon set | |
| 160 | difference). Accepts two objects that model polygon_90_set or one | |
| 161 | of its refinements. 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 | <typename T1, typename T2><br /> | |
| 167 | T1& <b>operator</b>|=(const T1& l, const T2& 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. 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 | <typename T1, typename T2><br /> | |
| 176 | T1& <b>operator</b>+=(T1& l, const T2& 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. 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 | <typename T1, typename T2><br /> | |
| 185 | T1& <b>operator</b>&=(const T1& l, const T2& r)</font></td> | |
| 186 | <td>Same as operator&, but with self assignment, left | |
| 187 | operand must model polygon_90_set and not one of it's | |
| 188 | refinements. 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 | <typename T1, typename T2><br /> | |
| 194 | T1& <b>operator</b>*=(T1& l, const T2& 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. 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 | <typename T1, typename T2><br /> | |
| 203 | T1& <b>operator</b>^=(const T1& l, const T2& 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. 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 | <typename T1, typename T2><br /> | |
| 212 | T1& <b>operator</b>-=(T1& l, const T2& 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. 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 | <typename T1><br /> | |
| 221 | T1 <b>operator</b>+(const T1&, coordinate_type bloating)</font></td> | |
| 222 | <td>Performs resize operation, inflating by bloating | |
| 223 | ammount. If negative the result is a shrink instead of | |
| 224 | bloat. Note: returns result by value. 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 | <typename T1, typename T2><br /> | |
| 230 | T1 <b>operator</b>-(const T1&, coordinate_type shrinking)</font></td> | |
| 231 | <td>Performs resize operation, deflating by bloating | |
| 232 | ammount. If negative the result is a bloat instead of | |
| 233 | shrink. Note: returns result by value. 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 | <typename T1, typename T2><br /> | |
| 239 | T1& <b>operator</b>+=(const T1&, coordinate_type bloating)</font></td> | |
| 240 | <td>Performs resize operation, inflating by bloating | |
| 241 | ammount. If negative the result is a shrink instead of | |
| 242 | bloat. Returns reference to modified argument. 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 | <typename T1, typename T2><br /> | |
| 248 | T1& <b>operator</b>-=(const T1&, coordinate_type shrinking)</font></td> | |
| 249 | <td>Performs resize operation, deflating by bloating | |
| 250 | ammount. If negative the result is a bloat instead of | |
| 251 | shrink. Returns reference to modified argument. 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 | <typename T1, typename T2><br /> | |
| 262 | T1& <b>assign</b>(T1& lvalue, const T2& 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. 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 | <typename T1, typename T2><br /> | |
| 271 | bool <b>equivalence</b>(const T1& lvalue, const T2& 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. For example: two of polygon_90 objects. 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 | <typename output_container_type, typename T><br /> | |
| 281 | void <b>get_rectangles</b>(output_container_type& output, <br /> | |
| 282 | | |
| 283 | const T& polygon_set)</font></td> | |
| 284 | <td>Output container is expected to be a standard | |
| 285 | container. 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. 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 | <typename output_container_type, typename T><br /> | |
| 293 | void <b>get_max_rectangles</b>(output_container_type& output, <br /> | |
| 294 | | |
| 295 | const T& polygon_set)</font></td> | |
| 296 | <td>Output container is expected to be a standard | |
| 297 | container. 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. 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 | <typename polygon_set_type><br /> | |
| 305 | void <b>clear</b>(polygon_set_type& 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 | <typename polygon_set_type><br /> | |
| 311 | bool <b>empty</b>(const polygon_set_type& polygon_set)</font></td> | |
| 312 | <td>Checks whether the object is empty of geometry. | |
| 313 | Polygons that are completely covered by holes will result in empty | |
| 314 | returning true. 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 | <typename T, typename rectangle_type><br /> | |
| 320 | bool <b>extents</b>(rectangle_type& extents_rectangle, <br /> | |
| 321 | | |
| 322 | const T& 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. | |
| 325 | If the polygon set is empty returns false. If there are holes | |
| 326 | outside of shells they do not contribute to the extents of the polygon | |
| 327 | set. 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 | <typename T><br /> | |
| 333 | manhattan_area_type <b>area</b>(const T& polygon_set)</font></td> | |
| 334 | <td>Computes the area covered by geometry in an object that | |
| 335 | models polygon_90_set. 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 | <typename T1, typename T2><br /> | |
| 341 | T1& <b>interact</b>(T1& a, const T2& 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. 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 | <typename T><br /> | |
| 351 | T& <b>self_intersect</b>(T& 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. 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 | <typename T><br /> | |
| 360 | T& <b>self_xor</b>(T& 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. 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 | <typename T><br /> | |
| 369 | T& <b>bloat</b>(T& polygon_set, unsigned_area_type bloating)</font></td> | |
| 370 | <td>Same as getting all the rectangles, bloating them and | |
| 371 | putting them back. 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 | <typename T><br /> | |
| 377 | T& <b>bloat</b>(T& polygon_set, orientation_2d orient,<br /> | |
| 378 | unsigned_area_type | |
| 379 | bloating)</font></td> | |
| 380 | <td>Same as getting all the rectangles, bloating them and | |
| 381 | putting them back. 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 | <typename T><br /> | |
| 387 | T& <b>bloat</b>(T& polygon_set, orientation_2d orient,<br /> | |
| 388 | unsigned_area_type | |
| 389 | low_bloating,<br /> | |
| 390 | unsigned_area_type | |
| 391 | high_bloating)</font></td> | |
| 392 | <td>Same as getting all the rectangles, bloating them and | |
| 393 | putting them back. 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 | <typename T><br /> | |
| 399 | T& <b>bloat</b>(T& polygon_set, direction_2d dir,<br /> | |
| 400 | unsigned_area_type | |
| 401 | bloating)</font></td> | |
| 402 | <td>Same as getting all the rectangles, bloating them and | |
| 403 | putting them back. 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 | <typename T><br /> | |
| 409 | T& <b>bloat</b>(T& polygon_set, <br /> | |
| 410 | unsigned_area_type | |
| 411 | west_bloating,<br /> | |
| 412 | unsigned_area_type | |
| 413 | east_bloating,<br /> | |
| 414 | unsigned_area_type | |
| 415 | south_bloating,<br /> | |
| 416 | unsigned_area_type | |
| 417 | north_bloating)</font></td> | |
| 418 | <td>Same as getting all the rectangles, bloating them and | |
| 419 | putting them back. 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 | <typename T><br /> | |
| 425 | T& <b>shrink</b>(T& 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. 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 | <typename T><br /> | |
| 434 | T& <b>shrink</b>(T& polygon_set, orientation_2d orient,<br /> | |
| 435 | | |
| 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. 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 | <typename T><br /> | |
| 445 | T& <b>shrink</b>(T& polygon_set, orientation_2d orient,<br /> | |
| 446 | | |
| 447 | unsigned_area_type low_shrinking,<br /> | |
| 448 | | |
| 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. 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 | <typename T><br /> | |
| 458 | T& <b>shrink</b>(T& polygon_set, direction_2d dir,<br /> | |
| 459 | | |
| 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. 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 | <typename T><br /> | |
| 469 | T& <b>shrink</b>(T& polygon_set, <br /> | |
| 470 | | |
| 471 | unsigned_area_type west_shrinking,<br /> | |
| 472 | | |
| 473 | unsigned_area_type east_shrinking,<br /> | |
| 474 | | |
| 475 | unsigned_area_type south_shrinking,<br /> | |
| 476 | | |
| 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. 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 | <typename T, typename coord_type><br /> | |
| 486 | T& <b>resize</b>(T& 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 | <typename T, typename coord_type><br /> | |
| 493 | T& <b>resize</b>(polygon_set_type& polygon_set, <br /> | |
| 494 | coord_type west, | |
| 495 | coord_type east, <br /> | |
| 496 | 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. 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 | <typename T><br /> | |
| 505 | T& <b>grow_and</b>(T& 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. 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 | <typename T><br /> | |
| 514 | T& <b>grow_and</b>(T& polygon_set, orientation_2d orient,<br /> | |
| 515 | | |
| 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. 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 | <typename T><br /> | |
| 525 | T& <b>grow_and</b>(T& polygon_set, orientation_2d orient,<br /> | |
| 526 | | |
| 527 | unsigned_area_type low_bloating,<br /> | |
| 528 | | |
| 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. 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 | <typename T><br /> | |
| 538 | T& <b>grow_and</b>(T& polygon_set, direction_2d dir,<br /> | |
| 539 | | |
| 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. 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 | <typename T><br /> | |
| 549 | T& <b>grow_and</b>(T& polygon_set, <br /> | |
| 550 | | |
| 551 | unsigned_area_type west_bloating,<br /> | |
| 552 | | |
| 553 | unsigned_area_type east_bloating,<br /> | |
| 554 | | |
| 555 | unsigned_area_type south_bloating,<br /> | |
| 556 | | |
| 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. 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 | <typename T><br /> | |
| 566 | T& <b>scale_up</b>(T& polygon_set, unsigned_area_type factor)</font></td> | |
| 567 | <td>Scales geometry up by unsigned factor. 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 | <typename T><br /> | |
| 573 | T& <b>scale_down</b>(T& polygon_set, unsigned_area_type factor)</font></td> | |
| 574 | <td>Scales geometry down by unsigned factor. 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 | <typename T, typename scaling_type><br /> | |
| 580 | T& <b>scale</b>(polygon_set_type& polygon_set, <br /> | |
| 581 | const | |
| 582 | scaling_type& scaling)</font></td> | |
| 583 | <td>Scales geometry by applying scaling.scale() on all | |
| 584 | vertices. 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 | <typename T, typename coord_type><br /> | |
| 590 | T& <b>move</b>(T& polygon_set,<br /> | |
| 591 | orientation_2d orient, | |
| 592 | coord_type displacement)</font></td> | |
| 593 | <td>Moves geometry by displacement amount in the | |
| 594 | orientation. 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 | <typename T, typename coord_type><br /> | |
| 600 | T& <b>move</b>(T& polygon_set, coord_type x_displacement, <br /> | |
| 601 | coord_type y_displacement)</font></td> | |
| 602 | <td>Moves the geometry by x_dispacement in x and | |
| 603 | y_displacement in y. Note: for consistency should be | |
| 604 | convolve(polygon_set, point). 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 | <typename T, typename transformation_type><br /> | |
| 610 | T& <b>transform</b>(T& polygon_set,<br /> | |
| 611 | | |
| 612 | const transformation_type& transformation)</font></td> | |
| 613 | <td>Applies transformation.transform() on all | |
| 614 | vertices. 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 | <typename T><br /> | |
| 620 | T& <b>keep</b>(T& polygon_set, <br /> | |
| 621 | unsigned_area_type min_area,<br /> | |
| 622 | unsigned_area_type max_area,<br /> | |
| 623 | unsigned_area_type min_width,<br /> | |
| 624 | unsigned_area_type max_width,<br /> | |
| 625 | unsigned_area_type | |
| 626 | min_height,<br /> | |
| 627 | unsigned_area_type | |
| 628 | max_height)</font></td> | |
| 629 | <td>Retains only regions that satisfy the min/max criteria | |
| 630 | in the argument list. Note: useful for visualization to cull too | |
| 631 | small polygons. 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. 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. 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 <typename T><br /> | |
| 652 | class polygon_90_set_data;</font></p> | |
| 653 | <p>The class is parameterized on the coordinate data type. | |
| 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. </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. 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 | <typename iT><br /> | |
| 673 | <b>polygon_90_set_data</b>(orientation_2d orient, <br /> | |
| 674 | | |
| 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& that)</font></td> | |
| 682 | <td>Copy construct.</td> | |
| 683 | </tr> | |
| 684 | <tr> | |
| 685 | <td width="586"><font face="Courier New">template | |
| 686 | <typename l, typename r, typename op><br /> | |
| 687 | <b>polygon_90_set_data</b>(const | |
| 688 | polygon_90_set_view<l,r,op>& 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 | | |
| 695 | const polygon_90_set_data& 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& | |
| 701 | <br /> | |
| 702 | <b>operator=</b>(const polygon_90_set_data& 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 | <typename l, typename r, typename op><br /> | |
| 709 | polygon_90_set_data& <br /> | |
| 710 | <b>operator=</b>(const polygon_90_set_view<l, r, | |
| 711 | op>& 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 | <typename geometry_object><br /> | |
| 717 | polygon_90_set_data& <b>operator=</b>(const geometry_object& | |
| 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 <typename iT><br /> | |
| 724 | void <b>insert</b>(iT input_begin, iT input_end)</font></td> | |
| 725 | <td>Insert objects of an iterator range. 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& polygon_set)</font></td> | |
| 731 | <td>Insert a polygon set. Linear wrt. inserted | |
| 732 | vertices.</td> | |
| 733 | </tr> | |
| 734 | <tr> | |
| 735 | <td width="586"><font face="Courier New"> | |
| 736 | template <typename geometry_type><br /> | |
| 737 | void <b>insert</b>(const geometry_type& geometry_object, <br /> | |
| 738 | 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. Linear wrt. | |
| 742 | inserted vertices.</td> | |
| 743 | </tr> | |
| 744 | <tr> | |
| 745 | <td width="586"><font face="Courier New">template | |
| 746 | <typename output_container><br /> | |
| 747 | void <b>get</b>(output_container& output) const</font></td> | |
| 748 | <td>Expects a standard container of geometry objects. | |
| 749 | Will scan and eliminate overlaps. Converts polygon set geometry | |
| 750 | to objects of that type and appends them to the container. | |
| 751 | Polygons will be output with counterclockwise winding, hole polygons | |
| 752 | will be output with clockwise winding. 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. 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 | <typename output_container><br /> | |
| 760 | void <b>get</b>(output_container& output, size_t k) const</font></td> | |
| 761 | <td style="vertical-align: top;">Expects a standard | |
| 762 | container of geometry objects. Will scan and eliminate | |
| 763 | overlaps. Converts polygon set geometry to objects of that type | |
| 764 | and appends them to the container. 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. 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. 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 | <typename output_container><br /> | |
| 776 | void <b>get_polygons</b>(output_container& output) const</font></td> | |
| 777 | <td>Expects a standard container of polygon objects. | |
| 778 | Will scan and eliminate overlaps. Converts polygon set geometry | |
| 779 | to polygons and appends them to the container. Polygons will have | |
| 780 | holes fractured out to the outer boundary along the positive direction | |
| 781 | of the scanline orientation of the polygon set. 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 | <typename output_container><br /> | |
| 787 | void <b>get_rectangles</b>(output_container& output) const</font></td> | |
| 788 | <td>Expects a standard container of rectangle | |
| 789 | objects. Will scan and eliminate overlaps. Slices polygon | |
| 790 | set geometry to rectangles along the scanning orientation and appends | |
| 791 | them to the container. 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 <typename output_container><br /> | |
| 797 | void <b>get_rectangles</b>(output_container& output, <br /> | |
| 798 | orientation_2d slicing_orientation) const </font> </td> | |
| 799 | <td>Expects a standard container of rectangle | |
| 800 | objects. Will scan and eliminate overlaps. Slices polygon | |
| 801 | set geometry to rectangles along the given orientation and appends them | |
| 802 | to the container. 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& p) const</font></td> | |
| 808 | <td>Once scanned the data representation of geometry within | |
| 809 | a polygon set is in a mathematically canonical form. 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. 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& 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. Note: does not | |
| 823 | de-allocate memory. 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. Will scan and eliminate overlaps because subtractive | |
| 831 | regions might make the polygon set empty. 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. Depending on the | |
| 839 | data it is sometimes more efficient to scan in a specific | |
| 840 | orientation. This is particularly true of Manhattan geometry | |
| 841 | data. 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. 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 | <typename input_iterator_type><br /> | |
| 853 | void <b>set</b>(input_iterator_type input_begin, <br /> | |
| 854 | input_iterator_type | |
| 855 | input_end, <br /> | |
| 856 | orientation_2d orient) | |
| 857 | </font> </td> | |
| 858 | <td>Overwrite geometry in polygon set with insertable | |
| 859 | objects in the iterator range. Also sets the scanning orientation | |
| 860 | to that specified.</td> | |
| 861 | </tr> | |
| 862 | <tr> | |
| 863 | <td width="586"><font face="Courier New">template | |
| 864 | <typename rectangle_type><br /> | |
| 865 | bool <b>extents</b>(rectangle_type& 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. 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&<br /> | |
| 874 | <b>bloat</b>(unsigned_area_type west_bloating,<br /> | |
| 875 | | |
| 876 | unsigned_area_type east_bloating,<br /> | |
| 877 | | |
| 878 | unsigned_area_type south_bloating,<br /> | |
| 879 | | |
| 880 | unsigned_area_type north_bloating) </font></td> | |
| 881 | <td>Scans to eliminate overlaps and subtractive | |
| 882 | regions. 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. 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&<br /> | |
| 890 | <b>shrink</b>(unsigned_area_type west_shrinking,<br /> | |
| 891 | | |
| 892 | unsigned_area_type east_shrinking,<br /> | |
| 893 | | |
| 894 | unsigned_area_type south_shrinking,<br /> | |
| 895 | | |
| 896 | unsigned_area_type north_shrinking)</font></td> | |
| 897 | <td>Scans to eliminate overlaps and subtractive | |
| 898 | regions. 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. Scans to eliminate overlapping | |
| 902 | subtractive regions. 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&<br /> | |
| 907 | <b>resize</b>(coordinate_type west, coordinate_type east, <br /> | |
| 908 | 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. 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& | |
| 916 | <b>move</b>(coordinate_type x_delta, <br /> | |
| 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. Linear wrt. vertices.</td> | |
| 920 | </tr> | |
| 921 | <tr> | |
| 922 | <td width="586"><font face="Courier New">template | |
| 923 | <typename transformation_type><br /> | |
| 924 | polygon_90_set_data& <br /> | |
| 925 | <b>transform</b>(const transformation_type& | |
| 926 | transformation) </font> </td> | |
| 927 | <td>Applies transformation.transform() on vertices stored | |
| 928 | within the polygon set. Linear wrt. vertices.</td> | |
| 929 | </tr> | |
| 930 | <tr> | |
| 931 | <td width="586"><font face="Courier New">polygon_90_set_data& | |
| 932 | <b>scale_up</b>(unsigned_area_type factor)</font></td> | |
| 933 | <td>Scales vertices stored within the polygon set up by | |
| 934 | factor. Linear wrt. vertices.</td> | |
| 935 | </tr> | |
| 936 | <tr> | |
| 937 | <td width="586"> | |
| 938 | <p><font face="Courier New">polygon_90_set_data& <b>scale_down</b>(unsigned_area_type | |
| 939 | factor)</font> </p> | |
| 940 | </td> | |
| 941 | <td>Scales vertices stored within the polygon set down by | |
| 942 | factor. Linear wrt. vertices.</td> | |
| 943 | </tr> | |
| 944 | <tr> | |
| 945 | <td width="586"><font face="Courier New">template | |
| 946 | <typename scaling_type><br /> | |
| 947 | polygon_90_set_data&<br /> | |
| 948 | <b>scale</b>(const | |
| 949 | anisotropic_scale_factor<scaling_type>& f)</font></td> | |
| 950 | <td>Scales vertices stored within the polygon set by | |
| 951 | applying f.scale(). Linear wrt. vertices.</td> | |
| 952 | </tr> | |
| 953 | <tr> | |
| 954 | <td width="586"><font face="Courier New">polygon_90_set_data& | |
| 955 | <b>scale</b>(double factor) </font></td> | |
| 956 | <td>Scales vertices stored within the polygon set by | |
| 957 | floating point factor. Linear wrt. vertices.</td> | |
| 958 | </tr> | |
| 959 | <tr> | |
| 960 | <td width="586"><font face="Courier New">polygon_90_set_data& | |
| 961 | <b>self_xor</b>()</font></td> | |
| 962 | <td>Retain only non-overlapping regions of geometry within | |
| 963 | polygon set. 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& | |
| 968 | <b>self_intersect</b>()</font></td> | |
| 969 | <td>Retain only overlapping regions of geometry within a | |
| 970 | polygon set. 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&<br /> | |
| 975 | <b>interact</b>(const polygon_90_set_data& that)</font></td> | |
| 976 | <td>Retain only regions that touch or overlap regions in | |
| 977 | argument. 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"> </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 |