[Boost-bugs] [Boost C++ Libraries] #5359: Serious performance problems with polygon::resize() and corner_fill_arc

Subject: [Boost-bugs] [Boost C++ Libraries] #5359: Serious performance problems with polygon::resize() and corner_fill_arc
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-03-23 04:54:12

#5359: Serious performance problems with polygon::resize() and corner_fill_arc
--------------------------------------------+-------------------------------
 Reporter:  Andy Ross <andy@…>              |       Owner:  ljsimons   
     Type:  Bugs                            |      Status:  new        
Milestone:  To Be Determined                |   Component:  polygon    
  Version:  Boost Development Trunk         |    Severity:  Showstopper
 Keywords:                                  |  
--------------------------------------------+-------------------------------
 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

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