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" lang="en" xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:(null)1="http://www.w3.org/TR/REC-html40"><head><!--
3
Copyright 2009-2010 Intel Corporation
6
<title>Boost Polygon Library: Polygon Set Concept</title>
7
<meta http-equiv="content-type" content="text/html;charset=ISO-8859-1">
8
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0" cellpadding="0" cellspacing="0"><tbody><tr>
9
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
10
<div style="padding: 5px;" align="center">
11
<img border="0" src="images/boost.png" width="277" height="86"><a title="www.boost.org home page" href="http://www.boost.org/" tabindex="2" style="border: medium none ;">
14
<div style="margin: 5px;">
15
<h3 class="navbar">Contents</h3>
17
<li><a href="index.htm">Boost.Polygon Main Page</a></li>
18
<li><a href="gtl_design_overview.htm">Design Overview</a></li>
19
<li><a href="gtl_isotropy.htm">Isotropy</a></li>
20
<li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
21
<li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
22
<li><a href="gtl_point_concept.htm">Point Concept</a></li>
23
<li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
24
<li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
25
<li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90 With Holes Concept</a></li>
26
<li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
27
<li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45 With Holes Concept</a></li>
28
<li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
29
<li><a href="gtl_polygon_with_holes_concept.htm">Polygon With Holes Concept</a></li>
30
<li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set Concept</a></li>
31
<li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set Concept</a></li>
32
<li>Polygon Set Concept</li>
33
<li><a href="gtl_connectivity_extraction_90.htm">Connectivity Extraction 90</a></li>
34
<li><a href="gtl_connectivity_extraction_45.htm">Connectivity Extraction 45</a></li>
35
<li><a href="gtl_connectivity_extraction.htm">Connectivity Extraction</a></li>
36
<li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
37
<li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
38
<li><a href="gtl_property_merge.htm">Property Merge</a></li>
40
<h3 class="navbar">Other Resources</h3>
42
<li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
43
<li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
45
<li><a href="analysis.htm">Performance Analysis</a></li>
46
<li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
47
<li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
50
<h3 class="navbar">Polygon Sponsor</h3>
51
<div style="padding: 5px;" align="center">
52
<img border="0" src="images/intlogo.gif" width="127" height="51">
55
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
61
</p><h1>Polygon Set Concept</h1>
64
<p>The polygon_set concept tag is <font face="Courier New">
65
polygon_set_concept</font></p>
67
<font face="Times New Roman">The semantic of a polygon_set is zero or more
68
geometry regions. A Polygon Set Concept may be defined with floating point
69
coordinates, but a snap rounding distance of one integer unit will still be
70
applied, furthermore, geometry outside the domain where one integer unit is
71
sufficient to provide robustness may lead to undefined behavior in algorithms.
72
It is recommended to use 32-bit integer coordinates for robust operations.
74
</font><p>Users are recommended to use std::vector and std::list of user defined polygons
75
or library provided polygon_set_data<coordinate_type> objects. Lists
76
and vectors of models of polygon_concept or polygon_with_holes_concept are automatically models of polygon_set_concept.</p>
77
<p>Example code <a href="gtl_custom_polygon_set.htm">custom_polygon_set.cpp</a>
78
demonstrates mapping a user defined class to the library polygon_set_concept</p>
79
<p>An object that is a model of <font face="Courier New">
80
polygon_set_concept</font> can be viewed as a model of <font face="Courier New">
81
polygon_90_set_concept</font> or <font face="Courier New">
82
polygon_45_set_concept</font> if it is determined at runtime to conform to the
83
restrictions of those concepts. This concept casting is accomplished
84
through the <font face="Courier New">view_as<>()</font> function.</p>
85
<p><font face="Courier New">view_as<polygon_90_set_concept>(polygon_set_object)<br>
86
view_as<polygon_45_set_concept>(polygon_set_object)</font></p>
87
<p>The return value of <font face="Courier New">view_as<>()</font> can be passed
88
into any interface that expects an object of the conceptual type specified in
89
its template parameter. Polygon sets cannot be viewed as single polygons
90
or rectangles since it generally cannot be known whether a polygon set contains
91
only a single polygon without converting to polygons.</p>
93
<p>The return type of some operators is the <font face="Courier New">polygon_set_view</font>
94
operator template type. This type is itself a model of the polygon 90 set
95
concept, but furthermore can be used as an argument to the <font face="Courier New">polygon_set_data</font>
96
constructor and assignment operator. The operator template exists to
97
eliminate temp copies of intermediate results when Boolean operators are chained
99
<p>Operators are declared inside the namespace <font face="Courier New">boost::polygon::operators</font>.</p>
100
<table border="1" width="100%" id="table5">
102
<td width="586"><font face="Courier New">template <typename T1, typename
104
polygon_set_view <b>operator</b>|(const T1& l, const T2& r)</font></td>
105
<td>Boolean OR operation (polygon set union). Accepts two objects
106
that model polygon_set or one of its refinements. Returns an
107
operator template that performs the operation on demand when chained or
108
or nested in a library function call such as assign(). Expected n
109
log n runtime, worst case quadratic runtime wrt. vertices +
113
<td width="586"><font face="Courier New">template <typename T1, typename
115
polygon_set_view <b>operator</b>+(const T1& l, const T2& r)</font></td>
116
<td>Same as operator|. The plus sign is also used for OR
117
operations in Boolean logic expressions. Expected n log n runtime,
118
worst case quadratic runtime wrt. vertices + intersections.</td>
121
<td width="586"><font face="Courier New">template <typename T1, typename
123
polygon_set_view <b>operator</b>&(const T1& l, const T2& r)</font></td>
124
<td>Boolean AND operation (polygon set intersection). Accepts two
125
objects that model polygon_set or one of its refinements. Expected
126
n log n runtime, worst case quadratic runtime wrt. vertices +
130
<td width="586"><font face="Courier New">template <typename T1, typename
132
polygon_set_view <b>operator</b>*(const T1& l, const T2& r)</font></td>
133
<td>Same as operator&. The multiplication symbol is also used for
134
AND operations in Boolean logic expressions. Expected n log n
135
runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
138
<td width="586"><font face="Courier New">template <typename T1, typename
140
polygon_set_view <b>operator</b>^(const T1& l, const T2& r)</font></td>
141
<td>Boolean XOR operation (polygon set disjoint-union). Accepts
142
two objects that model polygon_set or one of its refinements.
143
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
147
<td width="586"><font face="Courier New">template <typename T1, typename
149
polygon_set_view <b>operator</b>-(const T1& l, const T2& r)</font></td>
150
<td>Boolean SUBTRACT operation (polygon set difference). Accepts
151
two objects that model polygon_set or one of its refinements.
152
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
156
<td width="586"><font face="Courier New">template <typename T1, typename
158
T1& <b>operator</b>|=(const T1& l, const T2& r)</font></td>
159
<td>Same as operator|, but with self assignment, left operand must model
160
polygon_set and not one of it's refinements. Expected n log n
161
runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
164
<td width="586"><font face="Courier New">template <typename T1, typename
166
T1& <b>operator</b>+=(T1& l, const T2& r)</font></td>
167
<td>Same as operator+, but with self assignment, left operand must model
168
polygon_set and not one of it's refinements. Expected n log n
169
runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
172
<td width="586"><font face="Courier New">template <typename T1, typename
174
T1& <b>operator</b>&=(const T1& l, const T2& r)</font></td>
175
<td>Same as operator&, but with self assignment, left operand must model
176
polygon_set and not one of it's refinements. Expected n log n
177
runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
180
<td width="586"><font face="Courier New">template <typename T1, typename
182
T1& <b>operator</b>*=(T1& l, const T2& r)</font></td>
183
<td>Same as operator*, but with self assignment, left operand must model
184
polygon_set and not one of it's refinements. Expected n log n
185
runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
188
<td width="586"><font face="Courier New">template <typename T1, typename
190
T1& <b>operator</b>^=(const T1& l, const T2& r)</font></td>
191
<td>Same as operator^, but with self assignment, left operand must model
192
polygon_set and not one of it's refinements. Expected n log n
193
runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
196
<td width="586"><font face="Courier New">template <typename T1, typename
198
T1& <b>operator</b>-=(T1& l, const T2& r)</font></td>
199
<td>Same as operator-, but with self assignment, left operand must model
200
polygon_set and not one of it's refinements. Expected n log n
201
runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
204
<td width="586"><font face="Courier New">template <typename T1><br>
205
T1 <b>operator</b>+(const T1&, coordinate_type bloating)</font></td>
206
<td>Performs resize operation, inflating by bloating ammount. If
207
negative the result is a shrink instead of bloat. Note: returns
208
result by value. Expected n log n runtime, worst case quadratic
209
runtime wrt. vertices + intersections.</td>
212
<td width="586"><font face="Courier New">template <typename T1, typename
214
T1 <b>operator</b>-(const T1&, coordinate_type shrinking)</font></td>
215
<td>Performs resize operation, deflating by bloating ammount. If
216
negative the result is a bloat instead of shrink. Note: returns
217
result by value. Expected n log n runtime, worst case quadratic
218
runtime wrt. vertices + intersections.</td>
221
<td width="586"><font face="Courier New">template <typename T1, typename
223
T1& <b>operator</b>+=(const T1&, coordinate_type bloating)</font></td>
224
<td>Performs resize operation, inflating by bloating ammount. If
225
negative the result is a shrink instead of bloat. Returns
226
reference to modified argument. Expected n log n runtime, worst
227
case quadratic runtime wrt. vertices + intersections.</td>
230
<td width="586"><font face="Courier New">template <typename T1, typename
232
T1& <b>operator</b>-=(const T1&, coordinate_type shrinking)</font></td>
233
<td>Performs resize operation, deflating by bloating ammount. If
234
negative the result is a bloat instead of shrink. Returns
235
reference to modified argument. Expected n log n runtime, worst
236
case quadratic runtime wrt. vertices + intersections.</td>
240
<table border="1" width="100%" id="table6">
242
<td width="586"><font face="Courier New">template <typename T1, typename
244
T1& <b>assign</b>(T1& lvalue, const T2& rvalue)</font></td>
245
<td>Eliminates overlaps in geometry and copies from an object that
246
models polygon_set or any of its refinements into an object that
247
models polygon_set. Expected n log n runtime, worst case quadratic
248
runtime wrt. vertices + intersections.</td>
251
<td width="586"><font face="Courier New">template <typename T1, typename
253
bool <b>equivalence</b>(const T1& lvalue, const T2& rvalue) </font></td>
254
<td>Returns true if an object that models polygon_set or one of its
255
refinements covers the exact same geometric regions as another object
256
that models polygon_set or one of its refinements. For example:
257
two of polygon objects. Expected n log n runtime, worst case
258
quadratic runtime wrt. vertices + intersections.</td>
261
<td width="586"><font face="Courier New">template <typename
262
output_container_type, typename T><br>
263
void <b>get_trapezoids</b>(output_container_type& output, <br>
264
265
const T& polygon_set)</font></td>
266
<td>Output container is expected to be a standard container.
267
Slices geometry of an object that models polygon_set or one of its
268
refinements into non overlapping trapezoids along a vertical slicing
269
orientation and appends them to the
270
output, which must have a value type that models polygon or polygon_with_holes.
271
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
275
<td width="586"><font face="Courier New">template <typename
276
output_container_type, typename T><br>
277
void <b>get_trapezoids</b>(output_container_type& output, <br>
278
279
const T& polygon_set,<br> orientation_2d orient)</font></td>
280
<td>Output container is expected to be a standard container.
281
Slices geometry of an object that models polygon_set or one of its
282
refinements into non overlapping trapezoids along a the specified slicing
283
orientation and appends them to the
284
output, which must have a value type that models polygon or polygon_with_holes.
285
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
289
<td width="586"><font face="Courier New">template <typename
290
polygon_set_type><br>
291
void <b>clear</b>(polygon_set_type& polygon_set)</font></td>
292
<td>Makes the object empty of geometry.</td>
295
<td width="586"><font face="Courier New">template <typename
296
polygon_set_type><br>
297
bool <b>empty</b>(const polygon_set_type& polygon_set)</font></td>
298
<td>Checks whether the object is empty of geometry. Polygons that
299
are completely covered by holes will result in empty returning true.
300
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
304
<td width="586"><font face="Courier New">template <typename T, typename
305
rectangle_type><br>
306
bool <b>extents</b>(rectangle_type& extents_rectangle, <br>
307
const
308
T& polygon_set)</font></td>
309
<td>Computes bounding box of an object that models polygon_set and
310
stores it in an object that models rectangle. If the polygon set
311
is empty returns false. If there are holes outside of shells they
312
do not contribute to the extents of the polygon set. Expected n
313
log n runtime, worst case quadratic runtime wrt. vertices +
317
<td width="586"><font face="Courier New">template <typename T><br>
318
area_type <b>area</b>(const T& polygon_set)</font></td>
319
<td>Computes the area covered by geometry in an object that models
320
polygon_set. Expected n log n runtime, worst case quadratic
321
runtime wrt. vertices + intersections.</td>
324
<td width="586"><font face="Courier New">template <typename T><br>
325
T& <b>bloat</b>(T& polygon_set, unsigned_area_type bloating)</font></td>
326
<td>Same as getting all the polygons, bloating them and putting them
327
back. Expected n log n runtime, worst case quadratic runtime wrt.
328
vertices + intersections.</td>
331
<td width="586"><font face="Courier New">template <typename T><br>
332
T& <b>shrink</b>(T& polygon_set, unsigned_area_type shrinking)</font></td>
333
<td>Same as getting all the polygons, shrinking them and overwriting
334
the polygon set with the resulting regions. Expected n log n
335
runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
338
<td width="586"><font face="Courier New">template <typename T, typename
340
T& <b>resize</b>(T& polygon_set, coord_type resizing,<br>
341
342
bool corner_fill_arc = false, <br>
343
unsigned int num_circle_segments = 0)</font></td>
344
<td>Same as bloat if resizing is positive, same as shrink if resizing is
345
negative. Original topology at acute angle vertices is preserved
346
by default, segmented circular arcs are inserted if corner_fill_arc is
347
true. num_circle_segments specifies number of segments to
348
introduce on a full circle when filling acute angle corners with
349
circular arcs. Expected n log n runtime, worst case quadratic
350
runtime wrt. vertices + intersections.</td>
353
<td width="586"><font face="Courier New">template <typename T, typename
355
T& <b>simplify</b>(T& polygon_set, distance_type
356
threshold)</font></td>
357
<td>Simplify the polygon set by removing vertices that lie
358
within threshold distance of the line segment that
359
connects the two adjacent points in the polygon.
360
Expected n log n runtime, worst case quadratic
361
runtime wrt. vertices + intersections.</td>
364
<td width="586"><font face="Courier New">template <typename T><br>
365
T& <b>scale_up</b>(T& polygon_set, unsigned_area_type factor)</font></td>
366
<td>Scales geometry up by unsigned factor. Expected n log n
367
runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
370
<td width="586"><font face="Courier New">template <typename T><br>
371
T& <b>scale_down</b>(T& polygon_set, unsigned_area_type factor)</font></td>
372
<td>Scales geometry down by unsigned factor. Expected n log n
373
runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
376
<td width="586"><font face="Courier New">template <typename T, typename transformation_type><br>
377
T& <b>transform</b>(T& polygon_set,<br>
378
const
379
transformation_type& transformation)</font></td>
380
<td>Applies transformation.transform() on all vertices. Expected n
381
log n runtime, worst case quadratic runtime wrt. vertices +
385
<td width="586"><font face="Courier New">template <typename T><br>
386
T& <b>keep</b>(T& polygon_set, <br>
387
unsigned_area_type min_area,<br>
388
unsigned_area_type max_area,<br>
389
unsigned_area_type min_width,<br>
390
unsigned_area_type max_width,<br>
391
unsigned_area_type min_height,<br>
392
unsigned_area_type max_height)</font></td>
393
<td>Retains only regions that satisfy the min/max criteria in the
394
argument list. Note: useful for visualization to cull too small
395
polygons. Expected n log n runtime, worst case quadratic runtime
396
wrt. vertices + intersections.</td>
399
<h1>Polygon Set Data Object</h1>
402
<p>The polygon set data type encapsulates the internal data format that
403
serves as the input to the sweep-line algorithm that implements polygon-clipping
404
Boolean operations. It also internally keeps track of whether that data
405
has been sorted or scanned and maintains the invariant that when its flags
406
indicate that the data is sorted or scanned the data has not been changed to
407
violate that assumption. Using the Polygon Set Data type directly can
408
be more efficient than using lists and vectors of polygons in the functions
409
above because of the invariants it can enforce which provide the opportunity to
410
maintain the data is sorted form rather than going all the way out to polygons
411
then resorting those vertices for a subsequent operation.</p>
412
<p>The declaration of Polygon Set Data is the following:</p>
413
<p><font face="Courier New">template <typename T><br>
414
class polygon_set_data;</font></p>
415
<p>The class is parameterized on the coordinate data type. Algorithms that
416
benefit from knowledge of the invariants enforced by the class are implemented
417
as member functions to provide them access to information about those
418
invariants. </p>
419
<p>Example code <a href="gtl_polygon_set_usage.htm">polygon_set_usage.cpp</a>
421
the library provided polygon set data types and functions</p>
422
<h2>Member Functions</h2>
423
<table border="1" width="100%" id="table7">
425
<td width="586"><font face="Courier New"><b>polygon_set_data</b>()</font></td>
426
<td>Default constructor. </td>
429
<td width="586"><font face="Courier New">template <typename iT><br>
430
<b>polygon_set_data</b>(iT input_begin, iT
431
input_end)</font></td>
432
<td>Construct with scanning orientation from an iterator range of
433
insertable objects.</td>
436
<td width="586"><font face="Courier New">
437
<b>polygon_set_data</b>(const polygon_set_data& that)</font></td>
438
<td>Copy construct.</td>
442
<font face="Courier New">template <typename l, typename r, typename op><br>
443
<b>polygon_set_data</b>(const polygon_set_view<l,r,op>&
445
<td>Copy construct from a Boolean operator template.</td>
449
<font face="Courier New">polygon_set_data& <br><b>operator=</b>(const polygon_set_data& that)</font></td>
450
<td>Assignment from another polygon set, may change scanning
455
<font face="Courier New">template <typename l, typename r, typename op><br>
456
polygon_set_data& <br><b>operator=</b>(const polygon_set_view<l, r,
457
op>& that)</font></td>
458
<td>Assignment from a Boolean operator template.</td>
461
<td width="586"><font face="Courier New">template <typename geometry_object><br>
462
polygon_set_data& <b>operator=</b>(const geometry_object& geo)</font></td>
463
<td>Assignment from an insertable object.</td>
467
<font face="Courier New">
468
template <typename iT><br>
469
void <b>insert</b>(iT input_begin, iT input_end)</font></td>
470
<td>Insert objects of an iterator range. Linear wrt vertices
475
<font face="Courier New">
476
void <b>insert</b>(const polygon_set_data& polygon_set)</font></td>
477
<td>Insert a polygon set. Linear wrt vertices inserted.</td>
481
<font face="Courier New">
482
template <typename geometry_type><br>
483
void <b>insert</b>(const geometry_type& geometry_object, <br> bool is_hole
485
<td>Insert a geometry object, if is_hole is true then the inserted
486
region is subtractive rather than additive. Linear wrt vertices
490
<td width="586"><font face="Courier New">
491
template <typename output_container><br>
492
void <b>get</b>(output_container& output) const</font></td>
493
<td>Expects a standard container of polygons objects. Will scan
494
and eliminate overlaps. Converts polygon set geometry to objects
495
of the polygon type and appends them to the container. Polygons
496
will be output with counterclockwise winding, hole polygons will be
497
output with clockwise winding. The last vertex of an output
498
polygon is the duplicate of the first, and the number of points is equal
499
to the number of edges plus 1. If required by the output data
500
type, polygons will have holes fractured out to the outer boundary along
501
the positive y direction and off grid intersections on the outer
502
boundary introduced by this fracture will be truncated downward.
503
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
507
<td width="586"><font face="Courier New">
508
template <typename output_container><br>
509
void <b>get_trapezoids</b>(output_container& output) const</font></td>
510
<td>Expects a standard container of polygon objects. Will scan
511
and eliminate overlaps. Slices polygon set geometry to trapezoids
512
vertically and appends them to the container. Expected n log n
513
runtime, worst case quadratic runtime wrt. vertices + intersections.</td>
517
<font face="Courier New">
518
template <typename output_container><br>
519
void <b>get_trapezoids</b>(output_container& output, <br> orientation_2d
520
slicing_orientation) const </font>
522
<td>Expects a standard container of polygon objects. Will scan
523
and eliminate overlaps. Slices polygon set geometry to trapezoids
524
along the given orientation and appends them to the container.
525
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
530
<font face="Courier New">
531
bool <b>operator==</b>(const polygon_set_data& p) const</font></td>
532
<td>Once scanned the data representation of geometry within a polygon
533
set is in a mathematically canonical form. Comparison between two
534
sets is therefore a linear time operation once they are in the scanned
535
state. Will scan and eliminate overlaps in both polygon sets.
536
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
537
intersections. </td>
540
<td width="586"><font face="Courier New">
541
bool <b>operator!=</b>(const polygon_set_data& p) const</font></td>
542
<td>Inverse logic of equivalence operator.</td>
545
<td width="586"><font face="Courier New">void <b>clear</b>()</font></td>
546
<td>Make the polygon set empty. Note: does not de-allocate memory.
547
Use shrink to fit idiom and assign default constructed polygon set to
551
<td width="586"><font face="Courier New">bool <b>empty</b>() const </font>
553
<td>Check whether the polygon set contains no geometry. Will scan
554
and eliminate overlaps because subtractive regions might make the
555
polygon set empty. Expected n log n runtime, worst case quadratic
556
runtime wrt. vertices + intersections.</td>
559
<td width="586"><font face="Courier New">void <b>clean</b>() const</font></td>
560
<td>Scan and eliminate overlaps. Expected n log n runtime, worst
561
case quadratic runtime wrt. vertices + intersections the first time,
562
constant time subsequently.</td>
565
<td width="586"><font face="Courier New">
566
template <typename input_iterator_type><br>
567
void <b>set</b>(input_iterator_type input_begin, <br> input_iterator_type input_end) </font>
569
<td>Overwrite geometry in polygon set with insertable objects in the
570
iterator range. </td>
573
<td width="586"><font face="Courier New">
574
template <typename rectangle_type><br>
575
bool <b>extents</b>(rectangle_type& extents_rectangle) const</font></td>
576
<td>Given an object that models rectangle, scans and eliminates overlaps
577
in the polygon set because subtractive regions may alter its extents
578
then computes the bounding box and assigns it to extents_rectangle.
579
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
580
intersections the first time, linear subsequently.</td>
583
<td width="586"><font face="Courier New">
584
polygon_set_data&<br>
585
<b>resize</b>(coord_type resizing,<br>
586
bool corner_fill_arc = false, <br>
587
unsigned int num_circle_segments = 0)</font></td>
588
<td>Inflates if resizing is positive, deflates if resizing is
589
negative. Original topology at acute angle vertices is preserved
590
by default, segmented circular arcs are inserted if corner_fill_arc is
591
true. num_circle_segments specifies number of segments to
592
introduce on a full circle when filling acute angle corners with
593
circular arcs. Specifying zero for num_circle_segments results in
594
only a single segment being inserted at acute corners. Expected n
595
log n runtime, worst case quadratic runtime wrt. vertices +
599
<td width="586"><font face="Courier New">
600
template <typename transformation_type><br>
601
polygon_set_data& <br><b>transform</b>(const transformation_type& transformation) </font>
603
<td>Applies transformation.transform() on vertices stored within the
604
polygon set. Expected n log n runtime, worst case quadratic
605
runtime wrt. vertices + intersections.</td>
608
<td width="586"><font face="Courier New">
609
polygon_set_data& <b>scale_up</b>(unsigned_area_type factor)</font></td>
610
<td>Scales vertices stored within the polygon set up by factor.
611
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
616
<font face="Courier New">polygon_set_data& <b>scale_down</b>(unsigned_area_type
617
factor)</font> </td>
618
<td>Scales vertices stored within the polygon set down by factor.
619
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
623
<td width="586"><font face="Courier New">
624
template <typename scaling_type><br>
625
polygon_set_data&<br> <b>scale</b>(const scaling_type&
627
<td>Scales vertices stored within the polygon set by applying f.scale().
628
Expected n log n runtime, worst case quadratic runtime wrt. vertices +
633
<td style="background-color: rgb(238, 238, 238);" nowrap="1" valign="top">
635
<td style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;" valign="top" width="100%">
638
<table class="docinfo" rules="none" frame="void" id="table8">
640
<col class="docinfo-name"><col class="docinfo-content">
644
<th class="docinfo-name">Copyright:</th>
645
<td>Copyright � Intel Corporation 2008-2010.</td>
648
<th class="docinfo-name">License:</th>
649
<td class="field-body">Distributed under the Boost Software License,
650
Version 1.0. (See accompanying file <tt class="literal">
651
<span class="pre">LICENSE_1_0.txt</span></tt> or copy at
652
<a class="reference" target="_top" href="http://www.boost.org/LICENSE_1_0.txt">
653
http://www.boost.org/LICENSE_1_0.txt</a>)</td>