difference returns wrong results if double is the data type

[yurik42]

The sample code:

static const char p1_wkt[] = "POLYGON((-124.19999999845255 51.901455507812500, -124.19999999460376 51.935823093966235, -123.99999999648789 51.935823093966235, -123.99999999317222 51.902564290309876, -124.19999999845255 51.901455507812500))";
static const char p2_wkt[] = "POLYGON((-123.99999999367975 51.907655109375000, -123.99999999291659 51.900000006653443, -124.19999999861555 51.900000005468293, -124.19999999792353 51.906179355468751, -123.99999999367975 51.907655109375000))";

TEST_F( SpatialOperationF, t3_double )
{
    using point = boost::geometry::model::point<double, 2, boost::geometry::cs::cartesian>;
    using polygon = boost::geometry::model::polygon<point>;
    using polygon_vector = std::vector<polygon>;

    auto left = boost::geometry::from_wkt<polygon>( p1_wkt );
    auto right = boost::geometry::from_wkt<polygon>( p2_wkt );

    {
        THIS_IS_A_BUG();

        polygon_vector actual;
        boost::geometry::difference( left, right, actual );
        EXPECT_EQ( 0, actual.size() );
    }
    {
        polygon_vector actual;
        boost::geometry::intersection( left, right, actual );
        EXPECT_EQ( 1, actual.size() );
    }
    {
        polygon_vector actual;
        /* swap arguments */
        boost::geometry::difference( right, left, actual );
        EXPECT_EQ( 1, actual.size() );
    }
}

The same code ran with float data type produces expected results (1 polygon in difference results)

[vissarion]

I can reproduce it. For double this is a bug and should be fixed. It is probably created by inaccuracies in computation (maybe in azimuth) for almost colinear points.

Interestingly with long double it returns slightly different results i.e.
MULTIPOLYGON(((-124.2 51.9015,-124.2 51.9015,-124.2 51.9358,-124 51.9358,-124 51.9026,-124 51.9026,-124 51.9077,-124.2 51.9062,-124.2 51.9015)))

looks like a spike but if you zoom in it isn't

This is caused because the three points with longitude around -124.2 are not colinear.

EDIT: ubuntu 22.04, develop branch, gcc-9

[JohanDore]

Hi All,

I believe I hit this same issue and thought I may help by creating a few test cases showing to help:

BOOST_AUTO_TEST_CASE(Boost_Diffence_ClearAll)
{
	using PointXY = boost::geometry::model::d2::point_xy<double>;
	using Polygon = boost::geometry::model::polygon<PointXY>;
	using MultiPolygon = boost::geometry::model::multi_polygon<Polygon>;

	MultiPolygon polyA;
	read_wkt("MULTIPOLYGON((("
	    "-2.0785311235613415 -0.6304193410175202,"
      "-2.0534946127981359 -0.6304193410175202,"
      "-2.0534946127981359 -0.8867932112327471,"
      "-2.3098684830133629 -0.8867932112327471,"
      "-2.3098684830133629 -0.6554558517807265,"
      "-2.2848319722501573 -0.6554558517807265,"
      "-2.0785311235613415 -0.6554558517807265,"
      "-2.0785311235613415 -0.6304193410175202)))", polyA);

	MultiPolygon polyB;
	read_wkt("MULTIPOLYGON((("
			"-2.0785311235613420 -0.6304193410175202,"
			"-2.0534946127981359 -0.6304193410175202,"
			"-2.0534946127981359 -0.6554558517807265,"
			"-2.0785311235613420 -0.6554558517807265,"
			"-2.0785311235613420 -0.6304193410175202)))", polyB);

	MultiPolygon polyAB;
	//Clip off the small polyB appendix top/left in part polyA
	difference(polyA, polyB, polyAB);

	//Without an error we should get:
	//BOOST_CHECK_CLOSE(area(polyAB), area(polyA) - area(polyB), 0.0001);
	//BOOST_CHECK_EQUAL(polyAB.size(), 1u);
	//BOOST_CHECK(polyAB[0].inners().empty());

	//But we get this:
	BOOST_CHECK(polyAB.empty());
}

BOOST_AUTO_TEST_CASE(Boost_Diffence_ClearsTooMuch)
{
	using PointXY = boost::geometry::model::d2::point_xy<double>;
	using Polygon = boost::geometry::model::polygon<PointXY>;
	using MultiPolygon = boost::geometry::model::multi_polygon<Polygon>;

	MultiPolygon polyA;
	read_wkt("MULTIPOLYGON((("
		"-6.1723606999999996 3.2834021000000000,"
		"-6.1723606999999996 2.8006724999999992,"
		"-5.7133718999999994 2.8006724999999992,"
		"-5.7133718999999994 3.2834021000000000,"
		"-5.6896310999999997 3.2834021000000000,"
		"-5.6896310999999997 2.7769316999999996,"
		"-6.1961014999999993 2.7769316999999996,"
		"-6.1961014999999993 3.2834021000000000,"
		"-6.1723606999999996 3.2834021000000000)))", polyA);

	MultiPolygon polyB;
	read_wkt("MULTIPOLYGON((("
		"-6.1723606999999996 2.8006724999999997,"
		"-5.7133718999999994 2.8006724999999997,"
		"-5.7133718999999994 2.7769316999999996,"
		"-6.1723606999999996 2.7769316999999996,"
		"-6.1723606999999996 2.8006724999999997)))", polyB);

	MultiPolygon polyAB;
	//Clip off the small polyB at the bottom center part of polyA
	difference(polyA, polyB, polyAB);

	//Without an error we should get:
	//BOOST_CHECK_CLOSE(area(polyAB), area(polyA) - area(polyB), 0.0001);
	//BOOST_CHECK_EQUAL(polyAB.size(), 2u);
	//BOOST_CHECK(polyAB[0].inners().empty());
	//BOOST_CHECK(polyAB[1].inners().empty());

	//But we get this:
	BOOST_CHECK_CLOSE(area(polyAB), 0.5*(area(polyA) - area(polyB)), 0.0001);
	BOOST_CHECK(polyAB.size() == 1u);
	BOOST_CHECK(polyAB[0].inners().empty());
}

[barendgehrels]

Not fixed by my concept fix for #1294

And also Johan's two cases are (unfortunately) not fixed by that.

[barendgehrels]

Not fixed by my concept fix for #1226 and #1326
Neither are Johan's two cases.

[barendgehrels]

Not fixed by my concept fix for #1342 in PR #1343
Neither are Johan's two cases.

[barendgehrels]

@JohanDore I moved your two cases to #1345 because they have a different root cause.
I will create a PR with a fix for it today.

[JohanDore]

Thanks a lot @barend ***@***.***> Johan Doré CTO

[barendgehrels]

Though the case looks similar, it has a different cause than the new #1345.
In the reported case, two turns are just missed. In the cloned case, a wrong decision was made.
To be continued.

[mgaisser]

I may have the same issue with a different case. The inner loop vanishes during the difference operation. In order to reproduce the error, I have to serialize it with 18 significant digits, 15 is not enough.

#include <boost/geometry.hpp>

int main(int, char**)
{
    using Point2D = boost::geometry::model::d2::point_xy<double>;
    using PolygonCCW = boost::geometry::model::polygon<Point2D, false>;
    using MultiPolygonCCW = boost::geometry::model::multi_polygon<PolygonCCW>;

    const auto multipoly = boost::geometry::from_wkt<MultiPolygonCCW>("MULTIPOLYGON(((295.199999999999989 -295.199999999999989,295.199999999999989 295.199999999999989,-295.199999999999989 295.199999999999989,-295.199999999999989 -295.199999999999989,295.199999999999989 -295.199999999999989),(-179.997681584096682 -159.068022953381728,-179.997941555125578 -158.950077048237887,-180 -158.832148820362704,-180 -14.5241121286848625,-179.998787156680379 -14.4546283814396119,-179.999195199119924 -14.3851352478099308,-179.995132365653177 -14.2452455437218966,-179.992689924229154 -14.1053181682548523,-179.989052871933012 -14.0359190762519734,-179.987035390416196 -13.9664540354863789,-179.978092951651348 -13.8267913392705939,-179.970768603117904 -13.6870344437553584,-179.96471177303323 -13.6178045590987882,-179.960271225550514 -13.5484522436487858,-179.899302518930739 -12.8010583222347041,-179.862001646775752 -12.4192286301278614,-179.812514069087342 -12.0387864551623842,-179.756717919995367 -11.6575893141408002,-179.69354553378804 -11.2702990769800557,-179.617743949785876 -10.8852814175903685,-179.449050736785438 -10.0966985448598905,-179.370713374286112 -9.75497969251792263,-179.282427103876586 -9.41569507620525137,-179.18426728065765 -9.07913428598321026,-178.935424198586816 -8.27008653807789607,-178.812412221610401 -7.89249729706248626,-178.67697357776251 -7.51918515533267851,-178.52206744438692 -7.11329246102736157,-178.372718942212316 -6.74078412878685995,-178.210997411857903 -6.37347828985937515,-177.83796586524096 -5.56325522558086671,-177.683643331306087 -5.24079944287654875,-177.519784336166936 -4.92308352260890025,-177.346534296916872 -4.61038942260158002,-176.888642811189385 -3.8122348268109878,-176.682925174829364 -3.46716074752500347,-176.4657719066781 -3.12916618508967126,-176.203261097574938 -2.73523344331954199,-175.97364845346371 -2.40292746742542196,-175.732982121071331 -2.078537355980135,-175.143129804051284 -1.310831533374758,-174.920901565835123 -1.03035395323309942,-174.690409107515819 -0.756627283942919782,-174.451857396213086 -0.489894938965182547,-173.780108917183412 0.239037812837519681,-173.533488205359163 0.498765442860035435,-173.279226152669509 0.751017352386726955,-173.017549264610096 0.995568826627545533,-172.318055071282714 1.62999550300293983,-172.067822666567167 1.85068903895734671,-171.811551390238662 2.06434045156852441,-171.549439357600335 2.27078457361611186,-171.281689199261223 2.46986180961050472,-171.031950157793972 2.65021087534550936,-170.768065071279523 2.835433324854856,-170.499299340935181 3.01349982052276921,-170.225846968387685 3.18428182963124229,-169.947905338195852 3.34765607758145833,-169.680262243237394 3.50017672557883053,-169.398031980415396 3.65602528487362832,-169.111716805616084 3.80423566024079918,-168.821523388081118 3.94470086983453072,-168.527661196461878 4.07731952245764262,-168.245202320314831 4.20025185193289374,-167.947883471472693 4.32492822022349799,-167.64732257736847 4.44157230975317141,-167.343736590149689 4.55009992398729324,-167.037344645549581 4.6504327250600852,-166.743329216418374 4.74235824805159822,-166.434352475578294 4.83442381331231275,-166.123013965408205 4.91815568760162414,-165.809538417600521 4.99349343122062095,-165.494152106413281 5.06038266355761301,-165.191972700917376 5.12024067253396975,-164.874903279844006 5.17863311131773951,-164.556379617287462 5.2284866074688674,-164.23663163135754 5.26976517552396029,-163.915890123910316 5.3024390196108131,-163.609033520920434 5.32953882673178825,-163.287530010959983 5.35358436207679489,-162.965496567522251 5.36898423202898734,-162.643165642162018 5.375727320588501,-162.320769901163743 5.37380876043037148,-162.012776848660081 5.36783766723553946,-161.690549005093743 5.35725884322304502,-161.368721650836875 5.33802739140809557,-161.047527088684063 5.31015719351933235,-160.727197164665256 5.27366836694196373,-160.421621523858249 5.23469527250653854,-160.102387459886472 5.18961415576110952,-159.784479686856571 5.13597328949175136,-159.468127678314318 5.07381139297753059,-159.153559784816935 5.00317333618393612,-158.853927522957889 4.93164794210813451,-158.541370807245158 4.85258471329888774,-158.231050880339666 4.7651533822312695,-157.923191738695721 4.66941705896188797,-157.618015602513111 4.56544484829227759,-157.327784107566345 4.46219246969767802,-157.025511260386196 4.35005942129268952,-156.726359890085519 4.22984647550804382,-156.430545931383392 4.1016404049654156,-156.138282909974265 3.96553375191790813,-155.860801096610373 3.83174579432549756,-155.572299975036202 3.68783680385857515,-155.287769000407764 3.53622935297387997,-155.007413554087719 3.37703287560877818,-154.731436003441075 3.21036228364411969,-154.46990567067823 3.04758249561918326,-154.198505222998278 2.87355809593285194,-153.931877781715087 2.69230550356012799,-153.670215804986441 2.50395555102093859,-153.413708166777326 2.30864419388203324,-153.171147053156858 2.11875085407343189,-152.87864945418977 1.88227751953715927,-152.593706706865078 1.63675335759936136,-152.316598756515816 1.38241958634308926,-152.047597851087176 1.11952607895504297,-151.758492641328019 0.827987423984159143,-151.497863063903992 0.556792463263721338,-151.245860873059797 0.277562487870442354,-151.002733651293767 -0.00942816944216584574,-150.768720261787024 -0.303897551347931838,-150.580866676220865 -0.54804178071738896,-150.387712159765329 -0.806177457173726353,-150.201562005690334 -1.06940894241931783,-150.022550581694702 -1.33754622957983571,-149.850807102568638 -1.61039577065407258,-149.690225111389282 -1.87328129413026989,-149.633025334764199 -1.97070420726289952,-149.574266655031067 -2.06719491150401513,-149.526997232690093 -2.15129174077182661,-149.478152856477351 -2.23448369888000897,-149.424387935046411 -2.33384350802175922)))");
    const auto away = boost::geometry::from_wkt<MultiPolygonCCW>("MULTIPOLYGON(((-161.64096882920154 -24.7006892825620064,-161.289685158351034 -24.4725629993453921,-160.946576972490334 -24.2323160611842638,-160.612062296092091 -23.9802411719655595,-160.286548683761538 -23.7166454461126293,-159.970432723693705 -23.4418500344136262,-159.664099554492026 -23.1561897327487074,-159.367922395936176 -22.8600125741928615,-159.082262094271272 -22.5536794049911933,-158.807466682572255 -22.2375634449233637,-158.543870956719331 -21.9120498325927926,-158.291796067500627 -21.5775351561945712,-158.051549129339492 -21.2344269703338533,-157.823422846122895 -20.8831432994833506,-157.607695154586736 -20.5241121286848909,-157.404628885692887 -20.1577708821155781,-157.21447144440998 -19.7845658901538215,-157.037454508288789 -19.4049518455944927,-156.873793745198554 -19.0193912496758344,-156.723688550569108 -18.6283538485929157,-156.587321804458156 -18.2323160611842603,-156.464859648740173 -17.8317603984888819,-156.356451284688035 -17.4271748758809046,-156.262228791194332 -17.0190524184980028,-156.182306963853506 -16.6078902606880554,-156.116783175101148 -16.1941893402056749,-156.065737255580729 -15.7784536878967323,-156.029231396882096 -15.361189813614395,-156.007310075770846 -14.9429060891149028,-156 -14.5241121286848909,-156 -0.659861765609321083,-156 -0.659861765609321083,-156.007310075770874 -0.24106780517901305,-156.029231396882125 0.177215919320473647,-156.065737255580757 0.594479793602806117,-156.116783175101205 1.01021544591174406,-156.182306963853563 1.42391636639411612,-156.262228791194389 1.8350785242040577,-156.35645128468812 2.24320098158695203,-156.464859648740259 2.64778650419492223,-156.587321804458242 3.04834216689029436,-156.723688550569193 3.44437995429894173,-156.87379374519864 3.83541735538185424,-157.037454508288874 4.22097795130050457,-157.214471444410094 4.6005919958598227,-157.404628885693 4.97379698782157575,-157.60769515458685 5.34013823439087876,-157.823422846123009 5.69916940518932957,-158.051549129339634 6.0504530760398243,-158.291796067500769 6.39356126190053153,-158.543870956719473 6.72807593829874495,-158.807466682572397 7.05358955062930804,-159.082262094271414 7.36970551069712698,-159.367922395936318 7.67603867989878808,-159.664099554492168 7.97221583845462689,-159.970432723693847 8.25787614011953508,-160.28654868376168 8.53267155181853276,-160.612062296092233 8.79626727767145233,-160.946576972490448 9.04834216689014958,-161.289685158351176 9.28858910505127255,-161.640968829201682 9.51671538826787611,-162.000000000000142 9.73244307980402112,-162.366341246569448 9.93550934869787383,-162.739546238531204 10.1256667899807482,-163.119160283090537 10.3026837261019484,-163.504720879009199 10.4663444891921795,-163.89575828009211 10.6164496838216245,-164.291796067500741 10.7528164299325617,-164.692351730196123 10.8752785856505412,-165.096937252804111 10.9836869497026655,-165.505059710186998 11.0779094431963721,-165.916221867996938 11.1578312705371943,-166.329922788479308 11.2233550592895384,-166.745658440788247 11.2744009788099682,-167.162922315070603 11.3109068375085773,-167.581206039570077 11.3328281586198312,-168.000000000000085 11.3401382343906789,-168.418793960430094 11.3328281586198258,-168.837077684929568 11.3109068375085648,-169.254341559211923 11.2744009788099522,-169.670077211520862 11.2233550592895135,-170.083778132003232 11.1578312705371641,-170.494940289813172 11.077909443196333,-170.90306274719606 10.9836869497026228,-171.307648269804048 10.8752785856504914,-171.708203932499401 10.7528164299325084,-172.10424171990806 10.6164496838215658,-172.495279120990972 10.4663444891921138,-172.880839716909634 10.3026837261018773,-173.260453761468966 10.1256667899806718,-173.633658753430694 9.93550934869779212,-174 9.73244307980393408,-174.35903117079846 9.51671538826778551,-174.710314841648966 9.28858910505117663,-175.053423027509666 9.04834216689004656,-175.387937703907909 8.79626727767134398,-175.713451316238462 8.53267155181842085,-176.029567276306295 8.25787614011941784,-176.335900445507946 7.97221583845450077,-176.632077604063795 7.67603867989865307,-176.917737905728728 7.36970551069698487,-177.192533317427717 7.05358955062915793,-177.456129043280669 6.72807593829858508,-177.708203932499373 6.39356126190036278,-177.948450870660508 6.05045307603964844,-178.176577153877105 5.69916940518914394,-178.392304845413264 5.34013823439068602,-178.595371114307113 4.97379698782137414,-178.785528555589991 4.60059199585961309,-178.962545491711211 4.22097795130028608,-179.126206254801446 3.83541735538162776,-179.276311449430892 3.44437995429870725,-179.412678195541844 3.04834216689005189,-179.535140351259827 2.64778650419467221,-179.643548715311965 2.24320098158669401,-179.737771208805668 1.83507852420379303,-179.817693036146494 1.42391636639384433,-179.883216824898852 1.01021544591146517,-179.934262744419271 0.59447979360252079,-179.970768603117904 0.177215919320182214,-179.992689924229154 -0.241067805179310257,-180 -0.659861765609321083,-180 -14.5241121286848909,-179.992689924229154 -14.942906089114862,-179.970768603117904 -15.3611898136143541,-179.9342627444193 -15.7784536878966932,-179.883216824898852 -16.1941893402056394,-179.817693036146494 -16.6078902606880163,-179.737771208805668 -17.0190524184979672,-179.643548715311965 -17.4271748758808691,-179.535140351259827 -17.8317603984888464,-179.412678195541844 -18.2323160611842248,-179.276311449430921 -18.6283538485928801,-179.126206254801474 -19.0193912496758024,-178.962545491711239 -19.4049518455944607,-178.78552855559002 -19.7845658901537895,-178.595371114307142 -20.1577708821155497,-178.392304845413292 -20.5241121286848625,-178.176577153877133 -20.8831432994833222,-177.948450870660508 -21.2344269703338284,-177.708203932499373 -21.5775351561945428,-177.456129043280669 -21.9120498325927642,-177.192533317427745 -22.2375634449233388,-176.917737905728757 -22.5536794049911684,-176.632077604063824 -22.8600125741928366,-176.335900445507974 -23.1561897327486861,-176.029567276306324 -23.4418500344136049,-175.713451316238491 -23.7166454461126079,-175.387937703907909 -23.9802411719655382,-175.053423027509695 -24.2323160611842425,-174.710314841648994 -24.4725629993453779,-174.359031170798488 -24.7006892825619886,-174.000000000000028 -24.9164169740981407,-173.633658753430723 -25.1194832429920041,-173.260453761468938 -25.3096406842748856,-172.880839716909634 -25.4866576203960911,-172.495279120990972 -25.6503183834863329,-172.104241719908032 -25.8004235781157831,-171.708203932499401 -25.9367903242267275,-171.307648269804019 -26.0592524799447105,-170.903062747196032 -26.1676608439968419,-170.494940289813144 -26.2618833374905556,-170.083778132003175 -26.3418051648313849,-169.670077211520805 -26.4073289535837326,-169.254341559211866 -26.4583748731041695,-168.837077684929511 -26.4948807318027804,-168.418793960430037 -26.5168020529140378,-168.000000000000028 -26.5241121286848909,-167.581206039569992 -26.5168020529140378,-167.162922315070517 -26.4948807318027804,-166.745658440788162 -26.4583748731041695,-166.329922788479223 -26.4073289535837361,-165.916221867996853 -26.341805164831392,-165.505059710186913 -26.2618833374905591,-165.096937252803997 -26.167660843996849,-164.692351730196009 -26.0592524799447212,-164.291796067500627 -25.9367903242267381,-163.895758280091997 -25.8004235781157938,-163.504720879009056 -25.6503183834863435,-163.119160283090395 -25.4866576203961053,-162.739546238531091 -25.3096406842748962,-162.366341246569306 -25.1194832429920183,-162 -24.9164169740981585,-161.64096882920154 -24.7006892825620064)))");

    MultiPolygonCCW difference;
    boost::geometry::difference(multipoly, away, difference);

    return 0;
}

[barendgehrels]

I may have the same issue with a different case. The inner loop vanishes during the difference operation. In order to reproduce the error, I have to serialize it with 18 significant digits, 15 is not enough.

Thanks - but can you please open a separate issue for it? The cause might be very different. We also add failing or fixed issues with their issue number to the unit tests.

[mgaisser]

Created issue #1354