boost::geometry:sym_difference fails when called with two polygons with almost identical points

[Johan Doré <jdh@…>]

Dear Boost Contributors,

First of all thanks a lot for all your great work.

I ran into a special case which seems to fail using e.g. boost::geometry:sym_difference.

In the below example I have the two polygons shown in the attached image. Their points are distributed like on an ellipse. The first polygon having 6 points, while the second have 12 points on an ellipse with "almost" identical parameters.

Now using those two polygons causes e.g sym_difference to wrongly returns 0 polygons.

void Test_SymDifference() {

typedef boost::geometry::model::polygon<boost::geometry::model::d2::point_xy<double> > polygon;

polygon Poly1, Poly2;

boost::geometry::read_wkt("POLYGON((16.4030230586813990 21.4147098480789640, 17.3451877762964380 14.8677773110138890, 11.9421647176150360 6.4530674629349205, 5.5969769413186015 4.5852901519210345, 4.6548122237035621 11.1322226889861170, 10.0578352823849610 19.5469325370650790, 16.4030230586813990 21.4147098480789640, 16.4030230586813990 21.4147098480789640))", Poly1);

boost::geometry::read_wkt("POLYGON((16.4030230586814020 21.414709848078967, 17.7828326880709360 18.936596729241124, 17.3451877762964410 14.867777311013885, 15.2073549240394820 10.298488470659295, 11.9421647176150340 6.4530674629349125, 8.4245222359685457 4.3618917414181650, 5.5969769413185944 4.5852901519210292, 4.2171673119290620 7.0634032707588670, 4.6548122237035567 11.132222688986115, 6.7926450759605128 15.701511529340699, 10.0578352823849570 19.546932537065082, 13.5754777640314510 21.638108258581831, 16.4030230586814020 21.414709848078967))", Poly2);

boost::geometry::model::multi_polygon<polygon> Result;

sym_difference(Poly1, Poly2, Result);

_ASSERTE(Result.size() > 0);

}

If it is something I am doing wrong or if I can be of additional help please let me know

Best regards

Johan

[Johan Doré <jdh@…>]

Plot showing the two polygons

[Barend Gehrels]

Thanks for your report and for your nice words.

I was able to reproduce your issue on the development branch, so indeed it fails in Boost 1.55 and all lower versions.

There was already a current action to make all overlay operations more robust, which is done in a separate git-branch. Your cases is tested there, and added as a standard unit test. It is already fixed by these actions, so that is good news.

I mark this bug as fixed, though it still has to be merged back (somewhere coming weeks) in the development branch and (later) master branch. But it will be available in Boost 1.56

[anonymous]

Great.

I downloaded the 1.56 beta and checked that it is now working.

Thanks a lot for all your great work.

Best regards

Johan