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

Subject: [ggl] Re: Problems with the difference between two polygons
From: Simonson, Lucanus J (lucanus.j.simonson)
Date: 2011-08-16 07:19:39

Angus Johnson wrote:
> 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.) 

GTL handles self-intersecting polygons and applies positive winding rule.  EvenOdd and NonZero are easy for me to provide, since the rule applied is parameterized as a functor.  No one ever asked for these.  Positive winding was most useful for my own purposes.

Thanks,
Luke