4 ms·
You have run into a monster. https://en.wikipedia.org/wiki/Packing_problems https://en.wikipedia.org/wiki/Packing_problems Packing of regular shapes in a conf
by enthdegree 10y ago
You have run into a monster.
https://en.wikipedia.org/wiki/Packing_problems https://en.wikipedia.org/wiki/Packing_problems
Packing of regular shapes in a confined space is hard enough... much less a general collection of cuboids in a 3D box. On the bright side, if you find a good way to do this you will have accomplished a lot more than packaging candy.
Here is an annealing approach that might lead somewhere (although I'm not sure... I am no expert on packing and really smart people have been thinking about this for hundreds of years)
Instead of thinking of sharp cubes as geometric objects, think about each one as a function from space to 0 or 1. (0 if you're outside the box, 1 if you're in it).
Blur each cube function with a Gaussian, then try to position these blurry functions in your box so that they are well-separated. This positioning can be done using ordinary numerical optimization as a 'feasibility search': your objective function can be the maximum of the sum of the functions throughout the box, searching over the space of positions that lead to the cuboids being within the box's boundaries. You have to scale the blurred functions so that they all individually have the same max. Declare a positioning infeasible if the max of the sum is above the individual max.
The positions you get from this will be a first approximation of where you should put your candies.
After you've found the positions, reform your cube functions, this time using a sharper/thinner Gaussian. Then run the optimization again using the previous step's result as your first guess.
The idea here is that hopefully the problem of shifting blurry functions around to be uniform is a lot easier than the strict packing problem which most people try to avoid solving.
Also it's pretty amazing to me that you have made headway in this using Javascript. Good luck!
- adrianN 10y agoThe trunk capacity of cars in defined as the number of a certain kind of box you can fit into it. Car manufacturers naturally want to maximize this number for their cars. Traditionally there are expert packers (pretty nice job if you ask me) who do this, but there are now some algorithmic approaches: http://www.joachim-reichel.de/publications/diss.pdf http://www.joachim-reichel.de/publications/diss.pdf