Specialise (Multi)Polygon / Box intersection?

[systemed]

In tilemaker we have to clip potentially millions of geometries against the bounding box of a map tile. Previously we used boost::geometry::intersection for this.

In systemed/tilemaker#482 we moved to using a port of the Sutherland-Hodgman algorithm, which clips a polygon to a box. This has proved to be many times faster - for example, generating map tiles for Maine has come down from 34m37 to 4m23. When you consider that most of that 4m23 will be reading the source data, assembling geometries, processing attributes, and writing out the map tiles, that's a pretty massive saving on intersections alone.

It might be worth implementing this in Boost.Geometry core so that other users can benefit from this. The implementation is pretty simple - only 50 LOC, plus wrappers for Polygon and MultiPolygon.

Sutherland-Hodgman can retain a 0-width boundary around the edge of the box, which is undesirable. tilemaker fixes this by calling correct afterwards, using the code referenced in #868.

My C++fu isn't strong enough to prepare a PR for Boost.Geometry, I'm afraid, but you are very welcome to cannibalise the tilemaker code if you'd find it useful.