Re: [boost] [GGL] performance and bug

Subject: Re: [boost] [GGL] performance and bug
From: Simonson, Lucanus J (lucanus.j.simonson_at_[hidden])
Date: 2009-11-15 17:44:42

Barend Gehrels wrote:
> Luke,
>> That said, I feel you owe me an apology for publishing misleading
>> benchmark results
> 
> I've sent you the results, off-list, long before publishing them,
> including a report showing where things went wrong at your side. There
> were months for you to improve things before the figures were
> published. 
> 
> Our benchmark compares 6 libraries, not only 2. It's comparing 7
> algorithms, not only 1. If you found them misleading you could have
> objected easily before publishment. It's surprising to read this now.
> And not necessary, after acceptance of your library.
> 
> We've done our comparisons in a careful and honest way. We didn't hack
> things in frenetically to find bug X. Our website says: "We are aware
> of 
> the weaknesses of performance tests and that it is hard to design
> objective benchmarks. So, this comparison is not considered to be
> objective in terms of intentions. However, we did what we can to
> achieve 
> most comparable results." and "Therefore, everyone can review it and
> provide his critique as well as point bugs and weaknesses". So yes, we
> know that things can go wrong. Maybe I didn't discover option Y in
> library Z which speeds things up.
> 
> We're happy to read that you'll replace your algorithm with ours. I'd
> modify your tone then, otherwise you might prevent acceptance. I don't
> think it wise for me to react on more of your attempts to avoid that.

Not replace, but put along side, so calling a boolean op on polygons with integer would call my algorithm, but with floating point would call yours.  Even so, I will have to add compile time static asserts to prevent all the unsupported operations from being called on floating point polygons.  Your implementation cannot keyhole holes to outer shells or slice polygons into trapezoids.  You also don't support the n-layer map overlay operation, so I'd have to ensure that the users get a good error msg if they try to call it on floating point.  However, I won't integrate your algorithm into my library until your algorithm is ready to be used.  I am using that as my criteria for judging whether your library should be accepted into boost.  I am not trying to prevent acceptance of your library, but I do think that there are issues that need to be addressed before the library is accepted.  Given the unfinished state of the polygon clipping I'm a little confused that you felt now to be a good time to bring the library for review.  I fully expect your library will be accepted to boost eventually, either in this review, contingent on a list of changes or in a follow up review several months from now.

So now I'll discuss robustness.  I looked at the implementation of line segment pair intersection.  You are actually solving for the intersection itself and using the intersection point in the intermediate stages of the algorithm, even special casing the unfortunate circumstance where numberical error results in the intersection point being equal to one of the input segment end points.  It looks to me like the predicate for determining whether two line segments intersect produced as a byproduct of computing the intersection point is not robust.  Your suggestion that self intersecting output polygons can be cleaned up by pushing them back through the algorithm is therefore not a valid solution for the robustness problem.  I'd like to see the code that determines whether a pair of line segments intersect enhanced such that the result is robust for floating point coordinates.  I'd also like to see the method for doing so described in the documentation.  If we can be confident that the algorithm will find self intersections when the output is fed back through then I would accept that as a solution for the self-intersection/robustness issue.

I'll summarize my review presently.

Thanks,
Luke