Research Of Nestingalgorithm For Irregular Parts Based On Image

Metal sheet is a kind of the main material in ship building. A key problem in shipbuilding is how to design the cutting layout and let the utilization of the sheet be maximal.Nesting system for ship building can increase the production efficiency and the utilization ofresource, and it can ensure the shipbuilding intelligent and digital.The goal of the nesting problem is to place geometric figures in another given geometricfigure as more as posible, so that getting the maximum material utilization. This is a kind ofNP-hard problem. Furthermore, as to the large-scale or irregular nesting problem, thecomputation complexity will grow explosively when the problem scale increase. How toshorten the nesting time while increasing the utilization? It is the key point and difficulty inresearch. This paper studies the nesting problem deeply in data structure, optimization theory,algorithm, collaborative computing. A series of solutions and algorithms are brought forward.A testing nest system was developed and verified the algorithms. The achievments andinovations are listed as follow:(1) Put forward a set of data structures and evaluation methods based image processingAt present, most research of nesting problem is base on graphics. However, methodbased on image has special advantage. This paper explores in this area. This paper putforwards a method for overlap detection, out of bounds testing and evaluation. Throughcreating the data structures of “Vertex-Edge Chain”(describing part pixel coordinates andintersection information) and “Information Board”(recording which parts have occupiedwhich sheet pixels) and drawing according these data, analysis and evaluation can beachieved, so that the complexity of two-dimensional nesting problem based on imagedecreases to linear level from area level.(2)Brings forword the algorithm of dynamic neighborhood and parellel simulatedannealingA shortcoming of the method based on image is that the precision not enough. Expandthe image dimension can increase precision, but computing complexity will grow at very fastspeed. In order to resolve this conflict, this paper improves the neighborhood mechanism andof new solution accepting mechanism, and brings forward an algorithm of dynamicneighborhood scale and parallel simulated annealing. This algorithm resolved the conflict, sothat the speed of nesting increases greatly when using simulated annealing.(3) Put forward a decode method based on “open edge set”. Based on the “open edge set”, a encoding method which described with percentage andplacing angle is brought forward. This encoding method can represent all the possible places.Based of this percent encoding, we can search for good place quickly. This decoding methodis different from the traditional methods such as BL, BLF, Lowest Horizontal Line, remainingrectangle, and needn’t NFP. Rectangle pretreatment and collision post processing are notneeded either. It is a new idea for nest decoding.This paper continues to raise a mixed algorithm combined with the decoding method andgenetic algorithm. And further Some technologies that speed up nesting were discussed, suchangle match, open edge selecting and distributed method. These algorithms allow the nestingutilization be better. The utilization of some testing example exceed existing reports.(4) discussed the remnant management, and put forward a nesting plan method thatbased on remnant.This paper discussed the extraction, decomposition of remnants and the method ofattending nesting again automatically. Nesting plan and nesting optimization were realizeduniformly. On the one hand, it makes sheet selecting be more automatic. On the other hand, itmakes the sheet utilization be further promoted.(5) According to the above core algorithm, a nesting system has been developed.Experiments have proved that the system has good performance.