Re: [boost] [SoC] Summer of Code Project Ideas -- Polygon

Subject: Re: [boost] [SoC] Summer of Code Project Ideas -- Polygon
From: Mateusz Loskot (mateusz_at_[hidden])
Date: 2010-03-10 19:26:52

Simonson, Lucanus J wrote:
> Andrew Sutton wrote:
>>> 2D medial axis, veronoi diagrams and delaunay triangulation are
>>> three classical problems in computational geometry.  Veronoi
>>> diagrams are well known to be the dual graph of delaunay
>>> triangulation, so if you solve one you have solved the other.
>>> Medial axis is also related to the other two because it can also
>>> be solved with sweepline.  All three could be solved by a single
>>> generic-parameterized implementation of a sweepline algorithm.
>> 
>> I posted this much as a project idea on the wiki. I hope that a
>> good proposal would address the issues regarding floating point
>> problems. Plus, I would think that somebody would find your on the
>> problem comments and integrate them into their proposal.
> 
> I think that paragraph on its own is good enough to communicate the
> problem statement.  I know if I were a student I'd just at that.
> 
> I really want to underscore the difficulty in implementing (for
> exmaple) medial axis that is robust to floating point numerical
> issues.  Fernando's contribution to the CGAL project was exactly that
> and I think he can attest to the fact that it is not a summer
> project.  If we think back to Triangle and Shewchuk's use of Priest's
> expansions to implement Delaunay triangulation it was more than a
> summer project and there are very few students like Shewchuck out
> there.

I have pleasure to get familiar to some extent with Jonathan Shewchuck's
work together with Martin Isenburg for LiDAR data processing and such,
and it is a solid piece of complex matter indeed.

> Even my proposal for robust integer coordinate algorithms is
> an extremely challenging project that would require a solid three
> months of effort from a student who is a very strong programmer with
> quite a bit of coaching from me and code reuse from Boost.Polygon.
> It is likely that students would propose to implement a floating
> point implementation that is not robust and allow the user to
> parameterize the coordinate type to allow infinite precision floating
> point coordinates to be used to achieve robustness.  That w ould be a
> good student project, but not what I would like to see in boost, and
> I think Fernando would agree.  It does not constitute a solution to
> numerical robustness to rely heavily on infinite precision floating
> point because the runtime implications are easy two orders of
> magnitude.
> 
> This is a conversation I'll have to have with any students who submit
> proposals for implementing these algorithms.  There is a danger that
> the student will not be able to gauge difficulty or time required to
> implement their proposal and we would need to negotiate and
> compromise on a set of objectives and schedule for the project that
> is realistic but also worthwhile.

I think this kind of clear specification of requirements from a project
and mentor is in fact what candidates would eventually appreciate.

Best regards,
-- 
Mateusz Loskot, http://mateusz.loskot.net
Charter Member of OSGeo, http://osgeo.org