   Difficult algorithm for me to wrap my mind around
  Hello.I've been thinking about how to implement an algorithm that, given a rectangle, will determine if that rectangle can fit in a rectangular bin. For example, I would pass an arbitrary rectangle as an argument to a method, denoted in the following diagram by an arrow. The method would then determine whether it can fit in the bin amongst the other rectangles.A simplistic verson would subtract the combined area of the existing rectangles from the area of the bin and determine whether or not this area is greater than the area of the rectangle you want to stick in it.However, I want my algorithm to take shape into account. Even if there's enough volume to hold it the rectangle, my guess is that in the above diagram, that piece will not fit no matter how you arrange the other rectangles.I'm having massive amounts of trouble even imagining where to begin. At my job I pack boxes full of stuff -- often other boxes -- so I am very familiar with this particular problem. However, reflecting on the heuristics I use at work to fill the boxes does not reveal anything particularly useful for this problem. I find that I often rearrange items in the box in order to create more useable room. I figure that is an indication that the algo should be recursive.. I also would like to note that I do not wish to brute force this.. I was wondering if anyone had any advice or ideas. Thanks..If nothing else, it will be a fun little brainteaser to think about.   
Optimal rectangle packing is an NP-complete problem, meaning it basically can only be solved by brute force. So is bin packing. I suspect your own statement of the problem will lead to NP-completeness too. Heuristics may do better but, by definition, only provide an approximated solution.   ;  Might help: http://www.blackpawn.com/texts/lightmaps/   