Geometry Boost List: [ggl] Re: Problems with the difference between two polygons

Subject: [ggl] Re: Problems with the difference between two polygons
From: Angus Johnson (awj1958)
Date: 2011-08-15 00:06:32

Hi again Enrico.

On 14/08/2011 9:01 AM, Enrico Leoni wrote:
> If you are interested I can bring a case where the result is not what 
> I expect:
> C = A - B     (see attached file)
>
> I tried to scale A and B by a factor of 1000 and maybe 1000000 but C
> is never "clean" as I expect. Cases like this show problems with
> several libraries.

I would expect this extraneous 'noise' (for want of a better word) 
regardless of precision since ellipse coordinates can only ever be 
fractional approximations. I would've expected all libraries to generate 
some noise at any level of precision though it seems that you've 
encountered some libraries that clean this up pretty well.

>> Thanks for all your efforts in doing these tests. The results are very
>> interesting. Would you consider adding one more test that benchmarked
>> self-intersecting polygons too?
> I have tried. In the source code of my benchmark you can find a test
> similar to the one implemented in your benchmark. However there is a
> problem ... only four libraries can execute that test without throwing
> an exception (Clipper, Gpc, Gtl, KBool), only Gpc and Clipper give
> comparable results but sometimes Gpc gives less polygons (it is
> difficult to say which one is correct). So in the end I have commented
> those lines of code ...

 From my (admittedly brief) inspection of the various libraries, I 
believe only Clipper and GPC are capable of reliably handling 
self-intersecting polygons and I'm confident that they are the ones 
generating the correct results. However, only Clipper accepts both 
polygon fill modes - EvenOdd & NonZero - that are used by all the widely 
used graphics rendering libraries (GDI, GDI+, XLib, OpenGL, Cairo, AGG, 
Quartz, Graphics32) and also in SVG. (GPC only accepts EvenOdd filling.)

Finally, I see you've just updated your benchmarks again, and they seem 
even more impressive!
Thank you again for all your efforts there.

Angus