Boost logo

Geometry :

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.


Geometry list run by mateusz at