Result of difference of multi-polygons contains spike

[Volker Schöch <vschoech@…>]

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:

​difference of multi-polygon and box returns multi-polygon with redundant points

​boost::geometry::union_(...) creates redundant closing point

​remove_spikes does not remove spike

Note to self: RT#9769

[vschoech@…]

The problem is still present in boost 1.59.0.

[Volker Schöch <vschoech@…>]

This problem is still present in boost 1.63.0.

[Volker Schöch <vschoech@…>]

Still present in boost 1.66.0.

[Volker Schöch <vschoech@…>]

No longer reproducible in 1.67.0.

[Barend Gehrels]

Thanks for verifying!