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

Subject: [ggl] Re: Problems with the difference between two polygons
From: Barend Gehrels (barend)
Date: 2011-08-04 08:15:24

Hi Angus,

> Firstly, to introduce myself as a newcomer to the list, I'm the author of
> Clipper.

Welcome to the list!

>
> It's interesting to see that Clipper returns a smaller numbers of vertices
> in these tests.
> It's possible this is due to errors in Clipper's code but, given that
> Clipper spends very considerable 'post processing' time checking for
> polygons sharing common edges and merging them, I suspect that Clipper may
> in fact return 'simpler' solutions. Enrico, Is there any way to assess the
> correctness of (and hence the simplicity of) these results? 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 agree that the tests should be run in an optimal way for each library.

In Boost.Geometry's robustness test I verify the correctness of outputs 
by taking the area of the input polygons (p and q), and of the union (u) 
and the intersection (i), and the following should equal: area(p) + 
area(q) = area(u) + area(i)

If it this fails, there is of course an error. If it does not fail, the 
chance is high that the output is correct (but you still don't know for 
sure).

> Also Enrico, when you update your comparisons, I think it'd be helpful to
> include both GGL timings (ie with and without self-intersection testing).

With the (current, provisionally) define, I understand this suggestion. 
But the define will go next Friday, and the self-intersection will not 
be there as a separate step in the process. It is only tested on 
failure. IMO, if you want to show more lines, you might show the test 
with double vs. ttmath (high precision), also because Enrico already 
does these tests.

> Otherwise, it would be interesting to include a new test that evaluated this
> feature.

There are many things which could be tested... In our past test suite we 
also tested on area, envelope, centroid, convex hull...

Regards, Barend