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

Subject: [Boost-bugs] [Boost C++ Libraries] #12751: difference algorithm returning invalid geometry
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2017-01-12 11:15:53

#12751: difference algorithm returning invalid geometry
------------------------------------------------+--------------------------
 Reporter:  Volker Schöch <vschoech@…>          |      Owner:
     Type:  Bugs                                |  barendgehrels
Milestone:  To Be Determined                    |     Status:  new
  Version:  Boost 1.63.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(((1920 1462,3720 1462,3720
 3262,1920 3262,1920 1462)))", polygonA);
 boost::geometry::is_valid(polygonA); // returns true

 tc::geo::polygon<int> polygonB;
 boost::geometry::read_wkt("MULTIPOLYGON(((1918 1957,1918 1657,2218
 2189,1918 1957)),((3718 1957,3360 2233,3718 1561,3718 1957)),((3360
 2233,2818 3253,2218 2189,2818 2653,3360 2233)))", polygonB);
 boost::geometry::is_valid(polygonB); // returns true

 tc::geo::polygon<int> polygonC;
 boost::geometry::difference(polygonA, polygonB, polygonC);
 // polygonC: MULTIPOLYGON(((1920 1660,1920 1462,3720 1462,3720 3262,1920
 3262,1920 1959,2218 2189,1920 1660),(3718 1561,3360 2233,3718 1957,3718
 1561),(2818 2653,2218 2189,2818 3253,3360 2233,2818 2653)))
 boost::geometry::is_valid(polygonC); // returns true

 tc::geo::polygon<int> polygonD;
 boost::geometry::read_wkt("MULTIPOLYGON(((1918 2155,1918 1957,2818
 2653,3718 1957,3718 2154,2818 3055,1918 2155)))", polygonD);
 boost::geometry::is_valid(polygonD); // returns true

 tc::geo::polygon<int> polygonE;
 boost::geometry::difference(polygonC, polygonD, polygonE);
 // polygonE: MULTIPOLYGON(((2218 2189,1920 1660,1920 1462,3720 1462,3720
 3262,1920 3262,1920 2157,2562 2799,2818 3253,3043 2829,3718 2154,3718
 1957,3360 2234,3360 2233,2818 2653,2218 2189),(3718 1957,3718 1561,3360
 2233,3718 1957)))
 boost::geometry::is_valid(polygonD); // returns false!
 }}}

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

 May be related to tickets #10661, #11674, #11676.

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