difference algorithm returning invalid geometry (regression over 1.59.0)

[Volker Schöch <vschoech@…>]

My "tc::geo::polygon" type is actually a multi-polygon, using a polygon type that is based on int, oriented counter-clockwise and open (not closed). Please consider the following example:

tc::geo::polygon<int> polygonA;
boost::geometry::read_wkt("MULTIPOLYGON(((3232 2413,2136 2646,3232 2412,3232 2413)),((3232 2532,3232 2856,1031 2856,1031 1056,3232 1056,3232 2221,2136 2328,1032 1212,1032 1458,1032 1764,2136 2790,3232 2532)))", polygonA); // does not throw
_ASSERT( boost::geometry::is_valid(polygonA) ); // returns true

tc::geo::polygon<int> polygonB;
boost::geometry::read_wkt("MULTIPOLYGON(((1032 2130,1032 1764,2052 2712,1032 2130)),((3234 2580,2558 2690,3234 2532,3234 2580)),((2558 2690,2136 2790,2052 2712,2136 2760,2558 2690)))", polygonB); // does not throw
_ASSERT( boost::geometry::is_valid(polygonB) ); // returns true

tc::geo::polygon<int> polygonC;
boost::geometry::difference(polygonA, polygonB, polygonC); // does not throw
// polygonC: MULTIPOLYGON(((3232 2413,2136 2646,3232 2412,3232 2413)),((2568 2688,3232 2580,3232 2856,1031 2856,1031 1056,3232 1056,3232 2221,2136 2328,1032 1212,1032 1458,1032 1764,2052 2712,2136 2790,2568 2688),(1032 1764,1032 2130,2052 2712,1032 1764)),((2952 2598,3232 2532,3232 2533,2952 2598)))
boost::geometry::is_valid(polygonC); // returns false!

The difference of two valid multi-polygons yields an invalid multi-polygon.

May be related to tickets #10661, #11674, #11676, #12751.

This problem was NOT present in boost 1.59.0.

[Volker Schöch <vschoech@…>]

This is urgent because I do not have a work-around. I tried correct(...), remove_spikes(...) and unique(...), to no avail. Even if you cannot fix it right away, any hints to a useful work-around are welcome!

[Barend Gehrels]

Also, not yet fixed in 1.64. Case is added to unit test suite (and also #12751). It is tested for int/open/ccw, but it also fails for double/clockwise/closed

[Volker Schöch <vschoech@…>]

Still present in boost 1.66.0.

[Volker Schöch <vschoech@…>]

No longer reproducible in 1.67.0.

[Barend Gehrels]

Thanks for verifying!