boost geometry booleans create self-intersecting polygons from non-self-intersecting polygons

[snubdodecahedron@…]

The attached program mimics aspects of the way in which I am trying to use the boost geometry polygon boolean operations. It repeatedly selects two polygons from a list, computes the booleans, and adds the results to the list. It also checks the results for self-intersection and reports the input and operation that lead to the failure before exiting. When I run it as is I get this result:

FAILED TO SUBTRACT MULTIPOLYGON(((0.2654871893371946 0.2880663823207319,0.349204346823061 0.3819520178855695,0.4615617830267027 0.4487295340751242,0.2851297065819251 0.2894032238012155,0.2654871893371946 0.2880663823207319))) MULTIPOLYGON(((0.4615617830267023 0.4487295340751238,0.4809248136210044 0.4662152446243423,0.4861159661340977 0.46332284819279,0.4615617830267023 0.4487295340751238))) MULTIPOLYGON(((0.4615617830267027 0.4487295340751242,0.4615617830267023 0.4487295340751238,0.2851297065819251 0.2894032238012155,0.2654871893371946 0.2880663823207319,0.349204346823061 0.3819520178855695,0.4615617830267023 0.4487295340751238,0.4615617830267027 0.4487295340751242)))

Expected result: the program completes without finding a self-intersection.

Boost SVN revision: 85565.

[snubdodecahedron@…]

program that tends to cause degeneracies that break boost boolean operators

[Barend Gehrels]

Thanks for your report and complete program.

The reported issue is fixed (not yet committed), on continue there is (at least) one issue more, I'm currently looking into that.

[Barend Gehrels]

The new version (will be released in 1.56) handles the whole program correctly. Thanks again for the report and program. The program itself is (adapted) included in libs/geometry/test/algorithms/overlay/robustness Commit 86368.

There are no self-intersections detected or (as far as known) generated. A follow-up is still needed and will be done, but I now close this ticket. Follow-up consists of checking if intersections/unions really deliver the expected results...

[snubdodecahedron@…]

Thanks for the time you have put in working on the robustness of the booleans. Unfortunately, the robustness problems I am seeing have not gone away entirely. If I increase num_rounds, more errors occur. I encounter another failure at j=20873, just beyond the limit of 20000.

FAILED TO SUBTRACT MULTIPOLYGON(((0.7509300609729007 0.8324722592358975,0.8042829718252699 0.8481560887351229,0.7181553883226776 0.6956169841898348,0.6576278983598247 0.6540915246843938,0.6555644714177575 0.6659856895021095,0.6855025369140797 0.7285736700187314,0.6508925849594112 0.6929157379629282,0.650469437358133 0.6953548780212527,0.6469179553689026 0.7158266045776277,0.7509300609729007 0.8324722592358975)),((0.511504900593046 0.5538424538852912,0.5105372544083628 0.5628807906849378,0.5501918096233597 0.6073518791834868,0.5445123657939808 0.5833143541745091,0.5246796698528305 0.5628811294974216,0.511504900593046 0.5538424538852912))) MULTIPOLYGON(((0.6704462887352797 0.4110835792097198,0.6250869964715136 0.4027148156722666,0.6024038490759296 0.3985297879223852,0.52342126908305 0.4425371508249375,0.511504900593046 0.5538424538852911,0.5246796698528302 0.5628811294974214,0.5695140188658651 0.593640160568034,0.5869867771194113 0.6056275123606045,0.6142447919437877 0.5779925880842203,0.6598645622107746 0.5930492965993388,0.631771022000775 0.6363521690156905,0.6729706290597066 0.6646175508383255,0.6815434463447968 0.6704990135792724,0.7277038215460447 0.7021677775136729,0.8728228821986608 0.8017280877181142,0.8314998368182932 0.7219628318828109,0.7915526399468964 0.6448533558260428,0.7822765383665221 0.6269478358213545,0.6704462887352797 0.4110835792097199),(0.6690841332842773 0.5788384172674677,0.6322785133517944 0.5597095058883004,0.6381969058066019 0.5537092770242282,0.6715985349232937 0.5735609032668809,0.6712665681356453 0.5754744518426989,0.6690841332842773 0.5788384172674677))) MULTIPOLYGON(((0.7181553883226776 0.6956169841898348,0.6815434463447968 0.6704990135792724,0.6729706290597066 0.6646175508383255,0.6576278983598247 0.6540915246843938,0.6555644714177575 0.6659856895021095,0.6855025369140797 0.7285736700187314,0.6508925849594112 0.6929157379629282,0.650469437358133 0.6953548780212527,0.6469179553689026 0.7158266045776277,0.7509300609729007 0.8324722592358975,0.8042829718252699 0.8481560887351229,0.7181553883226776 0.6956169841898348)),((0.5246796698528305 0.5628811294974216,0.5246796698528302 0.5628811294974214,0.511504900593046 0.5538424538852912,0.5105372544083628 0.5628807906849378,0.5501918096233597 0.6073518791834868,0.5445123657939808 0.5833143541745091,0.5246796698528305 0.5628811294974216)))