Voronoi Diagram

### Contents Boost.Polygon Main Page Design Overview Isotropy Coordinate Concept Interval Concept Point Concept Segment Concept Rectangle Concept Polygon 90 Concept Polygon 90 With Holes Concept Polygon 45 Concept Polygon 45 With Holes Concept Polygon Concept Polygon With Holes Concept Polygon 90 Set Concept Polygon 45 Set Concept Polygon Set Concept Connectivity Extraction 90 Connectivity Extraction 45 Connectivity Extraction Property Merge 90 Property Merge 45 Property Merge Voronoi Main Page Voronoi Benchmark Voronoi Builder Voronoi Diagram ### Other Resources GTL Boostcon 2009 Paper GTL Boostcon 2009 Presentation Performance Analysis Layout Versus Schematic Tutorial Minkowski Sum Tutorial Voronoi Basic Tutorial Voronoi Advanced Tutorial ### 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 (half-edges) 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 one-dimenstion curve, that contains points equidistant from the two closest input geometries. The Voronoi edge data structure is implemented as the enhanced classical half-edge 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 x-coordinate of the point that represents the vertex.
const coordinate_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 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.
Copyright: | Copyright © Andrii Sydorchuk 2010-2013.
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)