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