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