geometry
geometry copied to clipboard
boostorg
Union operation fails on 1.87/1.88 for polygon contained inside another
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:
#include <iostream>
#include <boost/geometry/geometry.hpp>
namespace
{
using PointD = boost::geometry::model::point<double, 2, boost::geometry::cs::cartesian>;
using PolygonD = boost::geometry::model::polygon<PointD>;
using MultiPolygonD = boost::geometry::model::multi_polygon<PolygonD>;
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<PolygonD>(left);
const auto right = boost::geometry::from_wkt<PolygonD>(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
<Exit code 0>
Actual (1.87/1.88):
Boost version: 108800
Failed union!
<Exit code 1>
Additional test case with a multipolygon and polygon (both double precision), tested on MSVC 19.44 (Windows 11) and GCC 13.3 (Ubuntu 24.04 LTS).
#include <iostream>
#include <boost/geometry/geometry.hpp>
namespace
{
using PointD = boost::geometry::model::point<double, 2, boost::geometry::cs::cartesian>;
using PolygonD = boost::geometry::model::polygon<PointD>;
using MultiPolygonD = boost::geometry::model::multi_polygon<PolygonD>;
constexpr auto left_18dp = "MULTIPOLYGON(((0.783769150916601043 -5.1163938907494666,0.781857192516326904 -5.116973876953125,0.777865639269108122 -5.11736701124193782,0.513933539390563965 -5.1608729362487793,0.235958516597747803 -5.18695545196533203,0.0190191095880697381 -5.19210698645635649,0.00149590335786342621 -5.1938328742980957,-0.00921905168438488798 -5.19277754172228612,-0.0431587658822536469 -5.19358348846435547,-0.322058498859405518 -5.1807255744934082,-0.599381923675537109 -5.14844369888305664,-0.753708848628811268 -5.11945158449940241,-0.778865396976470947 -5.116973876953125,-0.798333232269654913 -5.11106837311093543,-0.873777866363525391 -5.09689521789550781,-1.14390969276428223 -5.02633142471313477,-1.40846109390258789 -4.93709611892700195,-1.50613559717685952 -4.89635885237989843,-1.52923774719238281 -4.88935089111328125,-1.55160916470933685 -4.87739311639640949,-1.66614329814910889 -4.82962417602539062,-1.91570103168487549 -4.70443916320800781,-2.14138729008522821 -4.57075771252682461,-2.21610522270202637 -4.58475685119628906,-2.49344444274902344 -4.61690425872802734,-2.77235031127929688 -4.62962770462036133,-2.80477571413798943 -4.62884197602096759,-2.81506752967834473 -4.62985563278198242,-2.83207604964493731 -4.62818043745892371,-3.05146431922912598 -4.6228642463684082,-3.32942652702331543 -4.59664726257324219,-3.59050749399862967 -4.55348135659018016,-3.5954289436340332 -4.55299663543701172,-3.59781257566015134 -4.55227356855471754,-3.60488319396972656 -4.55110454559326172,-3.87649154663085938 -4.48645782470703125,-4.1429290771484375 -4.40302181243896484,-4.32532848699282813 -4.33158402584732993,-4.34580135345458984 -4.32537364959716797,-4.35845711673374936 -4.31860900589784524,-4.40289735794067383 -4.30120372772216797,-4.65512943267822266 -4.18149900436401367,-4.89839744567871094 -4.04449129104614258,-5.01468801451035162 -3.9678464236634543,-5.03734874725341797 -3.9557340145111084,-5.05481698806558821 -3.94139819241610923,-5.1315155029296875 -3.89084768295288086,-5.3533482551574707 -3.72131681442260742,-5.56281423568725586 -3.53672456741333008,-5.62619092431979961 -3.47248348097286952,-5.64349460601806641 -3.4582827091217041,-5.65979278546168363 -3.43842332237588533,-5.75889396667480469 -3.33797049522399902,-5.94063138961791992 -3.1260228157043457,-6.10714149475097656 -2.90191388130187988,-6.13207064053998518 -2.86295115949214996,-6.1409459114074707 -2.85213661193847656,-6.15087336397276641 -2.83356365907086527,-6.25761318206787109 -2.66673588752746582,-6.39131259918212891 -2.42163419723510742,-6.50758934020996094 -2.16780328750610352,-6.50963032826742083 -2.16237675135747276,-6.51058578491210938 -2.16058921813964844,-6.51176615498121425 -2.15669806018275123,-6.60587644577026367 -1.9064795970916748,-6.68569469451904297 -1.63893640041351318,-6.7331046649066888 -1.42704290659416788,-6.73820877075195312 -1.41021692752838135,-6.73926197659392923 -1.39952349927802366,-6.74665594100952148 -1.36647701263427734,-6.78846311569213867 -1.09042894840240479,-6.81091213226318359 -0.81213688850402832,-6.81259031267254667 -0.65500493574293106,-6.81506729125976562 -0.629855632781982422,-6.81506729125976562 200,-3.99875664710998535 199.999999999999972,6.81564998626708984 200,6.81689310073852539 200,6.81689310073852539 -0.628176033496856689,6.81442589824288536 -0.653225924172821992,6.81423399613715741 -0.67041344457568286,6.81286525726318359 -0.807635903358459473,6.81267536294847087 -0.810010869156255642,6.81264877319335938 -0.812392354011535645,6.80154039391911436 -0.949273440783266031,6.79061269760131836 -1.08594369888305664,6.79025831846170025 -1.08829486879951043,6.79006528854370117 -1.09067344665527344,6.76943968123390238 -1.22641855634013486,6.74900102615356445 -1.36202120780944824,6.7484822544607157 -1.36434749842209824,6.74812459945678711 -1.36670136451721191,6.74104545656158471 -1.39826896183150207,6.74003410339355469 -1.40853738784790039,6.73508127867671469 -1.42486466254944855,6.71810793061815925 -1.50055289550642001,6.6882319450378418 -1.63452363014221191,6.68755245311900204 -1.6368071036384495,6.68703126907348633 -1.63913118839263916,6.64775051868362787 -1.77056390024221066,6.60860252380371094 -1.9021230936050415,6.60776513254508213 -1.90435431112748965,6.60708332061767578 -1.90663564205169678,6.55870449967809588 -2.03507569445612191,6.51318005152041302 -2.156374962131272,6.51241111755371094 -2.15890979766845703,6.51179870401060068 -2.16005554362376584,6.51049995422363281 -2.16351604461669922,6.50951028741034854 -2.16568051447757304,6.50866985321044922 -2.16791176795959473,6.45144322446725749 -2.29267720261819496,6.39440250396728516 -2.41742920875549316,6.39326294373281812 -2.41952178832612619,6.39227008819580078 -2.42168641090393066,6.32645883961297617 -2.54219446440540553,6.26087570190429688 -2.66262507438659668,6.25959529952778926 -2.66462938608514088,6.25845193862915039 -2.66672301292419434,6.18441161620624946 -2.78232015172709479,6.15244358857917817 -2.83236214862425051,6.14277172088623047 -2.85045695304870605,6.13425367431524915 -2.86083621164039359,6.11057043075561523 -2.89790940284729004,6.10915026350440105 -2.89982365184797919,6.10786628723144531 -2.90182828903198242,6.02597564194643365 -3.01193505003995421,5.94421863555908203 -3.12213563919067383,5.94267038990564966 -3.12394383254789032,5.94124794006347656 -3.12585639953613281,5.85185422563322355 -3.23000786999649403,5.76263093948364258 -3.33421158790588379,5.76095901453287951 -3.33590871497471753,5.75940752029418945 -3.33771634101867676,5.66302514499681742 -3.43531881162376829,5.66160157609764703 -3.43676383899298665,5.64531993865966797 -3.45660305023193359,5.62828165300614902 -3.47058601706637626,5.56669187545776367 -3.53310418128967285,5.56490457351337042 -3.53468148207487687,5.5632319450378418 -3.53637528419494629,5.46024155215592177 -3.62704699775441419,5.35735559463500977 -3.71784424781799316,5.35546513529124546 -3.71929110899528981,5.35367631912231445 -3.72086596488952637,5.24459859914869497 -3.80414270209360028,5.13564300537109375 -3.88753175735473633,5.13365441640157627 -3.88884441343471599,5.13176155090332031 -3.8902895450592041,5.05646656328428268 -3.9398627739895753,5.03917407989501953 -3.95405435562133789,5.01652754736550843 -3.96615918241208476,4.9026336669921875 -4.04133987426757812,4.90055913292780154 -4.04251017432002602,4.89856910705566406 -4.04382038116455078,4.7789040563958185 -4.11113905098690946,4.65946245193481445 -4.17851924896240234,4.65731313528699609 -4.17954113686232898,4.65523481369018555 -4.1807103157043457,4.53134115656664083 -4.23943423866042846,4.40731477737426758 -4.29840230941772461,4.40509141415903649 -4.299274914272873,4.40294456481933594 -4.3002924919128418,4.35994744601193673 -4.31710864413559836,4.34762668609619141 -4.32369422912597656,4.3274912453870904 -4.32980224839137406,4.27531368515394927 -4.3502088667841754,4.14741849899291992 -4.40040397644042969,4.14514613142355337 -4.40111733364678415,4.14292716979980469 -4.40198516845703125,4.01188688252565129 -4.44295099066431476,3.88103985786437988 -4.48402738571166992,3.87872473259837491 -4.48458014969727436,3.8764493465423584 -4.48529148101806641,3.74286620957504734 -4.51701800512022711,3.60947704315185547 -4.54886627197265625,3.60712814533548931 -4.54925633298440157,3.60480928421020508 -4.54980707168579102,0.789412021636962891 -5.1154637336730957,0.783769150916601043 -5.1163938907494666)))";
constexpr auto right_18dp = "POLYGON((-3.99737668037414551 -1.28879451751708984,-3.99737668037414551 200,6.8157658576965332 200,6.8157658576965332 -0.533213794231414795,-3.99737668037414551 -1.28879451751708984))";
}
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<MultiPolygonD>(left_18dp);
const auto right = boost::geometry::from_wkt<PolygonD>(right_18dp);
MultiPolygonD result;
boost::geometry::union_(left, right, result);
if (result.empty())
{
std::cerr << "Failed union!\n";
return 1;
}
return 0;
}
Thanks for the report. Did you try it with (the beta of) 1.89? Many things have changed and improved there. Is it possible to try it?
@barendgehrels, unfortunately neither geometry case succeeds under Boost 1.89.0 Beta1. Both produce a failed union message as below:
Boost version: 108900
Failed union!
<Exit code 1>