Help Designing a Glass Cutting Optimization Program

dragon432 · February 2017

Hi,

I've done some programming before (including designing things like brownian motion simulators, and the like in Processing, which yielded data that could be exported to excel) but I have trouble figuring out how to approach this new problem. Basically I need to design a program solving the 2D bin packing problem involved in glass cutting optimization by the most basic greedy algorithm. The program must take as input the size of glass sheets, the dimensions of needed pieces and their numbers, and then produce a drawing of the optimal arrangement (which minimises the amount of material wasted). The drawing should look similar to Figure 1 from this paper:

https://www.ac.tuwien.ac.at/files/pub/puchinger-04.pdf

I figured that I can take user inputs by using the controlP5 library. My issue is how to practically approach drawing the rectangles and the lines in the right positions? :-S If anyone can offer some step by step guidance about how to conceptualise the problem I'd greatly appreciate! Thanks!

Lord_of_the_Galaxy · February 2017

The math went beyond my brains, but if you figured that out, the rest is easy enough. So did you understand the math behind the glass cutting algorithm?

jeremydouglass · February 2017

@dragon432 --

Consider the largest-in-first, divide-and-conquer approach used here:

http://codeincomplete.com/posts/bin-packing/

Note that the resizing logic part won't apply to your case unless you have multiple sizes of glass sheet and are trying to pick the smallest available size.

Also note that the space-dividing approach described should work well for you if you also want all of your scrap glass to be rectangles when cutting is done.

Some discussion here:

http://stackoverflow.com/questions/8762569/how-is-2d-bin-packing-achieved-programmatically

jeremydouglass · February 2017

... I just looked at your link -- that paper contains a lot of very specific recommendations depending on what equipment you are using, whether or not you are stacking the output, etc. etc.

Is the end goal of your project actually real glass cutting, and is it computer-controlled glass-cutting? If so it seems like you should start by implementing the pseudo code in that paper -- it is quite authoritative!

dragon432 · February 2017

Thank you both for your responses! Yes, I do think I understand the math behind the cutting (greedy) algorithm (not really for the others).

Thanks for the links, I will have a look and try to implement quickly to see how it's working out! But yes, the space-dividing approach seems to make sense for the greedy algorithm! One issue I can foresee is that I am allowed to turn/rotate the rectangles, so basically width and height can change together. I guess I'll be taking this into account in the way I sort the rectangles in the beginning. So as I said, I'll give it a try, and I'll update! Thank you once again! :)

dragon432 · February 2017

Okay I've been having a look and designed the logic of a first-fit decreasing algorithm, but I would like some help implementing it in processing. I outline the solution below:

Start with a list of spaces containing just one sheet - the array should be of the form:

List_Spaces = { {x-coordinate, y-coordinate, Width, Height} }

Start with a list of pieces to be placed sorted from largest to smallest (sorting by largest side, whichever that one is):

List_Pieces = { {width_1, height_1}, {width_2, height_2}, etc }

    for (n=0, n<size(List_Pieces), n++) {
        for (m=0, m<size(List_Spaces), m++) {
             if (List_Pieces(n).w < List_Spaces(m).w && List_Pieces(n).h <      List_Spaces(m).h) {
    //This here will take each piece from largest to smallest, and for each one check each space, from smallest to largest, and find the first that fits, and then put the piece there:
                  rect(List_spaces(m).x, List_spaces(m).y, List_Pieces(n).w, List_Pieces(n).h)
                  some function to update List_Spaces // will detail this below
                  break loop
    } else if (m=size(List_Spaces-1)) {
    // this is in order to add a new sheet if the piece doesn't fit in any of the available spaces
          insert another sheet into spaces list + insert piece n into this new space + sort space list
    } else {
    return null
    }
    }
    }

Now this is a little sketch I made. I need to add a few else if statements to take into account cases of rotation, when the width and the height of the pieces can change, + statements in each case to label each rectangle created, color it, etc. but these aren't so important.

Now the essence I think will be the update the list of spaces function. Basically there may be two update List_Spaces functions. One in the case of adding a new bin, and one in the case of an older space being used. When a space is used the function should:

-remove the initial space from the list

-insert two additional spaces. Basically whenever a space gets used up, it will create two new spaces (even if one of those spaces has an area of 0). Say I just have my sheet and I add a block on it (starting always on the left). I go to the right-most edge of this block and draw a vertical imaginary line. This divides the remaining space into two - one below the block, and another to the right of the block. These two spaces are specified as follows:

The one below -> (x_occupied, y_initial_space+height_of_occupying_space, Width_of_occupying, height_initial_space-height_occupying)

The one to the right -> (x+width_of_occupying_space, y_occupied, Width_initial_space-width_occupying, height_of_initial_space)

Now those two (if they have both non-zero width and height) have to be inserted into List_Spaces. I'm not sure how to do this operation in processing... How would I insert additional elements into the 2d array in the way I have specified above? Furthermore, how would I go about ensuring that the spaces array is always sorted from smallest to largest by biggest side? What would be the commands/way to implement this? I much appreciate the help... it's been a long time since I've worked with processing, and I feel a bit stuck on this. Thanks!

Lord_of_the_Galaxy · February 2017

Still stuck on the math...

jeremydouglass · February 2017

@dragon432 -- Please edit your post and format the code (highlight, CTRL+o) as per https://forum.processing.org/two/discussion/15473/readme-how-to-format-code-and-text#latest

How would I insert additional elements into the 2d array in the way I have specified above? Furthermore, how would I go about ensuring that the spaces array is always sorted from smallest to largest by biggest side?

As your process is described you may not want a 2D array -- you may instead want a Java implementation of a binary search tree. Rather than "left" and "right" you want "below" and "right", but it is the same thing.

https://en.wikipedia.org/wiki/Binary_search_tree

See for example these discussions with example Java code:

dragon432 · February 2017

Please edit your post and format the code (highlight, CTRL+o) as per https://forum.processing.org/two/discussion/15473/readme-how-to-format-code-and-text#latest

Ok, hopefully I've done this correctly now, my apologies. Let me know if there's still something wrong with it, thanks!

As your process is described you may not want a 2D array -- you may instead want a Java implementation of a binary search tree. Rather than "left" and "right" you want "below" and "right", but it is the same thing.

Thanks for the links, I'll have a look and get back if I have any further questions! :)

Lord_of_the_Galaxy · February 2017

Your format of code is good enough.

dragon432 · February 2017

@jeremydouglass

Okay I've finally had some time to think about this today, as I was away from office the past two days. So yes, it seems it can work, but I have a few questions about the BST solution.

It seems to me that each glass sheet must have a separate binary tree; so every time when a new piece no longer fits in within an already existent sheet and its remaining spaces, then a new sheet needs to be added below that sheet. Then the program will be searching first in the binary tree of the first sheet, and then in the binary tree of the second sheet for each of the pieces remaining to be added. Would it be possible to add the new sheet within the same binary tree? The reason why I'm asking is that it seems that it wouldn't be possible - it wouldn't belong either under the bottom-node nor the right-node of any of the leafs in the currently existent binary tree. If the first sheet is the root, then the bottom-node, and right-node of the root will be the two spaces after it was split by adding one piece (both being smaller spaces than the initial sheet). So now a new sheet wouldn't belong anywhere in that tree.

Furthermore, it seems that this way of doing it effectively breaks the idea of the BST because the bottom/right nodes no longer follow the properties of being smaller/larger than the parent node. For example, when my sheet gets split into two spaces, both of those remaining spaces are necessarily smaller than their parent node. So I effectively have no way of sorting the spaces from smallest to largest in my find function.

jeremydouglass · February 2017

Two thoughts on this.

If you want to, you could add your second sheet above the top of your tree, underneath a node that contains sheets 1 (the previous root node) and now 2. HOWEVER note that this node is special (it doesn't specify a guillotine cut, or even require that the pre-existing sheets have matching dimensions) -- and it isn't binary (there could be three sheets!). In order to not have to track whether or not your tree is rooted in a sheet-stack, you might want to always have a top sheet-list node by default, even with starting with one sheet. To keep it binary, a sheet-list contains a sheet and a sheet-list. ...Or you could just keep a list of binary trees and logic to search across them for best fit open spots -- by the time you've done all that other stuff it is really the same thing!
Given that you are doing multiple bin packing in the style of the cutting stock problem -- https://en.m.wikipedia.org/wiki/Cutting_stock_problem -- you might want to consider using a library for this -- or at least inspecting the source of existing projects that use heuristics for multiple bins. One recommendation I see out there in discussion is for OptaPlanner, which is an open source Java library.

dragon432 · February 2017

Thanks for the reply @jeremydouglass

So from what I understand you're suggesting to have something like:

Root

S1, S2, ... Sn

Two binary nodes for each S1, S2, etc.

More binary nodes

Then what the searching for first smallest space algorithm would do is go through S1's tree, S2's tree, etc. and then remember the smallest space that the piece can be placed in, and then place it there. Do I understand you correctly?

At the moment S1, S2, and the other sheets will be the same size. In the future I plan to add scrap pieces as well to be used as sheets, so then S's can be different sizes too. But for the moment just considering single size sheets.

jeremydouglass · February 2017

Yes -- your implementation might have either:

A list of tree structures
A top non-binary node, as you explain above
Or, if you really want to fit the sheets into a pure binary tree data structure, a tree whose top node and each first right node is a stack index:

S is a binary sheet index node, T is bin backing tree for that sheet. The whole structure is a binary tree.

S1
T1 - S2
- T2 - S3
  - T3 - null

dragon432 · February 2017

@jeremydouglass Okay, so what would the sheet index node contain? Say S1 - would S1 contain say:

{x: 0, y: 0, w: width_sheet, h: height_sheet};

Or would T1 contain that?

I will sort this tree by area. So if S1 is as above, the bigger of the two spaces that are created after placing a piece would go in T1, and the smaller one a level down from T1, to the left.

dragon432 · February 2017

Hi guys, okay here's the thing I quickly set up so far:

BinaryTree tree = new BinaryTree();
Node a;
int [][] List_Pieces = {
 //{width,height}
 {35,5},
 {30,24},
 {9,24},
};

void setup() {
  size(400, 400);
  tree.addNode(0, 0, 40, 25); //first sheet
  tree.addNode(35, 0, 5, 25); //1st space created after FIRST piece placed
  tree.addNode(0, 5, 35, 20); //2nd space created after FIRST piece placed
  tree.addNode(0, 25, 40, 25);//SECOND piece doesn't fit, so insert second sheet
  tree.addNode(0, 49, 30, 1);//1st space created after second piece is placed
  tree.addNode(30, 25, 10, 25);//2nd space created after second piece is placed
  tree.printInOrderRec(a);//Test of in-order traversal function of space list
  println();
  for (int i = 0; i < List_Pieces.length; i++) {
  println(List_Pieces[i][0]+ ", " + List_Pieces[i][1]);
}

}

void draw() {
}



class Node {
  int xpos;
  int ypos;
  int w;
  int h;
  int max;
  boolean used = false;
  Node bottomNode;
  Node rightNode;

  Node (int xpos, int ypos, int w, int h) {
    this.w = w;
    this.h = h;
    this.max = max(h, w);
    this.xpos = xpos;
    this.ypos = ypos;
    bottomNode=null;
    rightNode=null;
  }
}

class BinaryTree {
  Node root;

  void addNode(int xpos, int ypos, int w, int h) {
    Node newNode = new Node(xpos, ypos, w, h); 

    if (root==null) {
      root = newNode;
      a = root;
    } else {
      Node focusNode = root;
      Node parent;
      while (true) {
        parent = focusNode;
        if (max(w, h) < focusNode.max) {
          focusNode = focusNode.bottomNode;
          if (focusNode==null) {
            parent.bottomNode = newNode;
            return;
          }
        } else {
          focusNode = focusNode.rightNode;
          if (focusNode==null) {
            parent.rightNode = newNode;
            return;
          }
        }
      }
    }
  }

  void printInOrderRec(Node currRoot) {
    if ( currRoot == null ) {
      return;
    }
    printInOrderRec(currRoot.bottomNode);
    print(currRoot.max+", ");
    printInOrderRec(currRoot.rightNode);
  }
}

Basically the user will feed in the sizes of the pieces to be placed and the size of the sheets on which the pieces are to be placed. At the moment this happens manually as seen at the top, and the pieces are also introduced manually for the moment until I write them to be introduced automatically once the user specifies them. What I'm looking for at the moment is at the bottom in the InOrderRec function. I want to specify another input to that recursive function (maybe another two inputs - height and width of piece to be placed). The idea is that the height and width of the piece to be placed are specified, then the recursive function is called and it traverses the tree in order sorted by biggest size of the space. Three scenarios:

(1) when it finds an exact space (width of space, and height of space equal width and height of piece to be placed) then it returns that node/space.

(2) when it finds a space where max(width, height) is smaller than max(width, height) of a piece, it should go back one by one through the nodes, and stop at the first one which meets the criteria width_piece<width_space and height_piece<height_space - it should return this node/space.

(3) if it reaches the end of the list, and still no space found, then insert sheet/node, and then return that newly inserted sheet/node.

Can anyone help me to develop the InOrderRec function at the bottom to do this? Thanks!

koogs · February 2017

continued here:

https://forum.processing.org/two/discussion/20779/how-can-i-make-inorder-traversal-of-a-binary-tree-stop-at-and-return-a-certain-node

(although that's annoying because it lacks the discussion of the tree in previous posts...)

Howdy, Stranger!

Categories

In this Discussion

Help Designing a Glass Cutting Optimization Program

Answers