sym_difference yields bad result for int polygons

[Volker Schöch <vschoech@…>]

My "_TPolygon" type is actually a multi-polygon, based on a polygon type that is oriented counter-clockwise and open (not closed). Please consider the following example, which apparently works fine:

_TPolygon<double> polygonA; // _TPolygon<...> is actually a MULTIPOLYGON, with polygons oriented COUNTER-CLOCKWISE and OPEN (not closed).
boost::geometry::read_wkt("MULTIPOLYGON(((516 1608,1308 1932,2094 2466,2094 32767,516 32767,516 1608)))", polygonA); // does not throw
boost::geometry::correct(polygonA); // read_wkt(...) does not deal correctly with closing point

_TPolygon<double> polygonB;
boost::geometry::read_wkt("MULTIPOLYGON(((516 2484,1308 3066,2094 3150,2094 32767,516 32767,516 2484)))", polygonB); // does not throw
boost::geometry::correct(polygonB); // read_wkt(...) does not deal correctly with closing point

_TPolygon<double> polygonC;
boost::geometry::sym_difference(polygonA, polygonB, polygonC); // does not throw
// polygonC is now "MULTIPOLYGON(((516 2484,516 1608,1308 1932,2094 2466,2094 3150,1308 3066,516 2484)))"

Now, simply replace double by int:

_TPolygon<int> polygonA; // _TPolygon<...> is actually a MULTIPOLYGON, with polygons oriented COUNTER-CLOCKWISE and OPEN (not closed).
boost::geometry::read_wkt("MULTIPOLYGON(((516 1608,1308 1932,2094 2466,2094 32767,516 32767,516 1608)))", polygonA); // does not throw
boost::geometry::correct(polygonA); // read_wkt(...) does not deal correctly with closing point

_TPolygon<int> polygonB;
boost::geometry::read_wkt("MULTIPOLYGON(((516 2484,1308 3066,2094 3150,2094 32767,516 32767,516 2484)))", polygonB); // does not throw
boost::geometry::correct(polygonB); // read_wkt(...) does not deal correctly with closing point

_TPolygon<int> polygonC;
boost::geometry::sym_difference(polygonA, polygonB, polygonC); // does not throw
// polygonC is now "MULTIPOLYGON(((516 2484,516 1608,1308 1932,2094 2466,2094 *!*32725*!*,1308 3066,516 2484)))"

As you can see, one value is completely off. This seems to happen reliably whenever the input is based on int and contains large numbers. However, the particular example worked well with boost 1.55.0.

This issue may be related to Ticket #8380.

[Volker Schöch <vschoech@…>]

Note for think-cell: RT 10356

[Volker Schöch <vschoech@…>]

Problem is still present in 1.57.0.

[mkaravel]

The problem was in the computation of the intersection points. In particular, integer overflow was taking place, yielding the wrong results.

The problem has been fixed by locally promoting the coordinates to a number type with increased precision, thus avoiding the overflow.

[mkaravel]

See also tickets #10835 and #11121.

[vschoech@…]

A related issue came up in boost 1.59.0, see Ticket #11675.