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">
8 Copyright 2009-2010 Intel Corporation
11 <title>Boost Polygon Library: Polygon
45 With Holes 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"> -->
16 <table style=
"margin: 0pt; padding: 0pt; width: 100%;" border=
"0"
17 cellpadding=
"0" cellspacing=
"0">
20 <td style=
"background-color: rgb(238, 238, 238);" nowrap=
"1"
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>
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>Polygon
45 With Holes Concept
</li>
42 <li><a href=
"gtl_polygon_concept.htm">Polygon Concept
</a></li>
43 <li><a href=
"gtl_polygon_with_holes_concept.htm">Polygon With
44 Holes Concept
</a></li>
45 <li><a href=
"gtl_polygon_90_set_concept.htm">Polygon
90 Set
47 <li><a href=
"gtl_polygon_45_set_concept.htm">Polygon
45 Set
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
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 />
61 <li><a href=
"voronoi_benchmark.htm">Voronoi Benchmark
</a><br />
63 <li><a href=
"voronoi_builder.htm">Voronoi Builder
</a></li>
64 <li><a href=
"voronoi_diagram.htm">Voronoi Diagram
</a></li>
66 <h3 class=
"navbar">Other Resources
</h3>
68 <li><a href=
"GTL_boostcon2009.pdf">GTL Boostcon
2009 Paper
</a></li>
69 <li><a href=
"GTL_boostcon_draft03.pdf">GTL Boostcon
2009
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
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>
86 style=
"padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
87 valign=
"top" width=
"100%">
88 <!-- End Header --><br />
91 <h1>Polygon
45 With Holes Concept
</h1>
93 <p>The polygon_45_with_holes concept tag is
<font
95 polygon_45_with_holes_concept
</font></p>
96 <p> To register a user defined type as a model of
<font
97 face=
"Times New Roman">polygon_45_with_holes
</font>concept,
98 specialize the geometry concept meta-function for that type.
In
99 the example below CPolygon45WithHoles is registered as a model of
100 polygon
<font face=
"Times New Roman">_45_with_holes
</font> concept.
</p>
101 <p> <font face=
"Courier New">template
<><br />
102 struct geometry_concept
<CPolygon45WithHoles
> { typedef
103 polygon_45_with_holes_concept type; };
</font></p>
104 <p> <font face=
"Times New Roman">The semantic of a
105 polygon_45_with_holes is a polygon_45 that it can provide iterators
106 over holes that are also polygon_45.
A mutable
107 polygon_45_with_holes must also be able to set its geometry based on an
108 interator range over polygon_45 holes.
There is no convention of
109 winding of holes enforced within the library.
</font></p>
110 <p> <font face=
"Times New Roman">Below is shown the default
111 polygon with holes traits.
Specialization of these traits is
112 required for types that don't conform to the default behavior.
</font></p>
113 <p><font face=
"Courier New">template
<typename T, typename
114 enable = void
><br />
115 struct polygon_with_holes_traits {
<br />
116 typedef typename T::iterator_holes_type
117 iterator_holes_type;
<br />
118 typedef typename T::hole_type hole_type;
<br />
119 static inline iterator_holes_type
120 begin_holes(const T
& t) {
<br />
121 return
122 t.begin_holes();
<br />
123 }
<br />
124 static inline iterator_holes_type
125 end_holes(const T
& t) {
<br />
126 return
128 }
<br />
129 static inline unsigned int size_holes(const
131 return
132 t.size_holes();
<br />
133 }
<br />
135 <p><font face=
"Courier New">template
<typename T, typename
136 enable = void
><br />
137 struct polygon_with_holes_mutable_traits {
<br />
138 template
<typename iT
><br />
139 static inline T
& set_holes(T
& t, iT
140 inputBegin, iT inputEnd) {
<br />
141
142 t.set_holes(inputBegin, inputEnd);
<br />
143 return t;
<br />
144 }
<br />
146 <p>An object that is a model of
<font face=
"Courier New">
147 polygon_45_with_holes_concept
</font> can be viewed as a model of any of
148 its refinements if it is determined at runtime to conform to the
149 restriction of those concepts.
This concept casting is
150 accomplished through the
151 <font face=
"Courier New">view_as
<>()
</font> function.
</p>
152 <p><font face=
"Courier New">view_as
<rectangle_concept
>(polygon_45_with_holes_object)
</font><br />
153 <font face=
"Courier New">view_as
<polygon_90_concept
>(polygon_45_with_holes_object)
</font><br />
154 <font face=
"Courier New">view_as
<polygon_90_with_holes_concept
>(polygon_45_with_holes_object)
</font><br />
155 <font face=
"Courier New">view_as
<polygon_45_concept
>(polygon_45_with_holes_object)
</font></p>
156 <p>The return value of
<font face=
"Courier New">view_as
<>()
</font>
157 can be passed into any interface that expects an object of the
158 conceptual type specified in its template parameter.
</p>
160 <table id=
"table1" border=
"1" width=
"100%">
163 <td width=
"586"><font face=
"Courier New">template
164 <typename T
><br />
165 point_iterator_type
<b>begin_points
</b>(const T
& polygon)
</font></td>
166 <td><font face=
"Times New Roman">Expects a model of
167 polygon_45_with_holes.
Returns the begin iterator over the range
168 of points that correspond to vertices of the polygon.
</font></td>
171 <td width=
"586"><font face=
"Courier New">template
172 <typename T
><br />
173 point_iterator_type
<b>end_points
</b>(const T
& polygon)
</font></td>
174 <td><font face=
"Times New Roman">Expects a model of
175 polygon_45_with_holes.
Returns the end iterator over the range of
176 points that correspond to vertices of the polygon.
</font></td>
179 <td width=
"586"><font face=
"Courier New">template
180 <typename T
><br />
181 hole_iterator_type
<b>begin_holes
</b>(const T
& polygon)
</font></td>
182 <td><font face=
"Times New Roman">Expects a model of
183 polygon_45_with_holes.
Returns the begin iterator over the range
184 of coordinates that correspond to horizontal and vertical edges.
</font></td>
187 <td width=
"586"><font face=
"Courier New">template
188 <typename T
><br />
189 hole_iterator_type
<b>end_holes
</b>(const T
& polygon)
</font></td>
190 <td><font face=
"Times New Roman">Expects a model of
191 polygon_45_with_holes.
Returns the end iterator over the range of
192 coordinates that correspond to horizontal and vertical edges.
</font></td>
195 <td width=
"586"><font face=
"Courier New">template
196 <typename T, typename iterator
><br />
197 void
<b>set_points
</b>(T
& polygon, iterator b, iterator e)
</font></td>
198 <td><font face=
"Times New Roman">Expects a model of
199 polygon_45_with_holes.
Sets the polygon to the point data
200 range [b,e) that corresponds to vertices of a polygon.
</font></td>
203 <td width=
"586"><font face=
"Courier New">template
204 <typename T, typename iterator
><br />
205 void
<b>set_holes
</b>(T
& polygon, iterator b, iterator e)
</font></td>
206 <td><font face=
"Times New Roman">Expects a model of
207 polygon_45_with_holes.
Sets the polygon holes to the hole
208 data range [b,e)
</font></td>
211 <td width=
"586"><font face=
"Courier New">template
212 <typename T
><br />
213 unsigned int
<b>size
</b>(const T
& polygon)
</font></td>
214 <td><font face=
"Times New Roman">Returns the number of
215 edges in the outer shell of the polygon_45_with_holes.
Does not
216 include sizes of the holes.
</font></td>
219 <td width=
"586"><font face=
"Courier New">template
220 <typename T1, typename T2
><br />
221 T1
& <b>assign
</b>(T1
& left, const T2
& right)
</font></td>
222 <td>Copies data from right object that models
223 polygon_45_with_holes or one of its refinements into left object that
224 models polygon_45_with_holes.
</td>
227 <td width=
"586"><font face=
"Courier New">template
228 <typename T, typename point_type
><br />
229 bool
<b>contains
</b>(const T
&, const point_type
& point,
<br />
230
231 bool consider_touch=true)
</font></td>
232 <td>Given an object that models polygon_45_with_holes and
233 an object that models point, returns true if the polygon shell contains
234 the point and one of its holes does not contain the point.
If the
235 consider_touch flag is true will return true if the point lies along
236 the boundary of the polygon or one of its holes.
</td>
239 <td width=
"586"><font face=
"Courier New">// get the center
241 template
<typename T, typename point_type
><br />
242 void
<b>center
</b>(point_type
& p, const T
& polygon)
</font></td>
243 <td>Sets object that models point to the center point of
244 the bounding box of an object that models polygon_45_with_holes.
</td>
247 <td width=
"586"><font face=
"Courier New">template
248 <typename T, typename rectangle_type
><br />
249 bool
<b>extents
</b>(rectangle_type
& bbox, const T
& polygon)
</font></td>
250 <td>Sets object that models rectangle to the bounding box
251 of an object that models polygon_45_with_holes and returns true.
252 Returns false and leaves bbox unchanged if polygon is empty.
</td>
255 <td width=
"586"><font face=
"Courier New">template
256 <typename T
><br />
257 manhattan_area_type
<b>area
</b>(const T
& polygon)
</font></td>
258 <td>Returns the area of an object that models
259 polygon_45_with_holes including subtracting the area of its holes from
260 the area of the outer shell polygon.
</td>
263 <td width=
"586"><font face=
"Courier New">template
264 <typename T
><br />
265 direction_1d
<b>winding
</b>(const T
& polygon)
</font></td>
266 <td>Returns the winding direction of an object that models
267 polygon_45_with_holes, LOW == CLOCKWISE, HIGH = COUNTERCLOCKWISE.
</td>
270 <td width=
"586"><font face=
"Courier New">template
271 <typename T
><br />
272 coordinate_difference
<b>perimeter
</b>(const T
& polygon)
</font></td>
273 <td>Returns the perimeter length of an object that models
274 polygon_45, including the perimeters of the holes.
</td>
277 <td width=
"586"><font face=
"Courier New">template
278 <typename T, typename transform_type
><br />
279 T
& <b>transform
</b>(T
& polygon, const transform_type
&)
</font></td>
280 <td>Applies transform() on the vertices of polygon and sets
281 the polygon to that described by the result of transforming its
282 vertices.
Also applies transform() on the holes of the polygon.
</td>
285 <td width=
"586"><font face=
"Courier New">template
286 <typename T
><br />
287 T
& <b>scale_up
</b>(T
& polygon, unsigned_area_type factor)
</font></td>
288 <td>Scales up outer shell and holes of an object that
289 models polygon_45 by unsigned factor.
</td>
292 <td width=
"586"><font face=
"Courier New">template
293 <typename T
><br />
294 T
& <b>scale_down
</b>(T
& polygon, unsigned_area_type factor)
</font></td>
295 <td>Scales down outer shell and holes of an object that
296 models polygon_45 by unsigned factor.
</td>
299 <td width=
"586"><font face=
"Courier New">template
300 <typename T, scaling_type
><br />
301 T
& <b>scale
</b>(T
& rectangle, double scaling)
</font></td>
302 <td>Scales outer shell and holes of an object that models
303 polygon_45 by floating point factor.
</td>
306 <td width=
"586"><font face=
"Courier New">template
307 <typename T
><br />
308 T
& <b>move
</b>(T
& polygon, orientation_2d,
<br />
309 coordinate_difference
310 displacement)
</font></td>
311 <td>Adds displacement value to coordinate indicated by
312 orientation_2d of vertices of an object that models polygon_45 .
</td>
315 <td width=
"586"><font face=
"Courier New">template
316 <typename polygon_type, typename point_type
><br />
317 polygon_type
& <b>convolve
</b>(polygon_type
& polygon,
<br />
318
319 const point_type
& point)
</font></td>
320 <td>Convolves coordinate values of point with the outer
321 shell and holes of an object that models polygon_45_with_holes.
</td>
325 <h1>Polygon
45 With Holes Data
</h1>
327 <p>The library provides a model of polygon
45 with holes concept
329 <font face=
"Courier New">template
<typename T
>
330 polygon_45_with_holes_data
</font>where T is the coordinate type.
</p>
331 <p>This data type is used internally when a
45 degree polygon
332 with holes is needed and is available to the library user who finds it
333 convenient to use a library polygon data type instead of providing
334 their own.
The data type is implemented to be convenient to use
335 with the library traits.
</p>
337 <table id=
"table2" border=
"1" width=
"100%">
340 <td width=
"586"><b><font face=
"Courier New">geometry_type
</font></b></td>
341 <td><font face=
"Times New Roman">polygon_45_with_holes_concept
</font></td>
344 <td width=
"586"><b><font face=
"Courier New">coordinate_type
</font></b></td>
345 <td><font face=
"Times New Roman">T
</font></td>
348 <td width=
"586"><b><font face=
"Courier New">iterator_type
</font></b></td>
349 <td>Iterator over vertices point_data
<T
> vertices of
353 <td width=
"586"><b><font face=
"Courier New">iterator_holes_type
</font></b></td>
354 <td><font face=
"Times New Roman">Iterator over hole
355 polygons of type polygon_45_data
<T
>.
</font></td>
358 <td width=
"586"><font face=
"Courier New"><b>polygon_45_with_holes_data
</b>()
</font></td>
359 <td><font face=
"Times New Roman">Default constructs the
</font>polygon.
</td>
362 <td width=
"586"><font face=
"Courier New"><b>polygon_45_with_holes_data
</b>(const
363 polygon_45_with_holes_data
& that)
</font></td>
364 <td><font face=
"Times New Roman">Copy construct
</font></td>
367 <td width=
"586"><font face=
"Courier New">polygon_45_with_holes_data
&
369 operator=
</b>(const polygon_45_with_holes_data
& that)
</font></td>
370 <td>Assignment operator.
</td>
373 <td width=
"586"><font face=
"Courier New">template
374 <typename T2
><b> </b> polygon_45_with_holes_data
&<b> <br />
375 operator=
</b>(const T2
& that) const
</font></td>
376 <td>Assign from an object that is a model of polygon
45
380 <td width=
"586"><font face=
"Courier New">iterator_type
<b>begin
</b>()
382 <td>Get the begin iterator over vertices of the polygon.
</td>
385 <td width=
"586"><font face=
"Courier New">iterator_type
<b>end
</b>()
387 <td>Get the end iterator over vertices of the polygon.
</td>
390 <td width=
"586"><font face=
"Courier New">iterator_hole_type
391 <b>begin_holes
</b>() const
</font></td>
392 <td>Get the begin compact iterator over non-redundant
393 coordinates of the polygon.
</td>
396 <td width=
"586"><font face=
"Courier New">iterator_hole_type
397 <b>end_holes
</b>() const
</font></td>
398 <td>Get the end compact iterator over non-redundant
399 coordinates of the polygon.
</td>
402 <td width=
"586"><font face=
"Courier New">std::size_t
<b>size
</b>()
404 <td>Get the number of elements in the sequence stored to
405 the polygon, usually equal to the number of edges of the polygon.
</td>
408 <td width=
"586"><font face=
"Courier New">std::size_t
<b>size_holes
</b>()
410 <td>Get the number of holes in the polygon
</td>
413 <td width=
"586"><font face=
"Courier New">template
414 <typename iT
><b> <br />
415 </b>void
<b>set
</b>(iT begin_points, iT end_points)
</font></td>
416 <td>Sets the polygon to the iterator range of points.
417 No check is performed to ensure the points describe a
45 degree figure.
</td>
420 <td width=
"586"><font face=
"Courier New">template
421 <typename iT
><b> <br />
422 </b>void
<b>set_holes
</b>(iT begin_holes, iT end_choless)
</font></td>
423 <td>Sets the polygon holes the iterator range of hole
424 polygons.
These polygons in the input range may be either
425 polygon_45_data or polygon_45_with_holes_data or any type that provides
426 begin and end member functions to iterate over point_data
<T
>.
</td>
433 <td style=
"background-color: rgb(238, 238, 238);" nowrap=
"1"
434 valign=
"top"> </td>
436 style=
"padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
437 valign=
"top" width=
"100%">
438 <table class=
"docinfo" id=
"table3" frame=
"void" rules=
"none">
439 <colgroup> <col class=
"docinfo-name" /><col
440 class=
"docinfo-content" /> </colgroup> <tbody valign=
"top">
442 <th class=
"docinfo-name">Copyright:
</th>
443 <td>Copyright © Intel Corporation
2008-
2010.
</td>
446 <th class=
"docinfo-name">License:
</th>
447 <td class=
"field-body">Distributed under the Boost Software
448 License, Version
1.0. (See accompanying file
<tt class=
"literal"> <span
449 class=
"pre">LICENSE_1_0.txt
</span></tt> or copy at
<a
450 class=
"reference" target=
"_top"
451 href=
"http://www.boost.org/LICENSE_1_0.txt">
452 http://www.boost.org/LICENSE_1_0.txt
</a>)
</td>