Re: [boost] [polygon] [GSOC] voronoi diagram of line segments

Subject: Re: [boost] [polygon] [GSOC] voronoi diagram of line segments
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2010-10-26 18:27:53

Thomas Klimpel wrote:
> I agree with Luke's assessment. Even the popular Qhull code
> <http://www.qhull.org/> only computes Voronoi diagrams of points. Of
> course, CGAL implements Voronoi diagrams of line segments
> <http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Segment_Delaunay_graph_2/Chapter_main.html>,
> but CGAL is not "free". I didn't see a "free" implementation in
> <http://www.geom.uiuc.edu/software/cglist/>, but I think
> <http://www.cosy.sbg.ac.at/~held/projects/vroni/vroni.html> is at
> least another non-"free" implementation for Voronoi diagrams of line
> segments.        

Thanks for the link to vroni, I didn't know of its existence.

> I recall Barend Gehrels
> complained that the student doing the spatial indexing GSOC project
> was publicly shot down
> <http://lists.boost.org/Archives/boost/2008/10/143220.php> and
> subsequently lost any motivation to continue working on his project.

I watched the whole thing play out with the GSOC 2006 spacial indexes project.  That particular GSOC project was a special case in that it would have been reasonable for the mentor to fail the student, in my opinion, based on lack of progress and poor quality of the code.  That's a tough call for a mentor to make, and I hope I'm never in the position where I have to make it.  I feel very fortunate to have found a strong student this year.

> It's not clear to me whether scarce positive feedback is even worse
> than abundant feedback also containing open critique, but working on
> such a project may depend more on inner motivation than on external
> feedback anyway. However, I wonder whether also posting to the
> Boost.Geometry mailing list
> <http://lists.osgeo.org/mailman/listinfo/ggl> would be a good idea,
> at least when the code is ready for review and experimentation. It
> might generate a bit more feedback, because the people there are at
> least interested in computational geometry. (But more feedback will
> normally also contain open critique, so you better be prepared.) As
> far as I can see, the only relation between Boost.Polygon and the
> sweepline project at the current moment is that both rely on integer
> coordinates to provide robustness (and of course the mentor), so that
> the project is not too closely tied to Boost.Polygon anyway.         

Should Andrii eventually provide for floating point numerical robustness I would expect that his work could be integrated into Boost.Geometry, perhaps as an extension that depends on minimal Boost.Polygon detail header files authored by Andrii.  As you say, he has not coupled his implementation to my library so far.  We will need to figure out the policies about cross library dependency between Polygon and Geometry, but that can wait until the first instance of such is suggested.

Regards,
Luke