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-07 14:56:44

Hi Enrico.

On 7/08/2011 8:39 AM, Enrico Leoni wrote:
> >It's interesting to see that Clipper returns a smaller numbers of 
> vertices
> >in these tests.

> However, in the first test other differences emerge. In the attached 
> example (svg file) the black poligon is an intersection and these are 
> the vertices returned:
> Clipper
> 51600,0
> 25800,-44686
> 26450,-45812
> 52900,0
>
> Gtl
> 52900,0
> 51600,0
> 25800,-44686
> 25799,-44686
> 26449,-45812
> 26450,-45812
> 52900,0
>
> Ggl
> 52900,0
> 26450,-45812
> 26449.711324944485,-45812
> 25799.615099925981,-44686
> 25800,-44686
> 51600,0
> 52900,0
>

I've rearranged the vertices above (see below) since Ggl's are 
counter-clockwise to the other two, and also removed duplicate vertices 
and I get the following ...

Gtl:
51600,0
25800,-44686
25799,-44686
26449,-45812
26450,-45812
52900,0

Ggl:
51600,0
25800,-44686
25799.615099925981,-44686
26449.711324944485,-45812
26450,-45812
52900,0

Clipper:
51600,0
25800,-44686
26450,-45812
52900,0

You can see that if the vertices returned by Ggl are then rounded 
they'll produce duplicate vertices. Once they're removed, the result is 
exactly that which is returned by Clipper. So it seems that Clipper is 
returning the correct and simplest solution.

I'm not sure of the significance of your SVG image. It looks very 
different to the image I get from the coordinates above. Is this showing 
some sort of error with Clipper??

> >Also, depending
> >on the degree of precision you're using in these tests, I suspect that
> >Clipper could be optimised by setting the UseFullCoordinateRange 
> property to
> >false.
>
> I wasn't aware of this setting and I am going to use it in the next 
> update.

When this is enabled it allows users to enter coordinates using the full 
Int64 range (using an internal Int128 class to do math on 64bit integers 
safely), but this adds roughly a 20% time penalty.

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?

Regards
Angus