[Boost-bugs] [Boost C++ Libraries] #13522: Invalid empty result using boost::geometry::difference

Subject: [Boost-bugs] [Boost C++ Libraries] #13522: Invalid empty result using boost::geometry::difference
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2018-04-16 09:43:01

#13522: Invalid empty result using boost::geometry::difference
---------------------------------+----------------------------
 Reporter:  lehnert@…            |      Owner:  Barend Gehrels
     Type:  Bugs                 |     Status:  new
Milestone:  To Be Determined     |  Component:  geometry
  Version:  Boost 1.66.0         |   Severity:  Problem
 Keywords:  geometry difference  |
---------------------------------+----------------------------
 Hello,

 executing the following polygon difference operation sequence produces an
 obviously incorrect empty result. The first difference produces a
 (possibliy) valid result with a spike which might be the actual problem.
 The third difference with the previous result generates an empty result.
 The intermediate difference is required the reproduce this behaviour.
 Without it the result of the third difference is correct. Removing the
 spike from step one also solves the problem.

 Code to reproduce this:

 using point_type = boost::geometry::model::d2::point_xy<double>; using
 polygon = boost::geometry::model::polygon<point_type>; using multi_polygon
 = boost::geometry::model::multi_polygon<polygon>;

     BoostGeometryBridge::Polygon2d_t Right[3];
     BoostGeometryBridge::MultiPolygon2d_t Left[4];

     boost::geometry::read_wkt("MULTIPOLYGON(((0.747399249902131135
 -0.974867609298678328,0.744720465461241043
 -0.984866128861542012,0.737400169703072983
 -0.992186849248596014,0.72740024741975795
 -0.994866631198703,0.169444950081761997
 -0.994882813404528998,0.156263880981993009
 -0.992649068186161054,0.144555091741144004
 -0.986196591543298973,0.135626528763234999
 -0.976246166252738967,0.0970341390445131069
 -0.91515608670535098,0.0527935015388215009
 -0.831873652851741974,0.0149278636239085008
 -0.745505885364162957,-0.016349202846282801
 -0.656539920475841976,-0.0408612872409169006
 -0.56547754891590496,-0.0584701351532070993
 -0.472832385681689005,-0.0690764281904878985
 -0.379126973119241983,-0.0726203441553292944
 -0.284889833651171986,-0.0690818944579700972
 -0.19065248877542601,-0.058481036857029399
 -0.0969464611485150035,-0.0408775628926898033
 -0.00430027666216776031,-0.0163707606471800993
 0.086763516577464006,0.0149011452653820004
 0.17573129555438699,0.0527617733210207981
 0.262101259307556012,0.0969975799226773933
 0.345386259216249991,0.135586426022915013
 0.406478577227274984,0.144514411807557003
 0.416429520405822984,0.156222826750318011
 0.422882676210660002,0.169403766258661992
 0.42511718599825099,0.727359063596658029
 0.425133368204076989,0.737359141304932963
 0.422454166307816015,0.744679861691986966
 0.415133870549649009,0.747359067455327319
 0.405136098375181386,0.747329770868999987
 1.43513394783313997,2.74732976755064007
 1.43524915817017007,2.74708725756255978
 5.64524915118547987,-2.74750006237453981
 1.25999999251885009,-2.74749997944197011
 -4.43500000748115042,0.747500020558034994
 -4.43500000604748035,0.747399249902131135
 -0.974867609298678328),(-2.49638915854706989
 0.152811596222504009,-1.75719536363572004
 1.80498971421238008,-1.01782283569549992
 1.4741902811305001,-1.75234596398119002
 -0.167548384003570999,-1.76762179055725999
 -0.173243028570225999,-2.49638915854706989 0.152811596222504009)))",
 Left[0]);

     boost::geometry::read_wkt("POLYGON((-1.57590744074229994
 2.19505211912179998,-2.74750006237453981
 1.25999999251885009,-2.74750004134586989
 -0.184043917378418992,-1.76796680349592994
 -0.184043903114115004,-1.74492840055212994
 -0.175455463366190001,-1.00461083616106994
 1.47923439340570995,-1.57590744074229994 2.19505211912179998))",
 Right[0]);
     boost::geometry::read_wkt("POLYGON((2.74708725756255001
 5.64524915118547987, 1.48149582377297007 4.63517624723808019,
 2.7471454369183701 4.6352491528611397, 2.74708725756255001
 5.64524915118547987))", Right[1]);
     boost::geometry::read_wkt("POLYGON((-2.74749997944197011
 -4.43500000748115042, -2.74750006237453981 1.25999999251885009,
 -3.11250006493298015 1.43568817247817004, -3.11249997689355018
 -4.61000000763086959, -2.74749997944197011 -4.43500000748115042))",
 Right[2]);

     for(int i = 0; i < 3; i++)
     {
       boost::geometry::difference(Left[i], Right[i], Left[i + 1]);
     }

 Final result in Left[3] is empty.

-- 
Ticket URL: <https://svn.boost.org/trac10/ticket/13522>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.