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

Subject: Re: [boost] [SoC] Summer of Code Project Ideas -- Polygon
From: Jeffrey Hellrung (jhellrung_at_[hidden])
Date: 2010-03-10 19:41:11

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.

- Jeff