[Boost-bugs] [Boost C++ Libraries] #11675: sym_difference yields bad result for int polygons

Subject: [Boost-bugs] [Boost C++ Libraries] #11675: sym_difference yields bad result for int polygons
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2015-09-21 14:31:07

#11675: sym_difference yields bad result for int polygons
-------------------------------------------------+-------------------------
 Reporter:  vschoech@…                           |      Owner:
     Type:  Bugs                                 |  barendgehrels
Milestone:  To Be Determined                     |     Status:  new
  Version:  Boost 1.59.0                         |  Component:  geometry
 Keywords:  sym_difference, polygon, large       |   Severity:  Problem
  numbers, domain of definition, integer         |
-------------------------------------------------+-------------------------
 My "_TPolygon" type is actually a '''multi-polygon''', based on a polygon
 type that is oriented '''counter-clockwise''' and '''open''' (not closed).
 Please consider the following example, which apparently works fine:
 {{{
 tc::geo::polygon<double> polygonA; // tc::geo::polygon<...> is actually a
 MULTIPOLYGON, with polygons oriented COUNTER-CLOCKWISE and OPEN (not
 closed).
 boost::geometry::read_wkt("MULTIPOLYGON(((564 2394,1548 2850,2526
 2916,2526 1073741823,564 1073741823,564 2394)))", polygonA); // does not
 throw
 boost::geometry::is_valid(polygonA); // returns true

 tc::geo::polygon<double> polygonB;
 boost::geometry::read_wkt("MULTIPOLYGON(((564 3252,2526 3252,2526
 1073741823,564 1073741823,564 3252)))", polygonB); // does not throw
 boost::geometry::is_valid(polygonB); // returns true

 tc::geo::polygon<double> polygonC;
 boost::geometry::sym_difference(polygonA, polygonB, polygonC); // does not
 throw
 boost::geometry::is_valid(polygonC); // returns true
 // polygonC is now "MULTIPOLYGON(((564 3252,564 2394,1548 2850,2526
 2916,2526 3252,564 3252)))"
 }}}
 Note: ''std::numeric_limits<int>::max()/2 == 1073741823''
 Now, simply replace '''double''' by '''int''':
 {{{
 tc::geo::polygon<int> polygonA; // tc::geo::polygon<...> is actually a
 MULTIPOLYGON, with polygons oriented COUNTER-CLOCKWISE and OPEN (not
 closed).
 boost::geometry::read_wkt("MULTIPOLYGON(((564 2394,1548 2850,2526
 2916,2526 1073741823,564 1073741823,564 2394)))", polygonA); // does not
 throw
 boost::geometry::is_valid(polygonA); // returns true

 tc::geo::polygon<int> polygonB;
 boost::geometry::read_wkt("MULTIPOLYGON(((564 3252,2526 3252,2526
 1073741823,564 1073741823,564 3252)))", polygonB); // does not throw
 boost::geometry::is_valid(polygonB); // returns true

 tc::geo::polygon<int> polygonC;
 boost::geometry::sym_difference(polygonA, polygonB, polygonC); // does not
 throw
 boost::geometry::is_valid(polygonC); // returns true
 TRACE( "===================== polygonC2=" << polygonC );
 // polygonC is now "MULTIPOLYGON(((564 3252,564 2394,1548 2850,2526
 2916,2526 *!*333412*!*,564 3252)))"
 }}}

 As you can see, one value is completely off. This seems to happen reliably
 whenever the input is based on int and contains large numbers.

 This issue may be related to Ticket #10658.

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