Boost logo

Geometry :

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


Geometry list run by mateusz at loskot.net