1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006 |
- <!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" 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><!--
- 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" /><!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> --></head><body>
- <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 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>
- <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_segment_concept.htm">Segment 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>
- <li><a href="voronoi_main.htm">Voronoi Main Page<br />
- </a></li>
- <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br />
- </li>
- <li><a href="voronoi_builder.htm">Voronoi Builder</a></li>
- <li><a href="voronoi_diagram.htm">Voronoi Diagram</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>
- <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
- <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
- Tutorial</a></li>
- </ul>
- </div>
- <h3 class="navbar">Polygon Sponsor</h3>
- <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>
- </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>
- <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>
- <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>
- <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 id="table3" border="1" width="100%">
- <tbody>
- <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>
- </tbody>
- </table>
- <h2>Functions</h2>
- <table id="table1" border="1" width="100%">
- <tbody>
- <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>
- </tbody>
- </table>
- <h1>Polygon 90 Set Data Object</h1>
- <p> </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 id="table2" border="1" width="100%">
- <tbody>
- <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 style="vertical-align: top;"><font face="Courier New">template
- <typename output_container><br />
- void <b>get</b>(output_container& output, size_t k) const</font></td>
- <td style="vertical-align: top;">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. The resulting polygons will
- have at most k vertices. For Manhattan data k should be at least 4 .
- 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.<br />
- </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> </p>
- </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>
- </tbody>
- </table>
- </td>
- </tr>
- <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" id="table4" frame="void" rules="none">
- <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>
- </tbody>
- </table>
- </td>
- </tr>
- </tbody>
- </table>
- </body></html>
|