https://svn.boost.org/trac10/ticket/5359 <p> When using corner_fill_arc==true in boost::polygon::resize(), the resulting polygons are prone to truly awful performance explosions. </p> <p> 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: </p> <pre class="wiki">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 ... </pre><p> The number of vertices explodes from 300 to over 6000, and the running time appears to be scaling superpolynomially. </p> <p> 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. </p> <p> Combined with the issue in bug <a class="closed ticket" href="https://svn.boost.org/trac10/ticket/5358" title="#5358: Bugs: polygon resize() generates bad/broken vertices (closed: invalid)">#5358</a> 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. </p> <p> Tested vs. svn as of submission date </p> en-us /htdocs/site/boost.png https://svn.boost.org/trac10/ticket/5359 Trac 1.4.3 Andy Ross <andy@…> Wed, 23 Mar 2011 04:55:09 GMT https://svn.boost.org/trac10/ticket/5359 https://svn.boost.org/trac10/ticket/5359 <ul> <li><strong>attachment</strong> → <span class="trac-field-new">slowshrink.cpp</span> </li> </ul> <p> code to exercise bug </p> Ticket anonymous Thu, 24 Mar 2011 06:46:15 GMT https://svn.boost.org/trac10/ticket/5359#comment:1 https://svn.boost.org/trac10/ticket/5359#comment:1 <ul> <li><strong>status</strong> <span class="trac-field-old">new</span> → <span class="trac-field-new">closed</span> </li> <li><strong>resolution</strong> → <span class="trac-field-new">invalid</span> </li> </ul> <p> Vertices introduced are never removed by resizing. Simplify or smooth the polygon after each resizing operation to bring the vertex count back down. </p> Ticket