A More Efficient Method for Clustering Sheet Metal Shapes


Article Preview

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 minimalarea 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.



Main Theme:

Edited by:

F. Micari, M. Geiger, J. Duflou, B. Shirvani, R. Clarke, R. Di Lorenzo and L. Fratini




E. Lo Valvo and R. Licari, "A More Efficient Method for Clustering Sheet Metal Shapes", Key Engineering Materials, Vol. 344, pp. 921-927, 2007

Online since:

July 2007




[1] S.K. Cheng, K.P. Rao, Quick and precise clustering of arbitrarily shaped flat patterns based on stringy effect, Computers and Industrial Engineering 33 (3-4) (1997) 485-488.

DOI: https://doi.org/10.1016/s0360-8352(97)00174-5

[2] M. Adamowicz, A. Albano, Nesting two-dimensional shapes in rectangular modules, Computer Aided Design 8 (1) (1976) 27-33.

DOI: https://doi.org/10.1016/0010-4485(76)90006-3

[3] A. Mahadevan, Optimization in Computer-Aided Pattern Packing, (1984) Ph.D. thesis, North Carolina State University.

[4] J.A. Bennell, K.A. Dowsland, W.B. Dowsland, The irregular cutting stock problem - a new procedure for deriving the no-fit polygon, Computers & Operations Research 28 (2001) 271-287.

DOI: https://doi.org/10.1016/s0305-0548(00)00021-6

[5] H. T. Dean, Y. Tu, J. F. Raffensperger, An improved method for calculating the no-fit polygon, Computers & Operations Research 33 (2006) 1521-1539.

DOI: https://doi.org/10.1016/j.cor.2004.11.005

[6] T. Lozano-Perez, Spatial Planning: A configuration space approach, IEEE Transactions on Computers, c-327 (2) (1983) 108-120.

[7] A. Murta, A generic polygon clipping library, ver 2. 32, 2004 (Downloadable from website http: /www. cs. man. ac. uk/~toby/alan/software/index. html).

[8] P.K. Agarwal, E. Flato, D. Halperin, Polygon Decomposition for Efficient Construction of Minkowski Sums, Proc. of ESA 2000, 8th Annual European Symposium on Algorithms.

DOI: https://doi.org/10.1007/3-540-45253-2_3

[9] E. Flato, D. Helperin, Robust and Efficient Construction of Planar Minkowski Sums (2000), Abstracts 16th European Workshop Comput. Geom. (2000) 85-88.

[10] B. Schachter, Decomposition of Polygons into Convex Sets, IEEE Transactions on Computers c-27 (11), (1978) 1078-1082.

DOI: https://doi.org/10.1109/tc.1978.1675001

[11] E. Lo Valvo, Nesting of irregular shapes on a strip in metal stamping blanks operations, Proc. of II Convegno AITEM (1995) 31-38.

[12] B. Chazelle, D. Dobkin, Optimal Convex Decomposition, in: Computational Geometry, Elsevier Science Publishers, North-Holland, 1985, pp.63-133.

[13] J. M Keil, J.R. Sack, Minimum decompositions of polygonal objects, in: Computational Geometry, Elsevier Science Publishers, North-Holland, 1985, pp.197-216.

DOI: https://doi.org/10.1016/b978-0-444-87806-9.50012-8

[14] J. Fernandez, L. Canovas, B. Pelegrin, Algorithms for the decomposition of a polygon into convex polygons, European Journal of Operational Research 121 (2000) 330-342.

DOI: https://doi.org/10.1016/s0377-2217(99)00033-8

[15] J.F. Oliveira, A.M. Gomes, J.S. Ferreira, TOPOS - a new constructive algorithm for nesting problems, OR Spectrum 22 (2000) 263-284.

DOI: https://doi.org/10.1007/s002910050105

[16] J.A. Bennell, K.A. Dowsland, A tabu thresholding implementation for the irregular stock cutting problem, International Journal of Production Research 37 (16) (1999) 4259-4275.

DOI: https://doi.org/10.1080/002075499189763

[17] Esicup DataSet download page - http: /paginas. fe. up. pt/~esicup/modules. php?name=Data_Sets.

[18] E. Lo Valvo, Clustering of arbitrarily shaped flat patterns using simulated annealing and the no fit polygon, in: 1° International Seminar on Progress in Innovative Manufacturing Engineering (PRIME 2001), Sestri Levante 20-22 Giugno 2001, pp.99-104.