boostorg / boostorg/geometry

Union operation fails on 1.87/1.88 for polygon contained inside another

Open
#1,414 9 comments 0 reactions 1 assignee Claimed by @barendgehrels View on GitHub
Dominant language
C++
Stars
517
Forks
232
PR merge metrics
No merged PRs in 30d

Description

Two very similar polygons, one contained inside the other and sharing most of their boundaries, fail to union with an empty result on Boost Geometry 1.87/1.88. This has been seen on several similar polygons with several output results, and with `double` as well as `float` (but more frequently with `float`). (Will aim to get a repro for the other cases.) May be related to https://github.com/boostorg/geometry/issues/1179 and issues discussed on https://github.com/boostorg/geometry/issues/1326?

Sample code:

```c++

#include

#include

namespace
{
using PointD = boost::geometry::model::point;
using PolygonD = boost::geometry::model::polygon;
using MultiPolygonD = boost::geometry::model::multi_polygon;

constexpr auto left = "POLYGON((-5.25274381859899275 -4.52961012931200813,-5.27276992797851562 -4.52604150772094727,-5.38840895471426951 -4.49698665904955153,-5.50441169738769531 -4.46909141540527344,-5.52382088290200901 -4.46296377600689986,-5.54354953765869141 -4.45800685882568359,-5.65690592687416149 -4.42094773374811467,-5.77065420150756836 -4.38503646850585938,-5.78958235194242921 -4.37757239103052331,-5.80892372131347656 -4.37124919891357422,-5.91942893502130207 -4.32636902811645196,-6.03038549423217773 -4.28261470794677734,-6.04874829337681064 -4.27384775155736651,-6.06759977340698242 -4.26619148254394531,-6.17470285239787131 -4.21371323081857518,-6.28233909606933594 -4.16232442855834961,-6.30004513638044106 -4.15229815300153415,-6.31831693649291992 -4.14334535598754883,-6.42151556188408534 -4.08351394508694732,-6.52528762817382812 -4.02475166320800781,-6.5422459884409756 -4.0135181313621997,-6.55985450744628906 -4.00330924987792969,-6.65863598680389046 -3.93641924134296239,-6.75804805755615234 -3.87056684494018555,-6.77418487381549372 -3.85817516068456356,-6.79103469848632812 -3.84676527976989746,-6.88488241654563993 -3.77316898751263574,-6.97948646545410156 -3.70052123069763184,-6.99472373166573824 -3.68703036105832371,-7.01073217391967773 -3.67447638511657715,-7.09921336059751518 -3.59451665531879128,-7.18852329254150391 -3.51544284820556641,-7.20278024434805708 -3.50092410359540684,-7.21787643432617188 -3.48728179931640625,-7.30057056792506831 -3.40133810845253848,-7.3841404914855957 -3.31623363494873047,-7.39735028531863215 -3.30075532522986093,-7.41145753860473633 -3.28609371185302734,-7.4879625250160764 -3.19458225939063967,-7.56538486480712891 -3.10386419296264648,-7.57747973845038203 -3.08750622936935093,-7.59053325653076172 -3.07189226150512695,-7.66047615793803427 -2.97525599440222566,-7.73137378692626953 -2.87936902046203613,-7.74229895507661059 -2.86220592755773229,-7.75423049926757812 -2.84572076797485352,-7.81725793288383208 -2.74444774915597645,-7.88129854202270508 -2.64384198188781738,-7.89099969098570408 -2.62595886221418029,-7.90175247192382812 -2.60868120193481445,-7.95757234465154628 -2.50323868370350588,-8.01442813873291016 -2.39843058586120605,-8.02285597720197963 -2.37991933023627666,-8.03238010406494141 -2.36192846298217773,-8.08069768878802996 -2.25287338448372099,-8.13011550903320312 -2.14433002471923828,-8.13723612630849047 -2.12526345163399988,-8.14547634124755859 -2.10666489601135254,-8.1860585878252099 -1.99453362938381895,-8.22779464721679688 -1.88277876377105713,-8.2335673037449677 -1.86326409797093784,-8.24049091339111328 -1.84413373470306396,-8.2731544422179617 -1.72943840203467247,-8.3069915771484375 -1.6150507926940918,-8.31138843429243224 -1.59518283940184502,-8.31696128845214844 -1.57561421394348145,-8.34154786272891968 -1.4589022881186724,-8.36731910705566406 -1.34245049953460693,-8.37031941613592956 -1.32232435866405851,-8.37451362609863281 -1.30241453647613525,-8.39089604014550261 -1.18429590146914321,-8.40848541259765625 -1.06630599498748779,-8.41007463260087818 -1.04601657610821941,-8.41286945343017578 -1.02586567401885986,-8.42097307670853645 -0.906877188745636609,-8.43028736114501953 -0.787962615489959717,-8.43045736426508086 -0.767615901357998509,-8.43183994293212891 -0.747314989566802979,-8.43183994293212891 -0.602142862433404646,-8.43262004852294922 -0.508776426315307617,-8.43262004852294922 200,-8.43183994293212891 200,-3.99802279472351074 200.000000000000028,8.43217563629150391 200,8.43255996704101562 200,8.43255996704101562 -0.494636744260787964,8.43217563629150391 -0.552158964847365041,8.43217563629150391 -0.733273923397064209,8.43083024569497397 -0.753521605664023264,8.430694580078125 -0.773826479911804199,8.42157484662831735 -0.892812291981363915,8.41366481781005859 -1.0118556022644043,8.41090908427688966 -1.03196925327965827,8.40935802459716797 -1.05220603942871094,8.3919695884970853 -1.17020555368200174,8.37576675415039062 -1.2884674072265625,8.37161286171393293 -1.30834815939842986,8.36865520477294922 -1.32841908931732178,8.3430719398817903 -1.4449465432952624,8.31866455078125 -1.56176161766052246,8.31313857815368884 -1.58128795421430346,8.30878448486328125 -1.60112011432647705,8.2751230423953448 -1.71561799808520754,8.24263763427734375 -1.83040702342987061,8.23576113175318092 -1.84950576815094681,8.23003578186035156 -1.8689802885055542,8.18849039923230038 -1.98079513364194804,8.14805698394775391 -2.0930945873260498,8.13986079273406915 -2.11167639109297456,8.13279438018798828 -2.13069486618041992,8.083537993644482 -2.2393673115462831,8.03538131713867188 -2.34854459762573242,8.02591729795222975 -2.36649360610361237,8.01753425598144531 -2.38498878479003906,7.96080919940144049 -2.48997452788163809,7.90516185760498047 -2.59551262855529785,7.89446234508253131 -2.61276812602704922,7.88481521606445312 -2.63062286376953125,7.82092375066371837 -2.73136652267432689,7.75803136825561523 -2.83279538154602051,7.74615485221751232 -2.84926164926920489,7.73528528213500977 -2.86640071868896484,7.66451941503564083 -2.96244559648261507,7.59470748901367188 -3.05923676490783691,7.58171158255647359 -3.07483407523397156,7.56967258453369141 -3.09117364883422852,7.49236572697147984 -3.18206438198501074,7.4159855842590332 -3.27373361587524414,7.40193777975455802 -3.28838176027518481,7.38878440856933594 -3.30384635925292969,7.30531899860366796 -3.38912959297699112,7.22273683547973633 -3.47524094581604004,7.20769904451141752 -3.4888756478326024,7.19350099563598633 -3.50338292121887207,7.10429569398104821 -3.58263103218167211,7.01590204238891602 -3.66277718544006348,6.99995038254807866 -3.67532920892092596,6.98477458953857422 -3.68881106376647949,6.89025989784421977 -3.76164232952203248,6.79648923873901367 -3.83542847633361816,6.77969956284503894 -3.8468380699513407,6.76362133026123047 -3.85922765731811523,6.66425731450845937 -3.9252880143191935,6.5655674934387207 -3.99235367774963379,6.54802430884225473 -4.00256341217270339,6.53111982345581055 -4.01380205154418945,6.42737954927161059 -4.07277591823044371,6.32426166534423828 -4.13278818130493164,6.30605038360545311 -4.14174864938445619,6.28840160369873047 -4.15178155899047852,6.18080373790224336 -4.20337355788833911,6.07374763488769531 -4.25604820251464844,6.05495330616528982 -4.26371746236455795,6.03664970397949219 -4.27249383926391602,5.9257442723762761 -4.31644281742883873,5.81524562835693359 -4.36153316497802734,5.7959543899484034 -4.36787521912813581,5.77709054946899414 -4.3753504753112793,5.66340436795687641 -4.41145144784223486,5.55001497268676758 -4.44872856140136719,5.53033111943042943 -4.453708770814651,5.51098918914794922 -4.45985078811645508,5.39503576895230719 -4.48793983163642896,5.27934789657592773 -4.51721000671386719,5.25937033879491267 -4.52080399524124132,5.23964118957519531 -4.52558326721191406,0.806275486946105957 -5.43700981140136719,0.698281184464580873 -5.45530918629051875,0.590559184551239014 -5.47523307800292969,0.560666561191082602 -5.47862765331744228,0.531003296375274658 -5.48365402221679688,0.421974743470873048 -5.49437735233467262,0.313146263360977173 -5.50673580169677734,0.283093028941384828 -5.50803684273937488,0.253148019313812256 -5.51098203659057617,0.143654165321626587 -5.51407332060959643,0.0342115163803100586 -5.51881122589111328,0.00413145950397833528 -5.51801239385488973,-0.0259367339313030243 -5.51886129379272461,-0.135367826503244193 -5.51430773002559249,-0.244886055588722229 -5.51139926910400391,-0.274834938722497479 -5.5085043301510046,-0.304891318082809448 -5.50725364685058594,-0.413742570649886454 -5.49507714781704948,-0.522786736488342285 -5.48453664779663086,-0.552460684631768673 -5.47955963248305267,-0.582356631755828857 -5.47621536254882812,-0.69009323829644198 -5.45647543337597618,-0.798136711120605469 -5.4383540153503418,-5.23295402526855469 -4.53436899185180664,-5.25274381859899275 -4.52961012931200813))";
constexpr auto right = "POLYGON((8.43415260314941406 200,8.43415260314941406 -0.607523918151855469,8.35729408264160156 -1.38788521289825439,8.12967109680175781 -2.13825750350952148,7.76003170013427734 -2.82980489730834961,7.26257991790771484 -3.43595099449157715,6.65643405914306641 -3.93340229988098145,5.96488666534423828 -4.30304193496704102,5.21451425552368164 -4.53066492080688477,4.43415307998657227 -4.60752391815185547,3.65379190444946289 -4.53066492080688477,2.90341949462890625 -4.30304193496704102,2.8771314054349082 -4.28899066417358021,2.82921433448791504 -4.34737777709960938,2.2230682373046875 -4.84482908248901367,1.53152096271514893 -5.21446895599365234,0.78114849328994751 -5.44209194183349609,0.000787202909123152494 -5.51895046234130859,-0.779574096202850342 -5.44209194183349609,-1.52994644641876221 -5.21446895599365234,-2.22149372100830078 -4.84482908248901367,-2.82763981819152832 -4.34737777709960938,-2.87175421157238198 -4.2936242396423534,-2.90329647064208984 -4.31048393249511719,-3.65366888046264648 -4.53810691833496094,-4.43403005599975586 -4.61496543884277344,-5.21439123153686523 -4.53810691833496094,-5.96476364135742188 -4.31048393249511719,-6.65631103515625 -3.94084405899047852,-7.26245689392089844 -3.44339275360107422,-7.75990867614746094 -2.83724665641784668,-8.12954807281494141 -2.14569950103759766,-8.35717105865478516 -1.39532697200775146,-8.43403053283691406 -0.614965677261352539,-8.43403053283691406 200,8.43415260314941406 200))";

}

int main(int argc, char** argv)
{
std::cout << "Boost version: " << BOOST_VERSION << '\n';

// Works with Boost 1.77
// Fails with Boost 1.87/1.88

const auto left = boost::geometry::from_wkt(left);
const auto right = boost::geometry::from_wkt(right);

MultiPolygonD result;
boost::geometry::union_(left, right, result);

if (result.empty())
{
std::cerr << "Failed union!\n";
return 1;
}

return 0;
}

```

Expected (1.77):

```

Boost version: 107700

```

Actual (1.87/1.88):

```

Boost version: 108800
Failed union!

```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.