So I have boxes of different sizes (squares). I have a Big Box (not a square). I have no guarantee that all of my boxes will fit, yet I need to try to fit as much as possible in a non-iterative manner without overlap. What algorithm allows for such non-iterative a box packing?
Asked
Active
Viewed 203 times
4
-
2"polygon shape that looks like a doughnut" is it a convex? A regular convex? Also what have you tried so far? – Yonlif Feb 17 '20 at 10:22
-
A doughnut is a 3D object (torus), so how does that describe a polygon? – trincot Feb 17 '20 at 15:49
-
1Are you optimising the area or the number of shapes? – Neil Feb 17 '20 at 18:00
-
Simplified the question and added details. – DuckQueen Feb 17 '20 at 20:32
-
What does non-iterative mean? No loops? Or just no guess-and-check brute-force? – Patrick87 Feb 17 '20 at 22:57
-
@Patrick87: just no guess-and-check brute-force – DuckQueen Feb 18 '20 at 01:19
-
1Isn't this now just about *2D bin packing* ? I don't think the Internet, nor even Stack Overflow, needs another explanation of that. – High Performance Mark Feb 18 '20 at 16:25
-
2Any algorithm will need to iterate over the input list of boxes. There is no non-iterative algorithm – Gene Feb 19 '20 at 06:58
-
I think there should be a note, that if the sum of certain boxes' areas is less than the area of the Big Box, that doesn't mean they can fit into it. – Gevorg Melkumyan Feb 22 '20 at 16:55
-
"as much as possible" is also not so clear. Do you want to occupy the maximum possible volume or to fit the highest possible number of boxes ? i.e. It is best to put one big box or 10 smaller boxes with the same cumulative volume ? – Nicola Lepetit Feb 24 '20 at 11:22
-
What have you tried? and why didn't they work for you? – Paddy3118 Feb 24 '20 at 19:54
-
Did you look at this question? https://stackoverflow.com/questions/8762569/how-is-2d-bin-packing-achieved-programmatically. It's at least similar. – Tobias Brösamle Feb 25 '20 at 12:53
-
I suspect the OP actually means "non recursive". – Tim Consolazio Feb 25 '20 at 20:50
-
@DuckQueen Is the Big Box a polygon? Is it convex? Can you rotate the boxes (e.g. to fit against an edge of the Big Box)? – Jonathan H Feb 25 '20 at 23:41
1 Answers
2
Here is it Bin Packing Algorithm, demo, start from biggets to lowest size and try search for the place.
Profesor08
- 1,181
- 1
- 13
- 20