What is the strategy to build a 2D Board Cutting Application?

Question

I need to buid a small application using VC#. The problem statement is:

You are provided a main board of height h and width w along with the height and width of small boards to be cut from the main board. The application should be able to draw the most optimized solution with the final output, the residue area left and the scrap which is left.

I have already made a plan of this application. I would be using 2D graphics to show the output. The main problem is how to build the algorithm to come to the solution. The algorithm should give the best optimized solution.

Please give your suggestions to solve this problem.

Alan · Answer

This is an instance of the '2D packing problem' which is generally difficult to solve because you have to consider not only all possible combinations of the small boards but also the positioning and orientation of each combination on the main board to arrive at the optimum solution. The difficulty increases exponentially the more small boards you have. The mathematics needed to solve this are a bit beyond me nowadays but this recent article by Rod Stephens should help you: http://www.devx.com/dotnet/Article/36005