need help in building an algorithm

ilan

Expert
Licensed User
Longtime User
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

Expert
Licensed User
Longtime User
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

Expert
Licensed User
Longtime User
thanx a lot @JohnC for your reply.

JohnC said:
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
Click to expand...

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

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

ilan

Expert
Licensed User
Longtime User
Star-Dust said:
do you have standard sizes of red boxes?
do you calculate only in 2d or also in 3d?
Click to expand...

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

Expert
Licensed User
Longtime User
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
 

Sandman

Expert
Licensed User
Longtime User

ilan

Expert
Licensed User
Longtime User
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

Expert
Licensed User
Longtime User
Sandman said:
It's a lovely challenge that seems so simple, but is so complex.
Click to expand...

yeah thats so true

Sandman said:
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).
Click to expand...

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.
 

ilan

Expert
Licensed User
Longtime User

Sandman

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

yfleury

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

TILogistic

Expert
Licensed User
Longtime User
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

Expert
Licensed User
Longtime User
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

Expert
Licensed User
Longtime User
Yes.

Traslate Javascripts to B4X.

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

emexes

Expert
Licensed User
ilan said:
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.
Click to expand...
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).

 
You must log in or register to reply here.
Menu
Log in
Register
Cookies are required to use this site. You must accept them to continue using the site. Learn more…