Re: [boost] GGL Review

Subject: Re: [boost] GGL Review
From: Brandon Kohn (blkohn_at_[hidden])
Date: 2009-11-17 11:46:57

Barend Gehrels wrote:
>> and has already suggested a battery of tests. I think this would be an 
>> excellent place to start.
> 
> Hi Brandon, some questions on this:

Hello Barend,

> 
> - did you look here: 
> http://geometrylibrary.geodan.nl/formal_review/sets.html Probably yes 
> but I want to be sure that you read it
> 

I have read this.

> - did you look in the tests? I don't think we need a "place to start" 
> because we already have many tests on this, in the distribution, and 
> more. I mean by this that we're started, on the way. But thanks for 
> pointing this out.

I have looked at test_overlay.hpp which seems to contain around 15 or so 
tests of very small polygons. My use cases require robust usage on 
polygonal regions (with holes) that come from CAD for airports, cities 
etc. with many operations performed sequentially and progressively on 
the outputs of previous iterations. So my point is that the tests we 
have seem inadequate in in proving more than a rudimentary level of 
robustness/correctness. Perhaps I missed more tests?

> 
> - clearly we didn't cover *all* cases, because of the bug in the (new) 
> assemble process, but we know that a lot of tests are necessary and 
> therefore we have a battery of them
> 
> - personally I don't think that batteries of random data will cover *all 
> *cases. I understand that exceptions or endless loops might become 
> clear. But with random it is difficult to verify the results. We can ask 
> Luke of course, how he verifies them, and I've no problem to add them then.
> 

Batteries of tests will never cover all cases in geometry because there 
are infinitely many input configurations. I think large numbers of tests 
on reasonably constructed random inputs does inspire more confidence 
that things work and is a good way to uncover problems. Real world use 
cases are probably the best, but these are much harder to implement in 
the sizes to really hammer the algorithm. I'll see if I can come up with 
some data to help on this.

> - it is still not clear to me if you refer to "algorithmic robustness" 
> (handling all cases) or "100% numeric stability" 

In this thread I have been talking about how it performs using native FP 
types. So what can I expect from using a double. Clearly this is where a 
majority of your users will come in. I don't expect that it will work in 
all cases as we all know it probably cannot. My own experience with FP 
boolean operations has shown them to be flawed with models of only 
moderate complexity (which I why I hesitate recommending them for 
Boost). Perhaps your algorithms fare better than the ones I've used (I 
hope!) At this point I don't know that we (from the tests you have) are 
certain if it works even when using something like GMP. We won't know 
until we test, find something that breaks using double and then works 
with GMP. I would define algorithmic robustness under this condition: 
when something works with a GMP type but fails using a native FP type. I 
don't really say 100% numeric stability anywhere do I? I think you never 
have this under native FP types. My assumption there is that numeric 
stability is defined as how the number's representation changes with use 
in arithmetic.

Regards,

Brandon