Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle
Go Back  Xtreme Visual Basic Talk > > > Auto position as many given different shapes in rectangle


Reply
 
Thread Tools Display Modes
  #1  
Old 06-18-2015, 01:58 AM
BM_Hackerman BM_Hackerman is offline
Newcomer
 
Join Date: Jun 2015
Posts: 4
Default 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 ?
Reply With Quote
  #2  
Old 06-18-2015, 04:20 PM
Gruff's Avatar
GruffAuto position as many given different shapes in rectangle Gruff is offline
Bald Mountain Survivor

Retired Moderator
* Expert *
 
Join Date: Aug 2003
Location: Oregon, USA - deceased
Posts: 6,440
Default

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.

Example of nesting with the Sigmanest software product.
__________________
Burn the land and boil the sea
You can't take the sky from me


~T

Last edited by Gruff; 06-18-2015 at 04:29 PM.
Reply With Quote
  #3  
Old 06-19-2015, 02:02 AM
BM_Hackerman BM_Hackerman is offline
Newcomer
 
Join Date: Jun 2015
Posts: 4
Default

Gruff thank you for your reply !
I did not know that this type of programs are called as nesting !
This is a start for a better Google searching !

Do you have in mind any code for (inside) basic shapes such as squares, circles and rectangles ?

Even something basic to understand how to begin !
Reply With Quote
  #4  
Old 06-19-2015, 10:08 AM
Gruff's Avatar
GruffAuto position as many given different shapes in rectangle Gruff is offline
Bald Mountain Survivor

Retired Moderator
* Expert *
 
Join Date: Aug 2003
Location: Oregon, USA - deceased
Posts: 6,440
Default

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


~T

Last edited by Gruff; 06-19-2015 at 10:18 AM.
Reply With Quote
  #5  
Old 06-22-2015, 01:08 AM
BM_Hackerman BM_Hackerman is offline
Newcomer
 
Join Date: Jun 2015
Posts: 4
Default

Gruff Thank You very much !

Your help has been invaluable !
I already began the reading !
Reply With Quote
  #6  
Old 06-24-2015, 06:56 AM
hDC_0Auto position as many given different shapes in rectangle hDC_0 is offline
Contributor

* Expert *
 
Join Date: Feb 2004
Posts: 559
Default Binpacking and knapsack optimization

Another name for this type of computational challenge (besides "bin-packing"), is the knapsack combinatorial optimization problem.

Here's some current links:
http://mathworld.wolfram.com/Bin-PackingProblem.html
https://en.wikipedia.org/wiki/Knapsack_problem
http://xlinux.nist.gov/dads//HTML/un...dKnapsack.html

Some other (old) bookmarked links (from 2007 out of the Internet Wayback Machine Archive):
https://web.archive.org/web/20070821...K5/NODE192.HTM
https://web.archive.org/web/20070820...K4/NODE145.HTM

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).

Last edited by hDC_0; 06-24-2015 at 07:09 AM.
Reply With Quote
  #7  
Old 06-24-2015, 02:39 PM
Gruff's Avatar
GruffAuto position as many given different shapes in rectangle Gruff is offline
Bald Mountain Survivor

Retired Moderator
* Expert *
 
Join Date: Aug 2003
Location: Oregon, USA - deceased
Posts: 6,440
Default

Nice to see you again HDC!

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


~T
Reply With Quote
  #8  
Old 06-24-2015, 10:15 PM
Cerian Knight's Avatar
Cerian KnightAuto position as many given different shapes in rectangle Cerian Knight is offline
Polymath (in disciplina)

Super Moderator
* Expert *
 
Join Date: May 2004
Location: Michigan
Posts: 4,191
Default

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 10:23 PM.
Reply With Quote
  #9  
Old 06-29-2015, 02:03 AM
BM_Hackerman BM_Hackerman is offline
Newcomer
 
Join Date: Jun 2015
Posts: 4
Default

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 !
Reply With Quote
Reply

Tags
area, rectangle, shapes, visual basic 6


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump

Advertisement:





Free Publications
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
Programmers Heaven C# School Book -Free 338 Page eBook
The Programmers Heaven C# School book covers the .NET framework and the C# language.
subscribe
Build Your Own ASP.NET 3.5 Web Site Using C# & VB, 3rd Edition - Free 219 Page Preview!
This comprehensive step-by-step guide will help get your database-driven ASP.NET web site up and running in no time..
subscribe
Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle
 
Auto position as many given different shapes in rectangle
Auto position as many given different shapes in rectangle
 
-->