An Efficient 2D Irregular Nesting Algorithm Based On Contour Geometric Invariant Description And Code Matching

The nesting is also called the layout cutting and packing.It can be described formally as that some given pieces are placed as much as possible in a given plate,without overlap between any two pieces.Two-dimensional(2D)irregular nesting has been most widespread in industrial applications.However,the relative position between two contours are usually searched by rotating or transforming the contour as its description is lack of geometric invariance.These methods easily miss the best layout position resulting in a poor solution.In this paper,a new nesting algorithm is proposed by combining the geometric invariant description and coding matching for free-form contours to solve the rotating and position connecting problems referring to the parametrization idea of curve geometric invariance.Main contents of the paper are as follows:(1)Geometric invariant description of contours.Analyzing classic expression methods for layout contour.After that,the geometric description form of layout contour was deduced and realized combining with the theory of curve geometric invariant description.(2)Extracting the contour shape features.After obtaining the geometric invariant description of the contour,the contour was encoded to obtain the shape information of the contour to describle the contour shape features.(3)Contour matching and connecting with similarity features.The longest common substring was proposed to solve the contour matching problem using to search the similar features of the two contour.The contour matching and connecting is accomplished by using vector superposition method with similar features of the contour.And then a positioning method based on hub-and-spoke is proposed to solve the contour position problem limited by the raw material boundary.Finally the algorithm is implemented and tested with different amounts and shapes of contours chosen from freeform surfaces of plane projections.The test results show that the proposed algorithm improved the nesting utilization and efficiency greatly.(4)The nesting algorithm based on the similar feature measuring with the longest common subsequence.For the generality of similar features of the layout contour,the foregoing methods are improved on contour shape features extraction,similar feature measuring and matching and contour connect methods to make the proposed algorithm more practical.Firstly,the angle sequences are extracted based on Difference Freeman Chain Code as the new contour descriptor to speed matching;And then the similarity features are found by the longest common subsequence matching based on the dynamic programming algorithm.Finally,the contour is guided by the distance-proximity algorithm to complete the connecting and position without overlap.The results show that the proposed method can improve the efficiency of layout and material utilization based on the effective contour feature information.