Home Explore Help
Register Sign In
devn00b
/
EQ2EMu
9
3
Fork 0
Files Issues 75 Pull Requests 0 Wiki
Tree: b93cabc72e
Branches Tags
EQ2EMu
/
EQ2
/
source
/
depends
/
boost_1_72_0
/
libs
/
polygon
/
doc
/
gtl_segment_concept.htm

gtl_segment_concept.htm 37 KB
History Raw

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784 
  1. <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
    2. 

  2. <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en"
    3. 

  3.  xmlns:v="urn:schemas-microsoft-com:vml"
    4. 

  4.  xmlns:o="urn:schemas-microsoft-com:office:office"
    5. 

  5.  xmlns:(null)1="http://www.w3.org/TR/REC-html40" lang="en">
    6. 

  6. <head>
    7. 

  7. <!--
    8. 

  8.     Copyright 2009-2010 Intel Corporation
    9. 

  9.     license banner
    10. 

  10. -->
    11. 

  11.   <title>Boost Polygon Library: Segment Concept</title>
    12. 

  12.   <meta http-equiv="content-type" content="text/html;charset=ISO-8859-1" />
    13. 

  13. <!-- <link type="text/css" rel="stylesheet" href="adobe_source.css"> -->
    14. 

  14. </head>
    15. 

  15. <body>
    16. 

  16. <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0"
    17. 

  17.  cellpadding="0" cellspacing="0">
    18. 

  18.   <tbody>
    19. 

  19.     <tr>
    20. 

  20.       <td style="background-color: rgb(238, 238, 238);" nowrap="1"
    21. 

  21.  valign="top">
    22. 

  22.       <div style="padding: 5px;" align="center"> <img
    23. 

  23.  src="images/boost.png" border="0" height="86" width="277" /><a
    24. 

  24.  title="www.boost.org home page" href="http://www.boost.org/"
    25. 

  25.  tabindex="2" style="border: medium none ;"> </a> </div>
    26. 

  26.       <div style="margin: 5px;">
    27. 

  27.       <h3 class="navbar">Contents</h3>
    28. 

  28.       <ul>
    29. 

  29.         <li><a href="index.htm">Boost.Polygon Main Page</a></li>
    30. 

  30.         <li><a href="gtl_design_overview.htm">Design Overview</a></li>
    31. 

  31.         <li><a href="gtl_isotropy.htm">Isotropy</a></li>
    32. 

  32.         <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
    33. 

  33.         <li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
    34. 

  34.         <li><a href="gtl_point_concept.htm">Point Concept</a><br />
    35. 

  35.         </li>
    36. 

  36.         <li>Segment Concept</li>
    37. 

  37.         <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
    38. 

  38.         <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
    39. 

  39.         <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
    40. 

  40. With Holes Concept</a></li>
    41. 

  41.         <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
    42. 

  42.         <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
    43. 

  43. With Holes Concept</a></li>
    44. 

  44.         <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
    45. 

  45.         <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
    46. 

  46. Holes Concept</a></li>
    47. 

  47.         <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
    48. 

  48. Concept</a></li>
    49. 

  49.         <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
    50. 

  50. Concept</a></li>
    51. 

  51.         <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
    52. 

  52.         <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
    53. 

  53. Extraction 90</a></li>
    54. 

  54.         <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
    55. 

  55. Extraction 45</a></li>
    56. 

  56.         <li><a href="gtl_connectivity_extraction.htm">Connectivity
    57. 

  57. Extraction</a></li>
    58. 

  58.         <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
    59. 

  59.         <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
    60. 

  60.         <li><a href="gtl_property_merge.htm">Property Merge</a></li>
    61. 

  61.         <li><a href="voronoi_main.htm">Voronoi Main Page<br />
    62. 

  62.           </a></li>
    63. 

  63.         <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a><br />
    64. 

  64.         </li>
    65. 

  65.         <li><a href="voronoi_builder.htm">Voronoi Builder</a></li>
    66. 

  66.         <li><a href="voronoi_diagram.htm">Voronoi Diagram</a></li>
    67. 

  67.       </ul>
    68. 

  68.       <h3 class="navbar">Other Resources</h3>
    69. 

  69.       <ul>
    70. 

  70.         <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
    71. 

  71.         <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
    72. 

  72. Presentation</a></li>
    73. 

  73.         <li><a href="analysis.htm">Performance Analysis</a></li>
    74. 

  74.         <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
    75. 

  75.         <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
    76. 

  76.         <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
    77. 

  77.         <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
    78. 

  78. Tutorial</a></li>
    79. 

  79.       </ul>
    80. 

  80.       </div>
    81. 

  81.       <h3 class="navbar">Polygon Sponsor</h3>
    82. 

  82.       <div style="padding: 5px;" align="center"> <img
    83. 

  83.  src="images/intlogo.gif" border="0" height="51" width="127" /><a
    84. 

  84.  title="www.adobe.com home page" href="http://www.adobe.com/"
    85. 

  85.  tabindex="2" style="border: medium none ;"> </a> </div>
    86. 

  86.       </td>
    87. 

  87.       <td
    88. 

  88.  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
    89. 

  89.  valign="top" width="100%"><!-- End Header --><br />
    90. 

  90.       <p> </p>
    91. 

  91.       <h1>Segment Concept</h1>
    92. 

  92.       <p> </p>
    93. 

  93.       <p> The segment concept tag is <font face="Courier New">segment_concept</font></p>
    94. 

  94.       <p> To register a user defined type as a model of the segment
    95. 

  95. concept, specialize the geometry concept meta-function for that
    96. 

  96. type.&nbsp; In the example below CSegment is registered as a model of
    97. 

  97. the segment concept.</p>
    98. 

  98.       <p style="font-family: Courier New,Courier,monospace;"> template
    99. 

  99. &lt;&gt;<br />
    100. 

  100. struct geometry_concept&lt;CSegment&gt;
    101. 

  101. { typedef segment_concept type; };</p>
    102. 

  102.       <p> The semantic of a segment is
    103. 

  103. that it has a low and high point.&nbsp; A
    104. 

  104. std::pair&lt;Point, Point&gt;,
    105. 

  105. boost::tuple&lt;Point, Point&gt; or boost::array&lt;Point, 2&gt; could
    106. 

  106. all be made models of
    107. 

  107. segment by simply providing indirect access to their elements through
    108. 

  108. traits, however, these objects cannot be made a model of both segment
    109. 

  109. and rectangle in the same compilation unit, for obvious reason that
    110. 

  110. duplicate specialization of the geometry_concept struct is illegal, but
    111. 

  111. also because it would make overloading generic function by concept
    112. 

  112. ambiguous if a type modeled more than one concept.</p>
    113. 

  113.       <p> Below is shown the default
    114. 

  114. segment traits. Specialization of these traits is required for
    115. 

  115. types that don't conform to the default behavior.</p>
    116. 

  116.       <p><span style="font-family: Courier New,Courier,monospace;"><span
    117. 

  117.  style="font-family: Courier New,Courier,monospace;">template
    118. 

  118. &lt;typename Segment&gt;</span><br
    119. 

  119.  style="font-family: Courier New,Courier,monospace;" />
    120. 

  120.       <span style="font-family: Courier New,Courier,monospace;">struct
    121. 

  121. segment_traits {</span><br
    122. 

  122.  style="font-family: Courier New,Courier,monospace;" />
    123. 

  123.       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
    124. 

  124. typedef typename Segment::coordinate_type coordinate_type;</span><br
    125. 

  125.  style="font-family: Courier New,Courier,monospace;" />
    126. 

  126.       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
    127. 

  127. typedef typename Segment::point_type point_type;</span><br
    128. 

  128.  style="font-family: Courier New,Courier,monospace;" />
    129. 

  129.       <br style="font-family: Courier New,Courier,monospace;" />
    130. 

  130.       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
    131. 

  131. static inline point_type get(const Segment&amp; segment, direction_1d
    132. 

  132. dir) {</span><br style="font-family: Courier New,Courier,monospace;" />
    133. 

  133.       <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
    134. 

  134. return segment.get(dir);</span><br
    135. 

  135.  style="font-family: Courier New,Courier,monospace;" />
    136. 

  136.       <span style="font-family: Courier New,Courier,monospace;">&nbsp; }</span><br
    137. 

  137.  style="font-family: Courier New,Courier,monospace;" />
    138. 

  138.       <span style="font-family: Courier New,Courier,monospace;">};</span><br />
    139. 

  139.       <br />
    140. 

  140.       <span style="font-family: Courier New,Courier,monospace;">template
    141. 

  141. &lt;typename Segment&gt;<br />
    142. 

  142. struct segment_mutable_traits {<br />
    143. 

  143. &nbsp; </span></span><span
    144. 

  144.  style="font-family: Courier New,Courier,monospace;"><span
    145. 

  145.  style="font-family: Courier New,Courier,monospace;">typedef typename
    146. 

  146. segment_traits&lt;Segment&gt;::coordinate_type </span></span><span
    147. 

  147.  style="font-family: Courier New,Courier,monospace;"><span
    148. 

  148.  style="font-family: Courier New,Courier,monospace;">coordinate_type;</span></span><br />
    149. 

  149.       <span style="font-family: Courier New,Courier,monospace;"><span
    150. 

  150.  style="font-family: Courier New,Courier,monospace;">&nbsp; typedef
    151. 

  151. typename segment_traits&lt;Segment&gt;::point_type point_type;<br />
    152. 

  152.       <br />
    153. 

  153. &nbsp; static inline void set(Segment&amp; segment, direction_1d dir,
    154. 

  154. const point_type&amp; point) {<br />
    155. 

  155. &nbsp;&nbsp;&nbsp; segment.set(dir, p);<br />
    156. 

  156. &nbsp; }<br />
    157. 

  157.       <br />
    158. 

  158. &nbsp; static inline Segment construct(const point_type&amp; low, const
    159. 

  159. point_type&amp; high) {<br />
    160. 

  160. &nbsp;&nbsp;&nbsp; return Segment(low, high);<br />
    161. 

  161. &nbsp; }<br />
    162. 

  162. };</span></span></p>
    163. 

  163.       <h2>Functions</h2>
    164. 

  164.       <table style="width: 100%;" id="table1" border="1">
    165. 

  165.         <tbody>
    166. 

  166.           <tr>
    167. 

  167.             <td width="586"><font face="Courier New">template
    168. 

  168. &lt;typename Segment&gt;<br />
    169. 

  169. point_type <b>get</b>(const Segment&amp; segment, direction_1d dir)</font></td>
    170. 

  170.             <td>Returns the low or high endpoint of an object that
    171. 

  171. models segment, depending on
    172. 

  172. the direction_1d value.<font face="Courier New">&nbsp;</font></td>
    173. 

  173.           </tr>
    174. 

  174.           <tr>
    175. 

  175.             <td width="586"><font face="Courier New">template
    176. 

  176. &lt;typename </font><font face="Courier New">Segment</font><font
    177. 

  177.  face="Courier New">, typename Point&gt;<br />
    178. 

  178. void <b>set</b>(</font><font face="Courier New">Segment</font><font
    179. 

  179.  face="Courier New">&amp; segment, direction_1d dir,<br />
    180. 

  180. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; const Point&amp; </font><span
    181. 

  181.  style="font-family: Courier New;">point</span><font face="Courier New">)</font></td>
    182. 

  182.             <td>Sets
    183. 

  183. the low or high endpoint of an object that models segment to an object
    184. 

  184. that models point, depending on the direction_1d value.</td>
    185. 

  185.           </tr>
    186. 

  186.           <tr>
    187. 

  187.             <td width="586"><font face="Courier New">template
    188. 

  188. &lt;typename Segment, typename Point1, typename Point2&gt;<br />
    189. 

  189. Segment<b> construct</b>(const Point1&amp; low, const Point2&amp; high)</font></td>
    190. 

  190.             <td>Constructs an object that is a model of segment given
    191. 

  191. the two objects that are models of point.</td>
    192. 

  192.           </tr>
    193. 

  193.           <tr>
    194. 

  194.             <td><font face="Courier New">template &lt;typename
    195. 

  195. Segment1, typename </font><font face="Courier New">Segment2</font><font
    196. 

  196.  face="Courier New">&gt;<br />
    197. 

  197.             </font><font face="Courier New">Segment1</font><font
    198. 

  198.  face="Courier New"> <span style="font-weight: bold;">copy_construct</span>(const
    199. 

  199.             </font><font face="Courier New">Segment2</font><font
    200. 

  200.  face="Courier New">&amp; segment)</font></td>
    201. 

  201.             <td style="text-align: left;">Copy constructs an object
    202. 

  202. that models segment given another segment.</td>
    203. 

  203.           </tr>
    204. 

  204.           <tr>
    205. 

  205.             <td width="586"><font face="Courier New">template
    206. 

  206. &lt;typename </font><font face="Courier New">Segment1</font><font
    207. 

  207.  face="Courier New">, typename </font><font face="Courier New">Segment2&gt;</font><br />
    208. 

  208.             <font face="Courier New">Segment1</font><font
    209. 

  209.  face="Courier New">&amp; <b>assign</b>(</font><font face="Courier New">Segment1</font><font
    210. 

  210.  face="Courier New">&amp; segment1,<br />
    211. 

  211. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
    212. 

  212. const </font><font face="Courier New">Segment2</font><font
    213. 

  213.  face="Courier New">&amp; segment2)</font></td>
    214. 

  214.             <td>Copies data from the second object that models segment
    215. 

  215. into
    216. 

  216. the first object that models segment.</td>
    217. 

  217.           </tr>
    218. 

  218.           <tr>
    219. 

  219.             <td width="586"><font face="Courier New">template
    220. 

  220. &lt;typename </font><font face="Courier New">Segment1</font><font
    221. 

  221.  face="Courier New">, typename </font><font face="Courier New">Segment1</font><font
    222. 

  222.  face="Courier New">&gt;<br />
    223. 

  223. bool <b>equivalence</b>(const </font><font face="Courier New">Segment1</font><font
    224. 

  224.  face="Courier New">&amp; segment1,<br />
    225. 

  225. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
    226. 

  226. const </font><font face="Courier New">Segment1</font><font
    227. 

  227.  face="Courier New">&amp; segment2)</font></td>
    228. 

  228.             <td>Given two objects that model segment, compares and
    229. 

  229. returns true if their low and high values are respectively equal.</td>
    230. 

  230.           </tr>
    231. 

  231.           <tr>
    232. 

  232.             <td><span
    233. 

  233.  style="font-family: Courier New,Courier,monospace;">template
    234. 

  234. &lt;typename Segment, typename Point&gt;</span><br
    235. 

  235.  style="font-family: Courier New,Courier,monospace;" />
    236. 

  236.             <span style="font-family: Courier New,Courier,monospace;">int
    237. 

  237.             <b>orientation</b></span><span
    238. 

  238.  style="font-family: Courier New,Courier,monospace;">(const </span><span
    239. 

  239.  style="font-family: Courier New,Courier,monospace;">Segment</span><span
    240. 

  240.  style="font-family: Courier New,Courier,monospace;">&amp; segment,</span><br
    241. 

  241.  style="font-family: Courier New,Courier,monospace;" />
    242. 

  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. 

  243. const Point&amp; point)</span><br />
    244. 

  244.             </td>
    245. 

  245.             <td>Implements
    246. 

  246. a robust orientation test of two objects that model segment and point.
    247. 

  247. Returns 0, if the point is collinear to the segment.<br />
    248. 

  248. Returns 1, if the point lies to the left of the segment.<br />
    249. 

  249. Returns -1, if the point lies to the right of the segment.<br />
    250. 

  250.             </td>
    251. 

  251.           </tr>
    252. 

  252.           <tr>
    253. 

  253.             <td><span
    254. 

  254.  style="font-family: Courier New,Courier,monospace;">template
    255. 

  255. &lt;typename Segment1, typename Segment2&gt;</span><br
    256. 

  256.  style="font-family: Courier New,Courier,monospace;" />
    257. 

  257.             <span style="font-family: Courier New,Courier,monospace;">int
    258. 

  258.             <b>orientation</b></span><span
    259. 

  259.  style="font-family: Courier New,Courier,monospace;">(const </span><span
    260. 

  260.  style="font-family: Courier New,Courier,monospace;">Segment1</span><span
    261. 

  261.  style="font-family: Courier New,Courier,monospace;">&amp; segment1,</span><br
    262. 

  262.  style="font-family: Courier New,Courier,monospace;" />
    263. 

  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. 

  264. const Segment2&amp; segment2)</span></td>
    265. 

  265.             <td>Implements a robust orientation test of two objects
    266. 

  266. that model segment. Note: segments are treated as math.
    267. 

  267. vectors.<br />
    268. 

  268. Returns 0, if segments are collinear.<br />
    269. 

  269. Returns 1, if the second segment is CCW oriented to the first segment.<br />
    270. 

  270. Returns -1, if the second segment is CW oriented to the first segment.<br />
    271. 

  271.             </td>
    272. 

  272.           </tr>
    273. 

  273.           <tr>
    274. 

  274.             <td><span
    275. 

  275.  style="font-family: Courier New,Courier,monospace;">template
    276. 

  276. &lt;typename </span><font face="Courier New">Segment, typename Point</font><span
    277. 

  277.  style="font-family: Courier New,Courier,monospace;">&gt;</span><br
    278. 

  278.  style="font-family: Courier New,Courier,monospace;" />
    279. 

  279.             <span style="font-family: Courier New,Courier,monospace;">bool
    280. 

  280.             </span><span
    281. 

  281.  style="font-weight: bold; font-family: Courier New,Courier,monospace;">contains</span><span
    282. 

  282.  style="font-family: Courier New,Courier,monospace;">(const </span><font
    283. 

  283.  face="Courier New">Segment</font><span
    284. 

  284.  style="font-family: Courier New,Courier,monospace;">&amp; segment,</span><br
    285. 

  285.  style="font-family: Courier New,Courier,monospace;" />
    286. 

  286.             <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
    287. 

  287. const Point&amp; value,</span><span
    288. 

  288.  style="font-family: Courier New,Courier,monospace;"> bool
    289. 

  289. consider_touch)</span><br />
    290. 

  290.             </td>
    291. 

  291.             <td>Returns true if an object that models segment contains
    292. 

  292. an object that models point, else false.<br />
    293. 

  293.             </td>
    294. 

  294.           </tr>
    295. 

  295.           <tr>
    296. 

  296.             <td><span
    297. 

  297.  style="font-family: Courier New,Courier,monospace;">template
    298. 

  298. &lt;typename Segment1, typename Segment2&gt;</span><br
    299. 

  299.  style="font-family: Courier New,Courier,monospace;" />
    300. 

  300.             <span style="font-family: Courier New,Courier,monospace;">bool
    301. 

  301.             </span><span
    302. 

  302.  style="font-weight: bold; font-family: Courier New,Courier,monospace;">contains</span><span
    303. 

  303.  style="font-family: Courier New,Courier,monospace;">(const </span><span
    304. 

  304.  style="font-family: Courier New,Courier,monospace;">Segment1</span><span
    305. 

  305.  style="font-family: Courier New,Courier,monospace;">&amp; segment1,</span><br
    306. 

  306.  style="font-family: Courier New,Courier,monospace;" />
    307. 

  307.             <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
    308. 

  308. const </span><span style="font-family: Courier New,Courier,monospace;">Segment</span><span
    309. 

  309.  style="font-family: Courier New,Courier,monospace;">2&amp; segment2,</span>
    310. 

  310.             <span style="font-family: Courier New,Courier,monospace;">bool
    311. 

  311. consider_touch)</span></td>
    312. 

  312.             <td>Returns true if the first object contains the second
    313. 

  313. one, else false. Both objects model segment.<br />
    314. 

  314.             </td>
    315. 

  315.           </tr>
    316. 

  316.           <tr>
    317. 

  317.             <td style="font-family: Courier New,Courier,monospace;">template
    318. 

  318. &lt;typename <span style="font-family: Courier New,Courier,monospace;">Segment</span>&gt;<br />
    319. 

  319. point_type <span style="font-weight: bold;">low</span>(const <span
    320. 

  320.  style="font-family: Courier New,Courier,monospace;">Segment</span>&amp;
    321. 

  321. segment)<br />
    322. 

  322.             </td>
    323. 

  323.             <td>Returns the low endpoint of an object that models
    324. 

  324. segment.<br />
    325. 

  325.             </td>
    326. 

  326.           </tr>
    327. 

  327.           <tr>
    328. 

  328.             <td style="font-family: Courier New,Courier,monospace;">template
    329. 

  329. &lt;typename <span style="font-family: Courier New,Courier,monospace;">Segment</span>&gt;<br />
    330. 

  330. point_type <span style="font-weight: bold;">high</span>(const <span
    331. 

  331.  style="font-family: Courier New,Courier,monospace;">Segment</span>&amp;
    332. 

  332. segment)</td>
    333. 

  333.             <td>Returns the high endpoint of an object that models
    334. 

  334. segment.<br />
    335. 

  335.             </td>
    336. 

  336.           </tr>
    337. 

  337.           <tr>
    338. 

  338.             <td style="font-family: Courier New,Courier,monospace;">template
    339. 

  339. &lt;typename <span style="font-family: Courier New,Courier,monospace;">Segment</span>&gt;<br />
    340. 

  340. point_type <span style="font-weight: bold;">center</span>(const <span
    341. 

  341.  style="font-family: Courier New,Courier,monospace;">Segment</span>&amp;
    342. 

  342. segment)</td>
    343. 

  343.             <td>Returns the central point of an object that models
    344. 

  344. segment.<br />
    345. 

  345.             </td>
    346. 

  346.           </tr>
    347. 

  347.           <tr>
    348. 

  348.             <td style="font-family: Courier New,Courier,monospace;">template
    349. 

  349. &lt;typename <span style="font-family: Courier New,Courier,monospace;">Segment</span>,
    350. 

  350. typename Point&gt;<br />
    351. 

  351. void <span style="font-weight: bold;">low</span>(<span
    352. 

  352.  style="font-family: Courier New,Courier,monospace;">Segment</span>&amp;
    353. 

  353. segment, const Point&amp; point)</td>
    354. 

  354.             <td>Sets the low endpoint of an object that models segment.<br />
    355. 

  355.             </td>
    356. 

  356.           </tr>
    357. 

  357.           <tr>
    358. 

  358.             <td style="font-family: Courier New,Courier,monospace;">template
    359. 

  359. &lt;typename <span style="font-family: Courier New,Courier,monospace;">Segment,
    360. 

  360. typename Point</span>&gt;<br />
    361. 

  361. void <span style="font-weight: bold;">high</span>(<span
    362. 

  362.  style="font-family: Courier New,Courier,monospace;">Segment</span>&amp;
    363. 

  363. segment, const Point&amp; point)</td>
    364. 

  364.             <td>Sets the high endpoint of an object that models of
    365. 

  365. segment.<br />
    366. 

  366.             </td>
    367. 

  367.           </tr>
    368. 

  368.           <tr>
    369. 

  369.             <td><span
    370. 

  370.  style="font-family: Courier New,Courier,monospace;">template
    371. 

  371. &lt;typename </span><span
    372. 

  372.  style="font-family: Courier New,Courier,monospace;">Segment</span><span
    373. 

  373.  style="font-family: Courier New,Courier,monospace;">&gt;</span><br
    374. 

  374.  style="font-family: Courier New,Courier,monospace;" />
    375. 

  375.             <span style="font-family: Courier New,Courier,monospace;">distance_type
    376. 

  376.             <span style="font-weight: bold;">length</span>(const </span><span
    377. 

  377.  style="font-family: Courier New,Courier,monospace;">Segment</span><span
    378. 

  378.  style="font-family: Courier New,Courier,monospace;">&amp; segment)</span><br />
    379. 

  379.             </td>
    380. 

  380.             <td>Returns length of an object that models segment.<br />
    381. 

  381.             </td>
    382. 

  382.           </tr>
    383. 

  383.           <tr>
    384. 

  384.             <td width="586"><font face="Courier New">template
    385. 

  385. &lt;typename </font><span
    386. 

  386.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    387. 

  387.  face="Courier New">&gt;<br />
    388. 

  388.             </font><span
    389. 

  389.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    390. 

  390.  face="Courier New">&amp; <b>scale_up</b>(</font><span
    391. 

  391.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    392. 

  392.  face="Courier New">&amp; </font><font face="Courier New">segment</font><font
    393. 

  393.  face="Courier New">, <br />
    394. 

  394. &nbsp;&nbsp;&nbsp; unsigned_area_type factor)</font></td>
    395. 

  395.             <td>Multiplies x and y coordinates of both endpoints of an
    396. 

  396. object that models segment by unsigned factor.</td>
    397. 

  397.           </tr>
    398. 

  398.           <tr>
    399. 

  399.             <td width="586"><font face="Courier New">template
    400. 

  400. &lt;typename </font><span
    401. 

  401.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    402. 

  402.  face="Courier New">&gt;<br />
    403. 

  403.             </font><span
    404. 

  404.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    405. 

  405.  face="Courier New">&amp; <b>scale_down</b>(</font><span
    406. 

  406.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    407. 

  407.  face="Courier New">&amp; </font><font face="Courier New">segment</font><font
    408. 

  408.  face="Courier New">, <br />
    409. 

  409. &nbsp;&nbsp;&nbsp; unsigned_area_type factor)</font></td>
    410. 

  410.             <td>Divides x and y coordinates of both endpoints of an
    411. 

  411. object that models segment by unsigned factor.</td>
    412. 

  412.           </tr>
    413. 

  413.           <tr>
    414. 

  414.             <td width="586"><font face="Courier New">template
    415. 

  415. &lt;typename </font><span
    416. 

  416.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    417. 

  417.  face="Courier New">, typename Scale&gt;<br />
    418. 

  418.             </font><span
    419. 

  419.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    420. 

  420.  face="Courier New">&amp; <b>scale</b>(</font><span
    421. 

  421.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    422. 

  422.  face="Courier New">&amp; </font><font face="Courier New">segment</font><font
    423. 

  423.  face="Courier New">, const Scale&amp; sc) </font></td>
    424. 

  424.             <td>Calls
    425. 

  425. the scale member function of the scaling type on the low and high
    426. 

  426. endpoint of
    427. 

  427. an object that models segment and updates the segment with the
    428. 

  428. scaled endpoints.</td>
    429. 

  429.           </tr>
    430. 

  430.           <tr>
    431. 

  431.             <td width="586"><font face="Courier New">template
    432. 

  432. &lt;typename </font><span
    433. 

  433.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    434. 

  434.  face="Courier New">, typename Transform&gt;<br />
    435. 

  435.             </font><span
    436. 

  436.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    437. 

  437.  face="Courier New">&amp; <b>transform</b>(</font><span
    438. 

  438.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    439. 

  439.  face="Courier New">&amp; segment, const </font><font
    440. 

  440.  face="Courier New">Transform</font><font face="Courier New">&amp; tr) </font></td>
    441. 

  441.             <td>Calls the transform member function of transform type
    442. 

  442. on the low and high endpoints of an object that models segment and
    443. 

  443. updates the segment with the transformed endpoints.</td>
    444. 

  444.           </tr>
    445. 

  445.           <tr>
    446. 

  446.             <td width="586"><font face="Courier New">template
    447. 

  447. &lt;typename </font><span
    448. 

  448.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    449. 

  449.  face="Courier New">&gt;<br />
    450. 

  450.             </font><span
    451. 

  451.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    452. 

  452.  face="Courier New">&amp; <b>move</b>(</font><span
    453. 

  453.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    454. 

  454.  face="Courier New">&amp; segment, orientation_2d<br />
    455. 

  455. &nbsp;&nbsp;&nbsp; coordinate_difference displacement)</font></td>
    456. 

  456.             <td>Adds displacement value to the x or y coordinates of
    457. 

  457. both endpoints of an object
    458. 

  458. that models segment indicated by the orientation_2d.</td>
    459. 

  459.           </tr>
    460. 

  460.           <tr>
    461. 

  461.             <td width="586"><font face="Courier New">template
    462. 

  462. &lt;</font><span style="font-family: Courier New,Courier,monospace;">Segment,
    463. 

  463. Point</span><font face="Courier New">&gt;<br />
    464. 

  464.             </font><span
    465. 

  465.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    466. 

  466.  face="Courier New">&amp; <b>convolve</b>(</font><span
    467. 

  467.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    468. 

  468.  face="Courier New">&amp; segment, const Point&amp; point)</font></td>
    469. 

  469.             <td>Convolves both endpoints of an object that models
    470. 

  470. segment with an object that models a point.<br />
    471. 

  471.             </td>
    472. 

  472.           </tr>
    473. 

  473.           <tr>
    474. 

  474.             <td width="586"><font face="Courier New">template
    475. 

  475. &lt;</font><span style="font-family: Courier New,Courier,monospace;">Segment,
    476. 

  476. Point</span><font face="Courier New">&gt;<br />
    477. 

  477.             </font><span
    478. 

  478.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    479. 

  479.  face="Courier New">&amp; <b>deconvolve</b>(</font><span
    480. 

  480.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    481. 

  481.  face="Courier New">&amp; segment, const Point&amp; point)</font></td>
    482. 

  482.             <td>Deconvolves both endpoints of an object that models
    483. 

  483. segment with an object that models a point. </td>
    484. 

  484.           </tr>
    485. 

  485.           <tr>
    486. 

  486.             <td style="font-family: Courier New,Courier,monospace;">template
    487. 

  487. &lt;typename Segment1, typename Segment2&gt;<br />
    488. 

  488. bool <span style="font-weight: bold;">abuts</span>(const Segment1&amp;
    489. 

  489. segment1,<br />
    490. 

  490. &nbsp;&nbsp;&nbsp; const Segment2&amp; segment2, direction_1d dir)</td>
    491. 

  491.             <td>Returns true if two objects that model segment abut,
    492. 

  492. depending on the direction_1d value.</td>
    493. 

  493.           </tr>
    494. 

  494.           <tr>
    495. 

  495.             <td style="font-family: Courier New,Courier,monospace;">template
    496. 

  496. &lt;typename Segment1, typename Segment2&gt;<br />
    497. 

  497. bool <span style="font-weight: bold;">abuts</span>(const Segment1&amp;
    498. 

  498. segment1,<br />
    499. 

  499. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; const
    500. 

  500. Segment2&amp; segment2)</td>
    501. 

  501.             <td>Returns true if two objects that model segment abut:
    502. 

  502. either the first one to the second one or vice versa.</td>
    503. 

  503.           </tr>
    504. 

  504.           <tr>
    505. 

  505.             <td><span
    506. 

  506.  style="font-family: Courier New,Courier,monospace;">template
    507. 

  507. &lt;typename Segment1, typename Segment2&gt;</span><br
    508. 

  508.  style="font-family: Courier New,Courier,monospace;" />
    509. 

  509.             <span style="font-family: Courier New,Courier,monospace;">bool
    510. 

  510.             <span style="font-weight: bold;">intersects</span>(const
    511. 

  511. Segment1&amp; segment1,</span><br
    512. 

  512.  style="font-family: Courier New,Courier,monospace;" />
    513. 

  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. 

  514. const Segment2&amp; segment2,<br />
    515. 

  515. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
    516. 

  516. bool consider_touch)</span><br />
    517. 

  517.             </td>
    518. 

  518.             <td>Returns true if two objects that model segment
    519. 

  519. intersect, else false.<br />
    520. 

  520.             </td>
    521. 

  521.           </tr>
    522. 

  522.           <tr>
    523. 

  523.             <td style="font-family: Courier New,Courier,monospace;"><font
    524. 

  524.  face="Courier New">template
    525. 

  525. &lt;typename </font><span
    526. 

  526.  style="font-family: Courier New,Courier,monospace;">Segment, typename
    527. 

  527. Point</span><font face="Courier New">&gt;<br />
    528. 

  528. distance_type <b>euclidean_distance</b>(<br />
    529. 

  529. &nbsp;&nbsp;&nbsp; const </font><span
    530. 

  530.  style="font-family: Courier New,Courier,monospace;">Segment</span><font
    531. 

  531.  face="Courier New">&amp; segment, const Point&amp; point)</font> </td>
    532. 

  532.             <td>Returns distance from an object that models segment
    533. 

  533. to an object that models point. </td>
    534. 

  534.           </tr>
    535. 

  535.           <tr>
    536. 

  536.             <td style="font-family: Courier New,Courier,monospace;"><font
    537. 

  537.  face="Courier New">template
    538. 

  538. &lt;typename Segment1, typename </font><font face="Courier New">Segment2</font><font
    539. 

  539.  face="Courier New">&gt;<br />
    540. 

  540. distance_type <b>euclidean_distance</b>(<br />
    541. 

  541. &nbsp;&nbsp;&nbsp; const </font><font face="Courier New">Segment1</font><font
    542. 

  542.  face="Courier New">&amp; segment1, const </font><font
    543. 

  543.  face="Courier New">Segment2</font><font face="Courier New">&amp;
    544. 

  544. segment2)</font> </td>
    545. 

  545.             <td>Returns distance between two objects that model
    546. 

  546. segment. </td>
    547. 

  547.           </tr>
    548. 

  548.         </tbody>
    549. 

  549.       </table>
    550. 

  550.       <h1>Segment Data</h1>
    551. 

  551.       <p> </p>
    552. 

  552.       <p>The library provides a model of the segment concept declared <font
    553. 

  553.  face="Courier New">template&lt;typename T&gt; segment_data</font>,
    554. 

  554. where
    555. 

  555. T is the coordinate type.</p>
    556. 

  556.       <p>This data type is used internally when a segment is needed and
    557. 

  557. is available to the library user, who finds it convenient to use a
    558. 

  558. library segment data type instead of providing their own.&nbsp; The
    559. 

  559. data
    560. 

  560. type is implemented to be convenient to use with the library traits.</p>
    561. 

  561.       <h2>Members</h2>
    562. 

  562.       <table style="width: 100%;" id="table2" border="1">
    563. 

  563.         <tbody>
    564. 

  564.           <tr>
    565. 

  565.             <td width="586"><b><font face="Courier New">geometry_type</font></b></td>
    566. 

  566.             <td>segment_concept</td>
    567. 

  567.           </tr>
    568. 

  568.           <tr>
    569. 

  569.             <td width="586"><b><font face="Courier New">coordinate_type</font></b></td>
    570. 

  570.             <td>T</td>
    571. 

  571.           </tr>
    572. 

  572.           <tr>
    573. 

  573.             <td><b><font face="Courier New">point_type</font></b></td>
    574. 

  574.             <td>point_data&lt;T&gt;<br />
    575. 

  575.             </td>
    576. 

  576.           </tr>
    577. 

  577.           <tr>
    578. 

  578.             <td width="586"><font face="Courier New"><b>segment_data</b>()</font></td>
    579. 

  579.             <td>Default constructor.</td>
    580. 

  580.           </tr>
    581. 

  581.           <tr>
    582. 

  582.             <td width="586"><font face="Courier New"><b>segment_data</b>(const
    583. 

  583. point_type&amp; low,<br />
    584. 

  584. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
    585. 

  585. const point_type&amp; high)</font></td>
    586. 

  586.             <td>Constructs a segment from the given endpoints.</td>
    587. 

  587.           </tr>
    588. 

  588.           <tr>
    589. 

  589.             <td width="586"><font face="Courier New"><b>segment_data</b>(const
    590. 

  590. segment_data&amp; that)</font></td>
    591. 

  591.             <td>Copy constructor.</td>
    592. 

  592.           </tr>
    593. 

  593.           <tr>
    594. 

  594.             <td width="586"><font face="Courier New">segment_data&amp; <b>operator=</b>(const
    595. 

  595. segment_data&amp; that)</font></td>
    596. 

  596.             <td>Assignment operator.</td>
    597. 

  597.           </tr>
    598. 

  598.           <tr>
    599. 

  599.             <td width="586"><font face="Courier New">template
    600. 

  600. &lt;typename SegmentType&gt;<b><br />
    601. 

  601.             </b>segment_data&amp; <b>operator=</b>(const </font><font
    602. 

  602.  face="Courier New">SegmentType</font><font face="Courier New">&amp;
    603. 

  603. that)
    604. 

  604. const</font></td>
    605. 

  605.             <td>Assign from an object that is a model of segment.</td>
    606. 

  606.           </tr>
    607. 

  607.           <tr>
    608. 

  608.             <td width="586"><font face="Courier New">bool<b> operator==</b>(const
    609. 

  609. segment_data&amp; that) const</font></td>
    610. 

  610.             <td>Equality operator overload.</td>
    611. 

  611.           </tr>
    612. 

  612.           <tr>
    613. 

  613.             <td width="586"><font face="Courier New"><b> </b>bool<b>
    614. 

  614. operator!=</b>(const segment_data&amp; that) const</font></td>
    615. 

  615.             <td>Inequality operator overload.</td>
    616. 

  616.           </tr>
    617. 

  617.           <tr>
    618. 

  618.             <td width="586"><font face="Courier New"><b> </b>bool<b>
    619. 

  619. operator&lt;</b>(const segment_data&amp; that) const</font></td>
    620. 

  620.             <td>Less operator overload. Compares low endpoints then
    621. 

  621. high endpoints to break ties.<br />
    622. 

  622.             </td>
    623. 

  623.           </tr>
    624. 

  624.           <tr>
    625. 

  625.             <td width="586"><font face="Courier New"><b> </b>bool<b>
    626. 

  626. operator&lt;=</b>(const segment_data&amp; that) const</font></td>
    627. 

  627.             <td>Less or equal operator overload. Compares low endpoints
    628. 

  628. then high endpoints to break ties.<br />
    629. 

  629.             </td>
    630. 

  630.           </tr>
    631. 

  631.           <tr>
    632. 

  632.             <td width="586"><font face="Courier New"><b> </b>bool<b>
    633. 

  633. operator&gt;</b>(const segment_data&amp; that) const</font></td>
    634. 

  634.             <td>Greater operator overload. Compares low endpoints then
    635. 

  635. high endpoints to break ties.<br />
    636. 

  636.             </td>
    637. 

  637.           </tr>
    638. 

  638.           <tr>
    639. 

  639.             <td width="586"><font face="Courier New"><b> </b>bool<b>
    640. 

  640. operator&gt;=</b>(const segment_data&amp; that) const</font></td>
    641. 

  641.             <td>Greater or equal operator overload. Compares low
    642. 

  642. endpoints then high endpoints to break ties.<br />
    643. 

  643.             </td>
    644. 

  644.           </tr>
    645. 

  645.           <tr>
    646. 

  646.             <td width="586"><font face="Courier New">point_type <b>get</b>(direction_1d
    647. 

  647. dir) const</font></td>
    648. 

  648.             <td>Retrieves the low/high endpoint considering direction
    649. 

  649. value.</td>
    650. 

  650.           </tr>
    651. 

  651.           <tr>
    652. 

  652.             <td width="586"><font face="Courier New">point_type <span
    653. 

  653.  style="font-weight: bold;">low</span>() const</font></td>
    654. 

  654.             <td>Retrieves the low endpoint.</td>
    655. 

  655.           </tr>
    656. 

  656.           <tr>
    657. 

  657.             <td width="586"><font face="Courier New">point_type <span
    658. 

  658.  style="font-weight: bold;">high</span>() const</font></td>
    659. 

  659.             <td>Retrieves the high endpoint.</td>
    660. 

  660.           </tr>
    661. 

  661.           <tr>
    662. 

  662.             <td width="586"><font face="Courier New">void <b>set</b></font><font
    663. 

  663.  face="Courier New">(direction_1d dir</font><font face="Courier New">,
    664. 

  664. const point_type&amp; point)</font></td>
    665. 

  665.             <td>Sets the endpoint in the given direction.</td>
    666. 

  666.           </tr>
    667. 

  667.           <tr>
    668. 

  668.             <td width="586"><font face="Courier New">segment_data&amp; <span
    669. 

  669.  style="font-weight: bold;">low</span>(const point_type&amp; point)</font></td>
    670. 

  670.             <td>Sets the low endpoint.</td>
    671. 

  671.           </tr>
    672. 

  672.           <tr>
    673. 

  673.             <td width="586"><font face="Courier New">segment_data&amp; <span
    674. 

  674.  style="font-weight: bold;">high(</span>const point_type&amp; point)</font></td>
    675. 

  675.             <td>Sets the high endpoint.</td>
    676. 

  676.           </tr>
    677. 

  677.         </tbody>
    678. 

  678.       </table>
    679. 

  679.       <h1>Segment Utils</h1>
    680. 

  680.       <p> </p>
    681. 

  681.       <p>The library provides several algorithms for the manipulation
    682. 

  682. of sets of segment data. In particular, the generalize line segment
    683. 

  683. intersection algorithm used for polygon set operations is exposed
    684. 

  684. through several interfaces to allow it to be used with any collection
    685. 

  685. or sequence of objects that model the <font face="Courier New">segment_concept</font>.
    686. 

  686.       </p>
    687. 

  687.       <h2>Functions</h2>
    688. 

  688.       <table style="width: 100%;" id="table3" border="1">
    689. 

  689.         <tbody>
    690. 

  690.           <tr>
    691. 

  691.             <td width="586"><font face="Courier New">template
    692. 

  692. &lt;</font><font face="Courier New">typename SegmentContainer</font><font
    693. 

  693.  face="Courier New">,</font><font face="Courier New"><br />
    694. 

  694. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; typename
    695. 

  695. SegmentIterator</font><font face="Courier New">&gt;<b><br />
    696. 

  696.             </b>void <b>intersect_segments</b>(<br />
    697. 

  697. &nbsp;&nbsp;&nbsp; </font><font face="Courier New">SegmentContainer*
    698. 

  698. result,</font><br />
    699. 

  699.             <font face="Courier New">&nbsp;&nbsp;&nbsp; SegmentIterator
    700. 

  700. first,<br />
    701. 

  701. &nbsp;&nbsp;&nbsp; SegmentIterator last) </font></td>
    702. 

  702.             <td>Accumulates
    703. 

  703. the result of splitting the segments in the iterator range at their
    704. 

  704. intersection points into the result container. Preconditions: segment
    705. 

  705. type used by all the input structures should model segment
    706. 

  706. concept.Postconditions: no segments intersect except at their end
    707. 

  707. points. Useful to satisfy the precondition of voronoi diagram
    708. 

  708. construction. Expected n log n runtime, worst case quadratic runtime
    709. 

  709. wrt. vertices + intersections. </td>
    710. 

  710.           </tr>
    711. 

  711.           <tr>
    712. 

  712.             <td width="586"><font face="Courier New">template
    713. 

  713. &lt;</font><font face="Courier New">typename Segment,</font><font
    714. 

  714.  face="Courier New"><br />
    715. 

  715. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </font><font
    716. 

  716.  face="Courier New">typename SegmentIterator</font><font
    717. 

  717.  face="Courier New">&gt;<b><br />
    718. 

  718.             </b>void <b>intersect_segments</b>(<br />
    719. 

  719. &nbsp;&nbsp;&nbsp; </font><font face="Courier New">vector&lt;pair&lt;size_t,
    720. 

  720. Segment&gt;* result,</font><br />
    721. 

  721.             <font face="Courier New">&nbsp;&nbsp;&nbsp; SegmentIterator
    722. 

  722. first,<br />
    723. 

  723. &nbsp;&nbsp;&nbsp; SegmentIterator last)</font></td>
    724. 

  724.             <td>Accumulates
    725. 

  725. the result of splitting the segments in the iterator range at their
    726. 

  726. intersection points into the result container. Preconditions: segment
    727. 

  727. type used by all the input structures should model segment concept.
    728. 

  728. Postconditions: no segments intersect except at their end points. The
    729. 

  729. index of the input segment is paired with each resultant segment that
    730. 

  730. was split to produce it to associate the result segments with the
    731. 

  731. inputs segments. Expected n log n runtime, worst case quadratic runtime
    732. 

  732. wrt. vertices + intersections. </td>
    733. 

  733.           </tr>
    734. 

  734.           <tr>
    735. 

  735.             <td width="586"><font face="Courier New">template
    736. 

  736. &lt;</font><font face="Courier New">typename Rectangle,<br />
    737. 

  737. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </font><font
    738. 

  738.  face="Courier New">typename </font><font face="Courier New">SegmentIterator</font><font
    739. 

  739.  face="Courier New">&gt;<b><br />
    740. 

  740.             </b>void <span style="font-weight: bold;">envelope_segments</span>(<br />
    741. 

  741. &nbsp;&nbsp;&nbsp; </font><font face="Courier New">Rectangle* rect,</font><br />
    742. 

  742.             <font face="Courier New">&nbsp;&nbsp;&nbsp; </font><font
    743. 

  743.  face="Courier New">SegmentIterator first,<br />
    744. 

  744. &nbsp; &nbsp; SegmentIterator last</font><font face="Courier New">) </font></td>
    745. 

  745.             <td>Computes
    746. 

  746. the bounding rectangle of the iterator range of line segments.
    747. 

  747. Preconditions: segment type and rectangle type used by the input
    748. 

  748. structures should model segment concept and rectangle concept
    749. 

  749. respectively. Linear runtime. </td>
    750. 

  750.           </tr>
    751. 

  751.         </tbody>
    752. 

  752.       </table>
    753. 

  753.       </td>
    754. 

  754.     </tr>
    755. 

  755.     <tr>
    756. 

  756.       <td style="background-color: rgb(238, 238, 238);" nowrap="1"
    757. 

  757.  valign="top"> &nbsp;</td>
    758. 

  758.       <td
    759. 

  759.  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
    760. 

  760.  valign="top" width="100%">
    761. 

  761.       <table class="docinfo" id="table4" frame="void" rules="none">
    762. 

  762.         <colgroup> <col class="docinfo-name" /><col
    763. 

  763.  class="docinfo-content" /> </colgroup> <tbody valign="top">
    764. 

  764.           <tr>
    765. 

  765.             <th class="docinfo-name">Copyright:</th>
    766. 

  766.             <td>Copyright © Intel Corporation 2008-2010.</td>
    767. 

  767.           </tr>
    768. 

  768.           <tr class="field">
    769. 

  769.             <th class="docinfo-name">License:</th>
    770. 

  770.             <td class="field-body">Distributed under the Boost Software
    771. 

  771. License, Version 1.0. (See accompanying file <tt class="literal"> <span
    772. 

  772.  class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
    773. 

  773.  class="reference" target="_top"
    774. 

  774.  href="http://www.boost.org/LICENSE_1_0.txt">
    775. 

  775. http://www.boost.org/LICENSE_1_0.txt</a>)</td>
    776. 

  776.           </tr>
    777. 

  777.         </tbody>
    778. 

  778.       </table>
    779. 

  779.       </td>
    780. 

  780.     </tr>
    781. 

  781.   </tbody>
    782. 

  782. </table>
    783. 

  783. </body>
    784. 

  784. </html>
    785.