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:
> - 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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk