Paper Title:
A More Efficient Method for Clustering Sheet Metal Shapes
  Abstract

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.

  Info
Periodical
Main Theme
Edited by
F. Micari, M. Geiger, J. Duflou, B. Shirvani, R. Clarke, R. Di Lorenzo and L. Fratini
Pages
921-927
DOI
10.4028/www.scientific.net/KEM.344.921
Citation
E. Lo Valvo, R. Licari, "A More Efficient Method for Clustering Sheet Metal Shapes", Key Engineering Materials, Vol. 344, pp. 921-927, 2007
Online since
July 2007
Export
Price
$32.00
Share

In order to see related information, you need to Login.

In order to see related information, you need to Login.

Authors: Gang Tong, Maria Savchenko, Ichiro Hagiwara
Abstract:Surface reconstruction and NURBS surface generation based on 3D surface mesh partitioning are more essential today. In this paper, we present...
1824
Authors: Xiao Ping Liao, Juan Lu, Jun Yan Ma, Jia Hai Xue, Xiao Mo Yu
Chapter 7: CAD/CAM/CAE
Abstract:This paper introduces a novel approach to develop a 2D layout system based on the convex hull plus rubber band analogy. The data processing...
1219
Authors: Yu Ping Zhang, Zhao Ri Deng, Rui Qi Zhang
Chapter 8: Software Design and Development
Abstract:The triangulation of convex hull has the characteristics of point-set and polygon triangulation. According to some relative definitions, this...
1605
Authors: Yong Fang Linghu, Heng Shu
Chapter 6: Computer, Automation, Comunication and Image Applications in Industry and Engineering
Abstract:The improve hybrid genetic algorithms is proposed using the notion of species for solving rectangle-packing problems.This can control the...
931
Authors: Chong Ying Guo, Jian Hua Liu, Ke Jiang, Hai Bo Liu
Chapter 1: Materials, Technologies for Processing and Chemical Engineering
Abstract:In order to obtain an orientation error of planar feature accurate, a method to evaluate it using convex hull is proposed. Firstly, a convex...
185