Contents

Other Resources

Polygon Sponsor

Voronoi Builder

Voronoi builder is the event generator structure. It implements the sweepline algorithm that scans a 2D space and generates two types of events: site events and circle events (we won't go into details what those are exactly). Each event is reported to the output data structure builder. The structure shares Voronoi name as the events generated by it correspond to the Voronoi diagram edges and vertices, thus giving enough information to construct the Voronoi diagram of a set of points and linear segments. The requirements for the input/output coordinate type of the builder geometries are not the same as for the rest of the Boost.Polygon library. The main differences are in the following:
  • The input coordinate type is not required to be integral (while it still should be an integer type)
  • The output coordinate type (for Voronoi vertices) is required to be IEEE-754 floating point type

Important

We encourage users to use default static methods defined in the voronoi.hpp header to construct Voronoi diagram, however it's always possible to use Voronoi builder explicitly, especially if the user wants to drop the external dependencies such as MPL (metaprogramming library). So the following include set woudn't depend on any heavy external headers (except STL and boost/cstdint.hpp), even Boost.Polygon itself:

#include <voronoi_builder.hpp>
#include <voronoi_diagram.hpp>

This also gives a way to build Voronoi construction API on top of the Voronoi builder data structure for the other Boost libraries.

Declaration

template <typename T,
          typename CTT = detail::voronoi_ctype_traits<T>,
          typename VP = detail::voronoi_predicates<CTT> >
class voronoi_builder;

T - specifies the coordinate type of the input geometries (points and segments).
CTT - defines input/output coordinate type traits used by Voronoi predicates (VP).
VP - predicate kernel, that provides builder with 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 set up of the coordinate type traits. Default voronoi_predicates<CTT> structure provides correct and efficient predicates as soon as types defined by CTT satisfy the requirements explained at the end of this page. In case those requirements are not satisfied for the user provided coordinate type traits, the proper predicates kernel implementation is required.

Member Functions

voronoi_builder() Default constructor.
size_t insert_point(const int_type& x,
                    const int_type& y)
 Inserts a point object with the specified coordinates into the Voronoi builder.
Returns index number of the inserted site.
size_t insert_segment(const int_type& x1,
                      const int_type& y1,
                      const int_type& x2,
                      const int_type& y2)
 Inserts a segment object with the specified coordinates into the Voronoi builder.
Returns index number of the inserted site.
template <typename OUTPUT>
void construct(OUTPUT* output)
 Runs sweepline algorithm over the set of the inserted geometries, outputs site and circle events to the OUTPUT data structure. It's responsibility of the output data structure to process them.
void clear()
 Clears the list of the inserted geometries. Sets index counter to zero.

Voronoi Coordinate Type Traits

The library provides the default coordinate type traits specialization for the 32-bit signed integer type:

template <typename T>
struct voronoi_ctype_traits;

template <>
struct voronoi_ctype_traits<int32> {
    typedef int32 int_type;
    typedef int64 int_x2_type;
    typedef uint64 uint_x2_type;
    typedef extended_int<128> big_int_type;
    typedef fpt64 fpt_type;
    typedef extended_exponent_fpt<fpt_type> efpt_type;
    typedef ulp_comparison<fpt_type> ulp_cmp_type;
    typedef type_converter_fpt to_fpt_converter_type;
    typedef type_converter_efpt to_efpt_converter_type;
};

 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 predicates user should define following set of coordinate types (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 for voronoi of points.
At least 64X-bit signed integer type for voronoi of 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().

Notes:

  • Four different integer types are used (instead of a single big_int_type) to slightly improve algorithm performance and memory usage.
  • As the maximum required size of the big_int_type is known in advance (based on the size of the integer type), library provided implementation of a fixed integer could be used (it is much faster than heap-allocated big integers).
  • Two separate floating-point types are defined because for the input with 32-bit signed integer coordinates double won't be able to handle 2048-bit (64 * 32) integers as they will overflow its exponent. On the gcc compiler it's possible to use 80-bit long doubles for both fpt types, however this is not supported by MSVC compiler.
  • efpt_type and to_efpt_converter_type are not used to construct Voronoi diagram of points (mocks will work fine).
  • For an example of the user defined coordinate type traits see advanced Voronoi tutorial.
 
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)