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-11 16:34:10

Jeffrey Hellrung wrote:
> Mateusz Loskot wrote:
>> Simonson, Lucanus J wrote:
> [...]
>>> 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.
> [...]
> 
> FWIW, I have working implementations of Schewchuk's expansion
> arithmetic algorithms (in free functions and classes utilizing these
> free functions), both for fixed-sized expansions (with error
> estimates) and arbitrary-sized expansions, if you (or anyone) is
> interested.  It's not self-contained (depends on some other
> components of our code base), but could be a good starting point if
> you're looking in that direction.  We currently use it in an adaptive
> context to "robustify" our geometric predicates.  Of course, it isn't
> 100% robust, as overflow and underflow could happen, but so far it
> has not failed.  It's also not going to be as efficient as the
> "tricks" Shewchuk uses in his triangulation (I'm guessing), but it
> still gets you somewhere.

Jeffrey, I'd be interested in taking look at it myself.
Perhaps you could push it to the Sandbox?

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