1
\$\begingroup\$

I'm wondering, are there any algorithms or theories in existence (that aren't patented/proprietary/protected) that would take a series of 3d rectangular prisms (or cubes but a cube is a prism) and stacks them in such a way as they form another cube or fit together in the best possible format?

I'm working on logistics software at work and this might be an interesting feature.

I'd also accept good articles that discuss the theory of this, if an algorithm isn't already available for me to look at and study.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Worth noting that there's nothing game related in this question. You may well get a better answer from math.stackexchange.com. \$\endgroup\$ – Trevor Powell Feb 15 '13 at 23:50
2
\$\begingroup\$

Essentially you are asking for a derivation of the Cube Packing Problem, which is just a special case of a Packing Problem. This class of problems is known to be NP-Hard (non polynomial time solvable and at least as hard as the hardest NP-Complete problem).

There are heuristics to try and solve this that aren't guaranteed to return the optimal solution. You're going to have to refer to papers though to dig deeper.

This paper may help you get started(behind a pay wall)

A heuristic algorithm for cube packing with time schedule - Wei Li, WenQi Huang, DongChen Jiang, XiangLong Liu

\$\endgroup\$
0

Not the answer you're looking for? Browse other questions tagged or ask your own question.