The Voronoi builder is the event generator structure, that implements
the sweepline
algorithm,
scanning 2D space and spawning the two types of events: site
events and circle events. Each event is reported to the output data
structure builder.
The structure shares Voronoi name, as the events generated by it
provide
enough information to construct the Voronoi diagram of a set of points
and linear segments. The requirements for the coordinate type of
the input/output geometries, configured through the coordinate type
traits template argument, are the following:
Тип входной координаты (для входных точек и точек входных сегментов) не обязательно должен быть интегральным (хотя он все равно должен быть целым типом).
Тип выходной координаты (для вершин Вороноя) должен быть типом плавающей точки IEEE-754.
Important
The users are encouraged to use the default static methods defined in
the voronoi.hpp
header for the Voronoi diagram construction. However it's also possible
to
use Voronoi builder explicitly, especially if the user wants to drop
the external dependencies such as MPL (metaprogramming library). The
following include set doesn't depend on any external headers
(except STL and boost/cstdint.hpp), even
the Boost.Polygon library:
T
- specifies the coordinate type of the input geometries (points and
segments). CTT
- defines the input/output coordinate type traits used by the Voronoi
predicates (VP). VP
- the predicate kernel, that contains robust and
efficient predicates and functors.
The Voronoi builder data structure is ready to use from the box with
32-bit signed integer input coordinate type. The user may extend the
input coordinate range to the other integer types (e.g. 64-bit
integer), however this will also require manual setup of the
coordinate type traits. Default predicate kernel provides correct and
efficient predicates as long as types
defined by the coordinate type traits satisfy the requirements
explained at the end of this page. In case
those
requirements are not satisfied,
the proper predicate kernel
implementation is required.
Member Functions
voronoi_builder()
Default
constructor.
size_t insert_point(const int_type& x, =2>
Вставляет точечный объект с заданными координатами в строитель Voronoi. Индекс возврата вставленной точки.
nbsp&n;bsp&pn;b
Вставляет сегментный объект с заданными координатами в Voronoi Builder. Индекс возврата вставленного сегмента.
Runs the sweepline
algorithm over the set of inserted geometries and generates site and
circle events to the OUTPUT data structure. It's the responsibility of
the
output data structure to process them.
Complexity: O(N * log N), where N is the total number of input points and segments.
void
clear()
Clears the
list of the inserted geometries. Sets the input geometry index to
zero.
Voronoi Coordinate Type Traits
Библиотека предоставляет специализацию характеристик по умолчанию для 32-битного подписанного целого типа:
One
of the most important features of the library is that Voronoi builder
output geometries are constructed within defined relative error (64
machine epsilons). That means, the more mantissa bits the user provided
fpt_type has, the better precision of the output geometries will be. In
order for the user defined traits to be consistent with the default
Voronoi builder predicate kernel user should define the following set
of traits (the assumption is made that input geometries have
X-bit signed integer coordinate type):
int_type
At least X-bit signed
integer type.
int_x2_type
At least 2X-bit signed
integer type.
uint_x2_type
At least 2X-bit unsigned
integer type.
big_int_type
At least 8X-bit signed
integer type if input dataset contains only points.
At least 64X-bit signed integer type if input dataset contains
segments.
fpt_type
IEEE-754 floating point
type, with mantissa at least (X+16) bits and exponent able to handle
32X-bit unsigned integer type.
efpt_type
IEEE-754 floating point
type, with mantissa at least (X+16) bits and exponent able to handle
64X-bit unsigned integer type.
ulp_cmp_type
Ulp comparison structure,
that checks if two fpt_type values are within the given ulp range
(relative error range).
to_fpt_converter_type
Type converter structure,
that converts any of the integer types above plus efpt_type to the
fpt_type using operator().
to_efpt_converter_type
Type converter structure,
that converts any of the integer types above to the efpt_type using
operator().
Примечания:
Используются четыре различных типа целых чисел (вместо одного большого_int_type), чтобы немного улучшить производительность алгоритма и использование памяти.
Поскольку максимальный требуемый размер большого_int_типа известен заранее, можно использовать фиксированный, выделенный стек, многоточный целочисленный тип.
Определены два отдельных типа с плавающей точкой, потому что для входных геометрий с 32-битными подписанными целочисленными координатами двойной тип не сможет обрабатывать 2048-битные (64 куска по 32 бита каждый) целые числа, поскольку они будут переполнять его показатель. На компиляторе gcc можно использовать 80-битные длинные двойники для обоих типов fpt, однако это не поддерживается компилятором MSVC.
efpt_type и to_efpt_converter_type не используются для построения диаграммы Вороноя набора точек (работает реализация мака).
