Re: [boost] GGL issues - fixed

Subject: Re: [boost] GGL issues - fixed
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-11-18 16:47:45

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