Shalom!
First weekend of working on my application is almost gone. So the time is high to write a short report.
General thought: I am LOUSY mathematician. Not a mathematician at all!
During my student days I had never been good at it. Add the time that passed since then and you have the outcome.
But let me cut to the chase. Here’s short explanation for those of you who haven’t had a chance to read what my application is going to be. My plan is to write a program that will help engineers to optimise utilisation of sheets used for cutting flat items from steel plates. It is common activity in fabrication companies and multitude of software is now available on the market. So it’s not going to be any innovation or breakthrough.
Packing as many items as possible in given space is called bin packing problem. And there is multitude of its varieties (1D, 2D, 3D) and algorthims to solve it (shelf, guillotine, max-rectangles).
Currently, I am convinced to use guillotine algorithm. It is not the one that gets most optimal results but its implementation is quite simple and achieved results (despite that not the efficient) can be described as acceptable. So, that’s the current choice but I am not saying that it’s final.
Guillotine algorithm
Entry point for this algorithm are set of rectangles to be packed (height and width) and size of available sheet (again height and width). Rectangles are stored in a list. They will be attempted to be placed into available containers. Available spaces are similarly stored in a list. Each container is described by its height, width and bottom-left coordinates (X and Y). Initial list of containers contains only one item based on available sheet – the container has width and height derived form available sheet and bottom-left coordinates equal to 0,0.
First item from rectangle list will be placed in that only one container. After that is done the remaining space must be divided into two containers as shown in the picture below.
Decision how to split the remaining space can be based on various factors: arbitrary decision that we’re going to cut vertically or horizontally; by shorter cut-line; which cut generates a rectangle of bigger area; which cut generates a rectangle which is closest to square or which cut generates a rectangle which is most suitable for next item to be placed. It practical application it would be best to consider all options and take best results.
Next step is to place another rectangle from the list. We check which of available container can accommodate the item and which does that most effectively area-wise. And that continues until all rectangles are allocated.
To distinguish which rectangle is allocated and which container is taken I used separate lists. At the very end of each iteration I simply move the rectangle that has just been placed into a container to that second list and the same thing happens to the container – it is moved to second list.
There are also different strategies how to set the order of rectangles to be allocated. They can be sorted by area, by height or width, or by longer edge. Similarly to decision how to cut remaining space after placing a rectangle this strategy also generates different results. We choose the most optimal.
So, that’s basically it. If you wish you can check my first implementation on GitHub. But I have to warn you: the code is dirty as hell. But for the time being that’s just playing around. It will get cleaner and nicer 🙂
That’s it for today!
Regards, Michal.