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

Subject: Re: [boost] [Review Request] Inclusion of the Boost.Polygon Voronoi Library
From: Andrii Sydorchuk (sydorchuk.andriy_at_[hidden])
Date: 2012-04-10 13:00:57

Hi Phil,

> Your message arrived at an interesting time, as I was looking for a
> Delaunay triangulation implementation yesterday and got depressed by the
> quality of what I found elsewhere.

Glad to hear!

Although your email mentions Delaunay triangulation, the impression that I
> get from the documentation (& code) is that you have not implemented this.

Voronoi diagram data structure is dual to the Delaunay graph. That means
you can retrieve all the Delaunay graph information from the Voronoi graph,
even do traversal. As this would be weird for many users we are also
planning to implement dedicated Delaunay triangulation data structure (this
is the first item in the priority list). In case you provide more details
on the task you are trying to solve I could help with the code examples.

My guess would be that this is a more popular algorithm than the Voronoi
> diagram; there are also more existing implementations that you could
> compare performance with (q-hull, s-hull etc.).

As I mentioned above it's possible to traverse Delaunay graph using Voronoi
diagram graph without any performance drawbacks (except that it's a bit
weird). Apart from that it corresponds to the medial axis transform of a
closed region. It could be also directly used for the path construction
algorithms. So construction of Voronoi graph allows to solve many more
problems than triangulation itself. Also Voronoi diagram is clearly defined
for the input data sets that contain linear segments while it's not for the
Delaunay triangulation.

Have you investigated how the output of your algorithm(s) could be used as
> input to Boost.Graph?

Not, yet :). But this is one of the items in my todo list on the main page:
http://svn.boost.org/svn/boost/sandbox/gtl/doc/voronoi_main.htm

 One practical question: what version of Boost / Boost.Polygon does your
> code require?

Voronoi code doesn't depend on the Boost.Polygon library. The intention is
to use those libraries side by side.
There is a single dependency on Boost: boost/cstdint.hpp. So I bet it
compiles with any recent version of Boost within the last 10 years.

Andrii