Research On Two-dimensional Irregular Strip Packing Problem With Random Rotation Angle

Two dimensional irregular strip layout problem is a kind of two-dimensional layout problem,which is also can be called by two-dimensional cutting problem or two-dimensional blanking problem.It is closely related to two-dimensional one size fits all,two-dimensional rectangular layout and so on.The essence of the problem is that for a given raw material,all the parts to be arranged are placed in it on the basis of non overlapping,so as to minimize the use area of raw materials,or the waste raw materials.If described in mathematical language,the problem can be understood as placing a given polygon to be arranged according to the principle of contact but no overlap in a rectangular area with a fixed width and unlimited length(the polygon is a simple polygon with arbitrary shape).The final placement effect is to meet the maximum ratio of the effective use area to the actual use area of the rectangular area.The specific research contents are as follows:The collision detection algorithm with minimum moving distance is adopted for the translation and intersection judgment of simple arbitrary polygon.The design rules and selection criteria of polygon increasing edge and decreasing edge and increasing chain and decreasing chain involved in this algorithm are explained.Compared with the traditional judgment algorithm of critical polygon of simple arbitrary polygon,the collision detection algorithm with minimum moving distance is easier to understand and the amount of calculation is significantly reduced.According to the basic idea of the classical BL algorithm,this paper takes the extreme right vertex of the arranged parts as the step increasing standard,and changes the original way of arranging samples with fixed length step into the way of variable length step.The minimum moving distance and rotation angle algorithm are constructed by using the distance formula of vertices and edges sliding through a straight line and the rotation angle formula of points and edges rotating through rotation operation.The movable distance and rotation angle between polygons are obtained,and a layout positioning algorithm based on the minimum moving distance and rotation angle is proposed.Based on the layout and positioning algorithm which is supported by the minimum moving distance algorithm and the minimum rotation angle algorithm,the concept of secondary sliding along the sliding belt formed by the collision edge after rotation is proposed;The available blank area formed between the templates after the initial layout is filled with the reverse detection algorithm to maximize the use of the plate.