Voronoi Diagram

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 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.

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 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> >
class voronoi_diagram;

T - specifies the coordinate type of the Voronoi vertices.
TRAITS - Voronoi diagram traits (explained in the end of this chapter).

Member Functions

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.

Member Types

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.

Voronoi Geometry Type

GeometryCategory

Defines geometry type of the input objects.

enum GeometryCategory {
GEOMETRY_CATEGORY_POINT = 0x0,
GEOMETRY_CATEGORY_SEGMENT = 0x1
};

SourceCategory

Defines category of the input site that forms Voronoi cell.

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
};

Voronoi diagram data structure doesn't store coordinates of the input geometries. Instead it links with those via source index and source category method of the Voronoi cell primitive. Source index is incrementally given (starting from zero) to each input site inserted into Voronoi builder. Considering the fact that each input segment is splitted onto three separate sites with the same index, we distinguish between them using SourceCategory. For the example see Voronoi basic tutorial.

Member Functions

bool belongs(
SourceCategory source_category,
GeometryCategory geometry_category)

Returns true if source category belongs to the given geometry category.
Returns false else.

Voronoi Edge

Voronoi edge is represented as enhanced classical half-edge data structure.

Declaration

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 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.

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

Voronoi cell is represented by a site the cell contains and a pointer to the incident edge.

Declaration

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 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.

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

Voronoi vertex is represented by a point that corresponds to the vertex and a pointer to the incident edge.

Declaration

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 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.

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

Voronoi diagram traits are used to configure Voronoi diagram data structure.

Declaration

template <typename T>
struct voronoi_diagram_traits;

T - coordinate type.

Member Types

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)

Contents

Other Resources

Polygon Sponsor

Voronoi Diagram

Important

Declaration

Member Functions

Member Types

Voronoi Geometry Type

GeometryCategory

SourceCategory

Member Functions

Voronoi Edge

Declaration

Member Functions

Member Types

Voronoi Cell

Declaration

Member Functions

Member Types

Miscellaneous

Voronoi Vertex

Declaration

Member Functions

Member Types

Miscellaneous

Voronoi Diagram Traits

Declaration

Member Types