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