Polygon Sponsor

Voronoi Diagram
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 from
Archaeology to Zoology. 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.
Important
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.
Declaration
Header: boost/polygon/voronoi_diagram.hpp
template
<typename T, typename TRAITS = voronoi_diagram_traits<T> >
class
voronoi_diagram;
T
 the coordinate type of the Voronoi vertices.
TRAITS
 the Voronoi diagram traits.
Member Functions
voronoi_diagram() 
Default constructor. 
void
clear() 
Removes all primitives from the Voronoi diagram. 
const
cell_container_type& cells()
const 
Returns the const
reference to the cell container. 
const
vertex_container_type& vertices()
const 
Returns the const
reference to the vertex container. 
const
edge_container_type& edges()
const 
Returns the const
reference to the edge container. 
size_t
num_cells() const 
Returns the number of the Voronoi
cells in the Voronoi diagram. 
size_t
num_edges() const 
Returns the number of the
Voronoi edges (halfedges) in the Voronoi diagram. 
size_t
num_vertices()
const 
Returns the number of the
Voronoi vertices in the Voronoi diagram. 
Member Types
coordinate_type 
Coordinate type. 
cell_type 
Voronoi cell. 
vertex_type 
Voronoi vertex. 
edge_type 
Voronoi edge. 
cell_container_type 
Container of the Voronoi cells. 
const_cell_iterator 
Const cell container iterator. 
vertex_container_type 
Container of the Voronoi vertices. 
const_vertex_iterator 
Const vertex container iterator. 
edge_container_type 
Container of the Voronoi edges. 
const_edge_iterator 
Const edge container iterator. 
Voronoi Geometry Type
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 Voronoi
builder.
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 Voronoi basic tutorial.
GeometryCategory
Defines geometric category of the input object.
Header: boost/polygon/voronoi_geometry_type.hpp
enum
GeometryCategory {
GEOMETRY_CATEGORY_POINT = 0x0,
GEOMETRY_CATEGORY_SEGMENT = 0x1
};
SourceCategory
Defines semantic category of the input site.
Header: boost/polygon/voronoi_geometry_type.hpp
enum
SourceCategory {
// Point subtypes.
SOURCE_CATEGORY_SINGLE_POINT = 0x0,
SOURCE_CATEGORY_SEGMENT_START_POINT = 0x1,
SOURCE_CATEGORY_SEGMENT_END_POINT = 0x2,
// Segment subtypes.
SOURCE_CATEGORY_INITIAL_SEGMENT = 0x8,
SOURCE_CATEGORY_REVERSE_SEGMENT = 0x9,
SOURCE_CATEGORY_GEOMETRY_SHIFT = 0x3,
SOURCE_CATEGORY_BITMASK = 0x1F
};
Member Functions
bool belongs(
SourceCategory source_category,
GeometryCategory geometry_category) 
Returns true if the
given source
category belongs to the given geometry category.
Returns false otherwise. 
Voronoi Edge
A Voronoi edge is a onedimenstion curve, that contains points
equidistant from the two closest input geometries. The Voronoi edge
data structure is implemented as the enhanced classical halfedge
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).
Each Voronoi edge (consider directed edge BA) provides efficient access
to the following primitives:
 Cell the edge belongs to (Voronoi cell P, with source
segment MN)
 Start point of the edge (Voronoi vertex B, that is
equidistant from the following input sites: O, L, MN)
 End point of the edge (Voronoi vertex A, that is
equidistant from the following input sites: O, M, MN)
 Twin edge (Voronoi edge AB)
 CCW next edge inside the Voronoi cell, that the edge
belongs to (green Voronoi edge AE)
 CCW previous edge inside the Voronoi cell, that the edge
belongs to (Voronoi edge CB)
 CCW rotated next edge around the start point of the edge
(Voronoi edge BC)
 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)
Declaration
Header: boost/polygon/voronoi_diagram.hpp
template
<typename T>
class
voronoi_edge;
T  coordinate type.
Member Functions
voronoi_edge(bool is_linear, bool
is_primary) 
Voronoi edge constructor. 
voronoi_cell_type*
cell() 
Returns the pointer to the
Voronoi cell
that the edge belongs to. 
const
voronoi_cell_type* cell()
const 
Returns the const pointer
to the Voronoi cell that the edge belongs to. 
void
cell(voronoi_cell_type*
c) 
Sets the Voronoi cell
pointer to the cell the current edge belongs to. 
voronoi_vertex_type*
vertex0() 
Returns the pointer to the
start point of the edge.
If the edge is infinite in that direction returns NULL. 
const
voronoi_vertex_type* vertex0()
const 
Returns the const pointer
to the start point vertex of the edge.
If the edge is infinite in that direction returns NULL. 
void
vertex0(voronoi_vertex_type*
v) 
Sets the start point
pointer of the edge. 
voronoi_vertex_type*
vertex1() 
Returns the pointer to the
end point of the edge.
If the edge is infinite in that direction returns NULL. 
const
voronoi_vertex_type* vertex1()
const 
Returns the const pointer
to the end point of the edge.
If the edge is infinite in that direction returns NULL. 
voronoi_edge_type*
twin() 
Returns the pointer to the
twin edge. 
const
voronoi_edge_type* twin()
const 
Returns the const pointer
to the twin edge. 
void
twin(voronoi_edge_type*
e) 
Sets the twin edge pointer
of the edge. 
voronoi_edge_type*
next() 
Returns the pointer to the
CCW next edge within the corresponding Voronoi cell.
Edges not necessarily share a common vertex (e.g. infinite edges). 
const
voronoi_edge_type* next()
const 
Returns the const pointer
to the CCW next edge within the corresponding Voronoi cell.
Edges not necessarily share a common vertex (e.g. infinite edges). 
void
next(voronoi_edge_type*
e) 
Sets the CCW next edge
pointer of the edge. 
voronoi_edge_type*
prev() 
Returns the pointer to the
CCW prev edge within the corresponding Voronoi cell.
Edges not necessarily share a common vertex (e.g. infinite edges). 
const
voronoi_edge_type* prev()
const 
Returns the const pointer
to the CCW prev edge within the corresponding Voronoi cell.
Edges not necessarily share a common vertex (e.g. infinite edges). 
void
prev(voronoi_edge_type*
e) 
Sets the CCW prev edge
pointer of the edge. 
color_type
color() const 
Returns the color value. 
void
color(color_type
color) const 
Sets the color of
the edge.
Allows to associate the user provided data with the primitive. 
voronoi_edge_type*
rot_next() 
Returns the pointer to the
CCW next edge rotated around the edge start point.
Works for infinite edges as well. 
const
voronoi_edge_type* rot_next()
const 
Returns the const pointer
to the CCW next edge rotated around the edge start point.
Works for infinite edges as well. 
voronoi_edge_type*
rot_prev() 
Returns the pointer to the
CCW prev edge rotated around the edge start point.
Works for infinite edges as well. 
const
voronoi_edge_type* rot_prev()
const 
Returns the const pointer
to the CCW prev edge rotated around the edge start point.
Works for infinite edges as well. 
bool
is_finite() const 
Returns true if the both
end points of the edge are finite, else false. 
bool
is_infinite() const 
Returns true if one of the
end points of the edge is infinite, else false. 
bool
is_linear() const 
Returns true if the edge
is linear (segment, ray, line), else false. 
bool
is_curved() const 
Returns true if the edge
is curved (parabolic arc), else false. 
bool
is_primary() const 
Returns false if the edge
goes through the endpoint of the segment site, else true. 
bool
is_secondary() const 
Returns true if the edge
goes through the endpoint of the segment site, else false. 
All
the above methods have O(1) complexity. The size of
the Voronoi edge structure is equal to: 5 * sizeof(void *) +
sizeof(size_t).
Member Types
coordinate_type 
Coordinate type. 
voronoi_cell_type 
Voronoi cell type. 
voronoi_vertex_type 
Voronoi vertex type. 
voronoi_edge_type 
Voronoi edge type. 
color_type

Color type (check the
Important section). 
Voronoi Cell
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).
Declaration
Header: boost/polygon/voronoi_diagram.hpp
template
<typename T>
class voronoi_cell;
T
 coordinate type.
Member Functions
voronoi_cell(source_index_type
source_index,
source_category_type source_category) 
Voronoi cell constructor. 
source_index_type
source_index()
const 
Returns input site index among the other sites.
Both segment and its end points will have the same index. 
source_category_type
source_category()
const 
Returns input site category among the other sites.
Allows to distinguish between segment site and its endpoints. 
voronoi_edge_type*
incident_edge() 
Returns the pointer to the
one of the boundary edges. 
const
voronoi_edge_type* incident_edge()
const 
Returns the const pointer
to the one of the boundary edges. 
void
incident_edge(voronoi_edge_type*
e) 
Sets the incident boundary
edge pointer of the cell. 
color_type
color() const 
Returns the color associated with the cell. 
void
color(color_type
color) const 
Sets the color of
the cell.
Allows to associate the user provided data with the primitive. 
bool
contains_point()
const 
Returns true if the cell
contains a point site, else false. 
bool
contains_segment()
const 
Returns true if the cell
contains a segment site, else false. 
bool
is_degenerate()
const 
Returns true if the cell
doesn't have an incident edge.
Can happen if a few input segments share a common endpoint. 
All
the above methods have O(1) complexity. The size of
the Voronoi cell structure is equal to: sizeof(void *) + 2 *
sizeof(size_t).
Member Types
coordinate_type 
Coordinate type. 
source_index_type 
Source index type. 
source_category_type

Source category type. 
voronoi_edge_type

Voronoi edge type. 
color_type 
Color type (check the Important section). 
Miscellaneous
The following code snippet effectively traverses the Voronoi edges
around the
Voronoi cell:
const
voronoi_edge<double>* edge = cell>incident_edge();
do {
edge = edge>next();
// Do smth. with edge.
} while
(edge != cell>incident_edge());
Voronoi Vertex
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).
Declaration
Header: boost/polygon/voronoi_diagram.hpp
template
<typename T>
class
voronoi_vertex;
T
 coordinate type.
Member Functions
voronoi_vertex(const
coordinate_type& x,
const coordinate_type& y) 
Voronoi vertex constructor. 
const
coordinate_type& x() const 
Returns the xcoordinate of the point that represents
the vertex. 
const
coordinate_type& y() const 
Returns the ycoordinate of the point that represents
the vertex. 
voronoi_edge_type*
incident_edge() 
Returns the incident edge
pointer. 
const
voronoi_edge_type* incident_edge()
const 
Returns the const pointer
to the incident edge. 
void
incident_edge(voronoi_edge_type*
e) 
Sets the incident edge
pointer. 
color_type
color() const 
Returns the color associated with the vertex. 
void
color(color_type
color) const 
Sets the color of
the vertex.
Allows to associate the user provided data with the primitive. 
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).
Member Types
coordinate_type 
Coordainte type. 
voronoi_edge_type

Voronoi edge type. 
color_type 
Color type (check the Important section). 
Miscellaneous
The following code snippet effectively traverses the Voronoi edges
around the
Voronoi vertex:
const
voronoi_edge<double>* edge = vertex>incident_edge();
do {
edge = edge>next();
// Do smth. with edge.
} while
(edge != vertex>incident_edge());
Voronoi Diagram Traits
The Voronoi diagram traits are used to configure the Voronoi primitive
types and predicates, used by the Voronoi diagram
data
structure.
The implementation includes default traits specialization for the
double output coordinate type.
Declaration
Header: boost/polygon/voronoi_diagram.hpp
template
<typename T>
struct
voronoi_diagram_traits;
T
 coordinate type.
Member Types
coordinate_type

Coordinate type
of the Voronoi diagram primitives. 
cell_type

Voronoi cell type. 
vertex_type

Voronoi vertex type. 
edge_type

Voronoi edge type. 
vertex_equality_predicate_type

Predicate that returns
true if the two points are considered to be equal.
False otherwise. It is used to unite nearby Voronoi vertices. 
