Boost logo

Geometry :

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

Geometry list run by mateusz at