Two almost idential rectangles has no interesection

[JohanDore]

Hi All,

I was looking into a bug reported for our software and found it boiling down to how Boost Geometry deals with almost identical rectangles.

Here is a test case showing the problem:

BOOST_AUTO_TEST_CASE(Boost_Intersection_Fails)
{
using PointXY = boost::geometry::model::d2::point_xy;
using Polygon = boost::geometry::model::polygon;
using MultiPolygon = boost::geometry::model::multi_polygon;

MultiPolygon polyA;
read_wkt("MULTIPOLYGON((("
"20.0970444515398512 -0.3449179410282249,"
"21.9812157674818778 -0.3449179410282249,"
"21.9812157674818778 -2.2293927797379025,"
"20.0970444515398512 -2.2293927797379025,"
"20.0970444515398512 -0.3449179410282249)))", polyA);

MultiPolygon polyB;
read_wkt("MULTIPOLYGON((("
"20.0970444515398476 -0.3449179410282246,"
"21.9812157674818813 -0.3449179410282246,"
"21.9812157674818813 -2.2293927797379034, "
"20.0970444515398476 -2.2293927797379034, "
"20.0970444515398476 -0.3449179410282246)))", polyB);

MultiPolygon polyAB;
intersection(polyA, polyB, polyAB);

// The intersection of polyA & polyB should be the ~same as polyA & polyB:
/*
BOOST_CHECK_CLOSE(area(polyAB), area(polyA), 0.0001);
BOOST_CHECK_CLOSE(area(polyAB), area(polyB), 0.0001);
BOOST_CHECK_EQUAL(polyAB.size(), 1);
BOOST_CHECK(polyAB[0].inners().empty());
*/
// But boost returns an empty object
BOOST_CHECK_EQUAL(polyAB.size(), 0);
}

It is also interesting that simply removing the last decimal for each x, y coordinate makes intersection return the right rectangle.

I tested this in both version 1.88 and 1.91.

Thanks a lot for your hard work on Boost Geometry

Johan

[barendgehrels]

hi @JohanDore , thanks for the precise report.

I'll try to look at this as well, end of June.