Hi list, Herewith explanations and backgrounds about this report this morning. Brandon, thanks for sending it.
I'm trying to run a test that will take the boolean difference of two polygons, but haven't been able to find an explicit difference function. So I've tried instead to get the difference by taking: A & !B (the intersection of A and the negation of B, where negation is done by reversing the winding.) Anyway, when I tried this I got a crash when the winding was reversed on B. I've attached a text with the test.
Both A and B were reversed, so in fact !A & !B was tested in the first case, and !A & B in the second case. The library does not test orientation, and that is on purpose. This behaviour is the same for self-intersections which are also not tested during intersections on purpose. The GGL is original built with OGC conventions in mind, polygons are clockwise, closed and non-self-intersecting. We added support for orientation (clockwise, counter clockwise or undetermined) and here the test was done with a polygon defined clockwise. The input should therefore be clockwise. GGL is not testing if it is really clockwise, on purpose, for performance reasons. When using the "undetermined" option, it should be tested (and reversed is necessary). However, that is currently not yet there (though trivial) because the counter clockwise option is also not there yet, they will both be applied when we add the (symmetric) difference. On A & B the behaviour is correct. As explained earlier, A&!B is not yet supported but will be. Theoretically and conceptually it is the same as A & reversed(B), but apparently we have to make a few more changes than only apply the reverse iterator, especially in paths to be taken. A&!B were not included in the submission, and therefore they are not tested (besides one simple case to verify conceptually). It is therefore not strange and does not really surprise me that if reverse polygons are tested now, errors are reported, you might get others, this is untested, valid input is assumed. So, having all information now, you should currently test with clockwise oriented polygons (so contrary to what I said earlier today). We will implement the difference (A&!B) and symmetric difference (A xor B), we will implement intersections for counter clockwise polygons, but in this submission it is not and we knew that beforehand. I wanted to research this case further, because of the small differences in input coordinates in this testcase, resulting in a difference in behaviour of our algorithm using float, double and long double. I therefore worked out the GMP and CLN types in the intersections. As I mailed earlier these high precision arithmetic types were in area, centroid and a few other algorithms but not yet in intersections. That is done now. Using GMP the behaviour is again different, all because these differences in input data (normally they are, of course, the same). Both double and GMP give the same output, but there are intersection points detected in the GMP/CLN which are not in the double version. This is why I mentioned "challenging conditions" above (and "to the limits"); I didn't mean the two reversed polygons of course (at that moment I didn't know that). This testcase is interesting because it shows differences detected intersection points (not in intersected polygons). In GMP and in CLN they are exactly the same, in float, double and long double they are all a little different amongst each other. Still, they give the same output polygon with this testcase. Again, about robustness, we *are *aware of the problems which might occur and we have our approach, using high precision arithmetics to avoid these from happening, either in coordinate type, or only in the calculations. In summary, our robustness approach, using GMP and CLN, have be applied easily, is done today. On valid input, nothing goes wrong. On invalid input, things go wrong on purpose, GGL contains functions to correct wrong windings (ggl::correct). Regards, Barend