On Mon, Nov 16, 2009 at 6:34 PM, Phil Endecott <spam_from_boost_dev@chezphil.org> wrote:
A while ago, Fernando Cacciola posted some links to a set of presentations and papers about FP line intersection robustness that I found very enlightening: ....
I strongly encourage anyone who wants to express an opinion on this subject in the context of the current review to look at this material; it is very accessible and on page 2 there's a compelling example of what can go wrong.
I include a the end of this message he 24/3/2009 email on geometry robustness as it provides a succinct opinion. It's unfortunate that this email encouraged a confrontational approach rather than the common boost cooperation approach !
Personally, I find it better to use fixed point (e.g. for latitude/longitude) and relax knowing that I don't have to worry.
One thing is to answer what is the best library design for multiple application domains and the other one is what is typical in each domain. Is it common to use fixed point in the GIS domain ? I think libraries have to capture common practice so that is easy to migrate to them --------------------------- 24/3/2009 email on Geometry Robustness by Fernando Cacciola -------------------------- Hi boost geometers ;) When Barend first presented his geometric library proposal I argued that the so-called "epsilon-based" approach used by the library is just fundamentally wrong, and most importantly, totally unnecessary since much better methodologies exist. It deeply worries me to find that the GGL proposal haven't been updated in this regard, because the instrumentation of the proper techniques have a significant impact on the overall design. Robustness can't be treated as an implementation detail to be deal with later on (and I'm sorry if I haven't made this point clear when I warn about it before). If I where to review the library today I would have to strongly vote for rejection because of this. Here is a simple example of the fundamental problems I see all over the proposed library: There is a point_in_circle algorithm, which (as I can see from its implementation), essentially returns whether the distance from the point to the center is smaller than the circle radius. No doubt *that* is the one and only correct *mathematical* formulation for the predicate, but is one that just doesn't stand in practice at all. Computing *that very particular predicate ROBUSTELY* has been the subject of active research during the past decade, to such an extent, that pretty much every paper or article on the subject of robustness in geometric computing uses the in-circle test as a common example. The library proposed by Lucannus, OTOH, at least acknowledges the problem appropriately and approaches a solution in the right direction (there is still some important design-influencing considerations but are not showstopers) Here is a starting point http://www.mpi-inf.mpg.de/departments/d1/ClassroomExamples/ Best