difference algorithm returning invalid geometry

[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). I am using boost 1.70.0. Please consider the following example:

tc::geo::polygon<int> polygonA;
boost::geometry::read_wkt("MULTIPOLYGON(((529 3217,529 998,5337 998,5337 1834,5070 2000,5337 2072,5337 3475,529 3475,529 3312,1734 2054,2934 1670,3230 1690,2934 1400,1734 1784,529 3217),(4140 2582,5071 2001,4140 1754,3231 1691,4140 2582)))", polygonA); // does not throw
boost::geometry::is_valid(polygonA); // returns true

tc::geo::polygon<int> polygonB;
boost::geometry::read_wkt("MULTIPOLYGON(((528 3218,528 2498,1734 1406,2556 1522,1734 1784,528 3218)),((4610 2288,5340 1178,5340 1832,4609 2289,4140 3002,2934 1574,2555 1521,2934 1400,4140 2582,4610 2288)))", polygonB); // does not throw
boost::geometry::is_valid(polygonB); // returns true

tc::geo::polygon<int> polygonC;
boost::geometry::difference(polygonA, polygonB, polygonC); // does not throw
// polygonC: MULTIPOLYGON(((2553 1521,1734 1406,529 2498,529 998,5337 998,5337 1183,4839 1939,4140 1754,3231 1691,4140 2582,3230 1690,2934 1400,2555 1521,2556 1522,2553 1521)),((1734 1784,529 3217,529 3216,1734 1784)),((3020 1676,4140 3002,4609 2289,5071 2001,5337 2072,5337 3475,529 3475,529 3312,1734 2054,2934 1670,3020 1676)))
boost::geometry::is_valid(polygonC); // **** returns false! ****

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

See also:
https://svn.boost.org/trac10/ticket/11674
https://svn.boost.org/trac10/ticket/10661
https://svn.boost.org/trac10/ticket/9768

[barendgehrels]

I have to postpone this issue until rescaling removal is finished. I know that in this usecase rescaling is not used, because integer coordinates are used, but the code changes to remove rescaling are broader than floating point only

[barendgehrels]

(Oops, sorry for the click on the wrong milestone )

[vschoech]

Confirmed that this issue is still present in boost 1.72.0. Looking forward to the next milestone!

[vschoech]

Confirming that this issue is still present in boost 1.73.0. Looking forward to the next milestone!

[mloskot]

Moving this to milestone 1.76

[vschoech]

Confirming that this issue is still present in boost 1.75.0. Looking forward to the next milestone!

[vissarion]

@vschoech is this still present in 1.79.0 (rescaling is removed). Sorry I cannot reproduce your issue because of the tc::geo::polygon type.

[vschoech]

@vissarion Thank you for looking into this. I'll check as soon as we update our boost library (we'll wait for 1.80 because there will be another fix we need), and let you know.

In the meantime, you can reproduce for yourself if you want. tc::geo::polygon isn't doing any magic. As described above, it is a multi-polygon, using a polygon type that is based on int, oriented counter-clockwise and open.

[vissarion]

This is still present in 1.79.0.
side note: for double instead of int the result is correct.

[vschoech]

@vschoech is this still present in 1.79.0 (rescaling is removed).

We updated our code base to 1.79 and I can now confirm that this issue is still present.

[vschoech]

⚠️ Still reproducible in boost 1.83.0.

The input values of our unit test have slightly changed, but I presume the error is still the same. The difference of two valid multi-polygons yields an invalid multi-polygon:

tc::geo::polygon<int> polygonA;
boost::geometry::read_wkt("MULTIPOLYGON(((529 3313,1734 2054,2934 1670,3231 1691,4140 2582,5070 2001,5337 2071,5337 3475,529 3475,529 3313)),((529 3217,529 998,5337 998,5337 1834,5070 2001,4140 1754,3231 1691,2934 1400,1734 1784,529 3217)))", polygonA); // does not throw
boost::geometry::is_valid(polygonA); // returns true

tc::geo::polygon<int> polygonB;
boost::geometry::read_wkt("MULTIPOLYGON(((528 3218,528 2498,1734 1406,2556 1522,1734 1784,528 3218)),((4610 2288,5340 1178,5340 1832,4609 2289,4140 3002,2934 1574,2555 1521,2934 1400,4140 2582,4610 2288)))", polygonB); // does not throw
boost::geometry::is_valid(polygonB); // returns true

tc::geo::polygon<int> polygonC;
boost::geometry::difference(polygonA, polygonB, polygonC); // does not throw
// polygonC: MULTIPOLYGON(((4608 2290,5070 2001,5337 2071,5337 3475,529 3475,529 3313,1734 2054,2934 1670,3020 1676,4140 3002,4608 2290)),((2554 1522,1734 1406,529 2497,529 998,5337 998,5337 1183,4839 1940,4140 1754,3231 1691,2934 1400,2555 1521,2556 1521,2554 1522),(4140 2582,3230 1690,3231 1691,4140 2582)),((5070 2001,5337 1833,5337 1834,5070 2001)))
boost::geometry::is_valid(polygonC); // **** returns false! ****