| <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
| <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" 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"><head><!-- |
| Copyright 2009-2010 Intel Corporation |
| license banner |
| --> |
| <title>Boost Polygon Library: Polygon 90 Set Concept</title> |
| <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1"> |
| <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0"><tbody><tr> |
| <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> |
| <div style="padding: 5px;" align="center"> |
| <img border="0" src="images/boost.png" width="277" height="86"><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;"> |
| </a> |
| </div> |
| <div style="margin: 5px;"> |
| <h3 class="navbar">Contents</h3> |
| <ul> |
| <li><a href="index.htm">Boost.Polygon Main Page</a></li> |
| <li><a href="gtl_design_overview.htm">Design Overview</a></li> |
| <li><a href="gtl_isotropy.htm">Isotropy</a></li> |
| <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li> |
| <li><a href="gtl_interval_concept.htm">Interval Concept</a></li> |
| <li><a href="gtl_point_concept.htm">Point Concept</a></li> |
| <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li> |
| <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li> |
| <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90 With Holes Concept</a></li> |
| <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li> |
| <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45 With Holes Concept</a></li> |
| <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li> |
| <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With Holes Concept</a></li> |
| <li>Polygon 90 Set Concept</li> |
| <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set Concept</a></li> |
| <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li> |
| <li><a href="gtl_connectivity_extraction_90.htm">Connectivity Extraction 90</a></li> |
| <li><a href="gtl_connectivity_extraction_45.htm">Connectivity Extraction 45</a></li> |
| <li><a href="gtl_connectivity_extraction.htm">Connectivity Extraction</a></li> |
| <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li> |
| <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li> |
| <li><a href="gtl_property_merge.htm">Property Merge</a></li> |
| </ul> |
| <h3 class="navbar">Other Resources</h3> |
| <ul> |
| <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li> |
| <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009 |
| Presentation</a></li> |
| <li><a href="analysis.htm">Performance Analysis</a></li> |
| <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li> |
| <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li> |
| </ul> |
| </div> |
| <h3 class="navbar">Polygon Sponsor</h3> |
| <div style="padding: 5px;" align="center"> |
| <img border="0" src="images/intlogo.gif" width="127" height="51"> |
| </div> |
| </td> |
| <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"> |
| |
| <!-- End Header --> |
| |
| <br> |
| <p> |
| </p><h1>Polygon 90 Set Concept</h1> |
| |
| <p> |
| <p>The polygon_90_set concept tag is <font face="Courier New"> |
| polygon_90_set_concept</font></p> |
| <p> |
| <font face="Times New Roman">The semantic of a polygon_90_set is zero or more |
| Manhattan geometry regions.</font><p> |
| <font face="Times New Roman">The motivation for providing the |
| polygon_90_set_concept is that it is a very common special case of planar |
| geometry which afford the implementation of a variety of optimizations on the |
| general planar geometry algorithms. Manhattan geometry processing by the |
| polygon_90_set_concept can be 100X faster than arbitrary angle polygon |
| manipulation. Because the performance benefits are so large and the |
| special case is important enough, the library provides these performance |
| benefits for those application domains that require them.</font><p>Users are recommended to use std::vector and std::list of user defined polygons |
| or library provided polygon_90_set_data<coordinate_type> objects. Lists |
| and vectors of models of polygon_90_concept or polygon_90_with_holes_concept or |
| rectangle_concept are automatically models of polygon_90_set_concept.</p> |
| <h2>Operators</h2> |
| <p>The return type of some operators is the <font face="Courier New">polygon_90_set_view</font> |
| operator template type. This type is itself a model of the polygon_90_set |
| concept, but furthermore can be used as an argument to the <font face="Courier New">polygon_90_set_data</font> |
| constructor and assignment operator. The operator template exists to |
| eliminate temp copies of intermediate results when Boolean operators are chained |
| together.</p> |
| <p>Operators are declared inside the namespace <font face="Courier New">boost::polygon::operators</font>.</p> |
| <table border="1" width="100%" id="table3"> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| polygon_90_set_view <b>operator</b>|(const T1& l, const T2& r)</font></td> |
| <td>Boolean OR operation (polygon set union). Accepts two objects |
| that model polygon_90_set or one of its refinements. Returns an |
| operator template that performs the operation on demand when chained or |
| or nested in a library function call such as assign(). O( n log n) |
| runtime complexity and O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| polygon_90_set_view <b>operator</b>+(const T1& l, const T2& r)</font></td> |
| <td>Same as operator|. The plus sign is also used for OR |
| operations in Boolean logic expressions. O( n log n) runtime |
| complexity and O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| polygon_90_set_view <b>operator</b>&(const T1& l, const T2& r)</font></td> |
| <td>Boolean AND operation (polygon set intersection). Accepts two |
| objects that model polygon_90_set or one of its refinements. O( n |
| log n) runtime complexity and O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| polygon_90_set_view <b>operator</b>*(const T1& l, const T2& r)</font></td> |
| <td>Same as operator&. The multiplication symbol is also used for |
| AND operations in Boolean logic expressions. O( n log n) runtime |
| complexity and O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| polygon_90_set_view <b>operator</b>^(const T1& l, const T2& r)</font></td> |
| <td>Boolean XOR operation (polygon set disjoint-union). Accepts |
| two objects that model polygon_90_set or one of its refinements. |
| O( n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections. O( n log n) runtime complexity and O(n) memory wrt |
| vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| polygon_90_set_view <b>operator</b>-(const T1& l, const T2& r)</font></td> |
| <td>Boolean SUBTRACT operation (polygon set difference). Accepts |
| two objects that model polygon_90_set or one of its refinements. |
| O( n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>operator</b>|=(const T1& l, const T2& r)</font></td> |
| <td>Same as operator|, but with self assignment, left operand must model |
| polygon_90_set and not one of it's refinements. O( n log n) |
| runtime complexity and O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>operator</b>+=(T1& l, const T2& r)</font></td> |
| <td>Same as operator+, but with self assignment, left operand must model |
| polygon_90_set and not one of it's refinements. O( n log n) |
| runtime complexity and O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>operator</b>&=(const T1& l, const T2& r)</font></td> |
| <td>Same as operator&, but with self assignment, left operand must model |
| polygon_90_set and not one of it's refinements. O( n log n) |
| runtime complexity and O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>operator</b>*=(T1& l, const T2& r)</font></td> |
| <td>Same as operator*, but with self assignment, left operand must model |
| polygon_90_set and not one of it's refinements. O( n log n) |
| runtime complexity and O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>operator</b>^=(const T1& l, const T2& r)</font></td> |
| <td>Same as operator^, but with self assignment, left operand must model |
| polygon_90_set and not one of it's refinements. O( n log n) |
| runtime complexity and O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>operator</b>-=(T1& l, const T2& r)</font></td> |
| <td>Same as operator-, but with self assignment, left operand must model |
| polygon_90_set and not one of it's refinements. O( n log n) |
| runtime complexity and O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1><br> |
| T1 <b>operator</b>+(const T1&, coordinate_type bloating)</font></td> |
| <td>Performs resize operation, inflating by bloating ammount. If |
| negative the result is a shrink instead of bloat. Note: returns |
| result by value. O( n log n) runtime complexity and O(n) memory |
| wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1 <b>operator</b>-(const T1&, coordinate_type shrinking)</font></td> |
| <td>Performs resize operation, deflating by bloating ammount. If |
| negative the result is a bloat instead of shrink. Note: returns |
| result by value. O( n log n) runtime complexity and O(n) memory |
| wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>operator</b>+=(const T1&, coordinate_type bloating)</font></td> |
| <td>Performs resize operation, inflating by bloating ammount. If |
| negative the result is a shrink instead of bloat. Returns |
| reference to modified argument. O( n log n) runtime complexity and |
| O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>operator</b>-=(const T1&, coordinate_type shrinking)</font></td> |
| <td>Performs resize operation, deflating by bloating ammount. If |
| negative the result is a bloat instead of shrink. Returns |
| reference to modified argument. O( n log n) runtime complexity and |
| O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| </table> |
| <h2>Functions</h2> |
| <table border="1" width="100%" id="table1"> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>assign</b>(T1& lvalue, const T2& rvalue)</font></td> |
| <td>Eliminates overlaps in geometry and copies from an object that |
| models polygon_90_set or any of its refinements into an object that |
| models polygon_90_set. O( n log n) runtime complexity and O(n) |
| memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| bool <b>equivalence</b>(const T1& lvalue, const T2& rvalue) </font></td> |
| <td>Returns true if an object that models polygon_90_set or one of its |
| refinements covers the exact same geometric regions as another object |
| that models polygon_90_set or one of its refinements. For example: |
| two of polygon_90 objects. O( n log n) runtime complexity and O(n) |
| memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| output_container_type, typename T><br> |
| void <b>get_rectangles</b>(output_container_type& output, <br> |
| |
| const T& polygon_set)</font></td> |
| <td>Output container is expected to be a standard container. |
| Slices geometry of an object that models polygon_90_set or one of its |
| refinements into non overlapping rectangles and appends them to the |
| output. O( n log n) runtime complexity and O(n) memory wrt |
| vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| output_container_type, typename T><br> |
| void <b>get_max_rectangles</b>(output_container_type& output, <br> |
| |
| const T& polygon_set)</font></td> |
| <td>Output container is expected to be a standard container. Given |
| an object that models polygon_90_set or one of its refinements finds all |
| overlapping rectangles that are maximal in area and appends them to the |
| output. Expected n log n runtime, worst case quadratic rutnime.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| polygon_set_type><br> |
| void <b>clear</b>(polygon_set_type& polygon_set)</font></td> |
| <td>Makes the object empty of geometry.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename |
| polygon_set_type><br> |
| bool <b>empty</b>(const polygon_set_type& polygon_set)</font></td> |
| <td>Checks whether the object is empty of geometry. Polygons that |
| are completely covered by holes will result in empty returning true. |
| O( n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T, typename |
| rectangle_type><br> |
| bool <b>extents</b>(rectangle_type& extents_rectangle, <br> |
| const |
| T& polygon_set)</font></td> |
| <td>Computes bounding box of an object that models polygon_90_set and |
| stores it in an object that models rectangle. If the polygon set |
| is empty returns false. If there are holes outside of shells they |
| do not contribute to the extents of the polygon set. O( n log n) |
| runtime complexity and O(n) memory wrt vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| manhattan_area_type <b>area</b>(const T& polygon_set)</font></td> |
| <td>Computes the area covered by geometry in an object that models |
| polygon_90_set. O( n log n) runtime complexity and O(n) memory wrt |
| vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T1, typename |
| T2><br> |
| T1& <b>interact</b>(T1& a, const T2& b)</font></td> |
| <td>Given an object that models polygon_90_set and an object that models |
| polygon_90_set or one of its refinements, modifies a to retain only |
| regions that overlap or touch regions in b. O( n log n) runtime |
| complexity and O(n) memory wrt vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>self_intersect</b>(T& polygon_set)</font></td> |
| <td>Given an object that models polygon_90_set that has self overlapping |
| regions, modifies the argument to contain only the regions of overlap. |
| O( n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>self_xor</b>(T& polygon_set)</font></td> |
| <td>Given an object that models polygon_90_set that has self overlapping |
| regions, modifies the argument to contain only the regions that do not |
| overlap. O( n log n) runtime complexity and O(n) memory wrt |
| vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>bloat</b>(T& polygon_set, unsigned_area_type bloating)</font></td> |
| <td>Same as getting all the rectangles, bloating them and putting them |
| back. O( n log n) runtime complexity and O(n) memory wrt vertices |
| + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>bloat</b>(T& polygon_set, orientation_2d orient,<br> |
| unsigned_area_type bloating)</font></td> |
| <td>Same as getting all the rectangles, bloating them and putting them |
| back. O( n log n) runtime complexity and O(n) memory wrt vertices |
| + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>bloat</b>(T& polygon_set, orientation_2d orient,<br> |
| unsigned_area_type low_bloating,<br> |
| unsigned_area_type |
| high_bloating)</font></td> |
| <td>Same as getting all the rectangles, bloating them and putting them |
| back. O( n log n) runtime complexity and O(n) memory wrt vertices |
| + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>bloat</b>(T& polygon_set, direction_2d dir,<br> |
| unsigned_area_type bloating)</font></td> |
| <td>Same as getting all the rectangles, bloating them and putting them |
| back. O( n log n) runtime complexity and O(n) memory wrt vertices |
| + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>bloat</b>(T& polygon_set, <br> |
| unsigned_area_type |
| west_bloating,<br> |
| unsigned_area_type |
| east_bloating,<br> |
| unsigned_area_type |
| south_bloating,<br> |
| unsigned_area_type |
| north_bloating)</font></td> |
| <td>Same as getting all the rectangles, bloating them and putting them |
| back. O( n log n) runtime complexity and O(n) memory wrt vertices |
| + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>shrink</b>(T& polygon_set, unsigned_area_type shrinking)</font></td> |
| <td>Same as getting all the rectangles of the inverse, bloating them and overwriting |
| the polygon set with the resulting regions then negating. O( n log |
| n) runtime complexity and O(n) memory wrt vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>shrink</b>(T& polygon_set, orientation_2d orient,<br> |
| unsigned_area_type |
| shrinking)</font></td> |
| <td>Same as getting all the rectangles of the inverse, bloating them and overwriting |
| the polygon set with the resulting regions then negating. O( n log |
| n) runtime complexity and O(n) memory wrt vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>shrink</b>(T& polygon_set, orientation_2d orient,<br> |
| unsigned_area_type |
| low_shrinking,<br> |
| unsigned_area_type |
| high_shrinking)</font></td> |
| <td>Same as getting all the rectangles of the inverse, bloating them and overwriting |
| the polygon set with the resulting regions then negating. O( n log |
| n) runtime complexity and O(n) memory wrt vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>shrink</b>(T& polygon_set, direction_2d dir,<br> |
| unsigned_area_type |
| shrinking)</font></td> |
| <td>Same as getting all the rectangles of the inverse, bloating them and overwriting |
| the polygon set with the resulting regions then negating. O( n log |
| n) runtime complexity and O(n) memory wrt vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>shrink</b>(T& polygon_set, <br> |
| unsigned_area_type |
| west_shrinking,<br> |
| unsigned_area_type |
| east_shrinking,<br> |
| unsigned_area_type |
| south_shrinking,<br> |
| unsigned_area_type |
| north_shrinking)</font></td> |
| <td>Same as getting all the rectangles of the inverse, bloating them and overwriting |
| the polygon set with the resulting regions then negating. O( n log |
| n) runtime complexity and O(n) memory wrt vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T, typename |
| coord_type><br> |
| T& <b>resize</b>(T& polygon_set, coord_type resizing)</font></td> |
| <td>Same as bloat if resizing is positive, same as shrink if resizing is |
| negative.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T, typename |
| coord_type><br> |
| T& <b>resize</b>(polygon_set_type& polygon_set, <br> |
| coord_type west, coord_type east, |
| <br> coord_type south, coord_type north)</font></td> |
| <td>Same as bloat if resizing is positive, same as shrink if resizing is |
| negative. O( n log n) runtime complexity and O(n) memory wrt |
| vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>grow_and</b>(T& polygon_set, unsigned_area_type bloating)</font></td> |
| <td>Same as bloating non-overlapping regions and then applying self |
| intersect to retain only the overlaps introduced by the bloat. O( |
| n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>grow_and</b>(T& polygon_set, orientation_2d orient,<br> |
| |
| unsigned_area_type bloating)</font></td> |
| <td>Same as bloating non-overlapping regions and then applying self |
| intersect to retain only the overlaps introduced by the bloat. O( |
| n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>grow_and</b>(T& polygon_set, orientation_2d orient,<br> |
| |
| unsigned_area_type low_bloating,<br> |
| |
| unsigned_area_type high_bloating)</font></td> |
| <td>Same as bloating non-overlapping regions and then applying self |
| intersect to retain only the overlaps introduced by the bloat. O( |
| n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>grow_and</b>(T& polygon_set, direction_2d dir,<br> |
| |
| unsigned_area_type bloating)</font></td> |
| <td>Same as bloating non-overlapping regions and then applying self |
| intersect to retain only the overlaps introduced by the bloat. O( |
| n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>grow_and</b>(T& polygon_set, <br> |
| |
| unsigned_area_type west_bloating,<br> |
| |
| unsigned_area_type east_bloating,<br> |
| |
| unsigned_area_type south_bloating,<br> |
| |
| unsigned_area_type north_bloating)</font></td> |
| <td>Same as bloating non-overlapping regions and then applying self |
| intersect to retain only the overlaps introduced by the bloat. O( |
| n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>scale_up</b>(T& polygon_set, unsigned_area_type factor)</font></td> |
| <td>Scales geometry up by unsigned factor. O( n log n) runtime |
| complexity and O(n) memory wrt vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>scale_down</b>(T& polygon_set, unsigned_area_type factor)</font></td> |
| <td>Scales geometry down by unsigned factor. O( n log n) runtime |
| complexity and O(n) memory wrt vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T, typename scaling_type><br> |
| T& <b>scale</b>(polygon_set_type& polygon_set, <br> |
| const scaling_type& scaling)</font></td> |
| <td>Scales geometry by applying scaling.scale() on all vertices. |
| O( n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T, typename coord_type><br> |
| T& <b>move</b>(T& polygon_set,<br> |
| orientation_2d orient, coord_type |
| displacement)</font></td> |
| <td>Moves geometry by displacement amount in the orientation. |
| O( n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T, typename coord_type><br> |
| T& <b>move</b>(T& polygon_set, coord_type x_displacement, <br> |
| coord_type y_displacement)</font></td> |
| <td>Moves the geometry by x_dispacement in x and y_displacement in y. |
| Note: for consistency should be convolve(polygon_set, point). O( n |
| log n) runtime complexity and O(n) memory wrt vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T, typename transformation_type><br> |
| T& <b>transform</b>(T& polygon_set,<br> |
| const |
| transformation_type& transformation)</font></td> |
| <td>Applies transformation.transform() on all vertices. O( n log |
| n) runtime complexity and O(n) memory wrt vertices + intersections. </td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename T><br> |
| T& <b>keep</b>(T& polygon_set, <br> |
| unsigned_area_type min_area,<br> |
| unsigned_area_type max_area,<br> |
| unsigned_area_type min_width,<br> |
| unsigned_area_type max_width,<br> |
| unsigned_area_type min_height,<br> |
| unsigned_area_type max_height)</font></td> |
| <td>Retains only regions that satisfy the min/max criteria in the |
| argument list. Note: useful for visualization to cull too small |
| polygons. O( n log n) runtime complexity and O(n) memory wrt |
| vertices + intersections. </td> |
| </tr> |
| </table> |
| <h1>Polygon 90 Set Data Object</h1> |
| |
| <p> |
| <p>The polygon 90 set data type encapsulates the internal data format that |
| serves as the input to the sweep-line algorithm that implements polygon-clipping |
| boolean operations. It also internally keeps track of whether that data |
| has been sorted or scanned and maintains the invariant that when its flags |
| indicate that the data is sorted or scanned the data has not been changed to |
| violate that assumption. Using the Polygon 90 Set Data type directly can |
| be more efficient than using lists and vectors of polygons in the functions |
| above because of the invariants it can enforce which provide the opportunity to |
| maintain the data is sorted form rather than going all the way out to polygons |
| then resorting those vertices for a subsequent operation.</p> |
| <p>The declaration of Polygon 90 Set Data is the following:</p> |
| <p><font face="Courier New">template <typename T><br> |
| class polygon_90_set_data;</font></p> |
| <p>The class is parameterized on the coordinate data type. Algorithms that |
| benefit from knowledge of the invariants enforced by the class are implemented |
| as member functions to provide them access to information about those |
| invariants. </p> |
| <h2>Member Functions</h2> |
| <table border="1" width="100%" id="table2"> |
| <tr> |
| <td width="586"><font face="Courier New"><b>polygon_90_set_data</b>()</font></td> |
| <td>Default constructor. Scanning orientation defaults to |
| HORIZONTAL</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"><b>polygon_90_set_data</b>(orientation_2d |
| orient)</font></td> |
| <td>Construct with scanning orientation.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename iT><br> |
| <b>polygon_90_set_data</b>(orientation_2d orient, <br> iT input_begin, iT |
| input_end)</font></td> |
| <td>Construct with scanning orientation from an iterator range of |
| insertable objects.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| <b>polygon_90_set_data</b>(const polygon_90_set_data& that)</font></td> |
| <td>Copy construct.</td> |
| </tr> |
| <tr> |
| <td width="586"> |
| <font face="Courier New">template <typename l, typename r, typename op><br> |
| <b>polygon_90_set_data</b>(const polygon_90_set_view<l,r,op>& |
| t)</font></td> |
| <td>Copy construct from a Boolean operator template.</td> |
| </tr> |
| <tr> |
| <td width="586"> |
| <font face="Courier New"> |
| <b>polygon_90_set_data</b>(orientation_2d orient, <br> const polygon_90_set_data& |
| that)</font></td> |
| <td>Construct with scanning orientation and copy from another polygon |
| set.</td> |
| </tr> |
| <tr> |
| <td width="586"> |
| <font face="Courier New">polygon_90_set_data& <br><b>operator=</b>(const polygon_90_set_data& that)</font></td> |
| <td>Assignment from another polygon set, may change scanning |
| orientation.</td> |
| </tr> |
| <tr> |
| <td width="586"> |
| <font face="Courier New">template <typename l, typename r, typename op><br> |
| polygon_90_set_data& <br><b>operator=</b>(const polygon_90_set_view<l, r, |
| op>& that)</font></td> |
| <td>Assignment from a Boolean operator template.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">template <typename geometry_object><br> |
| polygon_90_set_data& <b>operator=</b>(const geometry_object& geo)</font></td> |
| <td>Assignment from an insertable object.</td> |
| </tr> |
| <tr> |
| <td width="586"> |
| <font face="Courier New"> |
| template <typename iT><br> |
| void <b>insert</b>(iT input_begin, iT input_end)</font></td> |
| <td>Insert objects of an iterator range. Linear wrt. inserted |
| vertices.</td> |
| </tr> |
| <tr> |
| <td width="586"> |
| <font face="Courier New"> |
| void <b>insert</b>(const polygon_90_set_data& polygon_set)</font></td> |
| <td>Insert a polygon set. Linear wrt. inserted vertices.</td> |
| </tr> |
| <tr> |
| <td width="586"> |
| <font face="Courier New"> |
| template <typename geometry_type><br> |
| void <b>insert</b>(const geometry_type& geometry_object, <br> bool is_hole |
| = false)</font></td> |
| <td>Insert a geometry object, if is_hole is true then the inserted |
| region is subtractive rather than additive. Linear wrt. inserted |
| vertices.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| template <typename output_container><br> |
| void <b>get</b>(output_container& output) const</font></td> |
| <td>Expects a standard container of geometry objects. Will scan |
| and eliminate overlaps. Converts polygon set geometry to objects |
| of that type and appends them to the container. Polygons will be |
| output with counterclockwise winding, hole polygons will be output with |
| clockwise winding. The last vertex of an output polygon is not the |
| duplicate of the first, and the number of points is equal to the number |
| of edges. O( n log n) runtime complexity and O(n) memory wrt |
| vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| template <typename output_container><br> |
| void <b>get_polygons</b>(output_container& output) const</font></td> |
| <td>Expects a standard container of polygon objects. Will scan and |
| eliminate overlaps. Converts polygon set geometry to polygons and |
| appends them to the container. Polygons will have holes fractured |
| out to the outer boundary along the positive direction of the scanline |
| orientation of the polygon set. O( n log n) runtime complexity and |
| O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| template <typename output_container><br> |
| void <b>get_rectangles</b>(output_container& output) const</font></td> |
| <td>Expects a standard container of rectangle objects. Will scan |
| and eliminate overlaps. Slices polygon set geometry to rectangles |
| along the scanning orientation and appends them to the container. |
| O( n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"> |
| <font face="Courier New"> |
| template <typename output_container><br> |
| void <b>get_rectangles</b>(output_container& output, <br> orientation_2d |
| slicing_orientation) const </font> |
| </td> |
| <td>Expects a standard container of rectangle objects. Will scan |
| and eliminate overlaps. Slices polygon set geometry to rectangles |
| along the given orientation and appends them to the container. O( |
| n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"> |
| <font face="Courier New"> |
| bool <b>operator==</b>(const polygon_90_set_data& p) const</font></td> |
| <td>Once scanned the data representation of geometry within a polygon |
| set is in a mathematically canonical form. Comparison between two |
| sets is therefore a linear time operation once they are in the scanned |
| state. Will scan and eliminate overlaps in both polygon sets. O( n |
| log n) runtime complexity and O(n) memory wrt vertices + intersections |
| the first time, linear subsequently.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| bool <b>operator!=</b>(const polygon_90_set_data& p) const</font></td> |
| <td>Inverse logic of equivalence operator.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">void <b>clear</b>()</font></td> |
| <td>Make the polygon set empty. Note: does not de-allocate memory. |
| Use shrink to fit idiom and assign default constructed polygon set to |
| de-allocate.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">bool <b>empty</b>() const </font> |
| </td> |
| <td>Check whether the polygon set contains no geometry. Will scan |
| and eliminate overlaps because subtractive regions might make the |
| polygon set empty. O( n log n) runtime complexity and O(n) memory |
| wrt vertices + intersections the first time, linear subsequently.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">orientation_2d <b>orient</b>() const</font></td> |
| <td>Get the scanning orientation. Depending on the data it is |
| sometimes more efficient to scan in a specific orientation. This |
| is particularly true of Manhattan geometry data. Constant time.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">void <b>clean</b>() const</font></td> |
| <td>Scan and eliminate overlaps. O( n log n) runtime complexity |
| and O(n) memory wrt vertices + intersections the first time, constant |
| time subsequently.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| template <typename input_iterator_type><br> |
| void <b>set</b>(input_iterator_type input_begin, <br> input_iterator_type input_end, |
| <br> orientation_2d orient) </font> |
| </td> |
| <td>Overwrite geometry in polygon set with insertable objects in the |
| iterator range. Also sets the scanning orientation to that |
| specified.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| template <typename rectangle_type><br> |
| bool <b>extents</b>(rectangle_type& extents_rectangle) const</font></td> |
| <td>Given an object that models rectangle, scans and eliminates overlaps |
| in the polygon set because subtractive regions may alter its extents |
| then computes the bounding box and assigns it to extents_rectangle. |
| O( n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections the first time, linear subsequently.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| polygon_90_set_data&<br> |
| <b>bloat</b>(unsigned_area_type west_bloating,<br> |
| |
| unsigned_area_type east_bloating,<br> |
| |
| unsigned_area_type south_bloating,<br> |
| |
| unsigned_area_type north_bloating) </font></td> |
| <td>Scans to eliminate overlaps and subtractive regions. Inserts |
| rectangles of width specified by bloating values to the indicated side |
| of geometry within the polygon set and fills corners with rectangles of |
| the length and width specified for the adjacent sides. O( n log n) |
| runtime complexity and O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| polygon_90_set_data&<br> |
| <b>shrink</b>(unsigned_area_type west_shrinking,<br> |
| |
| unsigned_area_type east_shrinking,<br> |
| |
| unsigned_area_type south_shrinking,<br> |
| |
| unsigned_area_type north_shrinking)</font></td> |
| <td>Scans to eliminate overlaps and subtractive regions. Inserts |
| subtractiive rectangles of width specified by bloating values to the |
| indicated side of geometry within the polygon set and subtractive |
| rectangle at convex corners of the length and width specified for the |
| adjacent sides. Scans to eliminate overlapping subtractive |
| regions. O( n log n) runtime complexity and O(n) memory wrt |
| vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| polygon_90_set_data&<br> |
| <b>resize</b>(coordinate_type west, coordinate_type east, <br> coordinate_type south, coordinate_type north)</font></td> |
| <td>Call bloat or shrink or shrink then bloat depending on whether the |
| resizing values are positive or negative. O( n log n) runtime |
| complexity and O(n) memory wrt vertices + intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| polygon_90_set_data& <b>move</b>(coordinate_type x_delta, <br> coordinate_type |
| y_delta) </font> |
| </td> |
| <td>Add x_delta to x values and y_delta to y values of vertices stored |
| within the polygon set. Linear wrt. vertices.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| template <typename transformation_type><br> |
| polygon_90_set_data& <br><b>transform</b>(const transformation_type& transformation) </font> |
| </td> |
| <td>Applies transformation.transform() on vertices stored within the |
| polygon set. Linear wrt. vertices.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| polygon_90_set_data& <b>scale_up</b>(unsigned_area_type factor)</font></td> |
| <td>Scales vertices stored within the polygon set up by factor. |
| Linear wrt. vertices.</td> |
| </tr> |
| <tr> |
| <td width="586"> |
| <p><font face="Courier New">polygon_90_set_data& <b>scale_down</b>(unsigned_area_type |
| factor)</font> </td> |
| <td>Scales vertices stored within the polygon set down by factor. |
| Linear wrt. vertices.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New"> |
| template <typename scaling_type><br> |
| polygon_90_set_data&<br> <b>scale</b>(const anisotropic_scale_factor<scaling_type>& |
| f)</font></td> |
| <td>Scales vertices stored within the polygon set by applying f.scale(). |
| Linear wrt. vertices.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">polygon_90_set_data& <b>scale</b>(double factor) </font></td> |
| <td>Scales vertices stored within the polygon set by floating point |
| factor. Linear wrt. vertices.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">polygon_90_set_data& <b>self_xor</b>()</font></td> |
| <td>Retain only non-overlapping regions of geometry within polygon set. |
| O( n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">polygon_90_set_data& <b>self_intersect</b>()</font></td> |
| <td>Retain only overlapping regions of geometry within a polygon set. |
| O( n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections.</td> |
| </tr> |
| <tr> |
| <td width="586"><font face="Courier New">polygon_90_set_data&<br> <b>interact</b>(const polygon_90_set_data& that)</font></td> |
| <td>Retain only regions that touch or overlap regions in argument. |
| O( n log n) runtime complexity and O(n) memory wrt vertices + |
| intersections.</td> |
| </tr> |
| </table> |
| <tr> |
| <td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top"> |
| </td> |
| <td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%"> |
| |
| |
| <table class="docinfo" rules="none" frame="void" id="table4"> |
| <colgroup> |
| <col class="docinfo-name"><col class="docinfo-content"> |
| </colgroup> |
| <tbody vAlign="top"> |
| <tr> |
| <th class="docinfo-name">Copyright:</th> |
| <td>Copyright © Intel Corporation 2008-2010.</td> |
| </tr> |
| <tr class="field"> |
| <th class="docinfo-name">License:</th> |
| <td class="field-body">Distributed under the Boost Software License, |
| Version 1.0. (See accompanying file <tt class="literal"> |
| <span class="pre">LICENSE_1_0.txt</span></tt> or copy at |
| <a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt"> |
| http://www.boost.org/LICENSE_1_0.txt</a>)</td> |
| </tr> |
| </table> |
| |
| </html> |