Contents
Other ResourcesPolygon Sponsor |
Voronoi DiagramVoronoi 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 vary from Archaeology to Zoology. The Boost.Polygon library provides implementation of the Voronoi diagram data structure in 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 (the 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 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.![]() ImportantAll 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 would mean that the maximum supported value by color member is 32 times less than the one supported by std::size_t.Declaration
template
<typename T, typename TRAITS = voronoi_diagram_traits<T> > |
voronoi_diagram() |
Default constructor. |
void
clear() |
Clears 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
cells in the Voronoi diagram. This value should be the same as the size of the cell container. |
size_t num_edges() const |
Returns the number of the
edges (half-edges) in the Voronoi diagram. This value should be the same as the size of the edge container. |
size_t num_vertices() const |
Returns the number of the
vertices in the Voronoi diagram. This value should be the same as the size of the vertex container. |
coordinate_type |
Coordinate type. |
cell_type |
Voronoi cell. |
vertex_type |
Voronoi vertex. |
edge_type |
Voronoi edge. |
cell_container_type |
Container of Voronoi cells. |
const_cell_iterator |
Const cell container iterator. |
vertex_container_type |
Container of Voronoi vertices. |
const_vertex_iterator |
Const vertex container iterator. |
edge_container_type |
Container of Voronoi edges. |
const_edge_iterator |
Const edge container iterator. |
bool belongs( SourceCategory source_category, GeometryCategory geometry_category) |
Returns true if source category belongs to the given geometry category. Returns false else. |
voronoi_edge(bool is_linear, bool is_primary) |
Voronoi edge constructor. |
voronoi_cell_type* cell() |
Returns the pointer to the
Voronoi cell
that edge belongs to. |
const
voronoi_cell_type* cell() const |
Returns the const pointer
to the Voronoi cell that edge belongs to. |
void
cell(voronoi_cell_type* c) |
Sets the Voronoi cell
pointer for the cell 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 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 execute graph algorithms and associate data. |
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. |
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(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 endpoints and segment itself 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 execute graph algorithms and associate data. |
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. Could happen if a few input segments share a common endpoint. |
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). |
voronoi_vertex(const coordinate_type& x, const coordinate_type& y) |
Voronoi vertex constructor. |
const
point_type& x() const |
Returns the x-coordinate of the point that represents the vertex. |
const point_type& y() const | Returns the y-coordinate 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 executegraph algorithms and associate data. |
coordinate_type |
Coordainte type. |
voronoi_edge_type |
Voronoi edge type. |
color_type | Color type (check the Important section). |
coordinate_type |
The main 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 two points are considered to be equal. This is used to unite nearby Voronoi vertices. |
Copyright: | Copyright � Andrii Sydorchuk 2010-2012. |
---|---|
License: | Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |