A more efficient method for clustering sheet metal shapes

The nesting of two-dimensional irregular shapes is a common problem which is frequently encountered by a number of industries where raw material has to be, as economically as possible, cut from a given stock sheet. A frequently recurring problem as far as cutting stock is concerned, is how to obtain the best nesting of some pieces of flat patterns which occupy minimal-area convex enclosure. The area of convex enclosure is related to the convex hull of the union of patterns which can be imagined as a large rubber band surrounding the set of all polygons. Our goal is to automatically obtain the smallest area convex shape containing all the patterns. As a matter of fact, Cheng and Rao have proposed an heuristic “stringy effect” procedure for clustering which follows a descending order of area of patterns. The “stringy effect” is able to put each new piece in a position which minimises the value of the distance between the centroid of each added piece and the centroid of the already formed cluster. The procedures till now shown in literature are quite complex. They make use of sliding techniques, and are not able to effectively work with relatively multiply-connected figures. In particular, the different procedures proposed are based on the No Fit Polygon computation of non-convex polygons, which often generates holes. This work is a proposal for a more efficient method, which can be used in heuristic procedure. In this paper a new procedure for the calculation of “No Fit Polygon” (NFP) of non-convex polygons is presented. Given two non-convex polygons, the algorithm is able to calculate their NFP very quickly and without any approximation by a polygon clipping method. By iterating this procedure with every polygon of our set, and positioning them using the “stringy effect” technique, it is so possible to obtain a convex shape that contains all the patterns, having the minimal area.