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-06-28 14:56:37

Hi Phillip,

Thanks for the report.

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:
>
> 537.99678544791459, 124.30517362077681
> 437.36539413622404, 142.02728895075373
> 456.33031803043468, 249.50296671450121
> 556.96217263181723, 231.78347688272990
> 537.99678544791459, 124.30517362077681
>
> and
>
> 437.35, 142.03
> 461.94, 281.32
> 564.5, 263.26
> 539.9, 123.97
> 437.35, 142.03
>
> The first polygon is the result of intersecting several other 
> polygons, which is why there are so many numbers after the decimal 
> place.  When I cut it down to two numbers after the decimal, it worked 
> correctly.
>
> (These polygons are all from a PDF file.  Each time you set a clipping 
> path in a PDF, the result is the intersection of the current clipping 
> path and the new path)
>
> I also have a relatively short program that intersects those polygons, 
> if you want it.  I updated my copy from the boost trunk from this 
> morning after finding the problem.  It occurred with the older code 
> and the newer code.

Right, I can reproduce it. This is indeed an issue. I will see if it can 
be solved. However, if you are using high precision arithmetic, the 
intersection will result in a valid multi-polygon with one polygon. I'm 
using this polygon-type now:

     typedef boost::geometry::model::d2::point_xy<ttmath_big> point;

which runs OK. It gives me an area of 
11151.661763015599545531972518842496488 (Don't use ttmath::Big<1,4> 
because its default constructor is non-defined instead of zero). 
ttmath_big is defined in the extensions/contrib folder

But I'll check (probably next weekend) what is the exact reason for 
failing with a double type, and if it (hopefully) can be solved.

Regards, Barend