123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732 |
- <!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 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><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
- Concept</a></li>
- <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
- Concept</a></li>
- <li>Polygon Set Concept</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 Set Concept</h1>
- <p> </p>
- <p>The polygon_set concept tag is <font face="Courier New">
- polygon_set_concept</font></p>
- <p> <font face="Times New Roman">The semantic of a polygon_set
- is zero or more geometry regions. A Polygon Set Concept may be
- defined with floating point coordinates, but a snap rounding distance
- of one integer unit will still be applied, furthermore, geometry
- outside the domain where one integer unit is sufficient to provide
- robustness may lead to undefined behavior in algorithms. It is
- recommended to use integer coordinates for robust operations. In
- the case that data represented contains only Manhattan geometry a
- runtime check will default to the Manhattan algorithm. The
- results of which are identical to what the general algorithm would do,
- but obtained more efficiently. In the case that the data
- represented contains only Manhattan and 45-degree geometry a runtime
- check will default to the faster 45-degree algorithm. The results
- of which may differ slight from what the general algorithm would do
- because non-integer intersections will be handled differently.</font></p>
- <p>Users are recommended to use std::vector and std::list of user
- defined polygons or library provided
- polygon_set_data<coordinate_type> objects. Lists and
- vectors of models of polygon_concept or polygon_with_holes_concept are
- automatically models of polygon_set_concept.</p>
- <p>Example code <a href="gtl_custom_polygon_set.htm">custom_polygon_set.cpp</a>
- demonstrates mapping a user defined class to the library
- polygon_set_concept</p>
- <p>An object that is a model of <font face="Courier New">
- polygon_set_concept</font> can be viewed as a model of <font
- face="Courier New">
- polygon_90_set_concept</font> or <font face="Courier New">
- polygon_45_set_concept</font> if it is determined at runtime to conform
- to the restrictions of those concepts. This concept casting is
- accomplished through the <font face="Courier New">view_as<>()</font>
- function.</p>
- <p><font face="Courier New">view_as<polygon_90_set_concept>(polygon_set_object)<br />
- view_as<polygon_45_set_concept>(polygon_set_object)</font></p>
- <p>The return value of <font face="Courier New">view_as<>()</font>
- can be passed into any interface that expects an object of the
- conceptual type specified in its template parameter. Polygon sets
- cannot be viewed as single polygons or rectangles since it generally
- cannot be known whether a polygon set contains only a single polygon
- without converting to polygons.</p>
- <h2>Operators</h2>
- <p>The return type of some operators is the <font
- face="Courier New">polygon_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_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="table5" border="1" width="100%">
- <tbody>
- <tr>
- <td width="586"><font face="Courier New">template
- <typename T1, typename T2><br />
- polygon_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_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().
- Expected n log n runtime, worst case quadratic runtime wrt. vertices +
- intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">template
- <typename T1, typename T2><br />
- polygon_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. Expected n log n
- runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">template
- <typename T1, typename T2><br />
- polygon_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_set or one of its
- refinements. Expected n log n runtime, worst case quadratic
- runtime wrt. vertices + intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">template
- <typename T1, typename T2><br />
- polygon_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.
- Expected n log n runtime, worst case quadratic runtime wrt. vertices +
- intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">template
- <typename T1, typename T2><br />
- polygon_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_set or
- one of its refinements. Expected n log n runtime, worst case
- quadratic runtime wrt. vertices + intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">template
- <typename T1, typename T2><br />
- polygon_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_set or one of
- its refinements. Expected n log n runtime, worst case quadratic
- runtime 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_set and not one of it's refinements.
- Expected n log n runtime, worst case quadratic runtime 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_set and not one of it's refinements.
- Expected n log n runtime, worst case quadratic runtime 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_set and not one of it's refinements.
- Expected n log n runtime, worst case quadratic runtime 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_set and not one of it's refinements.
- Expected n log n runtime, worst case quadratic runtime 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_set and not one of it's refinements.
- Expected n log n runtime, worst case quadratic runtime 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_set and not one of it's refinements.
- Expected n log n runtime, worst case quadratic runtime 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. Expected n log n
- runtime, worst case quadratic runtime 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. Expected n log n
- runtime, worst case quadratic runtime 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. Expected n
- log n runtime, worst case quadratic runtime 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. Expected n
- log n runtime, worst case quadratic runtime wrt. vertices +
- intersections.</td>
- </tr>
- </tbody>
- </table>
- <h2>Functions</h2>
- <table id="table6" 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_set or any of its refinements into an object
- that models polygon_set. Expected n log n runtime, worst case
- quadratic runtime 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_set or
- one of its refinements covers the exact same geometric regions as
- another object that models polygon_set or one of its refinements.
- For example: two of polygon objects. Expected n log n runtime,
- worst case quadratic runtime wrt. vertices + intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">template
- <typename output_container_type, typename T><br />
- void <b>get_trapezoids</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_set
- or one of its refinements into non overlapping trapezoids along a
- vertical slicing orientation and appends them to the output, which must
- have a value type that models polygon or polygon_with_holes.
- Expected n log n runtime, worst case quadratic runtime wrt. vertices +
- intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">template
- <typename output_container_type, typename T><br />
- void <b>get_trapezoids</b>(output_container_type& output, <br />
-
- const T& polygon_set,<br />
-
- orientation_2d orient)</font></td>
- <td>Output container is expected to be a standard
- container. Slices geometry of an object that models polygon_set
- or one of its refinements into non overlapping trapezoids along a the
- specified slicing orientation and appends them to the output, which
- must have a value type that models polygon or polygon_with_holes.
- Expected n log n runtime, worst case quadratic runtime wrt. vertices +
- intersections.</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. Expected n log n runtime, worst case quadratic
- runtime 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_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. Expected n log n runtime, worst case quadratic runtime wrt.
- vertices + intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">template
- <typename T><br />
- area_type <b>area</b>(const T& polygon_set)</font></td>
- <td>Computes the area covered by geometry in an object that
- models polygon_set. Expected n log n runtime, worst case
- quadratic runtime 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 polygons, bloating them and
- putting them back. Expected n log n runtime, worst case quadratic
- runtime 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 polygons, shrinking them and
- overwriting the polygon set with the resulting regions. Expected
- n log n runtime, worst case quadratic runtime 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,<br />
- bool
- corner_fill_arc = false, <br />
- unsigned int
- num_circle_segments = 0)</font></td>
- <td>Same as bloat if resizing is positive, same as shrink
- if resizing is negative. Original topology at acute angle
- vertices is preserved by default, segmented circular arcs are inserted
- if corner_fill_arc is true. num_circle_segments specifies number
- of segments to introduce on a full circle when filling acute angle
- corners with circular arcs. Expected n log n runtime, worst case
- quadratic runtime 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. Expected n
- log n runtime, worst case quadratic runtime 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. Expected
- n log n runtime, worst case quadratic runtime 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. Expected n log n runtime, worst case quadratic runtime
- 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. Expected n log n runtime, worst case quadratic
- runtime wrt. vertices + intersections.</td>
- </tr>
- </tbody>
- </table>
- <h1>Polygon Set Data Object</h1>
- <p> </p>
- <p>The polygon 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 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 Set Data is the following:</p>
- <p><font face="Courier New">template <typename T><br />
- class polygon_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>
- <p>Example code <a href="gtl_polygon_set_usage.htm">polygon_set_usage.cpp</a>
- demonstrates using the library provided polygon set data types and
- functions</p>
- <h2>Member Functions</h2>
- <table id="table7" border="1" width="100%">
- <tbody>
- <tr>
- <td width="586"><font face="Courier New"><b>polygon_set_data</b>()</font></td>
- <td>Default constructor. </td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">template
- <typename iT><br />
- <b>polygon_set_data</b>(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_set_data</b>(const
- polygon_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_set_data</b>(const
- polygon_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">polygon_set_data&
- <br />
- <b>operator=</b>(const polygon_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_set_data& <br />
- <b>operator=</b>(const polygon_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_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
- vertices inserted.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">
- void <b>insert</b>(const polygon_set_data& polygon_set)</font></td>
- <td>Insert a polygon set. Linear wrt vertices
- inserted.</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
- vertices inserted.</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 polygons objects.
- Will scan and eliminate overlaps. Converts polygon set geometry
- to objects of the polygon 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 the duplicate of the first, and the number of points
- is equal to the number of edges plus 1. If required by the output
- data type, polygons will have holes fractured out to the outer boundary
- along the positive y direction and off grid intersections on the outer
- boundary introduced by this fracture will be truncated downward.
- Expected n log n runtime, worst case quadratic runtime wrt. vertices +
- intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">template
- <typename output_container><br />
- void <b>get_trapezoids</b>(output_container& output) const</font></td>
- <td>Expects a standard container of polygon objects.
- Will scan and eliminate overlaps. Slices polygon set geometry to
- trapezoids vertically and appends them to the container. Expected
- n log n runtime, worst case quadratic runtime wrt. vertices +
- intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">
- template <typename output_container><br />
- void <b>get_trapezoids</b>(output_container& output, <br />
- orientation_2d slicing_orientation) const </font> </td>
- <td>Expects a standard container of polygon objects.
- Will scan and eliminate overlaps. Slices polygon set geometry to
- trapezoids along the given orientation and appends them to the
- container. Expected n log n runtime, worst case quadratic runtime
- wrt. vertices + intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">
- bool <b>operator==</b>(const polygon_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. Expected n log n runtime, worst case quadratic runtime wrt.
- vertices + intersections. </td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">bool <b>operator!=</b>(const
- polygon_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. Expected n log n
- runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">void <b>clean</b>()
- const</font></td>
- <td>Scan and eliminate overlaps. Expected n log n
- runtime, worst case quadratic runtime 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) </font> </td>
- <td>Overwrite geometry in polygon set with insertable
- objects in the iterator range. </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. Expected n log n runtime, worst case quadratic
- runtime wrt. vertices + intersections the first time, linear
- subsequently.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">polygon_set_data&<br />
- <b>resize</b>(coord_type resizing,<br />
- bool corner_fill_arc = false, <br />
- unsigned int num_circle_segments =
- 0)</font></td>
- <td>Inflates if resizing is positive, deflates if resizing
- is negative. Original topology at acute angle vertices is
- preserved by default, segmented circular arcs are inserted if
- corner_fill_arc is true. num_circle_segments specifies number of
- segments to introduce on a full circle when filling acute angle corners
- with circular arcs. Specifying zero for num_circle_segments
- results in only a single segment being inserted at acute corners.
- Expected n log n runtime, worst case quadratic runtime wrt. vertices +
- intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">template
- <typename transformation_type><br />
- polygon_set_data& <br />
- <b>transform</b>(const transformation_type&
- transformation) </font> </td>
- <td>Applies transformation.transform() on vertices stored
- within the polygon set. Expected n log n runtime, worst case
- quadratic runtime wrt. vertices + intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">polygon_set_data&
- <b>scale_up</b>(unsigned_area_type factor)</font></td>
- <td>Scales vertices stored within the polygon set up by
- factor. Expected n log n runtime, worst case quadratic runtime
- wrt. vertices + intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">polygon_set_data&
- <b>scale_down</b>(unsigned_area_type factor)</font> </td>
- <td>Scales vertices stored within the polygon set down by
- factor. Expected n log n runtime, worst case quadratic runtime
- wrt. vertices + intersections.</td>
- </tr>
- <tr>
- <td width="586"><font face="Courier New">template
- <typename scaling_type><br />
- polygon_set_data&<br />
- <b>scale</b>(const scaling_type& f)</font></td>
- <td>Scales vertices stored within the polygon set by
- applying f.scale(). Expected n log n runtime, worst case
- quadratic runtime 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="table8" 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>
|