We closed this forum 18 June 2010. It has served us well since 2005 as the ALPHA forum did before it from 2002 to 2005. New discussions are ongoing at the new URL http://forum.processing.org. You'll need to sign up and get a new user account. We're sorry about that inconvenience, but we think it's better in the long run. The content on this forum will remain online.
Index › Programming Questions & Help › Programs › Ideas for 2D nesting algorithm
‹ Previous Topic | Next Topic ›
Page Index Toggle Pages: 1
Ideas for 2D nesting algorithm? (Read 1030 times)
jsavage
Ideas for 2D nesting algorithm?
Nov 5th, 2009, 3:46pm  
Project:  take an array of different sized rectangles and calculate the best orientation AND rotation of each rectangle to fit on a sheet of a given size to minimize material waste.

Anyone have any ideas on how I could accomplish this?  I've got the array of rectangle sizes, but I'm just scratching my head on how to approach this.
Back to top
 
 
davbol
Re: Ideas for 2D nesting algorithm?
Reply #1 - Nov 6th, 2009, 7:17am  
bad news:  it's an NP-hard problem (as asked, in the general case, assuming you don't have any additional conditions that somehow simplify it), so don't expect an "easy" answer.  (heck, don't even expect a "hard" answer, because it's "really, really hard")
good news:  it can be approximated relatively easily if you don't truly need optimal -- that is, if you can replace the word "best" in your post with "pretty good", then google "bin packing" to get you started
Back to top
 
WWW  
Page Index Toggle Pages: 1
‹ Previous Topic | Next Topic ›