One, Sphere packing is a special problem class, that is
especially hard to solve. I shouldn't have mentioned it.
Two, try it. But first, some numbers...
Lets limit ourselves here. 10 boxes. I'm not letting you
have cubical, so they have 6 orientations that matter.
We'll limit ourselves to 4 inch increments and reasonable
box sizes and so 52" is max. That is boxes ranging from
1 to 13 "increments" on a side. (btw that is not 13**3 types
of boxes but it doesn't matter, we are only interested in
ten at a time. Discrete box sizes doesn't help at all anyway,
except if you can keep the number of positions low.)
Now, max and min cases, the container can't be smaller than 4x3x3
and 130x130x130 is clearly large enough.
So, for each box to place you have around 2 million origins,
and 6 orientations. For 10 boxes. And in each of these
120 million cases, you have to determine that none of them
intersect.
Just whip that out in perl real quick and run it. You can
do it with a 3d matrix or be fancy about it. You can throw
entire sub trees out if you can tell that a case is already
bigger than the smallest case you've found so far.
It is still like 100 million cases you have to run,
brute force. It's an ugly problem and I've not seen
a good suggestion as to how to break it down much better
to throw out large sets of fails. Worse, I don't think
anyone has found an "answer", a strategy that lets you
cut thru the brute-force approach and jump straight to the
answer.
And I suppose you are correct that you can start small
and work your way up, but as I recall the algorithm in the
books is just a "pretty-good" solution that is a bug-out
brute-force. That means you are going to repeat trying
cases you know are bad, over and over again as you go up
in size. And you won't be SURE you have the right
answer, just sure that you have AN answer.
I really don't want to be a spoilsport on this and
I don't know everything® but I'm pretty sure
this is a frustration fest. Don't let me stop you guys from
trying tho. Just consider using a box you don't mind letting
sit a while. =)
--
$you = new YOU;
honk() if $you->love(perl) |