[ceph.git] / ceph / src / boost / libs / polygon / doc / voronoi_diagram.htm

<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta http-equiv="Content-Language" content="en-us">
  <meta http-equiv="Content-Type"
 content="text/html; charset=windows-1252">
  <title>Voronoi Diagram</title>
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
</head>
<body>
<table style="margin: 0pt; padding: 0pt; width: 100%;" border="0"
 cellpadding="0" cellspacing="0">
  <tbody>
    <tr>
      <td style="background-color: rgb(238, 238, 238);" nowrap="1"
 valign="top">
      <div style="padding: 5px;" align="center"> <img
 src="images/boost.png" border="0" height="86" width="277"><a
 title="www.boost.org home page" tabindex="2"
 style="border: medium none ;" href="http://www.boost.org/"> </a></div>
      <div style="margin: 5px;">
      <h3 class="navbar">Contents</h3>
      <ul>
        <li><a href="index.htm">Boost.Polygon Main Page</a></li>
        <li><a href="gtl_design_overview.htm">Design Overview</a></li>
        <li><a href="gtl_isotropy.htm">Isotropy</a></li>
        <li><a href="gtl_coordinate_concept.htm">Coordinate Concept</a></li>
        <li><a href="gtl_interval_concept.htm">Interval Concept</a></li>
        <li><a href="gtl_point_concept.htm">Point Concept</a></li>
        <li><a href="gtl_segment_concept.htm">Segment Concept</a></li>
        <li><a href="gtl_rectangle_concept.htm">Rectangle Concept</a></li>
        <li><a href="gtl_polygon_90_concept.htm">Polygon 90 Concept</a></li>
        <li><a href="gtl_polygon_90_with_holes_concept.htm">Polygon 90
With Holes Concept</a></li>
        <li><a href="gtl_polygon_45_concept.htm">Polygon 45 Concept</a></li>
        <li><a href="gtl_polygon_45_with_holes_concept.htm">Polygon 45
With Holes Concept</a></li>
        <li><a href="gtl_polygon_concept.htm">Polygon Concept</a></li>
        <li><a href="gtl_polygon_with_holes_concept.htm">Polygon With
Holes Concept</a></li>
        <li><a href="gtl_polygon_90_set_concept.htm">Polygon 90 Set
Concept</a></li>
        <li><a href="gtl_polygon_45_set_concept.htm">Polygon 45 Set
Concept</a></li>
        <li><a href="gtl_polygon_set_concept.htm">Polygon Set Concept</a></li>
        <li><a href="gtl_connectivity_extraction_90.htm">Connectivity
Extraction 90</a></li>
        <li><a href="gtl_connectivity_extraction_45.htm">Connectivity
Extraction 45</a></li>
        <li><a href="gtl_connectivity_extraction.htm">Connectivity
Extraction</a></li>
        <li><a href="gtl_property_merge_90.htm">Property Merge 90</a></li>
        <li><a href="gtl_property_merge_45.htm">Property Merge 45</a></li>
        <li><a href="gtl_property_merge.htm">Property Merge</a></li>
        <li><a href="voronoi_main.htm">Voronoi Main Page </a></li>
        <li><a href="voronoi_benchmark.htm">Voronoi Benchmark</a></li>
        <li><a href="voronoi_builder.htm">Voronoi Builder</a> </li>
        <li>Voronoi Diagram</li>
      </ul>
      <h3 class="navbar">Other Resources</h3>
      <ul>
        <li><a href="GTL_boostcon2009.pdf">GTL Boostcon 2009 Paper</a></li>
        <li><a href="GTL_boostcon_draft03.pdf">GTL Boostcon 2009
Presentation</a></li>
        <li><a href="analysis.htm">Performance Analysis</a></li>
        <li><a href="gtl_tutorial.htm">Layout Versus Schematic Tutorial</a></li>
        <li><a href="gtl_minkowski_tutorial.htm">Minkowski Sum Tutorial</a></li>
        <li><a href="voronoi_basic_tutorial.htm">Voronoi Basic Tutorial</a></li>
        <li><a href="voronoi_advanced_tutorial.htm">Voronoi Advanced
Tutorial</a></li>
      </ul>
      </div>
      <h3 class="navbar">Polygon Sponsor</h3>
      <div style="padding: 5px;" align="center"> <img
 src="images/intlogo.gif" border="0" height="51" width="127"><a
 title="www.adobe.com home page" tabindex="2"
 style="border: medium none ;" href="http://www.adobe.com/"> </a></div>
      </td>
      <td
 style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
 valign="top" width="100%"><!-- End Header --> <br>
      <h1>Voronoi Diagram</h1>
A Voronoi
diagram is the computational geometry concept that represents partition
of the given space onto regions, with bounds determined by distances to
a
specified family of objects. The application area of this concept
varies <a
 href="http://www.ics.uci.edu/%7Eeppstein/gina/scot.drysdale.html">from
Archaeology to Zoology</a>. The Boost.Polygon Voronoi extension
provides
implementation of
the Voronoi diagram data structure in the 2D space. The internal
representation
consists of the three arrays, that respectively contain: Voronoi cells
(represent the area around the input sites bounded by the Voronoi
edges), Voronoi vertices
(points where three or more Voronoi edges intersect), Voronoi edges
(one dimensional curves containing points equidistant from the two
closest input sites). Each of the primitives (cell, vertex, edge)
contains pointers to the other linked primitives, so that it's always
possible to efficiently traverse the Voronoi graph. The picture below
shows
the Voronoi vertices in red, Voronoi edges in black, input sites that
correspond to the Voronoi cells in blue. It is considered, that each
input segment consists of the three sites: segment itself and its
endpoints. As the result, two additional Voronoi edges are constructed
per each input segment. This is made to
simplify the representation of the Voronoi diagram and Voronoi edges in
particular.<br>
      <br>
      <img src="images/voronoi2.png" alt=""
 style="width: 600px; height: 600px;"><br>
      <h2>Important</h2>
All
the Voronoi primitive data structures (edge, vertex, cell) contain
mutable color member. Color type is equivalent to the std::size_t type,
except that the upper five bits are reserved for the internal usage.
That means, that the maximum supported value by the color member is 32
times less than the one supported by std::size_t.<br>
      <h2>Declaration</h2>
Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
      <br>
      <span style="font-family: Courier New,Courier,monospace;">template
&lt;typename T, typename TRAITS = voronoi_diagram_traits&lt;T&gt; &gt;</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">class
voronoi_diagram;<br>
      </span><font face="Courier New"><span
 style="font-family: 'Courier New',Courier,monospace;"><br>
T</span></font>
- the coordinate type of the Voronoi vertices.<br>
      <span style="font-family: Courier New,Courier,monospace;">TRAITS</span><font
 face="Courier New"><span
 style="font-family: 'Courier New',Courier,monospace;"></span></font>
- the Voronoi diagram traits.<br>
      <h2>Member Functions</h2>
      <span style="font-family: Courier New,Courier,monospace;"> </span>
      <table style="text-align: left; width: 100%;" border="1"
 cellpadding="2" cellspacing="2">
        <tbody>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;"><span
 style="font-weight: bold;">voronoi_diagram</span>() </td>
            <td>Default constructor. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">void
            <span style="font-weight: bold;">clear</span>() </td>
            <td>Removes all primitives from the Voronoi diagram. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
cell_container_type&amp; <span style="font-weight: bold;">cells</span>()
const </td>
            <td>Returns the const
reference to the cell container. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
vertex_container_type&amp; <span style="font-weight: bold;">vertices</span>()
const </td>
            <td>Returns the const
reference to the vertex container. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
edge_container_type&amp; <span style="font-weight: bold;">edges</span>()
const </td>
            <td>Returns the const
reference to the edge container. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">size_t
            <span style="font-weight: bold;">num_cells</span>() const </td>
            <td>Returns the number of the Voronoi
cells in the Voronoi diagram. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">size_t
            <span style="font-weight: bold;">num_edges</span>() const </td>
            <td>Returns the number of the
Voronoi edges (half-edges) in the Voronoi diagram. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">size_t
            <span style="font-weight: bold;">num_vertices</span>()
const </td>
            <td>Returns the number of the
Voronoi vertices in the Voronoi diagram. </td>
          </tr>
        </tbody>
      </table>
      <h2>Member Types</h2>
      <table style="text-align: left; width: 100%;" border="1"
 cellpadding="2" cellspacing="2">
        <tbody>
          <tr>
            <td style="font-weight: bold;">coordinate_type </td>
            <td>Coordinate type. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">cell_type </td>
            <td>Voronoi cell. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">vertex_type </td>
            <td>Voronoi vertex. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">edge_type </td>
            <td>Voronoi edge. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">cell_container_type </td>
            <td>Container of the Voronoi cells. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">const_cell_iterator </td>
            <td>Const cell container iterator. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">vertex_container_type </td>
            <td>Container of the Voronoi vertices. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">const_vertex_iterator </td>
            <td>Const vertex container iterator. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">edge_container_type </td>
            <td>Container of the Voronoi edges. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">const_edge_iterator </td>
            <td>Const edge container iterator. </td>
          </tr>
        </tbody>
      </table>
      <h1>Voronoi Geometry Type</h1>
The Voronoi
diagram data structure doesn't embed coordinates of the input
geometries.
Instead it links with those via source index and source category
methods
of the Voronoi cell primitive. Source index is incrementally given
(starting from zero) to each input site inserted into the <a
 href="voronoi_builder.htm">Voronoi
builder</a>.
Considering the fact, that each input segment is splitted onto three
separate sites with the same index, we distinguish between those using
source category. For more examples check the <a
 href="voronoi_basic_tutorial.htm">Voronoi basic tutorial</a>.<br>
      <h2>GeometryCategory </h2>
Defines geometric category of the input object.<br>
Header: <a href="../../../boost/polygon/voronoi_geometry_type.hpp">boost/polygon/</a><a
 href="../../../boost/polygon/voronoi_geometry_type.hpp">voronoi_geometry_type.hpp</a><br>
      <br>
      <span style="font-family: Courier New,Courier,monospace;">enum
GeometryCategory {</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
GEOMETRY_CATEGORY_POINT = 0x0,</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
GEOMETRY_CATEGORY_SEGMENT = 0x1</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">};</span><br>
      <h2>SourceCategory</h2>
Defines semantic category of the input site.<br>
Header: <a href="../../../boost/polygon/voronoi_geometry_type.hpp">boost/polygon/</a><a
 href="../../../boost/polygon/voronoi_geometry_type.hpp">voronoi_geometry_type.hpp</a><br>
      <br>
      <span style="font-family: Courier New,Courier,monospace;">enum
SourceCategory {</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
// Point subtypes.</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
SOURCE_CATEGORY_SINGLE_POINT = 0x0,</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
SOURCE_CATEGORY_SEGMENT_START_POINT = 0x1,</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
SOURCE_CATEGORY_SEGMENT_END_POINT = 0x2,</span><br
 style="font-family: Courier New,Courier,monospace;">
      <br style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
// Segment subtypes.</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
SOURCE_CATEGORY_INITIAL_SEGMENT = 0x8,</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
SOURCE_CATEGORY_REVERSE_SEGMENT = 0x9,</span><br
 style="font-family: Courier New,Courier,monospace;">
      <br style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
SOURCE_CATEGORY_GEOMETRY_SHIFT = 0x3,</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
SOURCE_CATEGORY_BITMASK = 0x1F</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">};</span><br>
      <h2>Member Functions</h2>
      <table style="text-align: left; width: 100%;" border="1"
 cellpadding="2" cellspacing="2">
        <tbody>
          <tr>
            <td style="vertical-align: top;"><span
 style="font-family: Courier New,Courier,monospace;">bool <span
 style="font-weight: bold;">belongs</span>(</span><br
 style="font-family: Courier New,Courier,monospace;">
            <span style="font-family: Courier New,Courier,monospace;">&nbsp;
&nbsp; SourceCategory source_category,</span><br
 style="font-family: Courier New,Courier,monospace;">
            <span style="font-family: Courier New,Courier,monospace;">&nbsp;&nbsp;&nbsp;
GeometryCategory geometry_category)</span> </td>
            <td style="vertical-align: middle;">Returns true if the
given source
category belongs to the given geometry category.<br>
Returns false otherwise. </td>
          </tr>
        </tbody>
      </table>
      <h1>Voronoi Edge</h1>
A Voronoi edge is a one-dimenstion curve, that contains points
equidistant from the two closest input geometries. The Voronoi edge
data structure is implemented as the enhanced classical <a
 href="http://www.flipcode.com/archives/The_Half-Edge_Data_Structure.shtml">half-edge</a>
data structure. On the image below, the Voronoi edges are drawn as
directed linear (e.g. AE) or curved (e.g. DE) dashed lines of either
green (e.g. AE) or black (e.g DE) color. The green edges are considered
to be secondary, as they are generated by an input segment and its
endpoint (e.g. edge EA, made by segment MN and its endpoint M). All the
other edges are considered to be primary (e.g. curved edge CD, made by
segment KL and point N). Apart from that, each edge can be finite (e.g.
ED) or infinite (e.g. edge starting at point B and going in the east
direction).<br>
      <img src="images/voronoi1.png" alt=""
 style="width: 600px; height: 600px;"><br>
Each Voronoi edge (consider directed edge BA) provides efficient access
to the following primitives:<br>
      <ul>
        <li>Cell the edge belongs to (Voronoi cell P, with source
segment MN)</li>
        <li>Start point of the edge (Voronoi vertex B, that is
equidistant from the following input sites: O, L, MN)</li>
        <li>End point of the edge (Voronoi vertex A, that is
equidistant from the following input sites: O, M, MN)</li>
        <li>Twin edge (Voronoi edge AB)</li>
        <li>CCW next edge inside the Voronoi cell, that the edge
belongs to (green Voronoi edge AE)</li>
        <li>CCW previous edge inside the Voronoi cell, that the edge
belongs to (Voronoi edge CB)</li>
        <li>CCW rotated next edge around the start point of the edge
(Voronoi edge BC)</li>
        <li>CCW rotated previous edge around the start point of the
edge (infinite Voronoi edge starting at the Voronoi vertex B and going
in the east direction) </li>
      </ul>
      <h2>Declaration</h2>
Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
      <br>
      <span style="font-family: Courier New,Courier,monospace;">template
&lt;typename T&gt;</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">class
voronoi_edge;<br>
      <br>
T</span> - coordinate type.<br>
      <h2>Member Functions</h2>
      <span style="font-family: Courier New,Courier,monospace;"> </span>
      <table style="text-align: left; width: 100%;" border="1"
 cellpadding="2" cellspacing="2">
        <tbody>
          <tr>
            <td><span
 style="font-family: Courier New,Courier,monospace;"><span
 style="font-weight: bold;">voronoi_edge</span>(bool is_linear, bool
is_primary)</span> </td>
            <td>Voronoi edge constructor. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">voronoi_cell_type*
            <span style="font-weight: bold;">cell</span>() </td>
            <td>Returns the pointer to the
Voronoi <span style="font-family: Courier New,Courier,monospace;"></span>cell
that the edge belongs to. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
voronoi_cell_type* <span style="font-weight: bold;">cell</span>()
const </td>
            <td>Returns the const pointer
to the Voronoi cell that the edge belongs to. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">void
            <span style="font-weight: bold;">cell</span>(voronoi_cell_type*
c) </td>
            <td>Sets the Voronoi cell
pointer to the cell the current edge belongs to. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type*
            <span style="font-weight: bold;">vertex0</span>() </td>
            <td>Returns the pointer to the
start point of the edge.<br>
If the edge is infinite in that direction returns NULL. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
voronoi_vertex_type* <span style="font-weight: bold;">vertex0</span>()
const </td>
            <td>Returns the const pointer
to the start point vertex of the edge.<br>
If the edge is infinite in that direction returns NULL. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">void
            <span style="font-weight: bold;">vertex0</span>(voronoi_vertex_type*
v) </td>
            <td>Sets the start point
pointer of the edge. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">voronoi_vertex_type*
            <span style="font-weight: bold;">vertex1</span>() </td>
            <td>Returns the pointer to the
end point of the edge.<br>
If the edge is infinite in that direction returns NULL. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
voronoi_vertex_type* <span style="font-weight: bold;">vertex1</span>()
const </td>
            <td>Returns the const pointer
to the end point of the edge.<br>
If the edge is infinite in that direction returns NULL. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
            <span style="font-weight: bold;">twin</span>() </td>
            <td>Returns the pointer to the
twin edge. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
voronoi_edge_type* <span style="font-weight: bold;">twin</span>()
const </td>
            <td>Returns the const pointer
to the twin edge. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">void
            <span style="font-weight: bold;">twin</span>(voronoi_edge_type*
e) </td>
            <td>Sets the twin edge pointer
of the edge. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
            <span style="font-weight: bold;">next</span>() </td>
            <td>Returns the pointer to the
CCW next edge within the corresponding Voronoi cell.<br>
Edges not necessarily share a common vertex (e.g. infinite edges). </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
voronoi_edge_type* <span style="font-weight: bold;">next</span>()
const </td>
            <td>Returns the const pointer
to the CCW next edge within the corresponding Voronoi cell.<br>
Edges not necessarily share a common vertex (e.g. infinite edges). </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">void
            <span style="font-weight: bold;">next</span>(voronoi_edge_type*
e) </td>
            <td>Sets the CCW next edge
pointer of the edge. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
            <span style="font-weight: bold;">prev</span>() </td>
            <td>Returns the pointer to the
CCW prev edge within the corresponding Voronoi cell.<br>
Edges not necessarily share a common vertex (e.g. infinite edges). </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
voronoi_edge_type* <span style="font-weight: bold;">prev</span>()
const </td>
            <td>Returns the const pointer
to the CCW prev edge within the corresponding Voronoi cell.<br>
Edges not necessarily share a common vertex (e.g. infinite edges). </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">void
            <span style="font-weight: bold;">prev</span>(voronoi_edge_type*
e) </td>
            <td>Sets the CCW prev edge
pointer of the edge. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">color_type
            <span style="font-weight: bold;">color</span>() const </td>
            <td>Returns the color value. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">void
            <span style="font-weight: bold;">color</span>(color_type
color) const </td>
            <td>Sets the color of
the edge.<br>
Allows to associate the user provided data with the primitive. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
            <span style="font-weight: bold;">rot_next</span>() </td>
            <td>Returns the pointer to the
CCW next edge rotated around the edge start point.<br>
Works for infinite edges as well. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
voronoi_edge_type* <span style="font-weight: bold;">rot_next</span>()
const </td>
            <td>Returns the const pointer
to the CCW next edge rotated around the edge start point.<br>
Works for infinite edges as well.</td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
            <span style="font-weight: bold;">rot_prev</span>() </td>
            <td>Returns the pointer to the
CCW prev edge rotated around the edge start point.<br>
Works for infinite edges as well. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
voronoi_edge_type* <span style="font-weight: bold;">rot_prev</span>()
const </td>
            <td>Returns the const pointer
to the CCW prev edge rotated around the edge start point.<br>
Works for infinite edges as well.</td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">bool
            <span style="font-weight: bold;">is_finite</span>() const </td>
            <td>Returns true if the both
end points of the edge are finite, else false. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">bool
            <span style="font-weight: bold;">is_infinite</span>() const</td>
            <td>Returns true if one of the
end points of the edge is infinite, else false.</td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">bool
            <span style="font-weight: bold;">is_linear</span>() const </td>
            <td>Returns true if the edge
is linear (segment, ray, line), else false. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">bool
            <span style="font-weight: bold;">is_curved</span>() const </td>
            <td>Returns true if the edge
is curved (parabolic arc), else false. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">bool
            <span style="font-weight: bold;">is_primary</span>() const </td>
            <td>Returns false if the edge
goes through the endpoint of the segment site, else true. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">bool
            <span style="font-weight: bold;">is_secondary</span>() const</td>
            <td>Returns true if the edge
goes through the endpoint of the segment site, else false.</td>
          </tr>
        </tbody>
      </table>
      <span style="font-family: Courier New,Courier,monospace;"> </span>All
the above methods have O(1) complexity. The size of
the Voronoi edge structure is equal to: 5 * sizeof(void *) +
sizeof(size_t).<span style="font-family: Courier New,Courier,monospace;"></span><br>
      <h2>Member Types</h2>
      <table style="text-align: left; width: 100%;" border="1"
 cellpadding="2" cellspacing="2">
        <tbody>
          <tr>
            <td style="font-weight: bold;">coordinate_type </td>
            <td>Coordinate type. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">voronoi_cell_type </td>
            <td>Voronoi cell type. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">voronoi_vertex_type </td>
            <td>Voronoi vertex type. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">voronoi_edge_type </td>
            <td>Voronoi edge type. </td>
          </tr>
          <tr>
            <td style="vertical-align: top; font-weight: bold;">color_type
            </td>
            <td style="vertical-align: top;">Color type (check the
Important section). </td>
          </tr>
        </tbody>
      </table>
      <h1>Voronoi Cell</h1>
A Voronoi cell represents a region of the Voronoi diagram bounded by
the Voronoi edges. On the image below, there are 7 such regions: P, Q,
R, S, T, U, V. Each Voronoi cell can contain a point (e.g. cells Q, S,
T, U, V with corresponding input sources N, K, L, O, M respectively) or
a segment
(e.g. cells P and R with corresponding input sources MN and KL
respectively) as its
source. The Voronoi cell primitive doesn't contain coordinates of the
source geometry, instead it stores the index and category of the source
geometry. Source index corresponds to the unique id, issued to each
input geometry (e.g. incremental counter, used by the Voronoi builder).
Such an index uniquely identifies any input point (e.g. O), however
doesn't make any distinction between segment (e.g. MN) and both its end
points (e.g. M, N). In order to resolve possible ambiguity, the source
category is used, that specifies the semantic topology of the input
object (e.g. segment's startpoint, segment's endpoint or segment
itself). The Voronoi cell data structure also provides access to a
random Voronoi edge, located on the boundary of the cell (e.g. edge AE
for
the cell P).<br>
      <img style="width: 600px; height: 600px;" alt=""
 src="images/voronoi1.png"><br>
      <h2>Declaration</h2>
Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
      <br>
      <span style="font-family: Courier New,Courier,monospace;">template
&lt;typename T&gt;<br>
class voronoi_cell;<br>
      <br>
      </span><span style="font-family: Courier New,Courier,monospace;">T</span>
- coordinate type.<br>
      <h2>Member Functions</h2>
      <span style="font-family: Courier New,Courier,monospace;"> </span>
      <table style="text-align: left; width: 100%;" border="1"
 cellpadding="2" cellspacing="2">
        <tbody>
          <tr>
            <td><span
 style="font-family: Courier New,Courier,monospace;"><span
 style="font-weight: bold;">voronoi_cell</span>(source_index_type
source_index,</span><span
 style="font-family: Courier New,Courier,monospace;"><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
source_category_type source_category)</span> </td>
            <td>Voronoi cell constructor. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">source_index_type
            <span style="font-weight: bold;">source_index</span>()
const </td>
            <td>Returns input site index among the other sites.<br>
Both segment and its end points will have the same index. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">source_category_type
            <span style="font-weight: bold;">source_category</span>()
const </td>
            <td>Returns input site category among the other sites.<br>
Allows to distinguish between segment site and its endpoints. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
            <span style="font-weight: bold;">incident_edge</span>() </td>
            <td>Returns the pointer to the
one of the boundary edges. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>()
const </td>
            <td>Returns the const pointer
to the one of the boundary edges. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">void
            <span style="font-weight: bold;">incident_edge</span>(voronoi_edge_type*
e) </td>
            <td>Sets the incident boundary
edge pointer of the cell. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">color_type
            <span style="font-weight: bold;">color</span>() const </td>
            <td>Returns the color associated with the cell.</td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">void
            <span style="font-weight: bold;">color</span>(color_type
color) const </td>
            <td>Sets the color of
the cell.<br>
Allows to associate the user provided data with the primitive. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">bool
            <span style="font-weight: bold;">contains_point</span>()
const</td>
            <td>Returns true if the cell
contains a point site, else false.</td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">bool
            <span style="font-weight: bold;">contains_segment</span>()
const</td>
            <td>Returns true if the cell
contains a segment site, else false.</td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">bool
            <span style="font-weight: bold;">is_degenerate</span>()
const </td>
            <td>Returns true if the cell
doesn't have an incident edge.<br>
Can happen if a few input segments share a common endpoint.</td>
          </tr>
        </tbody>
      </table>
      <span style="font-family: Courier New,Courier,monospace;"> </span>All
the above methods have O(1) complexity. The size of
the Voronoi cell structure is equal to: sizeof(void *) + 2 *
sizeof(size_t).<span style="font-family: Courier New,Courier,monospace;"></span>
      <h2>Member Types</h2>
      <table style="text-align: left; width: 100%;" border="1"
 cellpadding="2" cellspacing="2">
        <tbody>
          <tr>
            <td style="font-weight: bold;">coordinate_type </td>
            <td>Coordinate type. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">source_index_type</td>
            <td>Source index type. </td>
          </tr>
          <tr>
            <td style="vertical-align: top; font-weight: bold;">source_category_type
            </td>
            <td style="vertical-align: top;">Source category type. </td>
          </tr>
          <tr>
            <td style="vertical-align: top; font-weight: bold;">voronoi_edge_type
            </td>
            <td style="vertical-align: top;">Voronoi edge type. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">color_type </td>
            <td>Color type (check the Important section). </td>
          </tr>
        </tbody>
      </table>
      <h2>Miscellaneous</h2>
The following code snippet effectively traverses the Voronoi edges
around the
Voronoi cell:<br>
      <br>
      <span style="font-family: Courier New,Courier,monospace;">const
voronoi_edge&lt;double&gt;* edge = cell-&gt;incident_edge();</span><br>
      <span style="font-family: Courier New,Courier,monospace;">do {</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
edge = edge-&gt;next();</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
// Do smth. with edge.</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">} while
(edge != cell-&gt;incident_edge());</span><br>
      <h1>Voronoi Vertex</h1>
A Voronoi vertex represents a point, that is equidistant from the three
or more input geometries. As a consequence, it corresponds to the point
of the intersection of the three or more Voronoi edges. On the image
below, there are 5 such vertices: A, B, C, D, E. The Voronoi vertex
data structure embeds the coordinates of the underlying point and
provides access to a random Voronoi edge originating from the vertex
(e.g. edge
BC for the vertex B).<br>
      <img style="width: 600px; height: 600px;" alt=""
 src="images/voronoi1.png"><br>
      <h2>Declaration</h2>
Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
      <br>
      <span style="font-family: Courier New,Courier,monospace;">template
&lt;typename T&gt;</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">class
voronoi_vertex;<br>
      <br>
      </span><span style="font-family: Courier New,Courier,monospace;">T</span>
- coordinate type.<br>
      <h2>Member Functions</h2>
      <span style="font-family: Courier New,Courier,monospace;"> </span>
      <table style="text-align: left; width: 100%;" border="1"
 cellpadding="2" cellspacing="2">
        <tbody>
          <tr>
            <td><span
 style="font-family: Courier New,Courier,monospace;"><span
 style="font-weight: bold;">voronoi_vertex</span>(const
coordinate_type&amp; x,<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
const coordinate_type&amp; y)</span><span
 style="font-family: Courier New,Courier,monospace;"></span> </td>
            <td>Voronoi vertex constructor. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
point_type&amp; <span style="font-weight: bold;">x</span>() const </td>
            <td>Returns the x-coordinate of the point that represents
the vertex. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
point_type&amp; <span style="font-weight: bold;">y</span>() const</td>
            <td>Returns the y-coordinate of the point that represents
the vertex. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">voronoi_edge_type*
            <span style="font-weight: bold;">incident_edge</span>() </td>
            <td>Returns the incident edge
pointer. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">const
voronoi_edge_type* <span style="font-weight: bold;">incident_edge</span>()
const </td>
            <td>Returns the const pointer
to the incident edge. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">void
            <span style="font-weight: bold;">incident_edge</span>(voronoi_edge_type*
e) </td>
            <td>Sets the incident edge
pointer. </td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">color_type
            <span style="font-weight: bold;">color</span>() const </td>
            <td>Returns the color associated with the vertex.</td>
          </tr>
          <tr>
            <td style="font-family: Courier New,Courier,monospace;">void
            <span style="font-weight: bold;">color</span>(color_type
color) const </td>
            <td>Sets the color of
the vertex.<br>
Allows to associate the user provided data with the primitive.</td>
          </tr>
        </tbody>
      </table>
      <span style="font-family: Courier New,Courier,monospace;"> </span>All
the above methods have O(1) complexity. The size of
the Voronoi vertex structure is equal to: sizeof(void *) +
sizeof(size_t) + 2 *
sizeof(coordinate_type).<span
 style="font-family: Courier New,Courier,monospace;"></span>
      <h2>Member Types</h2>
      <table style="text-align: left; width: 100%;" border="1"
 cellpadding="2" cellspacing="2">
        <tbody>
          <tr>
            <td style="font-weight: bold;">coordinate_type </td>
            <td>Coordainte type. </td>
          </tr>
          <tr>
            <td style="vertical-align: top; font-weight: bold;">voronoi_edge_type
            </td>
            <td style="vertical-align: top;">Voronoi edge type. </td>
          </tr>
          <tr>
            <td style="font-weight: bold;">color_type </td>
            <td>Color type (check the Important section). </td>
          </tr>
        </tbody>
      </table>
      <h2>Miscellaneous</h2>
The following code snippet effectively traverses the Voronoi edges
around the
Voronoi vertex:<br>
      <br>
      <span style="font-family: Courier New,Courier,monospace;">const
voronoi_edge&lt;double&gt;* edge = vertex-&gt;incident_edge();</span><br>
      <span style="font-family: Courier New,Courier,monospace;">do {</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
edge = edge-&gt;next();</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">&nbsp;
// Do smth. with edge.</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">} while
(edge != vertex-&gt;incident_edge()); </span>
      <h1>Voronoi Diagram Traits </h1>
The Voronoi diagram traits are used to configure the Voronoi primitive
types and predicates, used by the Voronoi diagram
data
structure.<br>
The implementation includes default traits specialization for the
double output coordinate type.<br>
      <h2>Declaration</h2>
Header: <a href="../../../boost/polygon/voronoi_diagram.hpp">boost/polygon/voronoi_diagram.hpp</a><br>
      <br>
      <span style="font-family: Courier New,Courier,monospace;">template
&lt;typename T&gt;</span><br
 style="font-family: Courier New,Courier,monospace;">
      <span style="font-family: Courier New,Courier,monospace;">struct
voronoi_diagram_traits;<br>
      <br>
      </span><span style="font-family: Courier New,Courier,monospace;">T</span>
- coordinate type.<br>
      <h2>Member Types</h2>
      <span style="font-family: Courier New,Courier,monospace;"> </span>
      <table style="text-align: left; width: 100%;" border="1"
 cellpadding="2" cellspacing="2">
        <tbody>
          <tr>
            <td
 style="font-family: Courier New,Courier,monospace; font-weight: bold;">coordinate_type
            </td>
            <td>Coordinate type
of the Voronoi diagram primitives. </td>
          </tr>
          <tr>
            <td
 style="font-family: Courier New,Courier,monospace; font-weight: bold;">cell_type
            </td>
            <td>Voronoi cell type. </td>
          </tr>
          <tr>
            <td
 style="font-family: Courier New,Courier,monospace; font-weight: bold;">vertex_type
            </td>
            <td>Voronoi vertex type. </td>
          </tr>
          <tr>
            <td
 style="font-family: Courier New,Courier,monospace; font-weight: bold;">edge_type
            </td>
            <td>Voronoi edge type. </td>
          </tr>
          <tr>
            <td
 style="font-family: Courier New,Courier,monospace; font-weight: bold;">vertex_equality_predicate_type
            </td>
            <td>Predicate that returns
true if the two points are considered to be equal.<br>
False otherwise. It is used to unite nearby Voronoi vertices. </td>
          </tr>
        </tbody>
      </table>
      </td>
    </tr>
    <tr>
      <td style="background-color: rgb(238, 238, 238);" nowrap="1">&nbsp;</td>
      <td
 style="padding-left: 10px; padding-right: 10px; padding-bottom: 10px;"
 valign="top" width="100%">
      <table class="docinfo" id="table2" frame="void" rules="none">
        <colgroup> <col class="docinfo-name"><col
 class="docinfo-content"> </colgroup> <tbody valign="top">
          <tr>
            <th class="docinfo-name">Copyright:</th>