[Boost-bugs] [Boost C++ Libraries] #11674: difference algorithm returning invalid geometry

Subject: [Boost-bugs] [Boost C++ Libraries] #11674: difference algorithm returning invalid geometry
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2015-09-21 13:04:30

#11674: difference algorithm returning invalid geometry
------------------------------------------------+--------------------------
 Reporter:  vschoech@…                          |      Owner:
     Type:  Bugs                                |  barendgehrels
Milestone:  To Be Determined                    |     Status:  new
  Version:  Boost 1.59.0                        |  Component:  geometry
 Keywords:  difference, multi-polygon, polygon  |   Severity:  Problem
------------------------------------------------+--------------------------
 My "tc::geo::polygon" type is actually a '''multi-polygon''', using a
 polygon type that is based on '''int''', oriented '''counter-clockwise'''
 and '''open''' (not closed). Please consider the following example:

 {{{
 tc::geo::polygon<int> polygonA;
 boost::geometry::read_wkt("MULTIPOLYGON(((529 3217,529 998,5337 998,5337
 1834,5070 2000,5337 2072,5337 3475,529 3475,529 3312,1734 2054,2934
 1670,3230 1690,2934 1400,1734 1784,529 3217),(4140 2582,5071 2001,4140
 1754,3231 1691,4140 2582)))", polygonA); // does not throw
 boost::geometry::is_valid(polygonA); // returns true

 tc::geo::polygon<int> polygonB;
 boost::geometry::read_wkt("MULTIPOLYGON(((528 3218,528 2498,1734 1406,2556
 1522,1734 1784,528 3218)),((4610 2288,5340 1178,5340 1832,4609 2289,4140
 3002,2934 1574,2555 1521,2934 1400,4140 2582,4610 2288)))", polygonB); //
 does not throw
 boost::geometry::is_valid(polygonB); // returns true

 tc::geo::polygon<int> polygonC;
 boost::geometry::difference(polygonA, polygonB, polygonC); // does not
 throw
 // polygonC: MULTIPOLYGON(((2553 1521,1734 1406,529 2498,529 998,5337
 998,5337 1183,4839 1939,4140 1754,3231 1691,4140 2582,3230 1690,2934
 1400,2555 1521,2556 1522,2553 1521)),((1734 1784,529 3217,529 3216,1734
 1784)),((3020 1676,4140 3002,4609 2289,5071 2001,5337 2072,5337 3475,529
 3475,529 3312,1734 2054,2934 1670,3020 1676)))
 boost::geometry::is_valid(polygonC); // returns false!
 }}}

 The difference of two valid multi-polygons yields an invalid multi-
 polygon.

 May be related to Ticket #10661.

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