Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at