Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Ronald Garcia (rxg_at_[hidden])
Date: 2012-04-12 09:57:39
I've received your request and will add it to the review queue. Please let me know if Lucanus agrees to manage the review.
On Apr 9, 2012, at 5:03 PM, Andrii Sydorchuk wrote:
> 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: http://svn.boost.org/svn/boost/sandbox/gtl
> - Main documentation page:
> http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_main.htm or
> - Benchmarks:
> - Examples:
> - Tests: http://svn.boost.org/svn/boost/sandbox/gtl/libs/polygon/test/
> - Tutorials:
> - 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:
> Thanks and have fun,
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk