ceph/src/boost/libs/polygon/doc/gtl_segment_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: Segment 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><br />
  35         </li>
  36         <li>Segment Concept</li>
  37         <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
  38         <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
  39         <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
  40 With Holes Concept</a></li>
  41         <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
  42         <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
  43 With Holes Concept</a></li>
  44         <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
  45         <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
  46 Holes Concept</a></li>
  47         <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
  48 Concept</a></li>
  49         <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
  50 Concept</a></li>
  51         <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
  52         <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
  53 Extraction 90</a></li>
  54         <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
  55 Extraction 45</a></li>
  56         <li><a href="gtl_connectivity_extraction.htm">Connectivity
  57 Extraction</a></li>
  58         <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
  59         <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
  60         <li><a href="gtl_property_merge.htm">Property Merge</a></li>
  61         <li><a href="voronoi_main.htm">Voronoi Main Page<br />
  62           </a></li>
  63         <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br />
  64         </li>
  65         <li><a href="voronoi_builder.htm">Voronoi Builder</a></li>
  66         <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
  67       </ul>
  68       <h3 class="navbar">Other Resources</h3>
  69       <ul>
  70         <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
  71         <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
  72 Presentation</a></li>
  73         <li><a href="analysis.htm">Performance Analysis</a></li>
  74         <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
  75         <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
  76         <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
  77         <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
  78 Tutorial</a></li>
  79       </ul>
  80       </div>
  81       <h3 class="navbar">Polygon Sponsor</h3>
  82       <div style="padding: 5px;" align="center"> <img
  83  src="images/intlogo.gif" border="0" height="51" width="127" /><a
  84  title="www.adobe.com home page" href="http://www.adobe.com/"
  85  tabindex="2" style="border: medium none ;"> </a> </div>
  86       </td>
  87       <td
  88  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
  89  valign="top" width="100%"><!-- End Header --><br />
  90       <p> </p>
  91       <h1>Segment Concept</h1>
  92       <p> </p>
  93       <p> The segment concept tag is <font face="Courier New">segment_concept</font></p>
  94       <p> To register a user defined type as a model of the segment
  95 concept, specialize the geometry concept meta-function for that
  96 type.&nbsp; In the example below CSegment is registered as a model of
  97 the segment concept.</p>
  98       <p style="font-family: Courier New,Courier,monospace;"> template
  99 &lt;&gt;<br />
 100 struct geometry_concept&lt;CSegment&gt;
 101 { typedef segment_concept type; };</p>
 102       <p> The semantic of a segment is
 103 that it has a low and high point.&nbsp; A
 104 std::pair&lt;Point, Point&gt;,
 105 boost::tuple&lt;Point, Point&gt; or boost::array&lt;Point, 2&gt; could
 106 all be made models of
 107 segment by simply providing indirect access to their elements through
 108 traits, however, these objects cannot be made a model of both segment
 109 and rectangle in the same compilation unit, for obvious reason that
 110 duplicate specialization of the geometry_concept struct is illegal, but
 111 also because it would make overloading generic function by concept
 112 ambiguous if a type modeled more than one concept.</p>
 113       <p> Below is shown the default
 114 segment traits. Specialization of these traits is required for
 115 types that don't conform to the default behavior.</p>
 116       <p><span style="font-family: Courier New,Courier,monospace;"><span
 117  style="font-family: Courier New,Courier,monospace;">template
 118 &lt;typename Segment&gt;</span><br
 119  style="font-family: Courier New,Courier,monospace;" />
 120       <span style="font-family: Courier New,Courier,monospace;">struct
 121 segment_traits {</span><br
 122  style="font-family: Courier New,Courier,monospace;" />
 123       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 124 typedef typename Segment::coordinate_type coordinate_type;</span><br
 125  style="font-family: Courier New,Courier,monospace;" />
 126       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 127 typedef typename Segment::point_type point_type;</span><br
 128  style="font-family: Courier New,Courier,monospace;" />
 129       <br style="font-family: Courier New,Courier,monospace;" />
 130       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 131 static inline point_type get(const Segment&amp; segment, direction_1d
 132 dir) {</span><br style="font-family: Courier New,Courier,monospace;" />
 133       <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 134 return segment.get(dir);</span><br
 135  style="font-family: Courier New,Courier,monospace;" />
 136       <span style="font-family: Courier New,Courier,monospace;">&nbsp; }</span><br
 137  style="font-family: Courier New,Courier,monospace;" />
 138       <span style="font-family: Courier New,Courier,monospace;">};</span><br />
 139       <br />
 140       <span style="font-family: Courier New,Courier,monospace;">template
 141 &lt;typename Segment&gt;<br />
 142 struct segment_mutable_traits {<br />
 143 &nbsp; </span></span><span
 144  style="font-family: Courier New,Courier,monospace;"><span
 145  style="font-family: Courier New,Courier,monospace;">typedef typename
 146 segment_traits&lt;Segment&gt;::coordinate_type </span></span><span
 147  style="font-family: Courier New,Courier,monospace;"><span
 148  style="font-family: Courier New,Courier,monospace;">coordinate_type;</span></span><br />
 149       <span style="font-family: Courier New,Courier,monospace;"><span
 150  style="font-family: Courier New,Courier,monospace;">&nbsp; typedef
 151 typename segment_traits&lt;Segment&gt;::point_type point_type;<br />
 152       <br />
 153 &nbsp; static inline void set(Segment&amp; segment, direction_1d dir,
 154 const point_type&amp; point) {<br />
 155 &nbsp;&nbsp;&nbsp; segment.set(dir, p);<br />
 156 &nbsp; }<br />
 157       <br />
 158 &nbsp; static inline Segment construct(const point_type&amp; low, const
 159 point_type&amp; high) {<br />
 160 &nbsp;&nbsp;&nbsp; return Segment(low, high);<br />
 161 &nbsp; }<br />
 162 };</span></span></p>
 163       <h2>Functions</h2>
 164       <table style="width: 100%;" id="table1" border="1">
 165         <tbody>
 166           <tr>
 167             <td width="586"><font face="Courier New">template
 168 &lt;typename Segment&gt;<br />
 169 point_type <b>get</b>(const Segment&amp; segment, direction_1d dir)</font></td>
 170             <td>Returns the low or high endpoint of an object that
 171 models segment, depending on
 172 the direction_1d value.<font face="Courier New">&nbsp;</font></td>
 173           </tr>
 174           <tr>
 175             <td width="586"><font face="Courier New">template
 176 &lt;typename </font><font face="Courier New">Segment</font><font
 177  face="Courier New">, typename Point&gt;<br />
 178 void <b>set</b>(</font><font face="Courier New">Segment</font><font
 179  face="Courier New">&amp; segment, direction_1d dir,<br />
 180 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; const Point&amp; </font><span
 181  style="font-family: Courier New;">point</span><font face="Courier New">)</font></td>
 182             <td>Sets
 183 the low or high endpoint of an object that models segment to an object
 184 that models point, depending on the direction_1d value.</td>
 185           </tr>
 186           <tr>
 187             <td width="586"><font face="Courier New">template
 188 &lt;typename Segment, typename Point1, typename Point2&gt;<br />
 189 Segment<b> construct</b>(const Point1&amp; low, const Point2&amp; high)</font></td>
 190             <td>Constructs an object that is a model of segment given
 191 the two objects that are models of point.</td>
 192           </tr>
 193           <tr>
 194             <td><font face="Courier New">template &lt;typename
 195 Segment1, typename </font><font face="Courier New">Segment2</font><font
 196  face="Courier New">&gt;<br />
 197             </font><font face="Courier New">Segment1</font><font
 198  face="Courier New"> <span style="font-weight: bold;">copy_construct</span>(const
 199             </font><font face="Courier New">Segment2</font><font
 200  face="Courier New">&amp; segment)</font></td>
 201             <td style="text-align: left;">Copy constructs an object
 202 that models segment given another segment.</td>
 203           </tr>
 204           <tr>
 205             <td width="586"><font face="Courier New">template
 206 &lt;typename </font><font face="Courier New">Segment1</font><font
 207  face="Courier New">, typename </font><font face="Courier New">Segment2&gt;</font><br />
 208             <font face="Courier New">Segment1</font><font
 209  face="Courier New">&amp; <b>assign</b>(</font><font face="Courier New">Segment1</font><font
 210  face="Courier New">&amp; segment1,<br />
 211 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 212 const </font><font face="Courier New">Segment2</font><font
 213  face="Courier New">&amp; segment2)</font></td>
 214             <td>Copies data from the second object that models segment
 215 into
 216 the first object that models segment.</td>
 217           </tr>
 218           <tr>
 219             <td width="586"><font face="Courier New">template
 220 &lt;typename </font><font face="Courier New">Segment1</font><font
 221  face="Courier New">, typename </font><font face="Courier New">Segment1</font><font
 222  face="Courier New">&gt;<br />
 223 bool <b>equivalence</b>(const </font><font face="Courier New">Segment1</font><font
 224  face="Courier New">&amp; segment1,<br />
 225 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 226 const </font><font face="Courier New">Segment1</font><font
 227  face="Courier New">&amp; segment2)</font></td>
 228             <td>Given two objects that model segment, compares and
 229 returns true if their low and high values are respectively equal.</td>
 230           </tr>
 231           <tr>
 232             <td><span
 233  style="font-family: Courier New,Courier,monospace;">template
 234 &lt;typename Segment, typename Point&gt;</span><br
 235  style="font-family: Courier New,Courier,monospace;" />
 236             <span style="font-family: Courier New,Courier,monospace;">int
 237             <b>orientation</b></span><span
 238  style="font-family: Courier New,Courier,monospace;">(const </span><span
 239  style="font-family: Courier New,Courier,monospace;">Segment</span><span
 240  style="font-family: Courier New,Courier,monospace;">&amp; segment,</span><br
 241  style="font-family: Courier New,Courier,monospace;" />
 242             <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 243 const Point&amp; point)</span><br />
 244             </td>
 245             <td>Implements
 246 a robust orientation test of two objects that model segment and point.
 247 Returns 0, if the point is collinear to the segment.<br />
 248 Returns 1, if the point lies to the left of the segment.<br />
 249 Returns -1, if the point lies to the right of the segment.<br />
 250             </td>
 251           </tr>
 252           <tr>
 253             <td><span
 254  style="font-family: Courier New,Courier,monospace;">template
 255 &lt;typename Segment1, typename Segment2&gt;</span><br
 256  style="font-family: Courier New,Courier,monospace;" />
 257             <span style="font-family: Courier New,Courier,monospace;">int
 258             <b>orientation</b></span><span
 259  style="font-family: Courier New,Courier,monospace;">(const </span><span
 260  style="font-family: Courier New,Courier,monospace;">Segment1</span><span
 261  style="font-family: Courier New,Courier,monospace;">&amp; segment1,</span><br
 262  style="font-family: Courier New,Courier,monospace;" />
 263             <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 264 const Segment2&amp; segment2)</span></td>
 265             <td>Implements a robust orientation test of two objects
 266 that model segment. Note: segments are treated as math.
 267 vectors.<br />
 268 Returns 0, if segments are collinear.<br />
 269 Returns 1, if the second segment is CCW oriented to the first segment.<br />
 270 Returns -1, if the second segment is CW oriented to the first segment.<br />
 271             </td>
 272           </tr>
 273           <tr>
 274             <td><span
 275  style="font-family: Courier New,Courier,monospace;">template
 276 &lt;typename </span><font face="Courier New">Segment, typename Point</font><span
 277  style="font-family: Courier New,Courier,monospace;">&gt;</span><br
 278  style="font-family: Courier New,Courier,monospace;" />
 279             <span style="font-family: Courier New,Courier,monospace;">bool
 280             </span><span
 281  style="font-weight: bold; font-family: Courier New,Courier,monospace;">contains</span><span
 282  style="font-family: Courier New,Courier,monospace;">(const </span><font
 283  face="Courier New">Segment</font><span
 284  style="font-family: Courier New,Courier,monospace;">&amp; segment,</span><br
 285  style="font-family: Courier New,Courier,monospace;" />
 286             <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 287 const Point&amp; value,</span><span
 288  style="font-family: Courier New,Courier,monospace;"> bool
 289 consider_touch)</span><br />
 290             </td>
 291             <td>Returns true if an object that models segment contains
 292 an object that models point, else false.<br />
 293             </td>
 294           </tr>
 295           <tr>
 296             <td><span
 297  style="font-family: Courier New,Courier,monospace;">template
 298 &lt;typename Segment1, typename Segment2&gt;</span><br
 299  style="font-family: Courier New,Courier,monospace;" />
 300             <span style="font-family: Courier New,Courier,monospace;">bool
 301             </span><span
 302  style="font-weight: bold; font-family: Courier New,Courier,monospace;">contains</span><span
 303  style="font-family: Courier New,Courier,monospace;">(const </span><span
 304  style="font-family: Courier New,Courier,monospace;">Segment1</span><span
 305  style="font-family: Courier New,Courier,monospace;">&amp; segment1,</span><br
 306  style="font-family: Courier New,Courier,monospace;" />
 307             <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 308 const </span><span style="font-family: Courier New,Courier,monospace;">Segment</span><span
 309  style="font-family: Courier New,Courier,monospace;">2&amp; segment2,</span>
 310             <span style="font-family: Courier New,Courier,monospace;">bool
 311 consider_touch)</span></td>
 312             <td>Returns true if the first object contains the second
 313 one, else false. Both objects model segment.<br />
 314             </td>
 315           </tr>
 316           <tr>
 317             <td style="font-family: Courier New,Courier,monospace;">template
 318 &lt;typename <span style="font-family: Courier New,Courier,monospace;">Segment</span>&gt;<br />
 319 point_type <span style="font-weight: bold;">low</span>(const <span
 320  style="font-family: Courier New,Courier,monospace;">Segment</span>&amp;
 321 segment)<br />
 322             </td>
 323             <td>Returns the low endpoint of an object that models
 324 segment.<br />
 325             </td>
 326           </tr>
 327           <tr>
 328             <td style="font-family: Courier New,Courier,monospace;">template
 329 &lt;typename <span style="font-family: Courier New,Courier,monospace;">Segment</span>&gt;<br />
 330 point_type <span style="font-weight: bold;">high</span>(const <span
 331  style="font-family: Courier New,Courier,monospace;">Segment</span>&amp;
 332 segment)</td>
 333             <td>Returns the high endpoint of an object that models
 334 segment.<br />
 335             </td>
 336           </tr>
 337           <tr>
 338             <td style="font-family: Courier New,Courier,monospace;">template
 339 &lt;typename <span style="font-family: Courier New,Courier,monospace;">Segment</span>&gt;<br />
 340 point_type <span style="font-weight: bold;">center</span>(const <span
 341  style="font-family: Courier New,Courier,monospace;">Segment</span>&amp;
 342 segment)</td>
 343             <td>Returns the central point of an object that models
 344 segment.<br />
 345             </td>
 346           </tr>
 347           <tr>
 348             <td style="font-family: Courier New,Courier,monospace;">template
 349 &lt;typename <span style="font-family: Courier New,Courier,monospace;">Segment</span>,
 350 typename Point&gt;<br />
 351 void <span style="font-weight: bold;">low</span>(<span
 352  style="font-family: Courier New,Courier,monospace;">Segment</span>&amp;
 353 segment, const Point&amp; point)</td>
 354             <td>Sets the low endpoint of an object that models segment.<br />
 355             </td>
 356           </tr>
 357           <tr>
 358             <td style="font-family: Courier New,Courier,monospace;">template
 359 &lt;typename <span style="font-family: Courier New,Courier,monospace;">Segment,
 360 typename Point</span>&gt;<br />
 361 void <span style="font-weight: bold;">high</span>(<span
 362  style="font-family: Courier New,Courier,monospace;">Segment</span>&amp;
 363 segment, const Point&amp; point)</td>
 364             <td>Sets the high endpoint of an object that models of
 365 segment.<br />
 366             </td>
 367           </tr>
 368           <tr>
 369             <td><span
 370  style="font-family: Courier New,Courier,monospace;">template
 371 &lt;typename </span><span
 372  style="font-family: Courier New,Courier,monospace;">Segment</span><span
 373  style="font-family: Courier New,Courier,monospace;">&gt;</span><br
 374  style="font-family: Courier New,Courier,monospace;" />
 375             <span style="font-family: Courier New,Courier,monospace;">distance_type
 376             <span style="font-weight: bold;">length</span>(const </span><span
 377  style="font-family: Courier New,Courier,monospace;">Segment</span><span
 378  style="font-family: Courier New,Courier,monospace;">&amp; segment)</span><br />
 379             </td>
 380             <td>Returns length of an object that models segment.<br />
 381             </td>
 382           </tr>
 383           <tr>
 384             <td width="586"><font face="Courier New">template
 385 &lt;typename </font><span
 386  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 387  face="Courier New">&gt;<br />
 388             </font><span
 389  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 390  face="Courier New">&amp; <b>scale_up</b>(</font><span
 391  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 392  face="Courier New">&amp; </font><font face="Courier New">segment</font><font
 393  face="Courier New">, <br />
 394 &nbsp;&nbsp;&nbsp; unsigned_area_type factor)</font></td>
 395             <td>Multiplies x and y coordinates of both endpoints of an
 396 object that models segment by unsigned factor.</td>
 397           </tr>
 398           <tr>
 399             <td width="586"><font face="Courier New">template
 400 &lt;typename </font><span
 401  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 402  face="Courier New">&gt;<br />
 403             </font><span
 404  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 405  face="Courier New">&amp; <b>scale_down</b>(</font><span
 406  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 407  face="Courier New">&amp; </font><font face="Courier New">segment</font><font
 408  face="Courier New">, <br />
 409 &nbsp;&nbsp;&nbsp; unsigned_area_type factor)</font></td>
 410             <td>Divides x and y coordinates of both endpoints of an
 411 object that models segment by unsigned factor.</td>
 412           </tr>
 413           <tr>
 414             <td width="586"><font face="Courier New">template
 415 &lt;typename </font><span
 416  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 417  face="Courier New">, typename Scale&gt;<br />
 418             </font><span
 419  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 420  face="Courier New">&amp; <b>scale</b>(</font><span
 421  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 422  face="Courier New">&amp; </font><font face="Courier New">segment</font><font
 423  face="Courier New">, const Scale&amp; sc) </font></td>
 424             <td>Calls
 425 the scale member function of the scaling type on the low and high
 426 endpoint of
 427 an object that models segment and updates the segment with the
 428 scaled endpoints.</td>
 429           </tr>
 430           <tr>
 431             <td width="586"><font face="Courier New">template
 432 &lt;typename </font><span
 433  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 434  face="Courier New">, typename Transform&gt;<br />
 435             </font><span
 436  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 437  face="Courier New">&amp; <b>transform</b>(</font><span
 438  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 439  face="Courier New">&amp; segment, const </font><font
 440  face="Courier New">Transform</font><font face="Courier New">&amp; tr) </font></td>
 441             <td>Calls the transform member function of transform type
 442 on the low and high endpoints of an object that models segment and
 443 updates the segment with the transformed endpoints.</td>
 444           </tr>
 445           <tr>
 446             <td width="586"><font face="Courier New">template
 447 &lt;typename </font><span
 448  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 449  face="Courier New">&gt;<br />
 450             </font><span
 451  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 452  face="Courier New">&amp; <b>move</b>(</font><span
 453  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 454  face="Courier New">&amp; segment, orientation_2d<br />
 455 &nbsp;&nbsp;&nbsp; coordinate_difference displacement)</font></td>
 456             <td>Adds displacement value to the x or y coordinates of
 457 both endpoints of an object
 458 that models segment indicated by the orientation_2d.</td>
 459           </tr>
 460           <tr>
 461             <td width="586"><font face="Courier New">template
 462 &lt;</font><span style="font-family: Courier New,Courier,monospace;">Segment,
 463 Point</span><font face="Courier New">&gt;<br />
 464             </font><span
 465  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 466  face="Courier New">&amp; <b>convolve</b>(</font><span
 467  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 468  face="Courier New">&amp; segment, const Point&amp; point)</font></td>
 469             <td>Convolves both endpoints of an object that models
 470 segment with an object that models a point.<br />
 471             </td>
 472           </tr>
 473           <tr>
 474             <td width="586"><font face="Courier New">template
 475 &lt;</font><span style="font-family: Courier New,Courier,monospace;">Segment,
 476 Point</span><font face="Courier New">&gt;<br />
 477             </font><span
 478  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 479  face="Courier New">&amp; <b>deconvolve</b>(</font><span
 480  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 481  face="Courier New">&amp; segment, const Point&amp; point)</font></td>
 482             <td>Deconvolves both endpoints of an object that models
 483 segment with an object that models a point. </td>
 484           </tr>
 485           <tr>
 486             <td style="font-family: Courier New,Courier,monospace;">template
 487 &lt;typename Segment1, typename Segment2&gt;<br />
 488 bool <span style="font-weight: bold;">abuts</span>(const Segment1&amp;
 489 segment1,<br />
 490 &nbsp;&nbsp;&nbsp; const Segment2&amp; segment2, direction_1d dir)</td>
 491             <td>Returns true if two objects that model segment abut,
 492 depending on the direction_1d value.</td>
 493           </tr>
 494           <tr>
 495             <td style="font-family: Courier New,Courier,monospace;">template
 496 &lt;typename Segment1, typename Segment2&gt;<br />
 497 bool <span style="font-weight: bold;">abuts</span>(const Segment1&amp;
 498 segment1,<br />
 499 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; const
 500 Segment2&amp; segment2)</td>
 501             <td>Returns true if two objects that model segment abut:
 502 either the first one to the second one or vice versa.</td>
 503           </tr>
 504           <tr>
 505             <td><span
 506  style="font-family: Courier New,Courier,monospace;">template
 507 &lt;typename Segment1, typename Segment2&gt;</span><br
 508  style="font-family: Courier New,Courier,monospace;" />
 509             <span style="font-family: Courier New,Courier,monospace;">bool
 510             <span style="font-weight: bold;">intersects</span>(const
 511 Segment1&amp; segment1,</span><br
 512  style="font-family: Courier New,Courier,monospace;" />
 513             <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 514 const Segment2&amp; segment2,<br />
 515 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 516 bool consider_touch)</span><br />
 517             </td>
 518             <td>Returns true if two objects that model segment
 519 intersect, else false.<br />
 520             </td>
 521           </tr>
 522           <tr>
 523             <td style="font-family: Courier New,Courier,monospace;"><font
 524  face="Courier New">template
 525 &lt;typename </font><span
 526  style="font-family: Courier New,Courier,monospace;">Segment, typename
 527 Point</span><font face="Courier New">&gt;<br />
 528 distance_type <b>euclidean_distance</b>(<br />
 529 &nbsp;&nbsp;&nbsp; const </font><span
 530  style="font-family: Courier New,Courier,monospace;">Segment</span><font
 531  face="Courier New">&amp; segment, const Point&amp; point)</font> </td>
 532             <td>Returns distance from an object that models segment
 533 to an object that models point. </td>
 534           </tr>
 535           <tr>
 536             <td style="font-family: Courier New,Courier,monospace;"><font
 537  face="Courier New">template
 538 &lt;typename Segment1, typename </font><font face="Courier New">Segment2</font><font
 539  face="Courier New">&gt;<br />
 540 distance_type <b>euclidean_distance</b>(<br />
 541 &nbsp;&nbsp;&nbsp; const </font><font face="Courier New">Segment1</font><font
 542  face="Courier New">&amp; segment1, const </font><font
 543  face="Courier New">Segment2</font><font face="Courier New">&amp;
 544 segment2)</font> </td>
 545             <td>Returns distance between two objects that model
 546 segment. </td>
 547           </tr>
 548         </tbody>
 549       </table>
 550       <h1>Segment Data</h1>
 551       <p> </p>
 552       <p>The library provides a model of the segment concept declared <font
 553  face="Courier New">template&lt;typename T&gt; segment_data</font>,
 554 where
 555 T is the coordinate type.</p>
 556       <p>This data type is used internally when a segment is needed and
 557 is available to the library user, who finds it convenient to use a
 558 library segment data type instead of providing their own.&nbsp; The
 559 data
 560 type is implemented to be convenient to use with the library traits.</p>
 561       <h2>Members</h2>
 562       <table style="width: 100%;" id="table2" border="1">
 563         <tbody>
 564           <tr>
 565             <td width="586"><b><font face="Courier New">geometry_type</font></b></td>
 566             <td>segment_concept</td>
 567           </tr>
 568           <tr>
 569             <td width="586"><b><font face="Courier New">coordinate_type</font></b></td>
 570             <td>T</td>
 571           </tr>
 572           <tr>
 573             <td><b><font face="Courier New">point_type</font></b></td>
 574             <td>point_data&lt;T&gt;<br />
 575             </td>
 576           </tr>
 577           <tr>
 578             <td width="586"><font face="Courier New"><b>segment_data</b>()</font></td>
 579             <td>Default constructor.</td>
 580           </tr>
 581           <tr>
 582             <td width="586"><font face="Courier New"><b>segment_data</b>(const
 583 point_type&amp; low,<br />
 584 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 585 const point_type&amp; high)</font></td>
 586             <td>Constructs a segment from the given endpoints.</td>
 587           </tr>
 588           <tr>
 589             <td width="586"><font face="Courier New"><b>segment_data</b>(const
 590 segment_data&amp; that)</font></td>
 591             <td>Copy constructor.</td>
 592           </tr>
 593           <tr>
 594             <td width="586"><font face="Courier New">segment_data&amp; <b>operator=</b>(const
 595 segment_data&amp; that)</font></td>
 596             <td>Assignment operator.</td>
 597           </tr>
 598           <tr>
 599             <td width="586"><font face="Courier New">template
 600 &lt;typename SegmentType&gt;<b><br />
 601             </b>segment_data&amp; <b>operator=</b>(const </font><font
 602  face="Courier New">SegmentType</font><font face="Courier New">&amp;
 603 that)
 604 const</font></td>
 605             <td>Assign from an object that is a model of segment.</td>
 606           </tr>
 607           <tr>
 608             <td width="586"><font face="Courier New">bool<b> operator==</b>(const
 609 segment_data&amp; that) const</font></td>
 610             <td>Equality operator overload.</td>
 611           </tr>
 612           <tr>
 613             <td width="586"><font face="Courier New"><b> </b>bool<b>
 614 operator!=</b>(const segment_data&amp; that) const</font></td>
 615             <td>Inequality operator overload.</td>
 616           </tr>
 617           <tr>
 618             <td width="586"><font face="Courier New"><b> </b>bool<b>
 619 operator&lt;</b>(const segment_data&amp; that) const</font></td>
 620             <td>Less operator overload. Compares low endpoints then
 621 high endpoints to break ties.<br />
 622             </td>
 623           </tr>
 624           <tr>
 625             <td width="586"><font face="Courier New"><b> </b>bool<b>
 626 operator&lt;=</b>(const segment_data&amp; that) const</font></td>
 627             <td>Less or equal operator overload. Compares low endpoints
 628 then high endpoints to break ties.<br />
 629             </td>
 630           </tr>
 631           <tr>
 632             <td width="586"><font face="Courier New"><b> </b>bool<b>
 633 operator&gt;</b>(const segment_data&amp; that) const</font></td>
 634             <td>Greater operator overload. Compares low endpoints then
 635 high endpoints to break ties.<br />
 636             </td>
 637           </tr>
 638           <tr>
 639             <td width="586"><font face="Courier New"><b> </b>bool<b>
 640 operator&gt;=</b>(const segment_data&amp; that) const</font></td>
 641             <td>Greater or equal operator overload. Compares low
 642 endpoints then high endpoints to break ties.<br />
 643             </td>
 644           </tr>
 645           <tr>
 646             <td width="586"><font face="Courier New">point_type <b>get</b>(direction_1d
 647 dir) const</font></td>
 648             <td>Retrieves the low/high endpoint considering direction
 649 value.</td>
 650           </tr>
 651           <tr>
 652             <td width="586"><font face="Courier New">point_type <span
 653  style="font-weight: bold;">low</span>() const</font></td>
 654             <td>Retrieves the low endpoint.</td>
 655           </tr>
 656           <tr>
 657             <td width="586"><font face="Courier New">point_type <span
 658  style="font-weight: bold;">high</span>() const</font></td>
 659             <td>Retrieves the high endpoint.</td>
 660           </tr>
 661           <tr>
 662             <td width="586"><font face="Courier New">void <b>set</b></font><font
 663  face="Courier New">(direction_1d dir</font><font face="Courier New">,
 664 const point_type&amp; point)</font></td>
 665             <td>Sets the endpoint in the given direction.</td>
 666           </tr>
 667           <tr>
 668             <td width="586"><font face="Courier New">segment_data&amp; <span
 669  style="font-weight: bold;">low</span>(const point_type&amp; point)</font></td>
 670             <td>Sets the low endpoint.</td>
 671           </tr>
 672           <tr>
 673             <td width="586"><font face="Courier New">segment_data&amp; <span
 674  style="font-weight: bold;">high(</span>const point_type&amp; point)</font></td>
 675             <td>Sets the high endpoint.</td>
 676           </tr>
 677         </tbody>
 678       </table>
 679       <h1>Segment Utils</h1>
 680       <p> </p>
 681       <p>The library provides several algorithms for the manipulation
 682 of sets of segment data. In particular, the generalize line segment
 683 intersection algorithm used for polygon set operations is exposed
 684 through several interfaces to allow it to be used with any collection
 685 or sequence of objects that model the <font face="Courier New">segment_concept</font>.
 686       </p>
 687       <h2>Functions</h2>
 688       <table style="width: 100%;" id="table3" border="1">
 689         <tbody>
 690           <tr>
 691             <td width="586"><font face="Courier New">template
 692 &lt;</font><font face="Courier New">typename SegmentContainer</font><font
 693  face="Courier New">,</font><font face="Courier New"><br />
 694 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typename
 695 SegmentIterator</font><font face="Courier New">&gt;<b><br />
 696             </b>void <b>intersect_segments</b>(<br />
 697 &nbsp;&nbsp;&nbsp; </font><font face="Courier New">SegmentContainer*
 698 result,</font><br />
 699             <font face="Courier New">&nbsp;&nbsp;&nbsp; SegmentIterator
 700 first,<br />
 701 &nbsp;&nbsp;&nbsp; SegmentIterator last) </font></td>
 702             <td>Accumulates
 703 the result of splitting the segments in the iterator range at their
 704 intersection points into the result container. Preconditions: segment
 705 type used by all the input structures should model segment
 706 concept.Postconditions: no segments intersect except at their end
 707 points. Useful to satisfy the precondition of voronoi diagram
 708 construction. Expected n log n runtime, worst case quadratic runtime
 709 wrt. vertices + intersections. </td>
 710           </tr>
 711           <tr>
 712             <td width="586"><font face="Courier New">template
 713 &lt;</font><font face="Courier New">typename Segment,</font><font
 714  face="Courier New"><br />
 715 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </font><font
 716  face="Courier New">typename SegmentIterator</font><font
 717  face="Courier New">&gt;<b><br />
 718             </b>void <b>intersect_segments</b>(<br />
 719 &nbsp;&nbsp;&nbsp; </font><font face="Courier New">vector&lt;pair&lt;size_t,
 720 Segment&gt;* result,</font><br />
 721             <font face="Courier New">&nbsp;&nbsp;&nbsp; SegmentIterator
 722 first,<br />
 723 &nbsp;&nbsp;&nbsp; SegmentIterator last)</font></td>
 724             <td>Accumulates
 725 the result of splitting the segments in the iterator range at their
 726 intersection points into the result container. Preconditions: segment
 727 type used by all the input structures should model segment concept.
 728 Postconditions: no segments intersect except at their end points. The
 729 index of the input segment is paired with each resultant segment that
 730 was split to produce it to associate the result segments with the
 731 inputs segments. Expected n log n runtime, worst case quadratic runtime
 732 wrt. vertices + intersections. </td>
 733           </tr>
 734           <tr>
 735             <td width="586"><font face="Courier New">template
 736 &lt;</font><font face="Courier New">typename Rectangle,<br />
 737 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </font><font
 738  face="Courier New">typename </font><font face="Courier New">SegmentIterator</font><font
 739  face="Courier New">&gt;<b><br />
 740             </b>void <span style="font-weight: bold;">envelope_segments</span>(<br />
 741 &nbsp;&nbsp;&nbsp; </font><font face="Courier New">Rectangle* rect,</font><br />
 742             <font face="Courier New">&nbsp;&nbsp;&nbsp; </font><font
 743  face="Courier New">SegmentIterator first,<br />
 744 &nbsp; &nbsp; SegmentIterator last</font><font face="Courier New">) </font></td>
 745             <td>Computes
 746 the bounding rectangle of the iterator range of line segments.
 747 Preconditions: segment type and rectangle type used by the input
 748 structures should model segment concept and rectangle concept
 749 respectively. Linear runtime. </td>
 750           </tr>
 751         </tbody>
 752       </table>
 753       </td>
 754     </tr>
 755     <tr>
 756       <td style="background-color: rgb(238, 238, 238);" nowrap="1"
 757  valign="top"> &nbsp;</td>
 758       <td
 759  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
 760  valign="top" width="100%">
 761       <table class="docinfo" id="table4" frame="void" rules="none">
 762         <colgroup> <col class="docinfo-name" /><col
 763  class="docinfo-content" /> </colgroup> <tbody valign="top">
 764           <tr>
 765             <th class="docinfo-name">Copyright:</th>
 766             <td>Copyright © Intel Corporation 2008-2010.</td>
 767           </tr>
 768           <tr class="field">
 769             <th class="docinfo-name">License:</th>
 770             <td class="field-body">Distributed under the Boost Software
 771 License, Version 1.0. (See accompanying file <tt class="literal"> <span
 772  class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
 773  class="reference" target="_top"
 774  href="http://www.boost.org/LICENSE_1_0.txt">
 775 http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 776           </tr>
 777         </tbody>
 778       </table>
 779       </td>
 780     </tr>
 781   </tbody>
 782 </table>
 783 </body>
 784 </html>