Serious performance problems with polygon::resize() and corner_fill_arc

[Andy Ross <andy@…>]

When using corner_fill_arc==true in boost::polygon::resize(), the resulting polygons are prone to truly awful performance explosions.

The attached code iterates calls to resize() to shrink it until the polygon is empty. On my system, the ~26 iterations are near instantaneous for one initial shrink arguments, but take 30+ minutes when incrementing that value from -873 to -874. In fact, it hasn't completed yet, the output looks like this:

306 vertices, 0 secs
342 vertices, 0 secs
427 vertices, 0 secs
564 vertices, 0 secs
838 vertices, 0 secs
1556 vertices, 0 secs
3221 vertices, 6 secs
6636 vertices, 104 secs
3038 vertices, 1281 secs
...

The number of vertices explodes from 300 to over 6000, and the running time appears to be scaling superpolynomially.

See comments in the code: this behavior is very sensitive to input conditions. It's generally possible to tune any single input to give equivalent output at near-zero running time. But for real-world input I'm hitting this performance catastrophes regularly.

Combined with the issue in bug #5358 that forces me to use the corner_fill_arc feature, this is a showstopper for me. I'm stuck without a fix for one of them; resize() as it is basically doesn't work.

Tested vs. svn as of submission date

[Andy Ross <andy@…>]

code to exercise bug

[anonymous]

Vertices introduced are never removed by resizing. Simplify or smooth the polygon after each resizing operation to bring the vertex count back down.