need help in building an algorithm

[ilan]

you have several boxes of different sizes. now you need to find the size of 1 big box that will hold all boxes inside with a space between each box.

something like this:

the big box (in red) has a limit of size. if all boxes together cannot be placed in that big box a new big box will be taken. let say the max size is 1024x1024
but if you have only 4 small boxes the big box can be smaller then the max size so you just need to find the correct order to not lose space.

any idea?

 

[JohnC]

1) First find the box with the longest width
2) Find the box with the tallest height
3) If a box is found that is both #1 and #2 above, then that is the "biggest" box so far
4) of the remaining boxes, add up the widths of each box to get the max width needed to hold those boxes.
5) of the remaining boxes, add up the total heights of each box to get the max height needed to hold those boxes.
6) If the max height needed is less than the height of the "biggest" box and the max width needed is less than the width of the "biggest" box, then the biggest box will fit the other boxes (and maybe the biggest box can be reduced to just fit the max need width and max needed height).
7) If the max width needed or max height needed exceeds the "biggest" box's, then you need to a new bigger box and rerun through the steps above so the original biggest box will now be part of the remaining boxes.

 

[ilan]

thanx a lot @JohnC for your reply.

1) First find the box with the longest width
2) Find the box with the tallest height
3) If a box is found that is both #1 and #2 above, then that is the "biggest" box so far

from the first 3 points of you i assume that i was unclear (or maybe i understand you wrong)

the "biggest" box IS NOT part of the boxes that I have. let say I have 7 boxes of different sizes. I need now to order 1 box from the factory that is big enough to hold all boxes (in a 2 dimensional way)

you can imagine it like you have 7 clothing items and you need now to choose the right suitcase that can hold all items. the problem is to try to use all space and not take 2 suitcases unless there is no way to put all items in 1 suitcase.

example:

the red box is the BOX that i need to calculate with the algorithm and also calculate all X/Y position of each box so i can make the "big" box as small as possible that will also be inside the Max width/height

 

[Star-Dust]

do you have standard sizes of red boxes?
do you calculate only in 2d or also in 3d?

 

[ilan]

do you have standard sizes of red boxes?
do you calculate only in 2d or also in 3d?

hi Star-Dust. i don't have a standard size of the red box i have only Max size of the red box but i want to get the red box as small as possible.
yes only in 2d. i will explain for what i need it. i want to create for a new app i am building a library that creates from several images a sprite sheet.
all images should fit in 1 image that is not bigger then 1024x1204 but if it can be smaller it should be smaller.

with the image, i create a XML file that holds all images dimension and names like this i can crop them back in my app.

 

[ilan]

i used until today TextureAtlas for this i also build a library for b4i that reads the atlas file and get the images with their dimensions and all data i just wanted to try to make my own library. this one works really great and the algorithm behind it interested me.

Use TextureAtlas without libGDX

Hi. This is a simple class compiled to library for using atlas pictures made for libgdx with libgdx-texturepacker-gui out of libgdx. For example, you have packed some texture like in "atlas.pack" and "atlas.png" and you want to use it with GameView, GameSpriteView, AcceleratedSurface or...

www.b4x.com

 

[TILogistic]

The calculations to do this:

3D Loading plan calculation for loading objects into containers, trucks and wagon cars | packer3d.com

trucks/cargo trucks. wagon cars.

www.packer3d.com

 

[ilan]

The calculations to do this:

3D Loading plan calculation for loading objects into containers, trucks and wagon cars | packer3d.com

trucks/cargo trucks. wagon cars.

www.packer3d.com

3d is to complicated i need it in 2 d only

 

[Sandman]

It's a lovely challenge that seems so simple, but is so complex.

https://en.wikipedia.org/wiki/Packing_problems
https://en.wikipedia.org/wiki/Square_packing_in_a_square
https://en.wikipedia.org/wiki/Squaring_the_square

Unless you have a really good reason for picking a solution like this, I would absolutely recommend doing something less compex (that might have the downside of wasting a bit of space or other resources).

 

[ilan]

it works so fine:

i just choose the folder with all images inside and it creates the Atlas Image with perfect result but how is he doing it
really interesting !

 

[ilan]

It's a lovely challenge that seems so simple, but is so complex.

yeah thats so true

Unless you have a really good reason for picking a solution like this, I would absolutely recommend doing something less compex (that might have the downside of wasting a bit of space or other resources).

the problem in b4x that i cannot put folders inside DirAssets folder so i cannot put all images in the FILES folder. it can be around 500 images so i preffer to pack them in atlas images and like this i will have less then 50 images in the files folder. this is much more simple to handle later if you want do updates.

 

[Sandman]

how is he doing it

It's open source, so it should be in there somewhere:
https://github.com/libgdx/libgdx
https://github.com/crashinvaders/gdx-texture-packer-gui

 

[ilan]

It's open source, so it should be in there somewhere:
https://github.com/libgdx/libgdx
https://github.com/crashinvaders/gdx-texture-packer-gui

yeah but it won't be fun if i just copy-paste the code. i want to understand the logic of building such an algorithm

 

[Sandman]

I wasn't suggesting a copy-paste. I was suggesting reading the code to understand the logic behind it.

 

[ilan]

I wasn't suggesting a copy-paste. I was suggesting reading the code to understand the logic behind it.

yeah thats a good idea

 

[yfleury]

Aera calculation, place the biggest box (black) and the next one smaller. With this one try width or high. Then try another one.

 

[TILogistic]

These methods can guide you.

Box Stacking Problem - GeeksforGeeks

A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.

www.geeksforgeeks.org

Algorithm logic for filling packages with items of different dimensions

I'm writing some shipping functionality for an application I am working on. One of the requirements is finding the most efficient way of determining what items can fit into a box. We also have a

stackoverflow.com

 

[OliverA]

Explanation of 2d problem with a solution (not “the” solution) with a Java version linked in the comments section by Alex Bonilla.

Binary Tree Bin Packing Algorithm

Personal Website for Jake Gordon

codeincomplete.com

 

[TILogistic]

Explanation of 2d problem with a solution (not “the” solution) with a Java version linked in the comments section by Alex Bonilla.

Binary Tree Bin Packing Algorithm

Personal Website for Jake Gordon

codeincomplete.com

Yes.

Traslate Javascripts to B4X.

* packer.js - simple algorithm for a fixed width/height bin
* packer.growing.js - complex algorithm that grows automatically

 

[emexes]

you have several boxes of different sizes. now you need to find the size of 1 big box that will hold all boxes inside with a space between each box.

I was working on a similar problem back when Trump won his first election. If you get stuck, I could dig up the code, work out wtf I did, and translate any bits that might be useful to you (from PowerBasic to B4X).