2D Packing-Are there any BCX examples?

[djsb]

Thanks.

[Wayne Halsdorf (RIP)]

Here are some pdfs that may help.
https://www.sciencedirect.com/science/article/pii/S0166218X0100347X
https://www.sciencedirect.com/science/article/pii/S1877050913003980
https://www.sciencedirect.com/science/article/pii/S1572528605000216

[Wayne Halsdorf (RIP)]

I know this as a knapsack problem in combinatorial optimization where the best solution is the sum of the areas of all the boards you select. You will need a structure containing the minimum description of the board (area, length, width, any other needed information). You will have to decide on pruning search or an exhaustive search.

[djsb]

l A search using gerber will turn up several messages.

That could have been me asking about something called Gerb merge quite a while ago.

[Wayne Halsdorf (RIP)]

l A search using gerber will turn up several messages.

[MrBcx]

There was some talk about this subject on the old forum.  Since I can't find Ian's database of the messages from that forum I don't know how it ended.

https://bcxbasiccoders.com/bcxolr/bcxolr_downloads.html

I have the reader installed, ran a few searches, but found nothing.  Maybe
the old discussions used terms other than bin packing, arrangement, etc.

[jbk]

this is an interesting problem with some unusual ways to solve https://ieeexplore.ieee.org/document/5645122

[Wayne Halsdorf (RIP)]

There was some talk about this subject on the old forum.  Since I can't find Ian's database of the messages from that forum I don't know how it ended.

[djsb]

 

[MrBcx]

David,

If you have MS Excel on your PC, this might be of interest to you.

The video is a good place to start.

https://people.bath.ac.uk/ge277/bpp-spreadsheet-solver/

[mekanixx (RIP)]

Thank you.
I will check out the references that are mentioned.
But first I will spend some time trying to get more familiar with BCX and what it can do. I'm sure I can still come up with some helpful utilities.

David.

FWIW, the code at https://github.com/juj/RectangleBinPack compiles and runs using MingW using the makefile provided after uncommenting a couple of lines (lines 8 and 9) in the makefile.

Doyle

[djsb]

Thank you.
I will check out the references that are mentioned.
But first I will spend some time trying to get more familiar with BCX and what it can do. I'm sure I can still come up with some helpful utilities.

David.

[MrBcx]

David,

You have a common, interesting problem to solve.

A StackOverflow top answer references a pdf that I pulled off the Wayback Machine for you. (See attached)

The very brief reading that I've done on the subject asserts there is no generalized optimum solution,
only several well known algorithms that yield varying results.  People have also combined those algos
into hybrid solutions with varying success.

Joel Verhagen has a blog that looks interesting:


References:

https://stackoverflow.com/questions/8880975/is-there-a-c-source-lib-to-solve-2d-bin-packing-with-a-rectangular-bin-not-sq

https://www.joelverhagen.com/blog/2011/03/jim-scotts-packing-algorithm-in-c-and-sfml

[Michael Henning]

I don't know of any examples already written for BCX. I'm sure you can find some algorithms with a search on the internet. Once you have that the implementation should be fairly easy in BCX.

Your current thoughts are on the right track. Although you can't really determine the fit by just using the area of each rectangle unless your contained area is unlimited. My first thought would be to create a struct TYPE for each rectangle containing the name, size and a couple of flags to keep track of processing. You could then sort the array by size, area...etc.

[djsb]

I'd like to try to understand how I can fit different sized PCB's into a larger fixed area. The size of each PCB is defined by the dimensions of the board outline file (in Gerber format). To make it simpler, these are usually rectangles.
I have to examine the sizes of several (maybe around 30 or so) PCB's (one at a time) in a directory and just select the PCB's that will fit into the predetermined fixed area. At the moment I do this manually by importing each PCB into the board layout application (KiCAD EDA which uses files saved in ASCII format). I then move them around and PANELLIZE them. I them export the PANEL (which has a fixed size) in Gerber format (which is also text based).
I'm hoping to semi-automate the process of selection somehow. If I am not mistaken, this is classed as a 2D packing problem.
Are there any BCX examples that would help me to understand how to tackle this? I already have a BCX example that measures the board outline dimensions (attached). I guess my first task is to measure the board outline dimensions of EVERY board file in a given directory one at a time and then sum the total area. Or am I misunderstanding the 2d packing method (I probably am). Any thoughts?