Another week, another problem
Trying not to reinvent the wheel I googled around first. Of course the first problem of the googling thing is to figure out what is the popular name of the problem you are interested on (and believe me, I am yet to find an "original" problem never thought and wrote about it before). My first searches suggested Cutting stock problem, but it was not exactly my case. It is a pity as in 2007 a dynamic programming solution was published. So moving on I found the best fit to be the Bin packing problem. Again, an NP hard problem.
Wikipedia article suggested the heuristic of the first fit algorithm, that is known to provide good (but not optimal) solutions without too much work. The idea is as follows:
- First sort all the polygons in descending order of height.
- Next, try to fit a polygon in the available pages, leaving it there at the first fit.
- If no room was found, add a new page and fit the polygon in that page.
- Repeat until all polygons are allocated to a page.
I have added later a small variation that tries to add the polygon not only at the current orientation but also rotating it 90 degrees. This has improved a bit the efficiency, but I guess the best approach here might be to find the rotation that creates the minimum bounding box for each polygon before attempting to perform the fit.
Still, I can see that there is still a lot of empty space on the pages of my output and that a more thoughtful approach can take advantage of part of it. Any help is appreciated!!!
Update: Nesting problem is the popular name in the CAD environment.