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

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2 <html>
   3 <head>
   4   <meta http-equiv="Content-Language" content="en-us">
   5   <meta http-equiv="Content-Type"
   6  content="text/html; charset=windows-1252">
   7   <title>Voronoi Diagram</title>
   8   <meta http-equiv="content-type" content="text/html; charset=utf-8">
   9   <meta http-equiv="content-type" content="text/html; charset=utf-8">
  10 </head>
  11 <body>
  12 <table style="margin: 0pt; padding: 0pt; width: 100%;" border="0"
  13  cellpadding="0" cellspacing="0">
  14   <tbody>
  15     <tr>
  16       <td style="background-color: rgb(238, 238, 238);" nowrap="1"
  17  valign="top">
  18       <div style="padding: 5px;" align="center"> <img
  19  src="images/boost.png" border="0" height="86" width="277"><a
  20  title="www.boost.org home page" tabindex="2"
  21  style="border: medium none ;" href="http://www.boost.org/"> </a></div>
  22       <div style="margin: 5px;">
  23       <h3 class="navbar">Contents</h3>
  24       <ul>
  25         <li><a href="index.htm">Boost.Polygon Main Page</a></li>
  26         <li><a href="gtl_design_overview.htm">Design Overview</a></li>
  27         <li><a href="gtl_isotropy.htm">Isotropy</a></li>
  28         <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
  29         <li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
  30         <li><a href="gtl_point_concept.htm">Point Concept</a></li>
  31         <li><a href="gtl_segment_concept.htm">Segment Concept</a></li>
  32         <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
  33         <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
  34         <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
  35 With Holes Concept</a></li>
  36         <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
  37         <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
  38 With Holes Concept</a></li>
  39         <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
  40         <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
  41 Holes Concept</a></li>
  42         <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
  43 Concept</a></li>
  44         <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
  45 Concept</a></li>
  46         <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
  47         <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
  48 Extraction 90</a></li>
  49         <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
  50 Extraction 45</a></li>
  51         <li><a href="gtl_connectivity_extraction.htm">Connectivity
  52 Extraction</a></li>
  53         <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
  54         <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
  55         <li><a href="gtl_property_merge.htm">Property Merge</a></li>
  56         <li><a href="voronoi_main.htm">Voronoi Main Page </a></li>
  57         <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a></li>
  58         <li><a href="voronoi_builder.htm">Voronoi Builder</a> </li>
  59         <li>Voronoi Diagram</li>
  60       </ul>
  61       <h3 class="navbar">Other Resources</h3>
  62       <ul>
  63         <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
  64         <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
  65 Presentation</a></li>
  66         <li><a href="analysis.htm">Performance Analysis</a></li>
  67         <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
  68         <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
  69         <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
  70         <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
  71 Tutorial</a></li>
  72       </ul>
  73       </div>
  74       <h3 class="navbar">Polygon Sponsor</h3>
  75       <div style="padding: 5px;" align="center"> <img
  76  src="images/intlogo.gif" border="0" height="51" width="127"><a
  77  title="www.adobe.com home page" tabindex="2"
  78  style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
  79       </td>
  80       <td
  81  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
  82  valign="top" width="100%"><!-- End Header --> <br>
  83       <h1>Voronoi Diagram</h1>
  84 A Voronoi
  85 diagram is the computational geometry concept that represents partition
  86 of the given space onto regions, with bounds determined by distances to
  87 a
  88 specified family of objects. The application area of this concept
  89 varies <a
  90  href="http://www.ics.uci.edu/%7Eeppstein/gina/scot.drysdale.html">from
  91 Archaeology to Zoology</a>. The Boost.Polygon Voronoi extension
  92 provides
  93 implementation of
  94 the Voronoi diagram data structure in the 2D space. The internal
  95 representation
  96 consists of the three arrays, that respectively contain: Voronoi cells
  97 (represent the area around the input sites bounded by the Voronoi
  98 edges), Voronoi vertices
  99 (points where three or more Voronoi edges intersect), Voronoi edges
 100 (one dimensional curves containing points equidistant from the two
 101 closest input sites). Each of the primitives (cell, vertex, edge)
 102 contains pointers to the other linked primitives, so that it's always
 103 possible to efficiently traverse the Voronoi graph. The picture below
 104 shows
 105 the Voronoi vertices in red, Voronoi edges in black, input sites that
 106 correspond to the Voronoi cells in blue. It is considered, that each
 107 input segment consists of the three sites: segment itself and its
 108 endpoints. As the result, two additional Voronoi edges are constructed
 109 per each input segment. This is made to
 110 simplify the representation of the Voronoi diagram and Voronoi edges in
 111 particular.<br>
 112       <br>
 113       <img src="images/voronoi2.png" alt=""
 114  style="width: 600px; height: 600px;"><br>
 115       <h2>Important</h2>
 116 All
 117 the Voronoi primitive data structures (edge, vertex, cell) contain
 118 mutable color member. Color type is equivalent to the std::size_t type,
 119 except that the upper five bits are reserved for the internal usage.
 120 That means, that the maximum supported value by the color member is 32
 121 times less than the one supported by std::size_t.<br>
 122       <h2>Declaration</h2>
 123 Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
 124       <br>
 125       <span style="font-family: Courier New,Courier,monospace;">template
 126 &lt;typename T, typename TRAITS = voronoi_diagram_traits&lt;T&gt; &gt;</span><br
 127  style="font-family: Courier New,Courier,monospace;">
 128       <span style="font-family: Courier New,Courier,monospace;">class
 129 voronoi_diagram;<br>
 130       </span><font face="Courier New"><span
 131  style="font-family: 'Courier New',Courier,monospace;"><br>
 132 T</span></font>
 133 - the coordinate type of the Voronoi vertices.<br>
 134       <span style="font-family: Courier New,Courier,monospace;">TRAITS</span><font
 135  face="Courier New"><span
 136  style="font-family: 'Courier New',Courier,monospace;"></span></font>
 137 - the Voronoi diagram traits.<br>
 138       <h2>Member Functions</h2>
 139       <span style="font-family: Courier New,Courier,monospace;"> </span>
 140       <table style="text-align: left; width: 100%;" border="1"
 141  cellpadding="2" cellspacing="2">
 142         <tbody>
 143           <tr>
 144             <td style="font-family: Courier New,Courier,monospace;"><span
 145  style="font-weight: bold;">voronoi_diagram</span>() </td>
 146             <td>Default constructor. </td>
 147           </tr>
 148           <tr>
 149             <td style="font-family: Courier New,Courier,monospace;">void
 150             <span style="font-weight: bold;">clear</span>() </td>
 151             <td>Removes all primitives from the Voronoi diagram. </td>
 152           </tr>
 153           <tr>
 154             <td style="font-family: Courier New,Courier,monospace;">const
 155 cell_container_type&amp; <span style="font-weight: bold;">cells</span>()
 156 const </td>
 157             <td>Returns the const
 158 reference to the cell container. </td>
 159           </tr>
 160           <tr>
 161             <td style="font-family: Courier New,Courier,monospace;">const
 162 vertex_container_type&amp; <span style="font-weight: bold;">vertices</span>()
 163 const </td>
 164             <td>Returns the const
 165 reference to the vertex container. </td>
 166           </tr>
 167           <tr>
 168             <td style="font-family: Courier New,Courier,monospace;">const
 169 edge_container_type&amp; <span style="font-weight: bold;">edges</span>()
 170 const </td>
 171             <td>Returns the const
 172 reference to the edge container. </td>
 173           </tr>
 174           <tr>
 175             <td style="font-family: Courier New,Courier,monospace;">size_t
 176             <span style="font-weight: bold;">num_cells</span>() const </td>
 177             <td>Returns the number of the Voronoi
 178 cells in the Voronoi diagram. </td>
 179           </tr>
 180           <tr>
 181             <td style="font-family: Courier New,Courier,monospace;">size_t
 182             <span style="font-weight: bold;">num_edges</span>() const </td>
 183             <td>Returns the number of the
 184 Voronoi edges (half-edges) in the Voronoi diagram. </td>
 185           </tr>
 186           <tr>
 187             <td style="font-family: Courier New,Courier,monospace;">size_t
 188             <span style="font-weight: bold;">num_vertices</span>()
 189 const </td>
 190             <td>Returns the number of the
 191 Voronoi vertices in the Voronoi diagram. </td>
 192           </tr>
 193         </tbody>
 194       </table>
 195       <h2>Member Types</h2>
 196       <table style="text-align: left; width: 100%;" border="1"
 197  cellpadding="2" cellspacing="2">
 198         <tbody>
 199           <tr>
 200             <td style="font-weight: bold;">coordinate_type </td>
 201             <td>Coordinate type. </td>
 202           </tr>
 203           <tr>
 204             <td style="font-weight: bold;">cell_type </td>
 205             <td>Voronoi cell. </td>
 206           </tr>
 207           <tr>
 208             <td style="font-weight: bold;">vertex_type </td>
 209             <td>Voronoi vertex. </td>
 210           </tr>
 211           <tr>
 212             <td style="font-weight: bold;">edge_type </td>
 213             <td>Voronoi edge. </td>
 214           </tr>
 215           <tr>
 216             <td style="font-weight: bold;">cell_container_type </td>
 217             <td>Container of the Voronoi cells. </td>
 218           </tr>
 219           <tr>
 220             <td style="font-weight: bold;">const_cell_iterator </td>
 221             <td>Const cell container iterator. </td>
 222           </tr>
 223           <tr>
 224             <td style="font-weight: bold;">vertex_container_type </td>
 225             <td>Container of the Voronoi vertices. </td>
 226           </tr>
 227           <tr>
 228             <td style="font-weight: bold;">const_vertex_iterator </td>
 229             <td>Const vertex container iterator. </td>
 230           </tr>
 231           <tr>
 232             <td style="font-weight: bold;">edge_container_type </td>
 233             <td>Container of the Voronoi edges. </td>
 234           </tr>
 235           <tr>
 236             <td style="font-weight: bold;">const_edge_iterator </td>
 237             <td>Const edge container iterator. </td>
 238           </tr>
 239         </tbody>
 240       </table>
 241       <h1>Voronoi Geometry Type</h1>
 242 The Voronoi
 243 diagram data structure doesn't embed coordinates of the input
 244 geometries.
 245 Instead it links with those via source index and source category
 246 methods
 247 of the Voronoi cell primitive. Source index is incrementally given
 248 (starting from zero) to each input site inserted into the <a
 249  href="voronoi_builder.htm">Voronoi
 250 builder</a>.
 251 Considering the fact, that each input segment is splitted onto three
 252 separate sites with the same index, we distinguish between those using
 253 source category. For more examples check the <a
 254  href="voronoi_basic_tutorial.htm">Voronoi basic tutorial</a>.<br>
 255       <h2>GeometryCategory </h2>
 256 Defines geometric category of the input object.<br>
 257 Header: <a href="../../../boost/polygon/voronoi_geometry_type.hpp">boost/polygon/</a><a
 258  href="../../../boost/polygon/voronoi_geometry_type.hpp">voronoi_geometry_type.hpp</a><br>
 259       <br>
 260       <span style="font-family: Courier New,Courier,monospace;">enum
 261 GeometryCategory {</span><br
 262  style="font-family: Courier New,Courier,monospace;">
 263       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 264 GEOMETRY_CATEGORY_POINT = 0x0,</span><br
 265  style="font-family: Courier New,Courier,monospace;">
 266       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 267 GEOMETRY_CATEGORY_SEGMENT = 0x1</span><br
 268  style="font-family: Courier New,Courier,monospace;">
 269       <span style="font-family: Courier New,Courier,monospace;">};</span><br>
 270       <h2>SourceCategory</h2>
 271 Defines semantic category of the input site.<br>
 272 Header: <a href="../../../boost/polygon/voronoi_geometry_type.hpp">boost/polygon/</a><a
 273  href="../../../boost/polygon/voronoi_geometry_type.hpp">voronoi_geometry_type.hpp</a><br>
 274       <br>
 275       <span style="font-family: Courier New,Courier,monospace;">enum
 276 SourceCategory {</span><br
 277  style="font-family: Courier New,Courier,monospace;">
 278       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 279 // Point subtypes.</span><br
 280  style="font-family: Courier New,Courier,monospace;">
 281       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 282 SOURCE_CATEGORY_SINGLE_POINT = 0x0,</span><br
 283  style="font-family: Courier New,Courier,monospace;">
 284       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 285 SOURCE_CATEGORY_SEGMENT_START_POINT = 0x1,</span><br
 286  style="font-family: Courier New,Courier,monospace;">
 287       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 288 SOURCE_CATEGORY_SEGMENT_END_POINT = 0x2,</span><br
 289  style="font-family: Courier New,Courier,monospace;">
 290       <br style="font-family: Courier New,Courier,monospace;">
 291       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 292 // Segment subtypes.</span><br
 293  style="font-family: Courier New,Courier,monospace;">
 294       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 295 SOURCE_CATEGORY_INITIAL_SEGMENT = 0x8,</span><br
 296  style="font-family: Courier New,Courier,monospace;">
 297       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 298 SOURCE_CATEGORY_REVERSE_SEGMENT = 0x9,</span><br
 299  style="font-family: Courier New,Courier,monospace;">
 300       <br style="font-family: Courier New,Courier,monospace;">
 301       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 302 SOURCE_CATEGORY_GEOMETRY_SHIFT = 0x3,</span><br
 303  style="font-family: Courier New,Courier,monospace;">
 304       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 305 SOURCE_CATEGORY_BITMASK = 0x1F</span><br
 306  style="font-family: Courier New,Courier,monospace;">
 307       <span style="font-family: Courier New,Courier,monospace;">};</span><br>
 308       <h2>Member Functions</h2>
 309       <table style="text-align: left; width: 100%;" border="1"
 310  cellpadding="2" cellspacing="2">
 311         <tbody>
 312           <tr>
 313             <td style="vertical-align: top;"><span
 314  style="font-family: Courier New,Courier,monospace;">bool <span
 315  style="font-weight: bold;">belongs</span>(</span><br
 316  style="font-family: Courier New,Courier,monospace;">
 317             <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 318 &nbsp; SourceCategory source_category,</span><br
 319  style="font-family: Courier New,Courier,monospace;">
 320             <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
 321 GeometryCategory geometry_category)</span> </td>
 322             <td style="vertical-align: middle;">Returns true if the
 323 given source
 324 category belongs to the given geometry category.<br>
 325 Returns false otherwise. </td>
 326           </tr>
 327         </tbody>
 328       </table>
 329       <h1>Voronoi Edge</h1>
 330 A Voronoi edge is a one-dimenstion curve, that contains points
 331 equidistant from the two closest input geometries. The Voronoi edge
 332 data structure is implemented as the enhanced classical <a
 333  href="http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml">half-edge</a>
 334 data structure. On the image below, the Voronoi edges are drawn as
 335 directed linear (e.g. AE) or curved (e.g. DE) dashed lines of either
 336 green (e.g. AE) or black (e.g DE) color. The green edges are considered
 337 to be secondary, as they are generated by an input segment and its
 338 endpoint (e.g. edge EA, made by segment MN and its endpoint M). All the
 339 other edges are considered to be primary (e.g. curved edge CD, made by
 340 segment KL and point N). Apart from that, each edge can be finite (e.g.
 341 ED) or infinite (e.g. edge starting at point B and going in the east
 342 direction).<br>
 343       <img src="images/voronoi1.png" alt=""
 344  style="width: 600px; height: 600px;"><br>
 345 Each Voronoi edge (consider directed edge BA) provides efficient access
 346 to the following primitives:<br>
 347       <ul>
 348         <li>Cell the edge belongs to (Voronoi cell P, with source
 349 segment MN)</li>
 350         <li>Start point of the edge (Voronoi vertex B, that is
 351 equidistant from the following input sites: O, L, MN)</li>
 352         <li>End point of the edge (Voronoi vertex A, that is
 353 equidistant from the following input sites: O, M, MN)</li>
 354         <li>Twin edge (Voronoi edge AB)</li>
 355         <li>CCW next edge inside the Voronoi cell, that the edge
 356 belongs to (green Voronoi edge AE)</li>
 357         <li>CCW previous edge inside the Voronoi cell, that the edge
 358 belongs to (Voronoi edge CB)</li>
 359         <li>CCW rotated next edge around the start point of the edge
 360 (Voronoi edge BC)</li>
 361         <li>CCW rotated previous edge around the start point of the
 362 edge (infinite Voronoi edge starting at the Voronoi vertex B and going
 363 in the east direction) </li>
 364       </ul>
 365       <h2>Declaration</h2>
 366 Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
 367       <br>
 368       <span style="font-family: Courier New,Courier,monospace;">template
 369 &lt;typename T&gt;</span><br
 370  style="font-family: Courier New,Courier,monospace;">
 371       <span style="font-family: Courier New,Courier,monospace;">class
 372 voronoi_edge;<br>
 373       <br>
 374 T</span> - coordinate type.<br>
 375       <h2>Member Functions</h2>
 376       <span style="font-family: Courier New,Courier,monospace;"> </span>
 377       <table style="text-align: left; width: 100%;" border="1"
 378  cellpadding="2" cellspacing="2">
 379         <tbody>
 380           <tr>
 381             <td><span
 382  style="font-family: Courier New,Courier,monospace;"><span
 383  style="font-weight: bold;">voronoi_edge</span>(bool is_linear, bool
 384 is_primary)</span> </td>
 385             <td>Voronoi edge constructor. </td>
 386           </tr>
 387           <tr>
 388             <td style="font-family: Courier New,Courier,monospace;">voronoi_cell_type*
 389             <span style="font-weight: bold;">cell</span>() </td>
 390             <td>Returns the pointer to the
 391 Voronoi <span style="font-family: Courier New,Courier,monospace;"></span>cell
 392 that the edge belongs to. </td>
 393           </tr>
 394           <tr>
 395             <td style="font-family: Courier New,Courier,monospace;">const
 396 voronoi_cell_type* <span style="font-weight: bold;">cell</span>()
 397 const </td>
 398             <td>Returns the const pointer
 399 to the Voronoi cell that the edge belongs to. </td>
 400           </tr>
 401           <tr>
 402             <td style="font-family: Courier New,Courier,monospace;">void
 403             <span style="font-weight: bold;">cell</span>(voronoi_cell_type*
 404 c) </td>
 405             <td>Sets the Voronoi cell
 406 pointer to the cell the current edge belongs to. </td>
 407           </tr>
 408           <tr>
 409             <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type*
 410             <span style="font-weight: bold;">vertex0</span>() </td>
 411             <td>Returns the pointer to the
 412 start point of the edge.<br>
 413 If the edge is infinite in that direction returns NULL. </td>
 414           </tr>
 415           <tr>
 416             <td style="font-family: Courier New,Courier,monospace;">const
 417 voronoi_vertex_type* <span style="font-weight: bold;">vertex0</span>()
 418 const </td>
 419             <td>Returns the const pointer
 420 to the start point vertex of the edge.<br>
 421 If the edge is infinite in that direction returns NULL. </td>
 422           </tr>
 423           <tr>
 424             <td style="font-family: Courier New,Courier,monospace;">void
 425             <span style="font-weight: bold;">vertex0</span>(voronoi_vertex_type*
 426 v) </td>
 427             <td>Sets the start point
 428 pointer of the edge. </td>
 429           </tr>
 430           <tr>
 431             <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type*
 432             <span style="font-weight: bold;">vertex1</span>() </td>
 433             <td>Returns the pointer to the
 434 end point of the edge.<br>
 435 If the edge is infinite in that direction returns NULL. </td>
 436           </tr>
 437           <tr>
 438             <td style="font-family: Courier New,Courier,monospace;">const
 439 voronoi_vertex_type* <span style="font-weight: bold;">vertex1</span>()
 440 const </td>
 441             <td>Returns the const pointer
 442 to the end point of the edge.<br>
 443 If the edge is infinite in that direction returns NULL. </td>
 444           </tr>
 445           <tr>
 446             <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
 447             <span style="font-weight: bold;">twin</span>() </td>
 448             <td>Returns the pointer to the
 449 twin edge. </td>
 450           </tr>
 451           <tr>
 452             <td style="font-family: Courier New,Courier,monospace;">const
 453 voronoi_edge_type* <span style="font-weight: bold;">twin</span>()
 454 const </td>
 455             <td>Returns the const pointer
 456 to the twin edge. </td>
 457           </tr>
 458           <tr>
 459             <td style="font-family: Courier New,Courier,monospace;">void
 460             <span style="font-weight: bold;">twin</span>(voronoi_edge_type*
 461 e) </td>
 462             <td>Sets the twin edge pointer
 463 of the edge. </td>
 464           </tr>
 465           <tr>
 466             <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
 467             <span style="font-weight: bold;">next</span>() </td>
 468             <td>Returns the pointer to the
 469 CCW next edge within the corresponding Voronoi cell.<br>
 470 Edges not necessarily share a common vertex (e.g. infinite edges). </td>
 471           </tr>
 472           <tr>
 473             <td style="font-family: Courier New,Courier,monospace;">const
 474 voronoi_edge_type* <span style="font-weight: bold;">next</span>()
 475 const </td>
 476             <td>Returns the const pointer
 477 to the CCW next edge within the corresponding Voronoi cell.<br>
 478 Edges not necessarily share a common vertex (e.g. infinite edges). </td>
 479           </tr>
 480           <tr>
 481             <td style="font-family: Courier New,Courier,monospace;">void
 482             <span style="font-weight: bold;">next</span>(voronoi_edge_type*
 483 e) </td>
 484             <td>Sets the CCW next edge
 485 pointer of the edge. </td>
 486           </tr>
 487           <tr>
 488             <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
 489             <span style="font-weight: bold;">prev</span>() </td>
 490             <td>Returns the pointer to the
 491 CCW prev edge within the corresponding Voronoi cell.<br>
 492 Edges not necessarily share a common vertex (e.g. infinite edges). </td>
 493           </tr>
 494           <tr>
 495             <td style="font-family: Courier New,Courier,monospace;">const
 496 voronoi_edge_type* <span style="font-weight: bold;">prev</span>()
 497 const </td>
 498             <td>Returns the const pointer
 499 to the CCW prev edge within the corresponding Voronoi cell.<br>
 500 Edges not necessarily share a common vertex (e.g. infinite edges). </td>
 501           </tr>
 502           <tr>
 503             <td style="font-family: Courier New,Courier,monospace;">void
 504             <span style="font-weight: bold;">prev</span>(voronoi_edge_type*
 505 e) </td>
 506             <td>Sets the CCW prev edge
 507 pointer of the edge. </td>
 508           </tr>
 509           <tr>
 510             <td style="font-family: Courier New,Courier,monospace;">color_type
 511             <span style="font-weight: bold;">color</span>() const </td>
 512             <td>Returns the color value. </td>
 513           </tr>
 514           <tr>
 515             <td style="font-family: Courier New,Courier,monospace;">void
 516             <span style="font-weight: bold;">color</span>(color_type
 517 color) const </td>
 518             <td>Sets the color of
 519 the edge.<br>
 520 Allows to associate the user provided data with the primitive. </td>
 521           </tr>
 522           <tr>
 523             <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
 524             <span style="font-weight: bold;">rot_next</span>() </td>
 525             <td>Returns the pointer to the
 526 CCW next edge rotated around the edge start point.<br>
 527 Works for infinite edges as well. </td>
 528           </tr>
 529           <tr>
 530             <td style="font-family: Courier New,Courier,monospace;">const
 531 voronoi_edge_type* <span style="font-weight: bold;">rot_next</span>()
 532 const </td>
 533             <td>Returns the const pointer
 534 to the CCW next edge rotated around the edge start point.<br>
 535 Works for infinite edges as well.</td>
 536           </tr>
 537           <tr>
 538             <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
 539             <span style="font-weight: bold;">rot_prev</span>() </td>
 540             <td>Returns the pointer to the
 541 CCW prev edge rotated around the edge start point.<br>
 542 Works for infinite edges as well. </td>
 543           </tr>
 544           <tr>
 545             <td style="font-family: Courier New,Courier,monospace;">const
 546 voronoi_edge_type* <span style="font-weight: bold;">rot_prev</span>()
 547 const </td>
 548             <td>Returns the const pointer
 549 to the CCW prev edge rotated around the edge start point.<br>
 550 Works for infinite edges as well.</td>
 551           </tr>
 552           <tr>
 553             <td style="font-family: Courier New,Courier,monospace;">bool
 554             <span style="font-weight: bold;">is_finite</span>() const </td>
 555             <td>Returns true if the both
 556 end points of the edge are finite, else false. </td>
 557           </tr>
 558           <tr>
 559             <td style="font-family: Courier New,Courier,monospace;">bool
 560             <span style="font-weight: bold;">is_infinite</span>() const</td>
 561             <td>Returns true if one of the
 562 end points of the edge is infinite, else false.</td>
 563           </tr>
 564           <tr>
 565             <td style="font-family: Courier New,Courier,monospace;">bool
 566             <span style="font-weight: bold;">is_linear</span>() const </td>
 567             <td>Returns true if the edge
 568 is linear (segment, ray, line), else false. </td>
 569           </tr>
 570           <tr>
 571             <td style="font-family: Courier New,Courier,monospace;">bool
 572             <span style="font-weight: bold;">is_curved</span>() const </td>
 573             <td>Returns true if the edge
 574 is curved (parabolic arc), else false. </td>
 575           </tr>
 576           <tr>
 577             <td style="font-family: Courier New,Courier,monospace;">bool
 578             <span style="font-weight: bold;">is_primary</span>() const </td>
 579             <td>Returns false if the edge
 580 goes through the endpoint of the segment site, else true. </td>
 581           </tr>
 582           <tr>
 583             <td style="font-family: Courier New,Courier,monospace;">bool
 584             <span style="font-weight: bold;">is_secondary</span>() const</td>
 585             <td>Returns true if the edge
 586 goes through the endpoint of the segment site, else false.</td>
 587           </tr>
 588         </tbody>
 589       </table>
 590       <span style="font-family: Courier New,Courier,monospace;"> </span>All
 591 the above methods have O(1) complexity. The size of
 592 the Voronoi edge structure is equal to: 5 * sizeof(void *) +
 593 sizeof(size_t).<span style="font-family: Courier New,Courier,monospace;"></span><br>
 594       <h2>Member Types</h2>
 595       <table style="text-align: left; width: 100%;" border="1"
 596  cellpadding="2" cellspacing="2">
 597         <tbody>
 598           <tr>
 599             <td style="font-weight: bold;">coordinate_type </td>
 600             <td>Coordinate type. </td>
 601           </tr>
 602           <tr>
 603             <td style="font-weight: bold;">voronoi_cell_type </td>
 604             <td>Voronoi cell type. </td>
 605           </tr>
 606           <tr>
 607             <td style="font-weight: bold;">voronoi_vertex_type </td>
 608             <td>Voronoi vertex type. </td>
 609           </tr>
 610           <tr>
 611             <td style="font-weight: bold;">voronoi_edge_type </td>
 612             <td>Voronoi edge type. </td>
 613           </tr>
 614           <tr>
 615             <td style="vertical-align: top; font-weight: bold;">color_type
 616             </td>
 617             <td style="vertical-align: top;">Color type (check the
 618 Important section). </td>
 619           </tr>
 620         </tbody>
 621       </table>
 622       <h1>Voronoi Cell</h1>
 623 A Voronoi cell represents a region of the Voronoi diagram bounded by
 624 the Voronoi edges. On the image below, there are 7 such regions: P, Q,
 625 R, S, T, U, V. Each Voronoi cell can contain a point (e.g. cells Q, S,
 626 T, U, V with corresponding input sources N, K, L, O, M respectively) or
 627 a segment
 628 (e.g. cells P and R with corresponding input sources MN and KL
 629 respectively) as its
 630 source. The Voronoi cell primitive doesn't contain coordinates of the
 631 source geometry, instead it stores the index and category of the source
 632 geometry. Source index corresponds to the unique id, issued to each
 633 input geometry (e.g. incremental counter, used by the Voronoi builder).
 634 Such an index uniquely identifies any input point (e.g. O), however
 635 doesn't make any distinction between segment (e.g. MN) and both its end
 636 points (e.g. M, N). In order to resolve possible ambiguity, the source
 637 category is used, that specifies the semantic topology of the input
 638 object (e.g. segment's startpoint, segment's endpoint or segment
 639 itself). The Voronoi cell data structure also provides access to a
 640 random Voronoi edge, located on the boundary of the cell (e.g. edge AE
 641 for
 642 the cell P).<br>
 643       <img style="width: 600px; height: 600px;" alt=""
 644  src="images/voronoi1.png"><br>
 645       <h2>Declaration</h2>
 646 Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
 647       <br>
 648       <span style="font-family: Courier New,Courier,monospace;">template
 649 &lt;typename T&gt;<br>
 650 class voronoi_cell;<br>
 651       <br>
 652       </span><span style="font-family: Courier New,Courier,monospace;">T</span>
 653 - coordinate type.<br>
 654       <h2>Member Functions</h2>
 655       <span style="font-family: Courier New,Courier,monospace;"> </span>
 656       <table style="text-align: left; width: 100%;" border="1"
 657  cellpadding="2" cellspacing="2">
 658         <tbody>
 659           <tr>
 660             <td><span
 661  style="font-family: Courier New,Courier,monospace;"><span
 662  style="font-weight: bold;">voronoi_cell</span>(source_index_type
 663 source_index,</span><span
 664  style="font-family: Courier New,Courier,monospace;"><br>
 665 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 666 source_category_type source_category)</span> </td>
 667             <td>Voronoi cell constructor. </td>
 668           </tr>
 669           <tr>
 670             <td style="font-family: Courier New,Courier,monospace;">source_index_type
 671             <span style="font-weight: bold;">source_index</span>()
 672 const </td>
 673             <td>Returns input site index among the other sites.<br>
 674 Both segment and its end points will have the same index. </td>
 675           </tr>
 676           <tr>
 677             <td style="font-family: Courier New,Courier,monospace;">source_category_type
 678             <span style="font-weight: bold;">source_category</span>()
 679 const </td>
 680             <td>Returns input site category among the other sites.<br>
 681 Allows to distinguish between segment site and its endpoints. </td>
 682           </tr>
 683           <tr>
 684             <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
 685             <span style="font-weight: bold;">incident_edge</span>() </td>
 686             <td>Returns the pointer to the
 687 one of the boundary edges. </td>
 688           </tr>
 689           <tr>
 690             <td style="font-family: Courier New,Courier,monospace;">const
 691 voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>()
 692 const </td>
 693             <td>Returns the const pointer
 694 to the one of the boundary edges. </td>
 695           </tr>
 696           <tr>
 697             <td style="font-family: Courier New,Courier,monospace;">void
 698             <span style="font-weight: bold;">incident_edge</span>(voronoi_edge_type*
 699 e) </td>
 700             <td>Sets the incident boundary
 701 edge pointer of the cell. </td>
 702           </tr>
 703           <tr>
 704             <td style="font-family: Courier New,Courier,monospace;">color_type
 705             <span style="font-weight: bold;">color</span>() const </td>
 706             <td>Returns the color associated with the cell.</td>
 707           </tr>
 708           <tr>
 709             <td style="font-family: Courier New,Courier,monospace;">void
 710             <span style="font-weight: bold;">color</span>(color_type
 711 color) const </td>
 712             <td>Sets the color of
 713 the cell.<br>
 714 Allows to associate the user provided data with the primitive. </td>
 715           </tr>
 716           <tr>
 717             <td style="font-family: Courier New,Courier,monospace;">bool
 718             <span style="font-weight: bold;">contains_point</span>()
 719 const</td>
 720             <td>Returns true if the cell
 721 contains a point site, else false.</td>
 722           </tr>
 723           <tr>
 724             <td style="font-family: Courier New,Courier,monospace;">bool
 725             <span style="font-weight: bold;">contains_segment</span>()
 726 const</td>
 727             <td>Returns true if the cell
 728 contains a segment site, else false.</td>
 729           </tr>
 730           <tr>
 731             <td style="font-family: Courier New,Courier,monospace;">bool
 732             <span style="font-weight: bold;">is_degenerate</span>()
 733 const </td>
 734             <td>Returns true if the cell
 735 doesn't have an incident edge.<br>
 736 Can happen if a few input segments share a common endpoint.</td>
 737           </tr>
 738         </tbody>
 739       </table>
 740       <span style="font-family: Courier New,Courier,monospace;"> </span>All
 741 the above methods have O(1) complexity. The size of
 742 the Voronoi cell structure is equal to: sizeof(void *) + 2 *
 743 sizeof(size_t).<span style="font-family: Courier New,Courier,monospace;"></span>
 744       <h2>Member Types</h2>
 745       <table style="text-align: left; width: 100%;" border="1"
 746  cellpadding="2" cellspacing="2">
 747         <tbody>
 748           <tr>
 749             <td style="font-weight: bold;">coordinate_type </td>
 750             <td>Coordinate type. </td>
 751           </tr>
 752           <tr>
 753             <td style="font-weight: bold;">source_index_type</td>
 754             <td>Source index type. </td>
 755           </tr>
 756           <tr>
 757             <td style="vertical-align: top; font-weight: bold;">source_category_type
 758             </td>
 759             <td style="vertical-align: top;">Source category type. </td>
 760           </tr>
 761           <tr>
 762             <td style="vertical-align: top; font-weight: bold;">voronoi_edge_type
 763             </td>
 764             <td style="vertical-align: top;">Voronoi edge type. </td>
 765           </tr>
 766           <tr>
 767             <td style="font-weight: bold;">color_type </td>
 768             <td>Color type (check the Important section). </td>
 769           </tr>
 770         </tbody>
 771       </table>
 772       <h2>Miscellaneous</h2>
 773 The following code snippet effectively traverses the Voronoi edges
 774 around the
 775 Voronoi cell:<br>
 776       <br>
 777       <span style="font-family: Courier New,Courier,monospace;">const
 778 voronoi_edge&lt;double&gt;* edge = cell-&gt;incident_edge();</span><br>
 779       <span style="font-family: Courier New,Courier,monospace;">do {</span><br
 780  style="font-family: Courier New,Courier,monospace;">
 781       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 782 edge = edge-&gt;next();</span><br
 783  style="font-family: Courier New,Courier,monospace;">
 784       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 785 // Do smth. with edge.</span><br
 786  style="font-family: Courier New,Courier,monospace;">
 787       <span style="font-family: Courier New,Courier,monospace;">} while
 788 (edge != cell-&gt;incident_edge());</span><br>
 789       <h1>Voronoi Vertex</h1>
 790 A Voronoi vertex represents a point, that is equidistant from the three
 791 or more input geometries. As a consequence, it corresponds to the point
 792 of the intersection of the three or more Voronoi edges. On the image
 793 below, there are 5 such vertices: A, B, C, D, E. The Voronoi vertex
 794 data structure embeds the coordinates of the underlying point and
 795 provides access to a random Voronoi edge originating from the vertex
 796 (e.g. edge
 797 BC for the vertex B).<br>
 798       <img style="width: 600px; height: 600px;" alt=""
 799  src="images/voronoi1.png"><br>
 800       <h2>Declaration</h2>
 801 Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
 802       <br>
 803       <span style="font-family: Courier New,Courier,monospace;">template
 804 &lt;typename T&gt;</span><br
 805  style="font-family: Courier New,Courier,monospace;">
 806       <span style="font-family: Courier New,Courier,monospace;">class
 807 voronoi_vertex;<br>
 808       <br>
 809       </span><span style="font-family: Courier New,Courier,monospace;">T</span>
 810 - coordinate type.<br>
 811       <h2>Member Functions</h2>
 812       <span style="font-family: Courier New,Courier,monospace;"> </span>
 813       <table style="text-align: left; width: 100%;" border="1"
 814  cellpadding="2" cellspacing="2">
 815         <tbody>
 816           <tr>
 817             <td><span
 818  style="font-family: Courier New,Courier,monospace;"><span
 819  style="font-weight: bold;">voronoi_vertex</span>(const
 820 coordinate_type&amp; x,<br>
 821 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 822 const coordinate_type&amp; y)</span><span
 823  style="font-family: Courier New,Courier,monospace;"></span> </td>
 824             <td>Voronoi vertex constructor. </td>
 825           </tr>
 826           <tr>
 827             <td style="font-family: Courier New,Courier,monospace;">const
 828 point_type&amp; <span style="font-weight: bold;">x</span>() const </td>
 829             <td>Returns the x-coordinate of the point that represents
 830 the vertex. </td>
 831           </tr>
 832           <tr>
 833             <td style="font-family: Courier New,Courier,monospace;">const
 834 point_type&amp; <span style="font-weight: bold;">y</span>() const</td>
 835             <td>Returns the y-coordinate of the point that represents
 836 the vertex. </td>
 837           </tr>
 838           <tr>
 839             <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
 840             <span style="font-weight: bold;">incident_edge</span>() </td>
 841             <td>Returns the incident edge
 842 pointer. </td>
 843           </tr>
 844           <tr>
 845             <td style="font-family: Courier New,Courier,monospace;">const
 846 voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>()
 847 const </td>
 848             <td>Returns the const pointer
 849 to the incident edge. </td>
 850           </tr>
 851           <tr>
 852             <td style="font-family: Courier New,Courier,monospace;">void
 853             <span style="font-weight: bold;">incident_edge</span>(voronoi_edge_type*
 854 e) </td>
 855             <td>Sets the incident edge
 856 pointer. </td>
 857           </tr>
 858           <tr>
 859             <td style="font-family: Courier New,Courier,monospace;">color_type
 860             <span style="font-weight: bold;">color</span>() const </td>
 861             <td>Returns the color associated with the vertex.</td>
 862           </tr>
 863           <tr>
 864             <td style="font-family: Courier New,Courier,monospace;">void
 865             <span style="font-weight: bold;">color</span>(color_type
 866 color) const </td>
 867             <td>Sets the color of
 868 the vertex.<br>
 869 Allows to associate the user provided data with the primitive.</td>
 870           </tr>
 871         </tbody>
 872       </table>
 873       <span style="font-family: Courier New,Courier,monospace;"> </span>All
 874 the above methods have O(1) complexity. The size of
 875 the Voronoi vertex structure is equal to: sizeof(void *) +
 876 sizeof(size_t) + 2 *
 877 sizeof(coordinate_type).<span
 878  style="font-family: Courier New,Courier,monospace;"></span>
 879       <h2>Member Types</h2>
 880       <table style="text-align: left; width: 100%;" border="1"
 881  cellpadding="2" cellspacing="2">
 882         <tbody>
 883           <tr>
 884             <td style="font-weight: bold;">coordinate_type </td>
 885             <td>Coordainte type. </td>
 886           </tr>
 887           <tr>
 888             <td style="vertical-align: top; font-weight: bold;">voronoi_edge_type
 889             </td>
 890             <td style="vertical-align: top;">Voronoi edge type. </td>
 891           </tr>
 892           <tr>
 893             <td style="font-weight: bold;">color_type </td>
 894             <td>Color type (check the Important section). </td>
 895           </tr>
 896         </tbody>
 897       </table>
 898       <h2>Miscellaneous</h2>
 899 The following code snippet effectively traverses the Voronoi edges
 900 around the
 901 Voronoi vertex:<br>
 902       <br>
 903       <span style="font-family: Courier New,Courier,monospace;">const
 904 voronoi_edge&lt;double&gt;* edge = vertex-&gt;incident_edge();</span><br>
 905       <span style="font-family: Courier New,Courier,monospace;">do {</span><br
 906  style="font-family: Courier New,Courier,monospace;">
 907       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 908 edge = edge-&gt;next();</span><br
 909  style="font-family: Courier New,Courier,monospace;">
 910       <span style="font-family: Courier New,Courier,monospace;">&nbsp;
 911 // Do smth. with edge.</span><br
 912  style="font-family: Courier New,Courier,monospace;">
 913       <span style="font-family: Courier New,Courier,monospace;">} while
 914 (edge != vertex-&gt;incident_edge()); </span>
 915       <h1>Voronoi Diagram Traits </h1>
 916 The Voronoi diagram traits are used to configure the Voronoi primitive
 917 types and predicates, used by the Voronoi diagram
 918 data
 919 structure.<br>
 920 The implementation includes default traits specialization for the
 921 double output coordinate type.<br>
 922       <h2>Declaration</h2>
 923 Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
 924       <br>
 925       <span style="font-family: Courier New,Courier,monospace;">template
 926 &lt;typename T&gt;</span><br
 927  style="font-family: Courier New,Courier,monospace;">
 928       <span style="font-family: Courier New,Courier,monospace;">struct
 929 voronoi_diagram_traits;<br>
 930       <br>
 931       </span><span style="font-family: Courier New,Courier,monospace;">T</span>
 932 - coordinate type.<br>
 933       <h2>Member Types</h2>
 934       <span style="font-family: Courier New,Courier,monospace;"> </span>
 935       <table style="text-align: left; width: 100%;" border="1"
 936  cellpadding="2" cellspacing="2">
 937         <tbody>
 938           <tr>
 939             <td
 940  style="font-family: Courier New,Courier,monospace; font-weight: bold;">coordinate_type
 941             </td>
 942             <td>Coordinate type
 943 of the Voronoi diagram primitives. </td>
 944           </tr>
 945           <tr>
 946             <td
 947  style="font-family: Courier New,Courier,monospace; font-weight: bold;">cell_type
 948             </td>
 949             <td>Voronoi cell type. </td>
 950           </tr>
 951           <tr>
 952             <td
 953  style="font-family: Courier New,Courier,monospace; font-weight: bold;">vertex_type
 954             </td>
 955             <td>Voronoi vertex type. </td>
 956           </tr>
 957           <tr>
 958             <td
 959  style="font-family: Courier New,Courier,monospace; font-weight: bold;">edge_type
 960             </td>
 961             <td>Voronoi edge type. </td>
 962           </tr>
 963           <tr>
 964             <td
 965  style="font-family: Courier New,Courier,monospace; font-weight: bold;">vertex_equality_predicate_type
 966             </td>
 967             <td>Predicate that returns
 968 true if the two points are considered to be equal.<br>
 969 False otherwise. It is used to unite nearby Voronoi vertices. </td>
 970           </tr>
 971         </tbody>
 972       </table>
 973       </td>
 974     </tr>
 975     <tr>
 976       <td style="background-color: rgb(238, 238, 238);" nowrap="1">&nbsp;</td>
 977       <td
 978  style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
 979  valign="top" width="100%">
 980       <table class="docinfo" id="table2" frame="void" rules="none">
 981         <colgroup> <col class="docinfo-name"><col
 982  class="docinfo-content"> </colgroup> <tbody valign="top">
 983           <tr>
 984             <th class="docinfo-name">Copyright:</th>
 985             <td>Copyright © Andrii Sydorchuk 2010-2013.</td>
 986           </tr>
 987           <tr class="field">
 988             <th class="docinfo-name">License:</th>
 989             <td class="field-body">Distributed under the Boost Software
 990 License, Version 1.0. (See accompanying file <tt class="literal"><span
 991  class="pre">LICENSE_1_0.txt</span></tt> or copy at <a
 992  class="reference" target="_top"
 993  href="http://www.boost.org/LICENSE_1_0.txt">
 994 http://www.boost.org/LICENSE_1_0.txt</a>)</td>
 995           </tr>
 996         </tbody>
 997       </table>
 998       </td>
 999     </tr>
1000   </tbody>
1001 </table>
1002 </body>
1003 </html>