Subject: Re: [boost] GGL issues - fixed
From: Barend Gehrels (barend_at_[hidden])
Date: 2009-11-18 16:47:45
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).
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk