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-14 18:10:43

>
> Sure, I've looked at the benchmarks.  They compare Voronoi diagram
> generation with CGAL.  I'm interested in Delaunay triangulation generation,
> for which s-hull is possibly the fastest existing implementation.  I'd like
> to see a comparison with that.

I meant that I actually compared Voronoi diagram construction with CGAL's
Delaunay triangulation construction, as they don't have dedicated data
structure for diagrams. That also means that they don't compute coordinates
of the Voronoi vertices and I didn't penalize them for that in the
benchmark results.

> If you need a robust, fast Delaunay triangulation routine as source try
> S-Hull-Pro. <http://www.s-hull.org/index_files/commercial.html>

Do you want me to compare robust implementation Voronoi provides with
non-robust of S-hull? I can do that, but is it fair?

Fast is a relative term.  The GPU in my phone can draw tens of millions of
> triangles per second.  Could this code supply triangles quickly enough?
>  Probably not.

It's not a magic box to generate triangulation in O(1) time :-).

 Faster is always better.

Yes, I did profiling and know a few places that will improve performance in
total by 20-30%. However most of those are not connected with the
algorithm, but rather with STL data structures used. So I may end up with
STL independent library this way :-).

Regards,
Andrii