Auto position as many given different shapes in rectangle

Hi
I would like to make a program in visual basic 6 that I would give the dimensions of an rectangle and later I would give some certain shapes with the dimensions and the program will auto arrange the shapes in a such a way so to place as many as possible shapes in the rectangle but without any shape to overlap the other.

Basically it has to make about better usage of the rectangle area !

Can anyone help me with a sample code or any idea ?

What you are describing is known as nesting software. If the shapes can be anything then it becomes massively complex. It has to solve for every possible arrangement with all possible rotations of each part to find the best fit. Most sheet metal nesting companys guard their algorithms closely. They charge many thousands of dollars per seat just for the basic packages. I doubt your going to find code for free that does a decent job in a timely manner.

If those are the only shapes you will be using then it becomes more manageable.

Circles laid out orthagonally take the same space as a square. A square is the same as a rectangle. So given that situation one could sort all rectangles by size in descending order.
Then fit as many as possible per sheet. You would mark the used rectangles in your list as you worked your way down. You would keep looping through your list until all rectangles in the list are marked. when your parent rectangle is full you add a new parent rectangle. None of this deals with all possible combinations or rotations.

Another term used for this sort of program is called 'Bin Packing.' Here is a thread that has some code to download.

__________________ Burn the land and boil the sea
You can't take the sky from me

It actually has real world applications, such as the number of boxes that can be packed in a truck (and packing them most efficiently): Page about 2D Load Packer software
(no source code is available - Gruff is right that such code, given it's commercial application, is jealously guarded).

Such code also comes in handy when designing rpg game inventory systems, like the one that the old version of Diablo uses.

Since this an "NP-Hard" type problem from a mathematical/algorithmic standpoint,
I don't know of any Visual Basic code that can truly provide the most perfectly optimal solution for solving this (Gruff is right),
however, just to let you know the thread Gruff linked to is VB.Net (not VB6),
but you may be able to "backwardly" translate it.

At the very least, that thread has links to several other related xvbt threads over the years that deal with a similar type coding.

My advice to BM_Hackerman: limit your shapes to just rectangles initially.
This alone with be a hard enough design goal to solve.
Then expand to circular/triangular shapes as well as other convex/concave shapes delimited by an axis-aligned bounding box (AABB).

If you get really extreme you would also need to check for irregular shaped cavities inside individual parts and try to nest more parts in those spaces.
This wrinkle adds even more complexity.

__________________ Burn the land and boil the sea
You can't take the sky from me

Some of the NP problems I've dealt with in code are not too bad once pre-bin sorting, tree-pruning and dynamic statistical indexing were applied. For example, I nailed a brute force proof that the 48 contiguous United States map cannot be filled with only 3 colors in just 28 iterations (after the pre-sort)... which I understand should not be possible based on its NP Complete status (though I haven't spent much time researching others efforts).

That is the point. Give it a try, even if you are not sure how to proceed at first.

For example, I would suggest calculating the main region area and searching for a combination of shapes whose total area divided by an expected packing efficiency factor (say 0.9) is less than the main area. Reducing the size of each shape to force a fit and allowing them to grow (to full size), collide and move using a tectonic model will give a result, but far from optimal. If you can't follow this example, try your own ideas.

__________________
I got all the answers wrong on the GLAT, apparently even #9 (where I put a period in the middle of the box and labeled it 'singularity ripe for rapid inflation').

Last edited by Cerian Knight; 06-24-2015 at 11:23 PM.

Cerian Knight thank you very much for your proposal/idea !
hDC_0, YES you are right that the thread Gruff linked to is VB.NET and not VB6 , but the basic idea of VB6 and VB.NET are basically the same and the code is a good written one and relatively easy to understand it. I believe that I will have no issue analyzing and working with code.
In reality I have already working with this code and I started to develop it more in order to check all possible combinations of 90 degrees rotation (as this code do not rotate the shapes) !
I do not know if the result will be good but I will give a try !

Thank you very much guys !
If you find anything that may help me more please inform me !
I will inform you for my code results !

The ASP.NET 2.0 Anthology
101 Essential Tips, Tricks & Hacks - Free 156 Page Preview. Learn the most practical features and best approaches for ASP.NET. subscribe