[boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library

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.

Features:

- 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:
http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_main.htm

Limitations:

- 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
here:
http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_advanced_tutorial.htm
The second limitation could be waved using native Boost.Polygon
functionality:
http://svn.boost.org/svn/boost/sandbox/gtl/doc/gtl_polygon_set_concept.htm

Resources:

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

- Code location: http://svn.boost.org/svn/boost/sandbox/gtl
- Main documentation page:
http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_main.htm or
http://svn.boost.org/svn/boost/sandbox/gtl/doc/index.htm
- Benchmarks:
http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_benchmark.htm
- Examples:
http://svn.boost.org/svn/boost/sandbox/gtl/libs/polygon/example/output_data/
- Tests: http://svn.boost.org/svn/boost/sandbox/gtl/libs/polygon/test/
- Tutorials:
http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_basic_tutorial.htm
 and
http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_advanced_tutorial.htm
- Official Google+ page: https://plus.google.com/b/109395909314556242008/

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:
http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_basic_tutorial.htm

Thanks and have fun,
Andrii