Design On 2D Irregular Nesting CAD System

Research on 2D irregular nesting problems is presented in this thesis. Nesting is a kind of planar layout optimization problem with object of arranging a number of pieces inside a given plate, and in the same time, below restrictions must be satisfied: (1) Pieces should be nested inside the plate; (2) Each piece should not overlap with another; (3) Certain restrictions on manufacture should be fulfilled. The optimization object of 2D nesting problem is to find an arrangement for pieces, and minimize the wasted material, in other words, the material usage ratio should be maximized. Nesting problem has a significant influence on the industries such as ship-building, costume making, and mold-manufacture.According to the key problems and difficulties existed in nesting problem, this thesis conducted a fundamental researching and proposed corresponding algorithms and resolutions. The main research objects of 2D nesting problem include geometric calculation, placing poligy, the application of intelligent optimization, and the application system on nesting problem. Detailed research achievements and creative ideas are listed below:1) Research on No Fit Polygon algorithm: this thesis had a detailed analysis and researching on the basic geometric calculation problems, especially for the key algorithm of nesting problem– No Fit Polygon (NFP) algorithm. NFP algorithm is the neck factor for the development of 2D nesting algorithms, due to the lack of precise, stable and fast NFP algorithm for a long time, some problems such as optimization of piece's location, piece's rotation and holes in plate are still not resolved. On the other hand, because the intelligent optimization algorithms have a relative slow convergence speed and need a large mount of iterative search procedure, defects of existing NFP algorithms have been the main...