[Boost-bugs] [Boost C++ Libraries] #9942: Result of difference of multi-polygons contains spike

Subject: [Boost-bugs] [Boost C++ Libraries] #9942: Result of difference of multi-polygons contains spike
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2014-04-23 14:05:09

#9942: Result of difference of multi-polygons contains spike
-------------------------------------------------+-------------------------
 Reporter:  Volker Schöch <vschoech@…>           |      Owner:
     Type:  Bugs                                 |  barendgehrels
Milestone:  To Be Determined                     |     Status:  new
  Version:  Boost 1.55.0                         |  Component:  geometry
 Keywords:  difference, multi-polygon, polygon,  |   Severity:  Problem
  remove_spikes, spike                           |
-------------------------------------------------+-------------------------
 boost::geometry::difference(...) should not introduce spikes to a polygon.
 In the following example I subtract a multi-polygon from another multi-
 polygon, and the result contains a spike. My polygon type is oriented
 '''counter-clockwise''' and '''not closed''', my point type is based on
 '''int'''.

 This is the data used as input to difference:
 {{{
 _TPolygon<int> const polygon =
         _TPolygon<int>( "MULTIPOLYGON(((2058 1761,1996 1700,1660 1370,1324
 1040,982 1148,881 981,2644 981,2338 1982)),((1996 1760,2338 2078,2674
 1010,3010 1160,3254 2085,3352 2522,3427 2562,3688 2930,3688 2924,3688
 2702,3439 2568,3352 2444,3218 1926,3010 998,2959 981,3773 981,3773
 3702,732 3702,732 981,770 981,982 1310,1324 1148,1660 1442,1697 1472,1660
 1436,1698 1473,1697 1472)))" )
         - _TPolygon<int>( "MULTIPOLYGON(((646 932,646 788,870
 1136)),((3032 1096,3010 1040,2981 988,3010 998)),((3688 2702,3352
 2522,3032 1096,3352 1916,3688 2018)),((2981 988,2674 884,2338 1982,1996
 1712,1660 1442,1324 1148,982 1310,870 1136,982 1238,1324 1136,1660
 1304,1996 1460,2338 1610,2674 434)))" )
 }}}

 This is the resulting multi-polygon, with the spike:
 {{{
 MULTIPOLYGON(((2338 1982,2058 1761,2057 1760)),((2517 981,2338 1610,1996
 1460,1660 1304,1523 1235,1324 1040,982 1148,881 981)),((1695 1470,1697
 1472,1996 1760,2338 2078,2674 1010,3010 1160,3253 2083,3352 2522,3427
 2562,3688 2930,3688 2924,3688 2702,3688 2018,3352 1916,3032 1096,3219
 1933,3218 1926,3031 1095,3032 1096,3010 998,2981 988,2959 981,2960
 981,2981 988,2977 981,3773 981,3773 3702,732 3702,732 1010,869 1135,982
 1310,1324 1148,1660 1442,1697 1472)))
 }}}

 This is the multi-polygon I'd expect to see, without the spike:
 {{{
 MULTIPOLYGON(((2338 1982,2058 1761,2057 1760)),((2517 981,2338 1610,1996
 1460,1660 1304,1523 1235,1324 1040,982 1148,881 981)),((1996 1760,2338
 2078,2674 1010,3010 1160,3253 2083,3352 2522,3427 2562,3688 2930,3688
 2924,3688 2702,3688 2018,3352 1916,3032 1096,3219 1933,3218 1926,3031
 1095,3032 1096,3010 998,2981 988,2959 981,2960 981,2981 988,2977 981,3773
 981,3773 3702,732 3702,732 1010,869 1135,982 1310,1324 1148,1660 1442,1697
 1472)))
 }}}

 This is my code that wraps boost::geometry to implement the operator used
 above:
 {{{
 template<typename T>
 template<typename Geometry>
 _TPolygon< T > _TPolygon< T >::operator-(Geometry geometry) const
 {
         _TPolygon< T > polygonOut;
         boost::geometry::difference(*this, geometry, polygonOut);

         // the following line fixes the problem but should not be
 necessary
         //boost::geometry::remove_spikes( polygonOut );

         return polygonOut;
 }
 }}}

 (I apologize for the huge amount of nodes in the polygons. These are real
 life examples taken directly from our system. I admit that I did not try
 to boil them down to the minimal set of nodes needed to reproduce the
 problem.)

 Releated issues:

 [https://svn.boost.org/trac/boost/ticket/9768 difference of multi-polygon
 and box returns multi-polygon with redundant points]

 [https://svn.boost.org/trac/boost/ticket/9828 boost::geometry::union_(...)
 creates redundant closing point]

 [https://svn.boost.org/trac/boost/ticket/9871 remove_spikes does not
 remove spike]

 Note to self: RT#9769

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