Matrix

Calculate valid area by using matrix

The customer request is passed to a function indicating the rectangle relative to an allocating unit, that is, if it is strip requisition, then this rectangle will have the minimum length of a strip and will have the equivalent width of the minimum number of strips in an allocation; if it is a plates requisition, then the length will be equivalent to the minimum number of plates that can be allocated in a line and the equivalent width to the width of a plate and if it happens to be a coil requisition, then the rectangle length should be equivalent to the minimum tonnage required to each coil.

As a result, this function should answer if there is any area in the coil that is available for the allocation of the supplied requisition. If positive, then it should return all areas in a descending order of size.

In order to calculate the available areas, the semi-straight lines from the edges of the rectangles, representing the defects and allocations already performed, will be extended up to the edges of the coil as shown in figure.

Figure: Map division in matrix cells having the defects border as a reference

Then, a matrix will be generated in which each element will be representing a cell resulting from the cutout made on the coil. In the case of figure , the matrix will have 9 lines and 9 columns. This matrix will store the necessary calculation for identifying which cells will be able to receive the bottom right corner of the requisition. Once these cells have been identified, they should be expanded as much as possible to the left, then to the right, after that upwards and next downwards. This expansion will be made until the edge of the coil or some area that hasn't been made available for allocation is found. This will result in the largest area as possible that can be used from the identified cell. This process is repeated until there is no more area that can be reported. These areas are then put in a decedent order of size and returned as result.

I developed a tinny executable that I did to demonstrate the algorithm to search for valid areas by using matrix: Valid area by matrix