The Logic of Spacial Reasoning: Calculate Boxes in a Box

PHP programming forum. Ask questions or help people concerning PHP code. Don't understand a function? Need help implementing a class? Don't understand a class? Here is where to ask. Remember to do your homework!

Moderator: General Moderators

Post Reply
lightnb
Forum Newbie
Posts: 13
Joined: Mon Jul 28, 2008 11:13 pm

The Logic of Spacial Reasoning: Calculate Boxes in a Box

Post by lightnb »

I have an array of N boxes, each with X, Y, and Z dimensions. I need a programmatic way to calculate if these boxes will fit inside a larger box of given X, Y, and Z dimensions.

I can easily determine if one box will fit inside another, but I don't know where to go from there. I'm thinking that once the first box has been placed, I have to subdivide the remaining space into rectangular spaces, and then try the remaining boxes in those spaces?

The function should iterate through all possible orientations of the smaller boxes until all boxes fit (then return true) or until it runs out of possibilities (return false).
dancing dragon
Forum Newbie
Posts: 8
Joined: Sun Aug 17, 2008 4:57 am
Location: bed

Re: The Logic of Spacial Reasoning: Calculate Boxes in a Box

Post by dancing dragon »

That sounds pretty complex. More of a mathematics and computer science question than a PHP question. The difficult part is coming up with the algorithm. Programming it should be fairly straightforward. And you would probably use something other than a scripting language for something that could be computationally intense depending how large N is.

I am trying to think of how to store the information on occupied space vs. vacant space. Those are going to be some complex 3-dimensional shapes that are a bunch of cuboids attached to each other.

I am also thinking of working backwards from how to fit 1 box in the available space, 2 boxes... like those recursion problems in computer science classes.

I think I would ask Google and some PhD computer science friends.
User avatar
onion2k
Jedi Mod
Posts: 5263
Joined: Tue Dec 21, 2004 5:03 pm
Location: usrlab.com

Re: The Logic of Spacial Reasoning: Calculate Boxes in a Box

Post by onion2k »

Now that is an interesting puzzle. I'm not sure where I'd start. It's not too bad if the small boxes are all the same, but if they can be different sizes you're looking at an immensely difficult problem.
User avatar
jayshields
DevNet Resident
Posts: 1912
Joined: Mon Aug 22, 2005 12:11 pm
Location: Leeds/Manchester, England

Re: The Logic of Spacial Reasoning: Calculate Boxes in a Box

Post by jayshields »

I'll tell you from the off-set that you'll struggle to get an efficient algorithm for that problem. It requires an unbounded exhaustive search algorithm, which is exponential. If the original space you've got it large, and the number of boxes you've got is relatively large, and they are all different sizes, well I doubt you'll be able to get a feasible algorithm at all.

My only advice is research these types of algorithms alot and then try and spill your brains onto some pieces of paper before going anywhere near code or you'll drive youself insane!

Edit: After reading your problem again, I think 3D boxes would be much, much more difficult than 2D boxes. You'd be better off starting with 2D boxes and then trying to modify the algorithm from there.
Post Reply