ceph/src/boost/libs/polygon/doc/gtl_polygon_45_concept.htm

   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 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>Polygon 45 Concept</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><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
  49 Concept</a></li>
  50         <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
  51         <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
  52 Extraction 90</a></li>
  53         <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
  54 Extraction 45</a></li>
  55         <li><a href="gtl_connectivity_extraction.htm">Connectivity
  56 Extraction</a></li>
  57         <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
  58         <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
  59         <li><a href="gtl_property_merge.htm">Property Merge</a></li>
  60         <li><a href="voronoi_main.htm">Voronoi Main Page<br />
  61           </a></li>
  62         <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br />
  63         </li>
  64         <li><a href="voronoi_builder.htm">Voronoi Builder</a></li>
  65         <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
  66       </ul>
  67       <h3 class="navbar">Other Resources</h3>
  68       <ul>
  69         <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
  70         <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
  71 Presentation</a></li>
  72         <li><a href="analysis.htm">Performance Analysis</a></li>
  73         <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
  74         <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
  75         <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
  76         <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
  77 Tutorial</a></li>
  78       </ul>
  79       </div>
  80       <h3 class="navbar">Polygon Sponsor</h3>
  81       <div style="padding: 5px;" align="center"> <img
  82  src="images/intlogo.gif" border="0" height="51" width="127" /><a
  83  title="www.adobe.com home page" href="http://www.adobe.com/"
  84  tabindex="2" style="border: medium none ;"> </a> </div>
  85       </td>
  86       <td
  87  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
  88  valign="top" width="100%">
  89 <!-- End Header --><br />
  90       <p>
  91       </p>
  92       <h1>Polygon 45 Concept</h1>
  93       <p> </p>
  94       <p>The polygon_45 concept tag is <font face="Courier New">
  95 polygon_45_concept</font></p>
  96       <p> To register a user defined type as a model of <font
  97  face="Times New Roman">polygon_45 </font>concept, specialize the
  98 geometry concept meta-function for that type.&nbsp; In the example
  99 below CPolygon45 is registered as a model of polygon_45&nbsp; concept.</p>
 100       <p> <font face="Courier New">template &lt;&gt;<br />
 101 struct geometry_concept&lt;CPolygon45&gt; { typedef polygon_45_concept
 102 type; };</font></p>
 103       <p> <font face="Times New Roman">The semantic of a polygon_45 is
 104 that it can provide iterators over the points that represent its
 105 vertices, angles formed as these vertices must be multiple of 45-degree
 106 relative to the coordinate axis.&nbsp; It is acceptable to have the
 107 last edge explict with the first and last point equal to each other or
 108 implied by this segement that would connect the first and last
 109 point.&nbsp; A mutable polygon_45 must also be able to set its geometry
 110 based on an interator range over such points.&nbsp;&nbsp; A
 111 std::vector&lt;point_data&lt;int&gt; &gt; or
 112 std::list&lt;point_data&lt;int&gt; &gt; could be made models of
 113 polygon_45_concept by simply providing access to their iterators
 114 through traits.&nbsp; Library functions that create polygon objects
 115 require that those objects provide a default constructor.</font></p>
 116       <p> <font face="Times New Roman">Below is shown the default
 117 polygon traits.&nbsp; Specialization of these traits is required for
 118 types that don't conform to the default behavior.&nbsp; Note that these
 119 traits are also used by several other polygon concepts through SFINAE
 120 enable template parameter.&nbsp; The SFINAE enable parameter also
 121 allows the library to provide default specialization that work for any
 122 object that models the 90 degree polygon concepts.</font></p>
 123       <p><font face="Courier New">template &lt;typename T, typename
 124 enable = gtl_yes&gt;<br />
 125 struct polygon_traits {};<br />
 126       <br />
 127 template &lt;typename T&gt;<br />
 128 struct polygon_traits&lt;T, <br />
 129 &nbsp; typename gtl_or_4&lt;<br />
 130 &nbsp;&nbsp;&nbsp; typename gtl_same_type&lt;typename
 131 geometry_concept&lt;T&gt;::type, polygon_concept&gt;::type,<br />
 132 &nbsp;&nbsp;&nbsp; typename gtl_same_type&lt;typename
 133 geometry_concept&lt;T&gt;::type, polygon_45_concept&gt;::type,<br />
 134 &nbsp;&nbsp;&nbsp; typename gtl_same_type&lt;typename
 135 geometry_concept&lt;T&gt;::type, polygon_with_holes_concept&gt;::type,<br />
 136 &nbsp;&nbsp;&nbsp; typename gtl_same_type&lt;typename
 137 geometry_concept&lt;T&gt;::type, polygon_45_with_holes_concept&gt;::type<br />
 138 &nbsp; &gt;::type&gt; {<br />
 139 &nbsp;&nbsp;&nbsp;&nbsp; typedef typename T::coordinate_type
 140 coordinate_type;<br />
 141 &nbsp;&nbsp;&nbsp;&nbsp; typedef typename T::iterator_type
 142 iterator_type;<br />
 143 &nbsp;&nbsp;&nbsp;&nbsp; typedef typename T::point_type point_type;<br />
 144 &nbsp;&nbsp;&nbsp;&nbsp; static inline iterator_type begin_points(const
 145 T&amp; t) {<br />
 146 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return t.begin();<br />
 147 &nbsp;&nbsp;&nbsp;&nbsp; }<br />
 148 &nbsp;&nbsp;&nbsp;&nbsp; static inline iterator_type end_points(const
 149 T&amp; t) {<br />
 150 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return t.end();<br />
 151 &nbsp;&nbsp;&nbsp;&nbsp; }<br />
 152 &nbsp;&nbsp;&nbsp;&nbsp; static inline unsigned int size(const T&amp;
 153 t) {<br />
 154 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return t.size();<br />
 155 &nbsp;&nbsp;&nbsp;&nbsp; }<br />
 156 &nbsp;&nbsp;&nbsp;&nbsp; static inline winding_direction winding(const
 157 T&amp; t) {<br />
 158 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return
 159 unknown_winding;<br />
 160 &nbsp;&nbsp;&nbsp;&nbsp; }<br />
 161 };</font></p>
 162       <p><font face="Courier New">template &lt;typename T, typename
 163 enable = void&gt;<br />
 164 struct polygon_mutable_traits {<br />
 165 &nbsp;&nbsp;&nbsp;&nbsp; template &lt;typename iT&gt;<br />
 166 &nbsp;&nbsp;&nbsp;&nbsp; static inline T&amp; set_points(T&amp; t, iT
 167 input_begin, iT input_end) {<br />
 168 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 169 t.set(input_begin, input_end);<br />
 170 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; return t;<br />
 171 &nbsp;&nbsp;&nbsp;&nbsp; }<br />
 172 };</font></p>
 173       <p>An object that is a model of <font face="Courier New">
 174 polygon_45_concept</font> can be viewed as a model of any of its
 175 refinements if it is determined at runtime to conform to the
 176 restriction of those concepts.&nbsp; This concept casting is
 177 accomplished through the
 178       <font face="Courier New">view_as&lt;&gt;()</font> function.</p>
 179       <p><font face="Courier New">view_as&lt;rectangle_concept&gt;(polygon_45_object)</font><br />
 180       <font face="Courier New">view_as&lt;polygon_90_concept&gt;(polygon_45_object)</font></p>
 181       <p>The return value of <font face="Courier New">view_as&lt;&gt;()</font>
 182 can be passed into any interface that expects an object of the
 183 conceptual type specified in its template parameter.</p>
 184       <h2>Functions</h2>
 185       <table id="table1" border="1" width="100%">
 186         <tbody>
 187           <tr>
 188             <td width="586"><font face="Courier New">template
 189 &lt;typename T&gt;<br />
 190 point_iterator_type <b>begin_points</b>(const T&amp; polygon)</font></td>
 191             <td><font face="Times New Roman">Expects a model of
 192 polygon_45.&nbsp; Returns the begin iterator over the range of points
 193 that correspond to vertices of the polygon.</font></td>
 194           </tr>
 195           <tr>
 196             <td width="586"><font face="Courier New">template
 197 &lt;typename T&gt;<br />
 198 point_iterator_type <b>end_points</b>(const T&amp; polygon)</font></td>
 199             <td><font face="Times New Roman">Expects a model of
 200 polygon_45.&nbsp; Returns the end iterator over the range of points
 201 that correspond to vertices of the polygon.</font></td>
 202           </tr>
 203           <tr>
 204             <td width="586"><font face="Courier New">template
 205 &lt;typename T, typename iterator&gt;<br />
 206 void <b>set_points</b>(T&amp; polygon, iterator b, iterator e)</font></td>
 207             <td><font face="Times New Roman">Expects a model of
 208 polygon_45.&nbsp;&nbsp; Sets the polygon to the point data range [b,e)
 209 that corresponds to vertices of a polygon.&nbsp; Non-45 edges between
 210 successive input points is disallowed.</font></td>
 211           </tr>
 212           <tr>
 213             <td width="586"><font face="Courier New">template
 214 &lt;typename T&gt;<br />
 215 unsigned int <b>size</b>(const T&amp; polygon)</font></td>
 216             <td><font face="Times New Roman">Returns the number of
 217 edges in the polygon.</font></td>
 218           </tr>
 219           <tr>
 220             <td width="586"><font face="Courier New">template
 221 &lt;typename T1, typename T2&gt;<br />
 222 T1&amp; <b>assign</b>(T1&amp; left, const T2&amp; right)</font></td>
 223             <td>Copies data from right object that models polygon_45
 224 into left object that models polygon_45.</td>
 225           </tr>
 226           <tr>
 227             <td width="586"><font face="Courier New">template
 228 &lt;typename T, typename point_type&gt;<br />
 229 bool <b>contains</b>(const T&amp;, const point_type&amp; point, <br />
 230 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 231 bool consider_touch=true)</font></td>
 232             <td>Given an object that models polygon_45 and an object
 233 that models point, returns true if the polygon contains the
 234 point.&nbsp; If the consider_touch flag is true will return true if the
 235 point lies along the boundary of the polygon.&nbsp; Linear wrt.
 236 vertices.</td>
 237           </tr>
 238           <tr>
 239             <td width="586"><font face="Courier New">// get the center
 240 coordinate<br />
 241 template &lt;typename T, typename point_type&gt;<br />
 242 void <b>center</b>(point_type&amp; p, const T&amp; 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.&nbsp; Linear wrt.
 245 vertices.</td>
 246           </tr>
 247           <tr>
 248             <td width="586"><font face="Courier New">template
 249 &lt;typename T, typename rectangle_type&gt;<br />
 250 bool <b>extents</b>(rectangle_type&amp; bbox, const T&amp; polygon)</font></td>
 251             <td>Sets object that models rectangle to the bounding box
 252 of an object that models polygon_45 and returns true.&nbsp; Returns
 253 false and leaves bbox unchanged if polygon is empty.&nbsp; Linear wrt.
 254 vertices.</td>
 255           </tr>
 256           <tr>
 257             <td width="586"><font face="Courier New">template
 258 &lt;typename T&gt;<br />
 259 area_type <b>area</b>(const T&amp; polygon)</font></td>
 260             <td>Returns the area of an object that models
 261 polygon_45.&nbsp; Linear wrt. vertices.</td>
 262           </tr>
 263           <tr>
 264             <td width="586"><font face="Courier New">template
 265 &lt;typename T&gt;<br />
 266 direction_1d <b>winding</b>(const T&amp; polygon)</font></td>
 267             <td>Returns the winding direction of an object that models
 268 polygon_45, LOW == CLOCKWISE, HIGH = COUNTERCLOCKWISE.&nbsp; Complexity
 269 depends upon winding trait.</td>
 270           </tr>
 271           <tr>
 272             <td width="586"><font face="Courier New">template
 273 &lt;typename T&gt;<br />
 274 coordinate_distance <b>perimeter</b>(const T&amp; polygon)</font></td>
 275             <td>Returns the perimeter length of an object that models
 276 polygon_45.&nbsp; Linear wrt. vertices.</td>
 277           </tr>
 278           <tr>
 279             <td width="586"><font face="Courier New">template
 280 &lt;typename T, typename transform_type&gt;<br />
 281 T&amp; <b>transform</b>(T&amp; polygon, const transform_type&amp;)</font></td>
 282             <td>Applies transform() on the vertices of polygon and sets
 283 the polygon to that described by the result of transforming its
 284 vertices.&nbsp; Linear wrt. vertices.</td>
 285           </tr>
 286           <tr>
 287             <td width="586"><font face="Courier New">template
 288 &lt;typename T&gt;<br />
 289 T&amp; <b>scale_up</b>(T&amp; polygon, unsigned_area_type factor)</font></td>
 290             <td>Scales up coordinate of an object that models
 291 polygon_45 by unsigned factor.&nbsp; Linear wrt. vertices.</td>
 292           </tr>
 293           <tr>
 294             <td width="586"><font face="Courier New">template
 295 &lt;typename T&gt;<br />
 296 T&amp; <b>scale_down</b>(T&amp; polygon, unsigned_area_type factor)</font></td>
 297             <td>Scales down coordinates of an object that models
 298 polygon_45 by unsigned factor.&nbsp; Linear wrt. vertices.</td>
 299           </tr>
 300           <tr>
 301             <td width="586"><font face="Courier New">template
 302 &lt;typename T, scaling_type&gt;<br />
 303 T&amp; <b>scale</b>(T&amp; rectangle, double scaling) </font></td>
 304             <td>Scales coordinates of an object that models polygon_45
 305 by floating point factor.&nbsp; Linear wrt. vertices.</td>
 306           </tr>
 307           <tr>
 308             <td width="586"><font face="Courier New">template
 309 &lt;typename T&gt;<br />
 310 T&amp; <b>move</b>(T&amp; polygon, orientation_2d,<br />
 311 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; coordinate_difference
 312 displacement)</font></td>
 313             <td>Adds displacement value to coordinate indicated by
 314 orientation_2d of vertices of an object that models polygon_45.&nbsp;
 315 Linear wrt. vertices.</td>
 316           </tr>
 317           <tr>
 318             <td width="586"><font face="Courier New">template
 319 &lt;typename polygon_type, typename point_type&gt;<br />
 320 polygon_type&amp; <b>convolve</b>(polygon_type&amp; polygon,<br />
 321 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 322 const point_type&amp; point)</font></td>
 323             <td>Convolves coordinate values of point with vertices of
 324 an object that models polygon_45.&nbsp; Linear wrt. vertices.</td>
 325           </tr>
 326         </tbody>
 327       </table>
 328       <h1>Polygon 45 Data</h1>
 329       <p> </p>
 330       <p>The library provides a model of polygon 45 concept declared
 331       <font face="Courier New">template&lt;typename T&gt;
 332 polygon_45_data </font>where T is the coordinate type.</p>
 333       <p>This data type is used internally when a 45-degree polygon is
 334 needed and is available to the library user who finds it convenient to
 335 use a library polygon data type instead of providing their own.&nbsp;
 336 The data type is implemented to be convenient to use with the library
 337 traits.</p>
 338       <h2>Members</h2>
 339       <table id="table2" border="1" width="100%">
 340         <tbody>
 341           <tr>
 342             <td width="586"><b><font face="Courier New">geometry_type</font></b></td>
 343             <td><font face="Times New Roman">polygon_45_concept</font></td>
 344           </tr>
 345           <tr>
 346             <td width="586"><b><font face="Courier New">coordinate_type</font></b></td>
 347             <td><font face="Times New Roman">T</font></td>
 348           </tr>
 349           <tr>
 350             <td width="586"><b><font face="Courier New">iterator_type</font></b></td>
 351             <td>Iterator over vertices point_data&lt;T&gt; vertices of
 352 polygon</td>
 353           </tr>
 354           <tr>
 355             <td width="586"><font face="Courier New"><b>polygon_45_data</b>()</font></td>
 356             <td><font face="Times New Roman">Default constructs the </font>polygon.</td>
 357           </tr>
 358           <tr>
 359             <td width="586"><font face="Courier New"><b>polygon_45_data</b>(const
 360 polygon_45_data&amp; that)</font></td>
 361             <td><font face="Times New Roman">Copy construct</font></td>
 362           </tr>
 363           <tr>
 364             <td width="586"><font face="Courier New">polygon_45_data&amp;
 365             <b>operator=</b>(const polygon_45_data&amp; that)</font></td>
 366             <td>Assignment operator.</td>
 367           </tr>
 368           <tr>
 369             <td width="586"><font face="Courier New">template
 370 &lt;typename T2&gt;<b>&nbsp; <br />
 371             </b>polygon_45_data&amp; <b>operator=</b>(const T2&amp;
 372 that) const</font></td>
 373             <td>Assign from an object that is a model of polygon 45.</td>
 374           </tr>
 375           <tr>
 376             <td width="586"><font face="Courier New">iterator_type <b>begin</b>()
 377 const</font></td>
 378             <td>Get the begin iterator over vertices of the polygon.</td>
 379           </tr>
 380           <tr>
 381             <td width="586"><font face="Courier New">iterator_type <b>end</b>()
 382 const</font></td>
 383             <td>Get the end iterator over vertices of the polygon.</td>
 384           </tr>
 385           <tr>
 386             <td width="586"><font face="Courier New">std::size_t <b>size</b>()
 387 const</font></td>
 388             <td>Get the number of elements in the sequence stored to
 389 the polygon, usually equal to the number of edges of the polygon.</td>
 390           </tr>
 391           <tr>
 392             <td width="586"><font face="Courier New">template
 393 &lt;typename iT&gt;<b>&nbsp; <br />
 394             </b>void <b>set</b>(iT begin_points, iT end_points)</font></td>
 395             <td>Sets the polygon to the iterator range of points.&nbsp;
 396 No check is performed to ensure the points describe corners that are
 397 multiples of 45 degrees relative to the coordinate axis.</td>
 398           </tr>
 399         </tbody>
 400       </table>
 401       </td>
 402     </tr>
 403     <tr>
 404       <td style="background-color: rgb(238, 238, 238);" nowrap="1"
 405  valign="top"> &nbsp;</td>
 406       <td
 407  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
 408  valign="top" width="100%">
 409       <table class="docinfo" id="table3" frame="void" rules="none">
 410         <colgroup> <col class="docinfo-name" /><col
 411  class="docinfo-content" /> </colgroup> <tbody valign="top">
 412           <tr>
 413             <th class="docinfo-name">Copyright:</th>
 414             <td>Copyright © Intel Corporation 2008-2010.</td>
 415           </tr>
 416           <tr class="field">
 417             <th class="docinfo-name">License:</th>
 418             <td class="field-body">Distributed under the Boost Software
 419 License, Version 1.0. (See accompanying file <tt class="literal"> <span
 420  class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
 421  class="reference" target="_top"
 422  href="http://www.boost.org/LICENSE_1_0.txt">
 423 http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 424           </tr>
 425         </tbody>
 426       </table>
 427       </td>
 428     </tr>
 429   </tbody>
 430 </table>
 431 </body>
 432 </html>