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.
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()
Конструктор по умолчанию.
void
clear()
Удаляет все примитивы с диаграммы Вороноя.
const
cell_container_type& cells()
const
Возвращает ссылку на контейнер ячейки.
const
vertex_container_type& vertices()
const
Возвращает отсылку к вершинному контейнеру.
const
edge_container_type& edges()
const
Возвращает конст-ссылку на крайний контейнер.
size_t
num_cells() const
Возвращает число ячеек Вороноя на диаграмме Вороноя.
size_t
num_edges() const
Возвращает число краев Вороноя (полукраев) на диаграмме Вороноя.
size_t
num_vertices()
const
Возвращает число вершин Вороноя на диаграмме Вороноя.
Member Types
coordinate_type
Координационный тип.
cell_type
Ячейка Воронои.
vertex_type
Вершина Вороной.
edge_type
Вороной край.
cell_container_type
Контейнер ячеек Вороной.
const_cell_iterator
Итератор контейнеров Const Cell.
vertex_container_type
Контейнер вершин Вороноя.
const_vertex_iterator
Const vertex контейнерный итератор.
edge_container_type
Контейнер по краям Вороной.
const_edge_iterator
Const edge контейнерный итератор.
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.
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:
Клетка края относится (Воронская ячейка P, с исходным сегментом MN)
Начальная точка края (вершина Вороноя B, то есть равноудаленная от следующих входных площадок: O, L, MN)
Конечная точка края (вертикаль Вороной) A, то есть равноудаленная от следующих входных площадок: O, M, MN
Двойной край (Voronoi edge AB)
Следующий край CCW внутри ячейки Вороноя, к которому принадлежит край (зеленый край Вороноя AE)
Предыдущий край CCW внутри ячейки Вороноя, к которому принадлежит край (Voronoi edge CB)
CCW вращается вокруг начальной точки края (Voronoi edge BC)
CCW вращает предыдущий край вокруг начальной точки края (бесконечный край Вороноя, начинающийся в вершине В Вороноя и идущий в восточном направлении)
Возвращает указатель в ВоронойЯчейка, к которой принадлежит край.
const
voronoi_cell_type* cell()
const
Возвращает указатель const к ячейке Вороноя, к которой принадлежит край.
void
cell(voronoi_cell_type*
c)
Устанавливает указатель ячейки Voronoi на ячейку, к которой принадлежит текущий край.
voronoi_vertex_type*
vertex0()
Возвращает указатель в начальную точку края. Если край бесконечен в этом направлении, возвращается NULL.
const
voronoi_vertex_type* vertex0()
const
Возвращает указатель const к вершине начальной точки края. Если край бесконечен в этом направлении, возвращается NULL.
void
vertex0(voronoi_vertex_type*
v)
Устанавливает начальный указатель края.
voronoi_vertex_type*
vertex1()
Возвращает указатель в конечную точку края. Если край бесконечен в этом направлении возвращается NULL.
const
voronoi_vertex_type* vertex1()
const
Возвращает указатель const в конечную точку края. Если край бесконечен в этом направлении, возвращается NULL.
voronoi_edge_type*
twin()
Возвращает указатель на двойной край.
const
voronoi_edge_type* twin()
const
Возвращает указатель const к близнецовому краю.
void
twin(voronoi_edge_type*
e)
Устанавливает двойной указатель края.
voronoi_edge_type*
next()
Возвращает указатель к следующему краю CCW в соответствующей ячейке Вороной. Края не обязательно имеют общую вершину (например, бесконечные края).
const
voronoi_edge_type* next()
const
Возвращает указатель const к следующему краю CCW в соответствующей ячейке Voronoi. Края не обязательно имеют общую вершину (например, бесконечные края).
void
next(voronoi_edge_type*
e)
Устанавливает CCW следующий указатель края.
voronoi_edge_type*
prev()
Возвращает указатель к предварительному краю CCW в соответствующей ячейке Voronoi. Края не обязательно имеют общую вершину (например, бесконечные края).
const
voronoi_edge_type* prev()
const
Возвращает указатель const к предварительному краю CCW в соответствующей ячейке Voronoi. Края не обязательно имеют общую вершину (например, бесконечные края).
void
prev(voronoi_edge_type*
e)
Устанавливает CCW prev edge pointer края.
color_type
color() const
Возвращает цветовую ценность.
void
color(color_type
color) const
Устанавливает цвет края. Позволяет связать предоставленные пользователем данные с примитивными.
voronoi_edge_type*
rot_next()
Возвращает указатель к следующему краю CCW, повернутому вокруг начальной точки края. Работает также для бесконечных краев.
const
voronoi_edge_type* rot_next()
const
Возвращает указатель const к следующему краю CCW, повернутому вокруг начальной точки края. Работает также для бесконечных краев.
voronoi_edge_type*
rot_prev()
Возвращает указатель на CCW prev edge, повернутый вокруг начальной точки края. Работает также для бесконечных краев.
const
voronoi_edge_type* rot_prev()
const
Возвращает указатель const к предварительному краю CCW, повернутому вокруг начальной точки края. Работает также для бесконечных краев.
bool
is_finite() const
Возвращается истинным, если обе конечные точки края конечны, иначе ложны.
bool
is_infinite() const
Возвращается истинно, если одна из конечных точек края бесконечна, а другая ложна.
bool
is_linear() const
Возвращается истинным, если край линейный (сегмент, луч, линия), иначе ложный.
bool
is_curved() const
Возвращается истинным, если край искривлен (параболическая дуга), иначе ложным.
bool
is_primary() const
Возвращается ложно, если край проходит через конечную точку сегмента сайта, иначе верно.
bool
is_secondary() const
Возвращается истинно, если край проходит через конечную точку сегмента сайта, иначе ложно.
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
Координационный тип.
voronoi_cell_type
Тип клеток Воронои.
voronoi_vertex_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).
Возвращает индекс входного сайта среди других сайтов. И сегмент, и его конечные точки будут иметь одинаковый индекс.
source_category_type
source_category()
const
Возвращает входную категорию сайта среди других сайтов. Позволяет различать сегментный сайт и его конечные точки.
voronoi_edge_type*
incident_edge()
Возвращает указатель к одному из краев границы.
const
voronoi_edge_type* incident_edge()
const
Возвращает указатель const к одному из краев границы.
void
incident_edge(voronoi_edge_type*
e)
Устанавливает указатель краевого края ячейки.
color_type
color() const
Возвращает цвет, связанный с клеткой.
void
color(color_type
color) const
Устанавливает цвет клетки. Позволяет связать предоставленные пользователем данные с примитивными.
bool
contains_point()
const
Возвращается истинно, если ячейка содержит точечный сайт, иначе ложно.
bool
contains_segment()
const
Возвращается истинным, если ячейка содержит сайт сегмента, иначе ложным.
bool
is_degenerate()
const
Возвращается верно, если ячейка не имеет края инцидента. Может произойти, если несколько входных сегментов имеют общую конечную точку.
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
Координационный тип.
source_index_type
Тип исходного индекса.
source_category_type
Source category type.
voronoi_edge_type
Вороной край типа.
color_type
Тип цвета (проверьте важный раздел).
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).
Возвращает x-координату точки, которая представляет вершину.
const
point_type& y() const
Возвращает Y-координату точки, которая представляет вершину.
voronoi_edge_type*
incident_edge()
Возвращает указатель края инцидента.
const
voronoi_edge_type* incident_edge()
const
Возвращает указатель const на край инцидента.
void
incident_edge(voronoi_edge_type*
e)
Устанавливает указатель края инцидента.
color_type
color() const
Возвращает цвет, связанный с вершиной.
void
color(color_type
color) const
Установите цвет вершины. Позволяет связать предоставленные пользователем данные с примитивными.
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
Координированный тип.
voronoi_edge_type
Вороной край типа.
color_type
Тип цвета (проверьте важный раздел).
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.
Предикат, который возвращается истинным, если два пункта считаются равными. В противном случае — ложно. Используется для объединения близлежащих вершин Вороноя.
