]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> |
2 | <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" | |
3 | xmlns:v="urn:schemas-microsoft-com:vml" | |
4 | xmlns:o="urn:schemas-microsoft-com:office:office" | |
5 | xmlns:(null)1="http://www.w3.org/TR/REC-html40" lang="en"> | |
6 | <head> | |
7 | <!-- | |
8 | Copyright 2009-2010 Intel Corporation | |
9 | license banner | |
10 | --> | |
11 | <title>Boost Polygon Library: Polygon 45 Set Concept</title> | |
12 | <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" /> | |
13 | <!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> --> | |
14 | </head> | |
15 | <body> | |
16 | <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" | |
17 | cellpadding="0" cellspacing="0"> | |
18 | <tbody> | |
19 | <tr> | |
20 | <td style="background-color: rgb(238, 238, 238);" nowrap="1" | |
21 | valign="top"> | |
22 | <div style="padding: 5px;" align="center"> <img | |
23 | src="images/boost.png" border="0" height="86" width="277" /><a | |
24 | title="www.boost.org home page" href="http://www.boost.org/" | |
25 | tabindex="2" style="border: medium none ;"> </a> </div> | |
26 | <div style="margin: 5px;"> | |
27 | <h3 class="navbar">Contents</h3> | |
28 | <ul> | |
29 | <li><a href="index.htm">Boost.Polygon Main Page</a></li> | |
30 | <li><a href="gtl_design_overview.htm">Design Overview</a></li> | |
31 | <li><a href="gtl_isotropy.htm">Isotropy</a></li> | |
32 | <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li> | |
33 | <li><a href="gtl_interval_concept.htm">Interval Concept</a></li> | |
34 | <li><a href="gtl_point_concept.htm">Point Concept</a></li> | |
35 | <li><a href="gtl_segment_concept.htm">Segment Concept</a></li> | |
36 | <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li> | |
37 | <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li> | |
38 | <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90 | |
39 | With Holes Concept</a></li> | |
40 | <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li> | |
41 | <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45 | |
42 | With Holes Concept</a></li> | |
43 | <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li> | |
44 | <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With | |
45 | Holes Concept</a></li> | |
46 | <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set | |
47 | Concept</a></li> | |
48 | <li>Polygon 45 Set Concept</li> | |
49 | <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li> | |
50 | <li><a href="gtl_connectivity_extraction_90.htm">Connectivity | |
51 | Extraction 90</a></li> | |
52 | <li><a href="gtl_connectivity_extraction_45.htm">Connectivity | |
53 | Extraction 45</a></li> | |
54 | <li><a href="gtl_connectivity_extraction.htm">Connectivity | |
55 | Extraction</a></li> | |
56 | <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li> | |
57 | <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li> | |
58 | <li><a href="gtl_property_merge.htm">Property Merge</a></li> | |
59 | <li><a href="voronoi_main.htm">Voronoi Main Page<br /> | |
60 | </a></li> | |
61 | <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br /> | |
62 | </li> | |
63 | <li><a href="voronoi_builder.htm">Voronoi Builder</a></li> | |
64 | <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li> | |
65 | </ul> | |
66 | <h3 class="navbar">Other Resources</h3> | |
67 | <ul> | |
68 | <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li> | |
69 | <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009 | |
70 | Presentation</a></li> | |
71 | <li><a href="analysis.htm">Performance Analysis</a></li> | |
72 | <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li> | |
73 | <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li> | |
74 | <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li> | |
75 | <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced | |
76 | Tutorial</a></li> | |
77 | </ul> | |
78 | </div> | |
79 | <h3 class="navbar">Polygon Sponsor</h3> | |
80 | <div style="padding: 5px;" align="center"> <img | |
81 | src="images/intlogo.gif" border="0" height="51" width="127" /><a | |
82 | title="www.adobe.com home page" href="http://www.adobe.com/" | |
83 | tabindex="2" style="border: medium none ;"> </a> </div> | |
84 | </td> | |
85 | <td | |
86 | style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" | |
87 | valign="top" width="100%"> | |
88 | <!-- End Header --><br /> | |
89 | <p> | |
90 | </p> | |
91 | <h1>Polygon 45 Set Concept</h1> | |
92 | <p> </p> | |
93 | <p>The polygon_45_set concept tag is <font face="Courier New"> | |
94 | polygon_45_set_concept</font></p> | |
95 | <p> <font face="Times New Roman">The semantic of a | |
96 | polygon_45_set is zero or more geometry regions which have angles at | |
97 | the vertices that are multiples of 45-degrees relative to the | |
98 | coordinate axis. A Polygon 45 Set Concept makes no sense in | |
99 | floating point, but currently does not provide a static assert to | |
100 | prevent it from being used with floating point coordinates. The | |
101 | result of such use is undefined. When the intersection of two 45 | |
102 | degree edges results in a vertex that is off the integer grid that case | |
103 | is handled by inserting a unit length edge between the two 45 degree | |
104 | edges near the off grid intersection point. In the case that data | |
105 | represented contains no 45-degree angles and is Manhattan a runtime | |
106 | check will default to the Manhattan algorithm. The results of | |
107 | which are identical to what the 45-degree algorithm would do, but | |
108 | obtained more efficiently.</font></p> | |
109 | <p> <font face="Times New Roman">The motivation for providing | |
110 | the polygon_45_set is to extend the special case of Manhattan geometry | |
111 | capability of the library to encompass the slightly less common, but | |
112 | still important special case of geometry that is described by angles | |
113 | that are multiples of 45-degress with respect to the coordinate | |
114 | axis. This simplifies the implementation of geometry algorithms | |
115 | and affords many opportunities for optimization. 45-degree | |
116 | algorithms can be 50X faster than arbitrary angle algorithms and are | |
117 | required to provide a complete feature set that meets the performance | |
118 | requirements of application domains in which Manhattan and 45-degree | |
119 | geometry are a common special case.</font></p> | |
120 | <p>Users are recommended to use std::vector and std::list of user | |
121 | defined polygons or library provided | |
122 | polygon_45_set_data<coordinate_type> objects. Lists and | |
123 | vectors of models of polygon_45_concept or | |
124 | polygon_45_with_holes_concept are automatically models of | |
125 | polygon_45_set_concept.</p> | |
126 | <p>An object that is a model of <font face="Courier New"> | |
127 | polygon_45_set_concept</font> can be viewed as a model of <font | |
128 | face="Courier New"> | |
129 | polygon_90_set_concept</font> if it is determined at runtime to conform | |
130 | to the restriction that all edges are axis-parallel. This concept | |
131 | casting is accomplished through the <font face="Courier New">view_as<>()</font> | |
132 | function.</p> | |
133 | <p><font face="Courier New">view_as<polygon_90_set_concept>(polygon_set_object)</font></p> | |
134 | <p>The return value of <font face="Courier New">view_as<>()</font> | |
135 | can be passed into any interface that expects an object of the | |
136 | conceptual type specified in its template parameter. Polygon sets | |
137 | cannot be viewed as single polygons or rectangles since it generally | |
138 | cannot be known whether a polygon set contains only a single polygon | |
139 | without converting to polygons.</p> | |
140 | <h2>Operators</h2> | |
141 | <p>The return type of some operators is the <font | |
142 | face="Courier New">polygon_45_set_view</font> operator template | |
143 | type. This type is itself a model of the polygon 90 set concept, | |
144 | but furthermore can be used as an argument to the <font | |
145 | face="Courier New">polygon_45_set_data</font> constructor and | |
146 | assignment operator. The operator template exists to eliminate | |
147 | temp copies of intermediate results when Boolean operators are chained | |
148 | together.</p> | |
149 | <p>Operators are declared inside the namespace <font | |
150 | face="Courier New">boost::polygon::operators</font>.</p> | |
151 | <table id="table5" border="1" width="100%"> | |
152 | <tbody> | |
153 | <tr> | |
154 | <td width="586"><font face="Courier New">template | |
155 | <typename T1, typename T2><br /> | |
156 | polygon_45_set_view <b>operator</b>|(const T1& l, const T2& r)</font></td> | |
157 | <td>Boolean OR operation (polygon set union). Accepts | |
158 | two objects that model polygon_45_set or one of its refinements. | |
159 | Returns an operator template that performs the operation on demand when | |
160 | chained or or nested in a library function call such as assign(). | |
161 | O( n log n) runtime complexity and O(n) memory wrt vertices + | |
162 | intersections.</td> | |
163 | </tr> | |
164 | <tr> | |
165 | <td width="586"><font face="Courier New">template | |
166 | <typename T1, typename T2><br /> | |
167 | polygon_45_set_view <b>operator</b>+(const T1& l, const T2& r)</font></td> | |
168 | <td>Same as operator|. The plus sign is also used for | |
169 | OR operations in Boolean logic expressions. O( n log n) runtime | |
170 | complexity and O(n) memory wrt vertices + intersections.</td> | |
171 | </tr> | |
172 | <tr> | |
173 | <td width="586"><font face="Courier New">template | |
174 | <typename T1, typename T2><br /> | |
175 | polygon_45_set_view <b>operator</b>&(const T1& l, const | |
176 | T2& r)</font></td> | |
177 | <td>Boolean AND operation (polygon set intersection). | |
178 | Accepts two objects that model polygon_45_set or one of its | |
179 | refinements. O( n log n) runtime complexity and O(n) memory wrt | |
180 | vertices + intersections.</td> | |
181 | </tr> | |
182 | <tr> | |
183 | <td width="586"><font face="Courier New">template | |
184 | <typename T1, typename T2><br /> | |
185 | polygon_45_set_view <b>operator</b>*(const T1& l, const T2& r)</font></td> | |
186 | <td>Same as operator&. The multiplication symbol | |
187 | is also used for AND operations in Boolean logic expressions. O( | |
188 | n log n) runtime complexity and O(n) memory wrt vertices + | |
189 | intersections.</td> | |
190 | </tr> | |
191 | <tr> | |
192 | <td width="586"><font face="Courier New">template | |
193 | <typename T1, typename T2><br /> | |
194 | polygon_45_set_view <b>operator</b>^(const T1& l, const T2& r)</font></td> | |
195 | <td>Boolean XOR operation (polygon set | |
196 | disjoint-union). Accepts two objects that model polygon_45_set or | |
197 | one of its refinements. O( n log n) runtime complexity and O(n) | |
198 | memory wrt vertices + intersections.</td> | |
199 | </tr> | |
200 | <tr> | |
201 | <td width="586"><font face="Courier New">template | |
202 | <typename T1, typename T2><br /> | |
203 | polygon_45_set_view <b>operator</b>-(const T1& l, const T2& r)</font></td> | |
204 | <td>Boolean SUBTRACT operation (polygon set | |
205 | difference). Accepts two objects that model polygon_45_set or one | |
206 | of its refinements. O( n log n) runtime complexity and O(n) | |
207 | memory wrt vertices + intersections.</td> | |
208 | </tr> | |
209 | <tr> | |
210 | <td width="586"><font face="Courier New">template | |
211 | <typename T1, typename T2><br /> | |
212 | T1& <b>operator</b>|=(const T1& l, const T2& r)</font></td> | |
213 | <td>Same as operator|, but with self assignment, left | |
214 | operand must model polygon_45_set and not one of it's | |
215 | refinements. O( n log n) runtime complexity and O(n) memory wrt | |
216 | vertices + intersections.</td> | |
217 | </tr> | |
218 | <tr> | |
219 | <td width="586"><font face="Courier New">template | |
220 | <typename T1, typename T2><br /> | |
221 | T1& <b>operator</b>+=(T1& l, const T2& r)</font></td> | |
222 | <td>Same as operator+, but with self assignment, left | |
223 | operand must model polygon_45_set and not one of it's | |
224 | refinements. O( n log n) runtime complexity and O(n) memory wrt | |
225 | vertices + intersections.</td> | |
226 | </tr> | |
227 | <tr> | |
228 | <td width="586"><font face="Courier New">template | |
229 | <typename T1, typename T2><br /> | |
230 | T1& <b>operator</b>&=(const T1& l, const T2& r)</font></td> | |
231 | <td>Same as operator&, but with self assignment, left | |
232 | operand must model polygon_45_set and not one of it's | |
233 | refinements. O( n log n) runtime complexity and O(n) memory wrt | |
234 | vertices + intersections.</td> | |
235 | </tr> | |
236 | <tr> | |
237 | <td width="586"><font face="Courier New">template | |
238 | <typename T1, typename T2><br /> | |
239 | T1& <b>operator</b>*=(T1& l, const T2& r)</font></td> | |
240 | <td>Same as operator*, but with self assignment, left | |
241 | operand must model polygon_45_set and not one of it's | |
242 | refinements. O( n log n) runtime complexity and O(n) memory wrt | |
243 | vertices + intersections.</td> | |
244 | </tr> | |
245 | <tr> | |
246 | <td width="586"><font face="Courier New">template | |
247 | <typename T1, typename T2><br /> | |
248 | T1& <b>operator</b>^=(const T1& l, const T2& r)</font></td> | |
249 | <td>Same as operator^, but with self assignment, left | |
250 | operand must model polygon_45_set and not one of it's | |
251 | refinements. O( n log n) runtime complexity and O(n) memory wrt | |
252 | vertices + intersections.</td> | |
253 | </tr> | |
254 | <tr> | |
255 | <td width="586"><font face="Courier New">template | |
256 | <typename T1, typename T2><br /> | |
257 | T1& <b>operator</b>-=(T1& l, const T2& r)</font></td> | |
258 | <td>Same as operator-, but with self assignment, left | |
259 | operand must model polygon_45_set and not one of it's | |
260 | refinements. O( n log n) runtime complexity and O(n) memory wrt | |
261 | vertices + intersections.</td> | |
262 | </tr> | |
263 | <tr> | |
264 | <td width="586"><font face="Courier New">template | |
265 | <typename T1><br /> | |
266 | T1 <b>operator</b>+(const T1&, coordinate_type bloating)</font></td> | |
267 | <td>Performs resize operation, inflating by bloating | |
268 | ammount. If negative the result is a shrink instead of | |
269 | bloat. Note: returns result by value. O( n log n) runtime | |
270 | complexity and O(n) memory wrt vertices + intersections.</td> | |
271 | </tr> | |
272 | <tr> | |
273 | <td width="586"><font face="Courier New">template | |
274 | <typename T1, typename T2><br /> | |
275 | T1 <b>operator</b>-(const T1&, coordinate_type shrinking)</font></td> | |
276 | <td>Performs resize operation, deflating by bloating | |
277 | ammount. If negative the result is a bloat instead of | |
278 | shrink. Note: returns result by value. O( n log n) runtime | |
279 | complexity and O(n) memory wrt vertices + intersections.</td> | |
280 | </tr> | |
281 | <tr> | |
282 | <td width="586"><font face="Courier New">template | |
283 | <typename T1, typename T2><br /> | |
284 | T1& <b>operator</b>+=(const T1&, coordinate_type bloating)</font></td> | |
285 | <td>Performs resize operation, inflating by bloating | |
286 | ammount. If negative the result is a shrink instead of | |
287 | bloat. Returns reference to modified argument. O( n log n) | |
288 | runtime complexity and O(n) memory wrt vertices + intersections.</td> | |
289 | </tr> | |
290 | <tr> | |
291 | <td width="586"><font face="Courier New">template | |
292 | <typename T1, typename T2><br /> | |
293 | T1& <b>operator</b>-=(const T1&, coordinate_type shrinking)</font></td> | |
294 | <td>Performs resize operation, deflating by bloating | |
295 | ammount. If negative the result is a bloat instead of | |
296 | shrink. Returns reference to modified argument. O( n log n) | |
297 | runtime complexity and O(n) memory wrt vertices + intersections.</td> | |
298 | </tr> | |
299 | </tbody> | |
300 | </table> | |
301 | <h2>Functions</h2> | |
302 | <table id="table3" border="1" width="100%"> | |
303 | <tbody> | |
304 | <tr> | |
305 | <td width="586"><font face="Courier New">template | |
306 | <typename T1, typename T2><br /> | |
307 | T1& <b>assign</b>(T1& lvalue, const T2& rvalue)</font></td> | |
308 | <td>Eliminates overlaps in geometry and copies from an | |
309 | object that models polygon_45_set or any of its refinements into an | |
310 | object that models polygon_45_set. O( n log n) runtime complexity | |
311 | and O(n) memory wrt vertices + intersections.</td> | |
312 | </tr> | |
313 | <tr> | |
314 | <td width="586"><font face="Courier New">template | |
315 | <typename T1, typename T2><br /> | |
316 | bool <b>equivalence</b>(const T1& lvalue, const T2& rvalue) </font></td> | |
317 | <td>Returns true if an object that models polygon_45_set or | |
318 | one of its refinements covers the exact same geometric regions as | |
319 | another object that models polygon_45_set or one of its | |
320 | refinements. For example: two of polygon_45 objects. O( n | |
321 | log n) runtime complexity and O(n) memory wrt vertices + intersections.</td> | |
322 | </tr> | |
323 | <tr> | |
324 | <td width="586"><font face="Courier New">template | |
325 | <typename output_container_type, typename T><br /> | |
326 | void <b>get_trapezoids</b>(output_container_type& output, <br /> | |
327 | | |
328 | const T& polygon_set)</font></td> | |
329 | <td>Output container is expected to be a standard | |
330 | container. Slices geometry of an object that models | |
331 | polygon_45_set or one of its refinements into non overlapping | |
332 | trapezoids along a vertical slicing orientation and appends them to the | |
333 | output, which must have a value type that models polygon_45, | |
334 | polygon_45_with_holes, polygon or polygon_with_holes. O( n | |
335 | log n) runtime complexity and O(n) memory wrt vertices.</td> | |
336 | </tr> | |
337 | <tr> | |
338 | <td width="586"><font face="Courier New">template | |
339 | <typename output_container_type, typename T><br /> | |
340 | void <b>get_trapezoids</b>(output_container_type& output, <br /> | |
341 | | |
342 | const T& polygon_set,<br /> | |
343 | | |
344 | orientation_2d orient)</font></td> | |
345 | <td>Output container is expected to be a standard | |
346 | container. Slices geometry of an object that models | |
347 | polygon_45_set or one of its refinements into non overlapping | |
348 | trapezoids along a the specified slicing orientation and appends them | |
349 | to the output, which must have a value type that models polygon_45, | |
350 | polygon_45_with_holes, polygon or polygon_with_holes. O( n | |
351 | log n) runtime complexity and O(n) memory wrt vertices.</td> | |
352 | </tr> | |
353 | <tr> | |
354 | <td width="586"><font face="Courier New">template | |
355 | <typename polygon_set_type><br /> | |
356 | void <b>clear</b>(polygon_set_type& polygon_set)</font></td> | |
357 | <td>Makes the object empty of geometry.</td> | |
358 | </tr> | |
359 | <tr> | |
360 | <td width="586"><font face="Courier New">template | |
361 | <typename polygon_set_type><br /> | |
362 | bool <b>empty</b>(const polygon_set_type& polygon_set)</font></td> | |
363 | <td>Checks whether the object is empty of geometry. | |
364 | Polygons that are completely covered by holes will result in empty | |
365 | returning true. O( n log n) runtime complexity and O(n) | |
366 | memory wrt vertices.</td> | |
367 | </tr> | |
368 | <tr> | |
369 | <td width="586"><font face="Courier New">template | |
370 | <typename T, typename rectangle_type><br /> | |
371 | bool <b>extents</b>(rectangle_type& extents_rectangle, <br /> | |
372 | | |
373 | const T& polygon_set)</font></td> | |
374 | <td>Computes bounding box of an object that models | |
375 | polygon_45_set and stores it in an object that models rectangle. | |
376 | If the polygon set is empty returns false. If there are holes | |
377 | outside of shells they do not contribute to the extents of the polygon | |
378 | set. O( n log n) runtime complexity and O(n) memory wrt | |
379 | vertices.</td> | |
380 | </tr> | |
381 | <tr> | |
382 | <td width="586"><font face="Courier New">template | |
383 | <typename T><br /> | |
384 | area_type <b>area</b>(const T& polygon_set)</font></td> | |
385 | <td>Computes the area covered by geometry in an object that | |
386 | models polygon_45_set. O( n log n) runtime complexity and | |
387 | O(n) memory wrt vertices.</td> | |
388 | </tr> | |
389 | <tr> | |
390 | <td width="586"><font face="Courier New">template | |
391 | <typename T1, typename T2><br /> | |
392 | T1& <b>interact</b>(T1& a, const T2& b)</font></td> | |
393 | <td>Given an object that models polygon_45_set and an | |
394 | object that models polygon_45_set or one of its refinements, modifies a | |
395 | to retain only regions that overlap or touch regions in b. | |
396 | O( n log n) runtime complexity and O(n) memory wrt vertices plus | |
397 | intersections.</td> | |
398 | </tr> | |
399 | <tr> | |
400 | <td width="586"><font face="Courier New">template | |
401 | <typename T><br /> | |
402 | T& <b>self_intersect</b>(T& polygon_set)</font></td> | |
403 | <td>Given an object that models polygon_45_set that has | |
404 | self overlapping regions, modifies the argument to contain only the | |
405 | regions of overlap. O( n log n) runtime complexity and O(n) | |
406 | memory wrt vertices + intersections.</td> | |
407 | </tr> | |
408 | <tr> | |
409 | <td width="586"><font face="Courier New">template | |
410 | <typename T><br /> | |
411 | T& <b>self_xor</b>(T& polygon_set)</font></td> | |
412 | <td>Given an object that models polygon_45_set that has | |
413 | self overlapping regions, modifies the argument to contain only the | |
414 | regions that do not overlap. O( n log n) runtime complexity and | |
415 | O(n) memory wrt vertices + intersections.</td> | |
416 | </tr> | |
417 | <tr> | |
418 | <td width="586"><font face="Courier New">template | |
419 | <typename T><br /> | |
420 | T& <b>bloat</b>(T& polygon_set, unsigned_area_type bloating)</font></td> | |
421 | <td>Same as getting all the polygons, bloating them and | |
422 | putting them back. O( n log n) runtime complexity and O(n) memory | |
423 | wrt vertices + intersections.</td> | |
424 | </tr> | |
425 | <tr> | |
426 | <td width="586"><font face="Courier New">template | |
427 | <typename T><br /> | |
428 | T& <b>shrink</b>(T& polygon_set, unsigned_area_type shrinking)</font></td> | |
429 | <td>Same as getting all the polygons, shrinking them and | |
430 | overwriting the polygon set with the resulting regions. O( n log | |
431 | n) runtime complexity and O(n) memory wrt vertices + intersections.</td> | |
432 | </tr> | |
433 | <tr> | |
434 | <td width="586"><font face="Courier New">template | |
435 | <typename T, typename coord_type><br /> | |
436 | T& <b>resize</b>(T& polygon_set, coord_type resizing,<br /> | |
437 | RoundingOption | |
438 | rounding = CLOSEST, <br /> | |
439 | CornerOption | |
440 | corner = INTERSECTION)</font></td> | |
441 | <td>Same as bloat if resizing is positive, same as shrink | |
442 | if resizing is negative. RoundingOption is an enum that controls | |
443 | snapping of non-integer results of resizing 45 degree edges. | |
444 | CornerOption is an enum that controls how corner filling is | |
445 | performed. polygon_45_set_data.hpp defines these enums. O( | |
446 | n log n) runtime complexity and O(n) memory wrt vertices + | |
447 | intersections.</td> | |
448 | </tr> | |
449 | <tr> | |
450 | <td width="586"><font face="Courier New">template | |
451 | <typename T><br /> | |
452 | T& <b>grow_and</b>(T& polygon_set, unsigned_area_type bloating)</font></td> | |
453 | <td>Same as bloating non-overlapping regions and then | |
454 | applying self intersect to retain only the overlaps introduced by the | |
455 | bloat. O( n log n) runtime complexity and O(n) memory wrt | |
456 | vertices + intersections.</td> | |
457 | </tr> | |
458 | <tr> | |
459 | <td width="586"><font face="Courier New">template | |
460 | <typename T><br /> | |
461 | T& <b>scale_up</b>(T& polygon_set, unsigned_area_type factor)</font></td> | |
462 | <td>Scales geometry up by unsigned factor. O( n log | |
463 | n) runtime complexity and O(n) memory wrt vertices.</td> | |
464 | </tr> | |
465 | <tr> | |
466 | <td width="586"><font face="Courier New">template | |
467 | <typename T><br /> | |
468 | T& <b>scale_down</b>(T& polygon_set, unsigned_area_type factor)</font></td> | |
469 | <td>Scales geometry down by unsigned factor. Snaps 45 | |
470 | degree edges back to 45 degrees after division truncation leads to | |
471 | small changes in angle. O( n log n) runtime complexity and O(n) | |
472 | memory wrt vertices.</td> | |
473 | </tr> | |
474 | <tr> | |
475 | <td width="586"><font face="Courier New">template | |
476 | <typename T, typename scaling_type><br /> | |
477 | T& <b>scale</b>(polygon_set_type& polygon_set, double scaling)</font></td> | |
478 | <td>Scales geometry by multiplying by floating point | |
479 | factor. Snaps 45 degree edges back to 45 degrees after | |
480 | truncation of fractional results of multiply leads to small changes in | |
481 | angle. O( n log n) runtime complexity and O(n) memory wrt | |
482 | vertices.</td> | |
483 | </tr> | |
484 | <tr> | |
485 | <td width="586"><font face="Courier New">template | |
486 | <typename T, typename transformation_type><br /> | |
487 | T& <b>transform</b>(T& polygon_set,<br /> | |
488 | | |
489 | const transformation_type& transformation)</font></td> | |
490 | <td>Applies transformation.transform() on all | |
491 | vertices. O( n log n) runtime complexity and O(n) memory wrt | |
492 | vertices.</td> | |
493 | </tr> | |
494 | <tr> | |
495 | <td width="586"><font face="Courier New">template | |
496 | <typename T><br /> | |
497 | T& <b>keep</b>(T& polygon_set, <br /> | |
498 | unsigned_area_type min_area,<br /> | |
499 | unsigned_area_type max_area,<br /> | |
500 | unsigned_area_type min_width,<br /> | |
501 | unsigned_area_type max_width,<br /> | |
502 | unsigned_area_type | |
503 | min_height,<br /> | |
504 | unsigned_area_type | |
505 | max_height)</font></td> | |
506 | <td>Retains only regions that satisfy the min/max criteria | |
507 | in the argument list. Note: useful for visualization to cull too | |
508 | small polygons. O( n log n) runtime complexity and O(n) memory | |
509 | wrt vertices.</td> | |
510 | </tr> | |
511 | </tbody> | |
512 | </table> | |
513 | <h1>Polygon 45 Set Data Object</h1> | |
514 | <p> </p> | |
515 | <p>The polygon 45 set data type encapsulates the internal data | |
516 | format that serves as the input to the sweep-line algorithm that | |
517 | implements polygon-clipping Boolean operations. It also | |
518 | internally keeps track of whether that data has been sorted or scanned | |
519 | and maintains the invariant that when its flags indicate that the data | |
520 | is sorted or scanned the data has not been changed to violate that | |
521 | assumption. Using the Polygon 45 Set Data type directly can be | |
522 | more efficient than using lists and vectors of polygons in the | |
523 | functions above because of the invariants it can enforce which provide | |
524 | the opportunity to maintain the data is sorted form rather than going | |
525 | all the way out to polygons then resorting those vertices for a | |
526 | subsequent operation.</p> | |
527 | <p>The declaration of Polygon 45 Set Data is the following:</p> | |
528 | <p><font face="Courier New">template <typename T><br /> | |
529 | class polygon_45_set_data;</font></p> | |
530 | <p>The class is parameterized on the coordinate data type. | |
531 | Algorithms that benefit from knowledge of the invariants enforced by | |
532 | the class are implemented as member functions to provide them access to | |
533 | information about those invariants. </p> | |
534 | <h2>Member Functions</h2> | |
535 | <table id="table4" border="1" width="100%"> | |
536 | <tbody> | |
537 | <tr> | |
538 | <td width="586"><font face="Courier New"><b>polygon_45_set_data</b>()</font></td> | |
539 | <td>Default constructor. </td> | |
540 | </tr> | |
541 | <tr> | |
542 | <td width="586"><font face="Courier New">template | |
543 | <typename iT><br /> | |
544 | <b>polygon_45_set_data</b>(iT input_begin, iT input_end)</font></td> | |
545 | <td>Construct from an iterator range of insertable objects.</td> | |
546 | </tr> | |
547 | <tr> | |
548 | <td width="586"><font face="Courier New"> <b>polygon_45_set_data</b>(const | |
549 | polygon_45_set_data& that)</font></td> | |
550 | <td>Copy construct.</td> | |
551 | </tr> | |
552 | <tr> | |
553 | <td width="586"><font face="Courier New">template | |
554 | <typename l, typename r, typename op><br /> | |
555 | <b>polygon_45_set_data</b>(const | |
556 | polygon_45_set_view<l,r,op>& t)</font></td> | |
557 | <td>Copy construct from a Boolean operator template.</td> | |
558 | </tr> | |
559 | <tr> | |
560 | <td width="586"><font face="Courier New">polygon_45_set_data& | |
561 | <br /> | |
562 | <b>operator=</b>(const polygon_45_set_data& that)</font></td> | |
563 | <td>Assignment from another polygon set, may change | |
564 | scanning orientation.</td> | |
565 | </tr> | |
566 | <tr> | |
567 | <td width="586"><font face="Courier New">template | |
568 | <typename l, typename r, typename op><br /> | |
569 | polygon_45_set_data& <br /> | |
570 | <b>operator=</b>(const polygon_45_set_view<l, r, | |
571 | op>& that)</font></td> | |
572 | <td>Assignment from a Boolean operator template.</td> | |
573 | </tr> | |
574 | <tr> | |
575 | <td width="586"><font face="Courier New">template | |
576 | <typename geometry_object><br /> | |
577 | polygon_45_set_data& <b>operator=</b>(const geometry_object& | |
578 | geo)</font></td> | |
579 | <td>Assignment from an insertable object.</td> | |
580 | </tr> | |
581 | <tr> | |
582 | <td width="586"><font face="Courier New"> | |
583 | template <typename iT><br /> | |
584 | void <b>insert</b>(iT input_begin, iT input_end, <br /> | |
585 | bool | |
586 | is_hole = false)</font></td> | |
587 | <td>Insert objects of an iterator range. If is_hole | |
588 | is true inserts subtractive regions. Linear wrt the number of | |
589 | vertices added.</td> | |
590 | </tr> | |
591 | <tr> | |
592 | <td width="586"><font face="Courier New"> | |
593 | void <b>insert</b>(const polygon_45_set_data& polygon_set, <br /> | |
594 | bool | |
595 | is_hole = false)</font></td> | |
596 | <td>Insert a polygon set. Linear wrt the number of | |
597 | vertices added.</td> | |
598 | </tr> | |
599 | <tr> | |
600 | <td width="586"><font face="Courier New"> | |
601 | template <typename geometry_type><br /> | |
602 | void <b>insert</b>(const geometry_type& geometry_object, <br /> | |
603 | bool | |
604 | is_hole = false)</font></td> | |
605 | <td>Insert a geometry object, if is_hole is true then the | |
606 | inserted region is subtractive rather than additive. Linear wrt | |
607 | the number of vertices added.</td> | |
608 | </tr> | |
609 | <tr> | |
610 | <td width="586"><font face="Courier New">template | |
611 | <typename output_container><br /> | |
612 | void <b>get</b>(output_container& output) const</font></td> | |
613 | <td>Expects a standard container of geometry objects. | |
614 | Will scan and eliminate overlaps. Converts polygon set geometry | |
615 | to objects of that type and appends them to the container. | |
616 | Polygons will be output with counterclockwise winding, hole polygons | |
617 | will be output with clockwise winding. The last vertex of an | |
618 | output polygon is not the duplicate of the first, and the number of | |
619 | points is equal to the number of edges. O(n log n) runtime and | |
620 | O(n) memory wrt. vertices + intersections.</td> | |
621 | </tr> | |
622 | <tr> | |
623 | <td width="586"><font face="Courier New">template | |
624 | <typename output_container><br /> | |
625 | void <b>get_polygons</b>(output_container& output) const</font></td> | |
626 | <td>Expects a standard container of polygon objects. | |
627 | Will scan and eliminate overlaps. Converts polygon set geometry | |
628 | to polygons and appends them to the container. Polygons will have | |
629 | holes fractured out to the outer boundary along the positive y | |
630 | direction. O(n log n) runtime and O(n) memory wrt. vertices + | |
631 | intersections.</td> | |
632 | </tr> | |
633 | <tr> | |
634 | <td width="586"><font face="Courier New">template | |
635 | <typename output_container><br /> | |
636 | void <b>get_polygons_with_holes</b>(output_container& o) const</font></td> | |
637 | <td>Expects a standard container of polygon with holes | |
638 | objects. Will scan and eliminate overlaps. Converts polygon | |
639 | set geometry to polygons and appends them to the container. O(n | |
640 | log n) runtime and O(n) memory wrt. vertices + intersections.</td> | |
641 | </tr> | |
642 | <tr> | |
643 | <td width="586"><font face="Courier New">template | |
644 | <typename output_container><br /> | |
645 | void <b>get_trapezoids</b>(output_container& output) const</font></td> | |
646 | <td>Expects a standard container of polygon objects. | |
647 | Will scan and eliminate overlaps. Slices polygon set geometry to | |
648 | trapezoids vertically and appends them to the container. O(n log | |
649 | n) runtime and O(n) memory wrt. vertices + intersections.</td> | |
650 | </tr> | |
651 | <tr> | |
652 | <td width="586"><font face="Courier New"> | |
653 | template <typename output_container><br /> | |
654 | void <b>get_trapezoids</b>(output_container& output, <br /> | |
655 | orientation_2d slicing_orientation) const </font> </td> | |
656 | <td>Expects a standard container of polygon objects. | |
657 | Will scan and eliminate overlaps. Slices polygon set geometry to | |
658 | trapezoids along the given orientation and appends them to the | |
659 | container. O(n log n) runtime and O(n) memory wrt. vertices + | |
660 | intersections.</td> | |
661 | </tr> | |
662 | <tr> | |
663 | <td width="586"><font face="Courier New"> | |
664 | bool <b>operator==</b>(const polygon_45_set_data& p) const</font></td> | |
665 | <td>Once scanned the data representation of geometry within | |
666 | a polygon set is in a mathematically canonical form. Comparison | |
667 | between two sets is therefore a linear time operation once they are in | |
668 | the scanned state. Will scan and eliminate overlaps in both polygon | |
669 | sets. O(n log n) runtime and O(n) memory wrt. vertices + | |
670 | intersections the first time and linear runtime and constant memory | |
671 | subsequently. </td> | |
672 | </tr> | |
673 | <tr> | |
674 | <td width="586"><font face="Courier New">bool <b>operator!=</b>(const | |
675 | polygon_45_set_data& p) const</font></td> | |
676 | <td>Inverse logic of equivalence operator.</td> | |
677 | </tr> | |
678 | <tr> | |
679 | <td width="586"><font face="Courier New">void <b>clear</b>()</font></td> | |
680 | <td>Make the polygon set empty. Note: does not | |
681 | de-allocate memory. Use shrink to fit idiom and assign default | |
682 | constructed polygon set to de-allocate.</td> | |
683 | </tr> | |
684 | <tr> | |
685 | <td width="586"><font face="Courier New">bool <b>empty</b>() | |
686 | const </font> </td> | |
687 | <td>Check whether the polygon set contains no | |
688 | geometry. Will scan and eliminate overlaps because subtractive | |
689 | regions might make the polygon set empty. O(n log n) runtime and | |
690 | O(n) memory wrt. vertices + intersections the first time and linear | |
691 | runtime and constant memory subsequently. </td> | |
692 | </tr> | |
693 | <tr> | |
694 | <td width="586"><font face="Courier New">bool <b>is_manhattan</b>() | |
695 | const</font></td> | |
696 | <td>Returns in constant time the information about whether | |
697 | the geometry contains only Manhattan (axis-parallel rectilinear) | |
698 | edges. Constant time.</td> | |
699 | </tr> | |
700 | <tr> | |
701 | <td width="586"><font face="Courier New">void <b>clean</b>() | |
702 | const</font></td> | |
703 | <td>Scan and eliminate overlaps. O(n log n) runtime | |
704 | and O(n) memory wrt. vertices + intersections the first time and linear | |
705 | runtime and constant memory subsequently. </td> | |
706 | </tr> | |
707 | <tr> | |
708 | <td width="586"><font face="Courier New">template | |
709 | <typename input_iterator_type><br /> | |
710 | void <b>set</b>(input_iterator_type input_begin, <br /> | |
711 | input_iterator_type | |
712 | input_end) </font> </td> | |
713 | <td>Overwrite geometry in polygon set with insertable | |
714 | objects in the iterator range. </td> | |
715 | </tr> | |
716 | <tr> | |
717 | <td width="586"><font face="Courier New">template | |
718 | <typename rectangle_type><br /> | |
719 | bool <b>extents</b>(rectangle_type& extents_rectangle) const</font></td> | |
720 | <td>Given an object that models rectangle, scans and | |
721 | eliminates overlaps in the polygon set because subtractive regions may | |
722 | alter its extents then computes the bounding box and assigns it to | |
723 | extents_rectangle. O(n log n) runtime and O(n) memory wrt. | |
724 | vertices the first time and linear runtime and constant memory | |
725 | subsequently. </td> | |
726 | </tr> | |
727 | <tr> | |
728 | <td width="586"><font face="Courier New">polygon_45_set_data&<br /> | |
729 | <b>resize</b>(coord_type resizing,<br /> | |
730 | RoundingOption rounding = CLOSEST, | |
731 | <br /> | |
732 | CornerOption corner = INTERSECTION)</font></td> | |
733 | <td>Same as bloat if resizing is positive, same as shrink | |
734 | if resizing is negative. RoundingOption is an enum that controls | |
735 | snapping of non-integer results of resizing 45 degree edges. | |
736 | CornerOption is an enum that controls how corner filling is | |
737 | performed. polygon_45_set_data.hpp defines these enums. O(n | |
738 | log n) runtime and O(n) memory wrt. vertices + intersections.</td> | |
739 | </tr> | |
740 | <tr> | |
741 | <td width="586"><font face="Courier New">template | |
742 | <typename transformation_type><br /> | |
743 | polygon_45_set_data& <br /> | |
744 | <b>transform</b>(const transformation_type& | |
745 | transformation) </font> </td> | |
746 | <td>Applies transformation.transform() on vertices stored | |
747 | within the polygon set. O(n log n) runtime and O(n) memory wrt. | |
748 | vertices + intersections.</td> | |
749 | </tr> | |
750 | <tr> | |
751 | <td width="586"><font face="Courier New">polygon_45_set_data& | |
752 | <b>scale_up</b>(unsigned_area_type factor)</font></td> | |
753 | <td>Scales vertices stored within the polygon set up by | |
754 | factor. Linear wrt vertices.</td> | |
755 | </tr> | |
756 | <tr> | |
757 | <td width="586"><font face="Courier New">polygon_45_set_data& | |
758 | <b>scale_down</b>(unsigned_area_type factor)</font> </td> | |
759 | <td>Scales vertices stored within the polygon set down by | |
760 | factor. Linear wrt vertices.</td> | |
761 | </tr> | |
762 | <tr> | |
763 | <td width="586"><font face="Courier New">polygon_45_set_data& | |
764 | <b>scale</b>(double factor) </font></td> | |
765 | <td>Scales vertices stored within the polygon set by | |
766 | floating point factor. Linear wrt vertices.</td> | |
767 | </tr> | |
768 | <tr> | |
769 | <td width="586"><font face="Courier New">polygon_45_set_data& | |
770 | <b>self_xor</b>()</font></td> | |
771 | <td>Retain only non-overlapping regions of geometry within | |
772 | polygon set. O(n log n) runtime and O(n) memory wrt. vertices + | |
773 | intersections.</td> | |
774 | </tr> | |
775 | <tr> | |
776 | <td width="586"><font face="Courier New">polygon_45_set_data& | |
777 | <b>self_intersect</b>()</font></td> | |
778 | <td>Retain only overlapping regions of geometry within a | |
779 | polygon set. O(n log n) runtime and O(n) memory wrt. vertices + | |
780 | intersections.</td> | |
781 | </tr> | |
782 | <tr> | |
783 | <td width="586"><font face="Courier New">bool <b>has_error_data</b>() | |
784 | const </font></td> | |
785 | <td>Returns true if non-integer intersections resulted in | |
786 | small artifacts in the output of a boolean. Constant time.</td> | |
787 | </tr> | |
788 | <tr> | |
789 | <td width="586"><font face="Courier New">std::size_t <b>error_count</b>() | |
790 | const</font></td> | |
791 | <td>Returns the number of artifacts that may potentially be | |
792 | present in the output due to non-integer intersections. Constant | |
793 | time.</td> | |
794 | </tr> | |
795 | <tr> | |
796 | <td width="586"><font face="Courier New">void <b>get_error_data</b>(polygon_45_set_data& | |
797 | p) const</font></td> | |
798 | <td>Populates the input polygon set with 1x1 unit squares | |
799 | that bound the error that may be present in the output due to | |
800 | non-integer intersections. Linear wrt. vertices of error data.</td> | |
801 | </tr> | |
802 | <tr> | |
803 | <td width="586"><font face="Courier New">polygon_45_set_data& | |
804 | <b>self_intersect</b>()</font></td> | |
805 | <td>Retain only overlapping regions of geometry within a | |
806 | polygon set. O(n log n) runtime and O(n) memory wrt. vertices + | |
807 | intersections.</td> | |
808 | </tr> | |
809 | </tbody> | |
810 | </table> | |
811 | </td> | |
812 | </tr> | |
813 | <tr> | |
814 | <td style="background-color: rgb(238, 238, 238);" nowrap="1" | |
815 | valign="top"> </td> | |
816 | <td | |
817 | style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" | |
818 | valign="top" width="100%"> | |
819 | <table class="docinfo" id="table6" frame="void" rules="none"> | |
820 | <colgroup> <col class="docinfo-name" /><col | |
821 | class="docinfo-content" /> </colgroup> <tbody valign="top"> | |
822 | <tr> | |
823 | <th class="docinfo-name">Copyright:</th> | |
824 |