THE BOOST.POLYGON VORONOI LIBRARY


The Voronoi extension of the Boost.Polygon library provides functionality to construct a Voronoi diagram of a set of points and linear segments in 2D space with the following set of limitations:
  • coordinates of the input points and endpoints of the input segments should be of the integer type;
  • input segments should not overlap except their endpoints.
While the first restriction is permanent (it allows to give the exact warranties about the output precision and algorithm execution flow), the second one may be resolved using the Boost.Polygon segment utils. The strong sides of the library and main benefits comparing to the other implementations are discussed in the following paragraphs.

Fully Functional with Segments

There are just a few implementations of the Voronoi diagram construction algorithm that can handle input data sets that contain linear segment, even considering the commercial libraries. Support of the segments allows to discretize any input geometry (sampled floating-point coordinates can be scaled and snapped to the integer grid): circle, ellipse, parabola. This functionality allows to compute the medial axis transform of the arbitrary set of input geometries, with direct applications in the computer vision projects.

Robustness and Efficiency

Robustness issues can be divided onto the two main categories: memory management issues and numeric stability issues. The implementation avoids the first type of the issues using pure STL data structures, thus there is no presence of the new operator in the code. The second category of the problems is resolved using the multiprecision geometric predicates. Even for the commercial libraries, usage of such predicates results in a vast performance slowdown. The Voronoi implementation overcomes this by avoiding the multiprecision computations in the 95% of the cases and uses the efficient, floating-point based predicates. Such preciates don't produce the correct result always, however the library embeds the relative error arithmetic apparatus to identify such situations and switch to the higher precision predicates when appropriate. As the result, the implementation has a solid performance comparing to the other known libraries (more details in the benchmarks).

Precision of the Output Structures

The Voronoi implementation guaranties, that the relative error of the coordinates of the output geometries is at most 64 machine epsilons (6 bits of mantissa, for the IEEE-754 floating-point type), while on average it's slightly lower. This means, that the precision of the output geometries can be increased simply by using a floating-point type with the larger mantissa. The practical point of this statements is explained in the following table:
Output Coordinate Type Output Coordinate Value Max Absolute Error Precise Value Range
double (53 bit mantissa) 1 2-53 * 26 = 2-47 1 ± 2-47
double (53 bit mantissa) 231 2-53 * 231 * 26 = 2-16 231 ± 2-16
long double (64 bit mantissa) 1 2-64 * 26 = 2-58 1 ± 2-58
long double (64 bit mantissa) 231 2-64 * 231 * 26 = 2-27 231 ± 2-27
Detailed description of the absolute and relative errors evaluation can be found in the article: "What Every Computer Scientist Should Know About Floating-Point Arithmetic".

During the finalization step the implementation unites the Voronoi vertices whose both coordinates are situated within the relative error range equal to 128 machine epsilons and removes any Voronoi edges between those. This is the only case, that might cause differences between the algorithm output topology and theoretically precise one, and practically means the following: for the Voronoi diagram of a set of solid bodies inside the Solar System (radius 242 metres) and the long double (64 bit mantissa) output coordinate type the maximum absolute error within the Solar System rectangle will be equal to 2-64 * 242 * 26 = 2-18 metres; as the result, vertices with both coordinates that are within 2-18 metres (8 micrometres or the size of a bacteria) will be considered equal and united.

Simple Interface

The boost/polygon/voronoi.hpp library header defines the following static functions to integrate the Voronoi library functionality with the Boost.Polygon interfaces:

template <typename Point, typename VB>
size_t insert(const Point &point, VB *vb)
Inserts a point into the Voronoi builder data structure.
Point type should model the point concept.
Returns index of the inserted site.
template <typename PointIterator, typename VB>
void insert(PointIterator first,
            PointIterator last,
            VB *vb)
Inserts an iterator range of points into the Voronoi builder data structure.
Corresponding point type should model the point concept.
template <typename Segment, typename VB>
size_t insert(const Segment &segment, VB *vb)
Inserts a segment into the Voronoi builder data structure.
Segment type should model the segment concept.
Returns index of the inserted site.
template <typename SegmentIterator, typename VB>
void insert(SegmentIterator first,
            SegmentIterator last,
            VB *vb)
Inserts an iterator range of segments into the Voronoi builder data structure.
Corresponding segment type should model the segment concept.
template <typename PointIterator, typename VD>
void construct_voronoi(PointIterator first,
                       PointIterator last,
                       VD *vd)
Constructs the Voronoi diagram of a set of points.
Corresponding point type should model the point concept.
template <typename SegmentIterator, typename VD>
void construct_voronoi(SegmentIterator first,
                       SegmentIterator last,
                       VD *vd)
Constructs the Voronoi diagram of a set of segments.
Corresponding segment type should model the segment concept.
template <typename PointIterator,
          typename SegmentIterator,
          typename VD>
void construct_voronoi(PointIterator p_first,
                       PointIterator p_last,
                       SegmentIterator s_first,
                       SegmentIterator s_last,
                       VD *vd)
Constructs the Voronoi diagram of a set of points and segments.
Corresponding point type should model the point concept.
Corresponding segment type should model the segment concept.

The following two lines of code construct the Voronoi diagram of a set of points (as long as the corresponding input geometry type satisfies the Boost.Polygon concept model):

voronoi_diagram<double> vd;
construct_voronoi(points.begin(), points.end(), &vd);

The library provides the clear interfaces to associate the user data with the output geometries and efficiently traverse the Voronoi graph. More details on those topics are covered in the basic Voronoi tutorial. Advanced usage of the library with the configuration of the coordinate types is explained in the advanced Voronoi tutorial. The library allows users to implement their own Voronoi diagram / Delaunay triangulation construction routines based on the Voronoi builder API.

No Third Party Dependencies

The Voronoi extension of the Boost.Polygon library doesn't depend on any 3rd party code and contains single dependency on the Boost libraries: boost/cstdint.hpp. All the required multiprecision types and related functionality are encapsulated as part of the implementation. The library is fast to compile (3 public and 4 private heades), has strong cohesion between its components and is clearly modularized from the rest of the Boost.Polygon library, with the optional integration through the voronoi.hpp header.

Extensible for the User Provided Coordinate Types

The implementation is coordinate type agnostic. As long as the user provided types satisfy the set of the requirements of the Voronoi builder coordinate type traits, no additional changes are needed neither to the algorithm, nor to the implementation of the predicates. For example, it's possible to construct the Voronoi diagram with the 256-bit integer input coordinate type and 512-bit output floating-point type without making any changes to the library.

Future Development

Below one may find the list of the main directions for the future development of the library.
The high-priority tasks that already have the approximate implementation plan are the following (some of those may be proposed as future GSoC projects):
  • Implement the Delaunay triangulation data structure.
    Note: only data structure needs to be implemented that properly processes events provided by the Voronoi builder.
  • Implement the medial axis transform data structure.
    Note: in general case the Voronoi diagram has completely the same geometry as the medial axis (they are 100% equal), however for many applications user is not interested in the Voronoi edges inside the hole regions. The main point of this data structure is to automatically filter the Voronoi edges that belong to those areas.
  • The Voronoi diagram data structure can be used to find the K nearest neighbors of the N sites in O(N*K*log(K) + N*log(N)) time. The return value would be a list of the k nearest neighbors for each site.
  • Use the r-tree data structure built on top of the bounding rectangles around the Voronoi cells to answer the nearest neighbor queries in log(N) time, where N is the number of the Voronoi cells.
    Note: there should be r-tree data structure available soon as part of the Boost libraries.
  • Expose O(N) interface to retrieve the convex hull of a set of points and segments from the Voronoi builder, once the Voronoi diagram is constructed.
  • Provide serialization utilities for the Voronoi diagram data structure.
High-priority tasks to be considered:
  • Drop the restriction on the non-intersecting input geometries.
  • Integrate the Voronoi diagram data structure with the BGL (Boost Graph Library).
  • Support the other types of distance metrics.
  • Construction of the constrained Delaunay triangulation.
  • Support of the circular input geometries.
Based on the community suggestions priorities may be changed.

Theoretical Research

The Voronoi library was developed as part of the Google Summer of Code 2010. The library was actively maintained for the last three years and involved the strong mathematical research in the field of algorithms, data structures, relative error arithmetic and numerical robustness. Nowadays one can often read a scientific paper, that contains non-practical theoretical results or implementation with benchmarks nobody else can reproduce. The opposite story is with the Voronoi library, that contains complete implementation of the Voronoi diagram construction algorithm and benchmarks one may run on his/her PC. Upon the community request, more documentation on the theoretical aspects of the implementation will be published. The authors would like to acknowledge the Steven Fortune's article "A Sweepline algorithm for Voronoi diagrams", that covers fundamental ideas of the current implementation.
 
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)