Boost logo

Boost :

Subject: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2012-04-09 17:03:46

Boost community,

It has been two years since I started development of the Voronoi library as
part of the Google Summer of Code 2010.
Finally I feel that the library is ready to become public and would like to
request a review for the inclusion into the Boost.Polygon library.


- Robust and efficient implementation of the sweepline algorithm that
allows to construct Voronoi diagram, Delaunay triangulation and medial axis
of a set of points and line segments.
- Coordinates of the output geometries are computed within the 64 machine
epsilon relative error (6 mantissa bits).
- Voronoi diagram data structure that allows efficient traversal and data
association with the output Voronoi graph.
- No 3rd party dependencies (e.g. GMP, MPFR), all the required multiple
precision types are implemented as part of the library.
- The input and output coordinate type domains are configurable via
coordinate type traits, thus allowing to compute coordinates of the Voronoi
vertices within any required precision.
- The full construction of the Voronoi diagram of 100 000 points takes only
0.27 seconds (see benchmarks).
The full list of features could be found here:


- Input geometries should have integer coordinates;
- Input segment data sets should not contain intersection points, except
segment's endpoints.
Information on why the first limitation is not sufficient is explained
The second limitation could be waved using native Boost.Polygon


The code is already merged with the Boost.Polygon sandbox branch. All the
Voronoi related files are prefixed with "voronoi".

- Code location:
- Main documentation page: or
- Benchmarks:
- Examples:
- Tests:
- Tutorials:
- Official Google+ page:

Review manager:

I would kindly ask Simonson, Lucanus J. the author of the Boost.Polygon
library to be my review manager.

PS. The library was designed in a user friendly way, so I would invite
everyone to give it a try!
No configuration of the geometric or predicate kernels is required. Simply
follow the basic tutorial:

Thanks and have fun,

Boost list run by bdawes at, gregod at, cpdaniel at, john at