Geometry Boost List: [ggl] Intersection of two polygons returning empty result

Subject: [ggl] Intersection of two polygons returning empty result
From: Barend Gehrels (barend)
Date: 2011-07-02 12:49:16

Hi Phillip,

On 27-6-2011 22:10, Phillip Seaver wrote:

> I think I found a bug in intersection().  I have two polygons for 
> which intersects() correctly returns true, but intersect() results in 
> an empty multi-polygon instead of the intersection:

It is solved and Trunk is updated, including your testcase in the unit 
tests.

For those who are interested: the reason was that the segment 
intersection did not found this intersection-point, for the type 
"double". For "float" it did, but not on gcc on Linux. After that, if 
there are no intersections found, it should have detected that one was 
inside the other. But I selected a "midpoint" for that, I mean a point 
halfway on a segment (usually the first segment). That midpoint happened 
to fall outside (due to FP precision). I now, if there are no 
intersection points, select the a vertex from the polygon (so not a 
midpoint), to have one of the points used for segment intersection. That 
makes it mutually consistent and solves the problem.

I also included this testcase in the union and difference test. The 
difference test returns now an empty polygon for double, a very small 
polygon for float and an even smaller polygon for ttmath high precision. 
So another codepath is used for different precisions, and the output is 
zero or nearly zero. This is also the case in SQL Server/PostGIS: SQL 
Server returns a very small polygon, PostGIS returns the empty set.

Thanks again for reporting this issue.

Regards, Barend