# Descending Packing Algorithm for Irregular Graphics Based on Geometric Feature Points

Authors: Pengfei Zheng; Jingjing Lou; Dajun Lin; Qi An
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

The packing for two-dimensional irregular graphics is one of the NP-complete problems and widely used in industrial applications. In this paper, a descending nesting algorithm for a two-dimensional irregular graph based on geometric feature points is proposed. Before the packing, the parts to be packed are sorted, matched, and spliced, and the matching of the rectangular pieces and the rectangular-like pieces is carried out according to the plate size. On this basis, the geometric feature points of the parts are used to construct the packing baseline, and the packing is accurately carried out according to the principles of the bottom left, the principle of the lowest center of gravity, and combination with virtual moving, rotating collision calculation. The computation of the moving collision distance between the graphics is replaced by the projecting computation of the geometric feature points of the graphic parts, so the computation amount can be reduced. Also, this method is used to test a number of benchmarks examples which are provided by ESICUP (EURO Special Interest Group on Cutting and Packing), which show that the proposed algorithm not only can improve packing but also has better stability and reliability.


---

## Body

## 1. Introduction

Two-dimensional packing is a classic problem, and the purpose of it is to find a layout with minimal waste on a given shape and size of a plate. The packing technology has been widely used in sheet metal, clothing, shipbuilding, and furniture industries [1]. For the problem of cutting and packing of irregular parts, how to obtain the applicable layout of the geometric conditions is very complicated since all parts must be completely inside the plate and cannot overlap [2]. Two-dimensional irregular packing is a kind of combinatorial optimization problems, which is a NP-complete problem. The calculation complexity is extremely high, and there is no effective mathematical calculation method up to now. Due to its wide application in modern industry, researchers have done a lot of research on this and also proposed many feasible solutions. For example, Baldacci et al. [3] used Lagrangian relaxation method and heuristic algorithm to carry out defect layout and applied it to the leather clothing and furniture industry, but the convergence of this method is difficult to guarantee. To reduce the complexity of the packing problem, pairwise clustering was introduced in literature [4] to group congruent polygons together in pairs. Pairwise clustering was done automatically to discover matched features among multiple present polygons. In literature [5], a systematic study of the problem and an exact branch-and-bound Algorithm was made by reducing the size of the problem to be solved at each node. Based on the literature [5], Wang et al. [6] utilized a novel branching scheme to deal with the reverse convex quadratic constraints in the quadratic model and incorporated a number of problem-specific algorithmic tweaks. Literature [4–9] all belonged to the NFP- (no-fit polygon-) based packing algorithm. Although some improvements had been made to achieve packing, due to the large amount of calculation of NFP itself, the algorithm efficiency could not be improved well. Based on two known techniques, the vector graphics were transformed into pixel matrix by AutoCAD before packing, and the bottom-left-fill algorithm was used for packing, an irregular stock cutting system (NEST) developed on AutoCAD software platform, which is presented in [10]. But this method lacks accurate collision detection, and the material utilization rate is not very high. Since the existing packing algorithms do not consider the shape contour features, an irregular packing algorithm was proposed to solve this problem based on a principal component analysis methodology in [11], but the collision detection between two pixels increases the amount of calculation. Jones et al. [12] introduced a fully general, exact algorithm for packing irregular shapes based on a specialized branch-and-bound algorithm together with some heuristics. Camacho et al. [13] proposed an adaptation to the two-dimensional irregular bin packing problem of the Djang and Finch heuristic (DJD) which is originally designed for the one-dimensional bin packing problem. A new mixed-integer model in which binary decision variables were associated with each discrete point of the board (a dot) and with each piece type was proposed in [14]. Based on [14], a mixed-integer-linear programming formulation was proposed to optimize the packing of particular polygonal shapes [15]. These algorithms above used discrete methods to calculate the collision distance, but the discretization method required a large number of data points. Liao et al. [16] adopted a physical method that used the rubber band packing algorithm to simulate a rubber band wrapping those packing irregular shapes. The simulation showed a visual and fast packing process. However, this method had no advantage for mixed packing of multiple irregularities. There are some strip packing algorithms, heuristic algorithms, hybrid algorithms, three-dimensional packing algorithms, and some applications of these algorithms [17–25]. But some are only suitable for rectangular packing, and the calculation is complicated, which will be improved in this paper. In addition, similar heuristic optimization layout ideas have also been applied to more and more fields, which are also worth learning [26–29].In summary, the two-dimensional irregular graphics packing algorithm can be roughly divided into two categories: one is to simplify the two-dimensional irregular layout problem to a regular piece (rectangular bounding box) layout problem and perform simplified layout and the other one is based on the BL principle, through extrusion, abutment, and pattern rotation to adjust the abutment angle to optimize packing and improve material utilization. However, when you rotate and adjust the docking angle if you choose a preset angle for docking, you will lose the best angle docking. And, in the process of horizontal moving docking and vertical moving docking, it is often to cause the overlapping phenomenon in the previous moving direction after the second movement.In view of these defects, a two-dimensional irregular descending geometric optimization packing algorithm based on the geometric feature points of graphs is proposed in this paper. This paper has made some contributions in the following aspects:(1)
Use the graph normalization preprocessing to sort the layout parts in descending order that overcomes the space waste defect caused by random layout.(2)
Use variable packing baseline to arrange the layout graphs by collision. Overcome the limitation of layered packing strategy and improve the compactness of packing.(3)
According to the principle of adaptation, the precise touch between the layout graphs is replaced by the discrete feature points of graphs, which greatly reduces the amount of calculation.(4)
The adaptive virtual collision computing is carried out to reduce the calculation caused by the graphs’ movement, which also avoids the phenomenon that the one-way collision calculation easily causes the failure of finding the best packing position.


## 2. Methods

This paper proposes a two-dimensional irregular packing algorithm. This method builds an irregular packing baseline based on the geometric feature points of the layout piece. In this paper, the layout of the same parts is processed in advance to improve the priority of the same parts packing. Therefore, the regularity of the similar parts packing is effectively improved. The calculation of the distance between horizontal and vertical collisions and the angle of rotation against collisions can greatly enhance the efficiency of packing and the positioning accuracy of a one-time layout. The calculation of the graphic feature points is used instead of the graphic mobile layout, which realizes virtual packing and can save time. Figure1 shows the main processes of this algorithm.Figure 1
Flowchart of the proposed algorithm.


### 2.1. Graphics Preprocessing

#### 2.1.1. Graphic Prenormalization

In order to simplify the packing process and reduce the time of repeated searches, before the packing, it is proposed to encode and store graphics with a unified standard to be packing. The normalization rules are to sort the geometric feature points of all the pieces by arranging clockwise and to store them with the BL (bottom left) point as the starting point, to extract the geometric feature points of the packing parts and save them as the points group table named obj(i)_plst. As shown in Figure 2, the layout part is a polygon formed by eight points connected in sequence. According to the normalization rules, the order of the eight points stored in obj(i)_plst is P8⟶P1⟶P2⟶P3⟶P4⟶P5⟶P6⟶P7. The purpose of such normalization is to facilitate the subsequent search of the reference points for packing; that is, the first point of each points’ group of the part is used as the reference point for the packing movement.Figure 2
Increase graphic feature points. (a) Graphics before midpoint adding process. (b) Graphics after midpoint adding process.
(a)(b)In order to ensure a unique correspondence in the process of matching the initial layout patterns, during the normalization process, the horizontal and vertical lines will automatically add points. As shown in Figure2(a), where the lines P1P2¯, P3P4¯, P5P6¯, and P7P8¯ are horizontal lines, and the lines P1P8¯, P2P3¯, P4P5¯, and P6P7¯ are vertical lines, adding point processing is required for them. The method of increasing the midpoints is adopted. After processing, it is shown in Figure 2(b). Its role is to increase the number of discrete points in order to minimize the loss of information caused by the reduction of the vector graph to the discrete feature points representation and ensure the effectiveness of subsequent graphic matching and collision calculation. In order to reduce the recognition of the graphic features for packing, when the layout pieces contain arc features, the arc discretization will be used to divide the arc into discrete points and connect the discrete points with polylines for approximate replacement. After the packing is finished, the arc features are restored.


#### 2.1.2. Matching Stitching of Graphics

Since the two similar pieces can be reassembled into a more compact new piece, reassembling the similar pieces first and then arranging will greatly save the layout space and improve the utilization of the layout. In the packing process, in order to avoid similar parts as independent pieces to be individually packed, the graphics are matched and stitched during the preprocessing of the graphics. The principle of graphic matching is the preliminary arrangement of packing parts according to area and number of feature points; that is, two layout parts with the same area and the same number of feature points are treated as similar pieces, and the features with the highest degree of coincidence are used as matching objects. As shown in Figure3(a), the highest coincidence characteristics of the layout pieces P and T are P2P3¯ and T1T3¯, respectively. After the matching and stitching process, the layout pieces P and T are merged into a rectangular piece. The prepacking pieces in Figure 3(b) are not the same kind, but they belong to similar kinds. They need to be matched and spliced in the preprocessing stage; otherwise, it will waste the packing space in the subsequent packing. When the moving parts P and T are matched by moving and touching, the feature point P3 corresponding to the touching points are T2 and T3, and there is a nonsingle correspondence relationship. At this time, such a point is not used as the touching feature point. The same is for points P2, P4, P5, and P6. By adding points as described in Section 2.1.1, we can use the newly added midpoints P14, P15, and P16 as horizontal touchpoints for matching and stitching. In this way, we can complete the precise splicing of two layout parts and reduce unnecessary waste for the next optimization of packing.Figure 3
Graphic matching and stitching. (a) Stitching of similar pieces. (b) Stitching of heterogeneous pieces. (c) Rectangular-like piece. (d) Open point and close point.
(a)(b)(c)(d)In order to better adapt to the size of the board for packing, during the preprocessing of the graphics, the rectangular parts and rectangular-like parts are preferentially matched and stitched. As shown in Figure3(c), the packing piece A is located in the smallest rectangular enclosing frame B. We define the approximation coefficient of a rectangular-like piece as sδ=sA/sB, where sA is the area of piece A and sB is the area of piece B. The value of sδ will directly affect the packing effect. Through a large number of experiments, an appropriate value of sδ is chosen as follows: if it is satisfied sδ≥85%, then, A is called a rectangular-like piece. In the preprocessing stage, if a certain piece meets sδ≥90%, it will be matched and spliced. The maximum length of the splicing is the width of the plate. The purpose is to make the bottom layer “fully packed” as much as possible to reduce the waste of the plate.


#### 2.1.3. Constructing Packing Baseline Based on Geometric Feature Points

In 2D regular parts packing, the strip model is commonly used to achieve layered packing. However, in irregular packing, it is difficult to form a clear strip model and the horizontality of the layered layout cannot be guaranteed, so this strategy is not suitable for the packing of two-dimensional irregular parts. However, the layout idea still has guiding significance. Based on this idea, the strategy of layering layout of the strip model is extended, and the idea of packing baseline based on geometric feature points is proposed. The packing baseline is not a traditional horizontal baseline, but a multipolyline and contour line updated in real time.Definition 1.
As shown in Figure3(d), we divide the area around a point into four parts: top left, top right, bottom left, and bottom right. We set this point Pi as the eye. If you cannot see that side, then this side is considered closed; if you can see it, this side is considered open, so the top right side of point Pi is close, and other sides are open. If all sides of a point (top left, bottom left, top right, and bottom right) are closed, that is, the point is surrounded by the fixed pieces, these geometric feature points are called closed points, as C1 and C2 shown in Figure 4.;Figure 4
Packing baseline with geometric feature points.Definition 2.
If at least one direction around the point (top left, bottom left, top right, and bottom right) is not closed, that is, the point is not completely surrounded by the fixed parts, these geometric feature points are called open points, asO1 and O2 shown in Figure 4.
Connecting all the current open points into a polyline in a certain order, that is, the packing baseline based on the geometric feature points, the feature points that make up the baseline are called the open points group and recorded as base_open_plst. Similarly, record all the points forming a closed-loop asclose_plst. As shown in Figure 4, O5⟶C1⟶C2⟶O5 is a closed points group, which is called the packing closed area. The packing closed areas are also the source of waste of layout materials. The smaller the packing closed area, the better the layout effect and the higher the material utilization rate.
As shown in Figure4, the current packing baseline is O1⟶O2⟶O3⟶…⟶O15, and the currently scheduled piece is A. According to the BL principle, its initial position is the position of the dashed box in Figure 4. Obviously, this position is not the optimal layout, so the position needs to be adjusted by the assistance of a further heuristic collision strategy.


### 2.2. Packing Rules

#### 2.2.1. Sorting Descending Order

In the graphic preprocessing, all parts have been normalized and matched and stitched, but the matching and stitching process will reorganize some of the layouts (shown in Figure3), so we need to do a stitching process for the recombinant pieces before packing. The processed parts are used as the initial input graphics. The area of each recombinant part is calculated and packed in descending order according to their area.According to Pick’s theorem, we can transformn polygons into n-2 triangles and use the cross multiplication to calculate the area of each triangle in turn. The sum of the areas of triangles is the area of the polygon. The formula for calculating the area of the prepacking piece (polygon) is(1)SA=∑i=1nxiyixi+1yi+12,i=1,…,n,where xiandyi are the coordinates of each vertex of part A.The calculation formula for the centroid of the prepacking piece is(2)xc=∑i=1nxin,yc=∑i=1nyini=1…n,where SA is the area of part A and xcandyc are the centroid coordinates of part A.The algorithm of the packing process is as follows:Step 1: calculate the areas of all the prepacking pieces (SA), total length (LA), and centroid coordinates (xc,yc), extract feature points list (obji_plst), and save them into the data list obji_info_lstSA,LA,xc,yc,obji_plst.Step 2: sort the data listobji_info_lstSA,LA,xc,yc,obji_plst in descending order by SA.Step 3: extract the feature points of the initial layout and record asbase_open_plstplt,plb,prb. Among them, plt is the upper left corner point of the plate, plb is the lower left corner point of the plate, and prb is the lower right corner point of the plate. Set the initial closed points list as close_plst.Step 4: take out a piece from the prepacking pieces information list asobji_info_lst in order, and record it as the currently active prepacking piece as active_obji_lst. Compare the area of the closed area in the current layout with the closed points group. If it can be placed, it will be preferentially located in the closed area. If it cannot be placed, perform virtual mobile packing calculation on the current layout part, virtually move the part to the reference point position of the current packing baseline, and wait for accurate calculation by collision.Step 5: perform virtual precise collision calculation between the current layout position and the current packing baseline. By repeating the iteration of the calculation, the final layout position is determined, and the coordinates of the final layout position are computed.Step 6: move the current part from the initial position to the final layout position to complete packing the current part according to the coordinates of the final layout position in the previous step. Calculate the open points group and closed points group of the current layout, add open points group tobase_open_plst, update, merge, and save the current closed points group into close_plst.Step 7: calculate whether the current part exceeds the plate size; if not, go to Step 4 and continue packing. If it exceeds the plate size, delete the current layout part, go to step 4 to find a suitable prepacking part, until the end of traversing all parts.


#### 2.2.2. Discrete Virtual Packing Calculation

In order to save the time of the moving and contacting test, the geometric feature points of the prepacking piece are extracted as the basis for computing of the virtual packing, and the virtual movement and virtual rotation and contacting test are performed through corresponding calculations. As shown in Figure5(a), eight discrete feature points of the part are extracted as the feature information for packing. If you need to perform a moving and touching test on a prepacking piece, you only need to calculate the translation matrix of these points to get the new feature points coordinates after the piece moves. Similarly, after calculating the rotation of the centroid of Figure 5(a), the feature points of the virtual rotating arrangement can be obtained as shown in Figure 5(c). In this way, the computation of the contacting test of packing can be reduced, and the operation process of multiple physical translation can be avoided. It only needs to actually move and rotate once after getting the exact position, so this method can achieve precise packing in one step.Figure 5
Virtual translation, rotation computation of graphics. (a) Original graphic. (b) Graphic after translation. (c) Graphic after rotation.
(a)(b)(c)The virtual translation calculation formula is(3)xmym1=10tx01ty001xy1,where x,y are the original coordinates; xm,ym are the coordinates after moving; tx is the movement in x direction; and ty is the movement in y direction.The virtual rotation calculation formula is(4)xryr1=Mxy1,where x,y are the original coordinates; xr,yr are the coordinates after the centroid rotation; tx,ty are centroid coordinates of the prepacking piece; and θ is the rotation angle:(5)M=10tx01ty001∗cosθ−sinθ0sinθcosθ0001∗10−tx01−ty001=cosθ−sinθ1−cosθtx+ty∗sinθsinθcosθ1−cosθty−tx∗sinθ001.


#### 2.2.3. Bottom Left and Center of Gravity Principles and Packing Priorities

In the virtual packing calculation, the BL combined with the lowest center of gravity principle is used as the basis for determining the optimal packing. That is, in the virtual translation packing calculation, try to arrange the layout pieces to the leftmost and bottommost position of the plate, use the packing baseline as the benchmark, and try to squeeze it to the left and bottom. In the calculation of the virtual rotation packing, the rotation angle corresponding to the lowest position of the centroid is used as the angle value required for the optimal layout position.At the same time, material utilization is also an important indicator for evaluating the effect of packing. According to the principle of optimal packing for maximum plate utilization, the following layout priorities are set.(1)
The packing process is from left to right and from bottom to top. That is, when the heights of the center of gravity of the two prepacking pieces are equal, the left one takes precedence, and when the distances of the two prepacking pieces from the left boundary are equal, the lower height of the center of gravity takes precedence.(2)
The ranking of recombinant components priority over the area descending principle.(3)
The principle that the highest point is lower after the part is placed will take precedence over the principle of the lowest center of gravity.(4)
According to the area descending principle, when the current part is placed and exceeds the highest point of the current packing baseline if it meets the plate utilization condition, it is allowed to continue packing once again. If the above situation is not caused by the principle of descending area, there is no such priority.Plate utilization conditions:∑i=insi≥sover=lwidth×hover, where ∑i=insi is the sum of the areas of the remaining pieces to be arranged, sover is the overflow area caused by the current packing, lwidth is the width of the plate, and hover is the height difference between the highest point after the current packed part and the highest point of the current packing baseline.(5)
If there are only two pieces to be packed at present, the principle of the lower highest point after the piece is placed is a priority to any other principles.


### 2.3. Adaptive Precise Collision Computing

#### 2.3.1. Moving and Collision Computing

In order to achieve two-direction precise moving collision packing, a variable step size for horizontal moving layout is used, and then vertical moving and collision calculation is carried out to obtain the lowest collision position. As shown in Figure6, the leftmost point of the bounding box of piece A is used as the initial position of horizontal movement; then, take accumulative horizontal movement with appropriate steps (δ=0.5box_width), take vertical collision calculations at each moving position, and compute the horizontal position corresponding to the minimum value of the observation point Pbl of the packing piece (position A as shown in Figure 7). Use this position as the positioning reference for subsequent precise movement. Increase the width of the enclosing frame by 0.5 times to the left and right as the range of accurate horizontal movement. Shorten the step size and recalculate Pbl. This method from coarse positioning to precise subdivision collision computing greatly reduces the computation for uniformly discrete and traversal collision. Moreover, in the vertical collision calculation, the calculation of the distances between the linear discrete points is replaced by the projection calculation of several geometric feature points face to face, which greatly reduces the time of the vertical collision distance calculation. In the calculation of the vertical collision distance, a “face-to-face” collision test is carried out by using a bounding box projection of prepacking piece to intercept a part of the packing baseline to reduce the computation.Figure 6
Graphic moving collision computation.Figure 7
Graphical computing of vertical collision detection.There are two types of collision detection calculations: vertical collision detection and horizontal collision detection. The specific detection and calculation processes are as follows: as shown in Figure7, when part A to be scheduled moves to the location to be scheduled (black line frame in Figure 7), the key points (p1,p2,p3,p4) of part A are projected onto the current packing baseline (O1⟶O2⟶O3⟶…⟶O10) for the vertical collision detection; the projection points (t1,t2,o3,t3) are obtained, respectively; and the projection distances are p1t1¯,p2t2¯,p3o3¯,p4t3¯, respectively. Since the “face-to-face” collision detection is mutual, the back projection is performed in the same way, intercept the feature points (o2,o3,o4) located on the packing baseline between the key points of part A, and project these feature points onto part A. The projected points (t4,t4,t5) are obtained, respectively, and the projection distances are o2t4¯,o3t4¯,o4t5¯, respectively. Take the shortest distance of the vertical collision detection as the vertical movement amount, and record as Lv.In Figure7, Lv=minp1t1¯,p2t2¯,p3o3¯,p4t3¯,o2t4¯,o3t4¯,o4t5¯=o2t4¯, there is only one tough point for part A to be arranged, so the current layout position is not completely touched; it needs to cooperate with the horizontal collision detection for further collision computing.In the calculation of the horizontal collision detection, the process is similar to the vertical collision detection, and it also uses two-way mutual projection to compute the shortest projection distance.As shown in Figure8, the movement amount of horizontal collision is Lh=p4t6¯. Because the horizontal collision movement will cause the original vertical tough relationship to be invalidated, in order to automatically and repeatedly detect the vertical and horizontal collision and finally reach the best tough position, a suitable margin is set for the movement amount of the horizontal collision. After tests, when the actual horizontal movement amount is Lh′=0.5Lh, it is beneficial to increase the speed of collision detection. After repeating vertical and horizontal collision detection calculations, the final packing position of part A is A3, as shown in Figure 9.Figure 8
Graphical computing of horizontal collision detection.Figure 9
Graphic rotating collision computation.


#### 2.3.2. Rotating and Collision Computing

When computing the lowest layout position, the 90° rotation angle is used for the general rectangular and rectangular-like parts (sδ≥85%) to compute the collision position, and for nonrectangular parts, use any angles to rotate and contact. As shown in Figure 9, A3 is the best position for the two-direction movement after collision, but it is not the lowest position. It can rotate piece A around its centroid, then use vertical and horizontal collision detection, and find the lower position A4 as the final layout position. In order to save the time of packing, the above movements and rotations are performed in the form of virtual movement and rotation computing.


## 2.1. Graphics Preprocessing

### 2.1.1. Graphic Prenormalization

In order to simplify the packing process and reduce the time of repeated searches, before the packing, it is proposed to encode and store graphics with a unified standard to be packing. The normalization rules are to sort the geometric feature points of all the pieces by arranging clockwise and to store them with the BL (bottom left) point as the starting point, to extract the geometric feature points of the packing parts and save them as the points group table named obj(i)_plst. As shown in Figure 2, the layout part is a polygon formed by eight points connected in sequence. According to the normalization rules, the order of the eight points stored in obj(i)_plst is P8⟶P1⟶P2⟶P3⟶P4⟶P5⟶P6⟶P7. The purpose of such normalization is to facilitate the subsequent search of the reference points for packing; that is, the first point of each points’ group of the part is used as the reference point for the packing movement.Figure 2
Increase graphic feature points. (a) Graphics before midpoint adding process. (b) Graphics after midpoint adding process.
(a)(b)In order to ensure a unique correspondence in the process of matching the initial layout patterns, during the normalization process, the horizontal and vertical lines will automatically add points. As shown in Figure2(a), where the lines P1P2¯, P3P4¯, P5P6¯, and P7P8¯ are horizontal lines, and the lines P1P8¯, P2P3¯, P4P5¯, and P6P7¯ are vertical lines, adding point processing is required for them. The method of increasing the midpoints is adopted. After processing, it is shown in Figure 2(b). Its role is to increase the number of discrete points in order to minimize the loss of information caused by the reduction of the vector graph to the discrete feature points representation and ensure the effectiveness of subsequent graphic matching and collision calculation. In order to reduce the recognition of the graphic features for packing, when the layout pieces contain arc features, the arc discretization will be used to divide the arc into discrete points and connect the discrete points with polylines for approximate replacement. After the packing is finished, the arc features are restored.


### 2.1.2. Matching Stitching of Graphics

Since the two similar pieces can be reassembled into a more compact new piece, reassembling the similar pieces first and then arranging will greatly save the layout space and improve the utilization of the layout. In the packing process, in order to avoid similar parts as independent pieces to be individually packed, the graphics are matched and stitched during the preprocessing of the graphics. The principle of graphic matching is the preliminary arrangement of packing parts according to area and number of feature points; that is, two layout parts with the same area and the same number of feature points are treated as similar pieces, and the features with the highest degree of coincidence are used as matching objects. As shown in Figure3(a), the highest coincidence characteristics of the layout pieces P and T are P2P3¯ and T1T3¯, respectively. After the matching and stitching process, the layout pieces P and T are merged into a rectangular piece. The prepacking pieces in Figure 3(b) are not the same kind, but they belong to similar kinds. They need to be matched and spliced in the preprocessing stage; otherwise, it will waste the packing space in the subsequent packing. When the moving parts P and T are matched by moving and touching, the feature point P3 corresponding to the touching points are T2 and T3, and there is a nonsingle correspondence relationship. At this time, such a point is not used as the touching feature point. The same is for points P2, P4, P5, and P6. By adding points as described in Section 2.1.1, we can use the newly added midpoints P14, P15, and P16 as horizontal touchpoints for matching and stitching. In this way, we can complete the precise splicing of two layout parts and reduce unnecessary waste for the next optimization of packing.Figure 3
Graphic matching and stitching. (a) Stitching of similar pieces. (b) Stitching of heterogeneous pieces. (c) Rectangular-like piece. (d) Open point and close point.
(a)(b)(c)(d)In order to better adapt to the size of the board for packing, during the preprocessing of the graphics, the rectangular parts and rectangular-like parts are preferentially matched and stitched. As shown in Figure3(c), the packing piece A is located in the smallest rectangular enclosing frame B. We define the approximation coefficient of a rectangular-like piece as sδ=sA/sB, where sA is the area of piece A and sB is the area of piece B. The value of sδ will directly affect the packing effect. Through a large number of experiments, an appropriate value of sδ is chosen as follows: if it is satisfied sδ≥85%, then, A is called a rectangular-like piece. In the preprocessing stage, if a certain piece meets sδ≥90%, it will be matched and spliced. The maximum length of the splicing is the width of the plate. The purpose is to make the bottom layer “fully packed” as much as possible to reduce the waste of the plate.


### 2.1.3. Constructing Packing Baseline Based on Geometric Feature Points

In 2D regular parts packing, the strip model is commonly used to achieve layered packing. However, in irregular packing, it is difficult to form a clear strip model and the horizontality of the layered layout cannot be guaranteed, so this strategy is not suitable for the packing of two-dimensional irregular parts. However, the layout idea still has guiding significance. Based on this idea, the strategy of layering layout of the strip model is extended, and the idea of packing baseline based on geometric feature points is proposed. The packing baseline is not a traditional horizontal baseline, but a multipolyline and contour line updated in real time.Definition 1.
As shown in Figure3(d), we divide the area around a point into four parts: top left, top right, bottom left, and bottom right. We set this point Pi as the eye. If you cannot see that side, then this side is considered closed; if you can see it, this side is considered open, so the top right side of point Pi is close, and other sides are open. If all sides of a point (top left, bottom left, top right, and bottom right) are closed, that is, the point is surrounded by the fixed pieces, these geometric feature points are called closed points, as C1 and C2 shown in Figure 4.;Figure 4
Packing baseline with geometric feature points.Definition 2.
If at least one direction around the point (top left, bottom left, top right, and bottom right) is not closed, that is, the point is not completely surrounded by the fixed parts, these geometric feature points are called open points, asO1 and O2 shown in Figure 4.
Connecting all the current open points into a polyline in a certain order, that is, the packing baseline based on the geometric feature points, the feature points that make up the baseline are called the open points group and recorded as base_open_plst. Similarly, record all the points forming a closed-loop asclose_plst. As shown in Figure 4, O5⟶C1⟶C2⟶O5 is a closed points group, which is called the packing closed area. The packing closed areas are also the source of waste of layout materials. The smaller the packing closed area, the better the layout effect and the higher the material utilization rate.
As shown in Figure4, the current packing baseline is O1⟶O2⟶O3⟶…⟶O15, and the currently scheduled piece is A. According to the BL principle, its initial position is the position of the dashed box in Figure 4. Obviously, this position is not the optimal layout, so the position needs to be adjusted by the assistance of a further heuristic collision strategy.


## 2.1.1. Graphic Prenormalization

In order to simplify the packing process and reduce the time of repeated searches, before the packing, it is proposed to encode and store graphics with a unified standard to be packing. The normalization rules are to sort the geometric feature points of all the pieces by arranging clockwise and to store them with the BL (bottom left) point as the starting point, to extract the geometric feature points of the packing parts and save them as the points group table named obj(i)_plst. As shown in Figure 2, the layout part is a polygon formed by eight points connected in sequence. According to the normalization rules, the order of the eight points stored in obj(i)_plst is P8⟶P1⟶P2⟶P3⟶P4⟶P5⟶P6⟶P7. The purpose of such normalization is to facilitate the subsequent search of the reference points for packing; that is, the first point of each points’ group of the part is used as the reference point for the packing movement.Figure 2
Increase graphic feature points. (a) Graphics before midpoint adding process. (b) Graphics after midpoint adding process.
(a)(b)In order to ensure a unique correspondence in the process of matching the initial layout patterns, during the normalization process, the horizontal and vertical lines will automatically add points. As shown in Figure2(a), where the lines P1P2¯, P3P4¯, P5P6¯, and P7P8¯ are horizontal lines, and the lines P1P8¯, P2P3¯, P4P5¯, and P6P7¯ are vertical lines, adding point processing is required for them. The method of increasing the midpoints is adopted. After processing, it is shown in Figure 2(b). Its role is to increase the number of discrete points in order to minimize the loss of information caused by the reduction of the vector graph to the discrete feature points representation and ensure the effectiveness of subsequent graphic matching and collision calculation. In order to reduce the recognition of the graphic features for packing, when the layout pieces contain arc features, the arc discretization will be used to divide the arc into discrete points and connect the discrete points with polylines for approximate replacement. After the packing is finished, the arc features are restored.


## 2.1.2. Matching Stitching of Graphics

Since the two similar pieces can be reassembled into a more compact new piece, reassembling the similar pieces first and then arranging will greatly save the layout space and improve the utilization of the layout. In the packing process, in order to avoid similar parts as independent pieces to be individually packed, the graphics are matched and stitched during the preprocessing of the graphics. The principle of graphic matching is the preliminary arrangement of packing parts according to area and number of feature points; that is, two layout parts with the same area and the same number of feature points are treated as similar pieces, and the features with the highest degree of coincidence are used as matching objects. As shown in Figure3(a), the highest coincidence characteristics of the layout pieces P and T are P2P3¯ and T1T3¯, respectively. After the matching and stitching process, the layout pieces P and T are merged into a rectangular piece. The prepacking pieces in Figure 3(b) are not the same kind, but they belong to similar kinds. They need to be matched and spliced in the preprocessing stage; otherwise, it will waste the packing space in the subsequent packing. When the moving parts P and T are matched by moving and touching, the feature point P3 corresponding to the touching points are T2 and T3, and there is a nonsingle correspondence relationship. At this time, such a point is not used as the touching feature point. The same is for points P2, P4, P5, and P6. By adding points as described in Section 2.1.1, we can use the newly added midpoints P14, P15, and P16 as horizontal touchpoints for matching and stitching. In this way, we can complete the precise splicing of two layout parts and reduce unnecessary waste for the next optimization of packing.Figure 3
Graphic matching and stitching. (a) Stitching of similar pieces. (b) Stitching of heterogeneous pieces. (c) Rectangular-like piece. (d) Open point and close point.
(a)(b)(c)(d)In order to better adapt to the size of the board for packing, during the preprocessing of the graphics, the rectangular parts and rectangular-like parts are preferentially matched and stitched. As shown in Figure3(c), the packing piece A is located in the smallest rectangular enclosing frame B. We define the approximation coefficient of a rectangular-like piece as sδ=sA/sB, where sA is the area of piece A and sB is the area of piece B. The value of sδ will directly affect the packing effect. Through a large number of experiments, an appropriate value of sδ is chosen as follows: if it is satisfied sδ≥85%, then, A is called a rectangular-like piece. In the preprocessing stage, if a certain piece meets sδ≥90%, it will be matched and spliced. The maximum length of the splicing is the width of the plate. The purpose is to make the bottom layer “fully packed” as much as possible to reduce the waste of the plate.


## 2.1.3. Constructing Packing Baseline Based on Geometric Feature Points

In 2D regular parts packing, the strip model is commonly used to achieve layered packing. However, in irregular packing, it is difficult to form a clear strip model and the horizontality of the layered layout cannot be guaranteed, so this strategy is not suitable for the packing of two-dimensional irregular parts. However, the layout idea still has guiding significance. Based on this idea, the strategy of layering layout of the strip model is extended, and the idea of packing baseline based on geometric feature points is proposed. The packing baseline is not a traditional horizontal baseline, but a multipolyline and contour line updated in real time.Definition 1.
As shown in Figure3(d), we divide the area around a point into four parts: top left, top right, bottom left, and bottom right. We set this point Pi as the eye. If you cannot see that side, then this side is considered closed; if you can see it, this side is considered open, so the top right side of point Pi is close, and other sides are open. If all sides of a point (top left, bottom left, top right, and bottom right) are closed, that is, the point is surrounded by the fixed pieces, these geometric feature points are called closed points, as C1 and C2 shown in Figure 4.;Figure 4
Packing baseline with geometric feature points.Definition 2.
If at least one direction around the point (top left, bottom left, top right, and bottom right) is not closed, that is, the point is not completely surrounded by the fixed parts, these geometric feature points are called open points, asO1 and O2 shown in Figure 4.
Connecting all the current open points into a polyline in a certain order, that is, the packing baseline based on the geometric feature points, the feature points that make up the baseline are called the open points group and recorded as base_open_plst. Similarly, record all the points forming a closed-loop asclose_plst. As shown in Figure 4, O5⟶C1⟶C2⟶O5 is a closed points group, which is called the packing closed area. The packing closed areas are also the source of waste of layout materials. The smaller the packing closed area, the better the layout effect and the higher the material utilization rate.
As shown in Figure4, the current packing baseline is O1⟶O2⟶O3⟶…⟶O15, and the currently scheduled piece is A. According to the BL principle, its initial position is the position of the dashed box in Figure 4. Obviously, this position is not the optimal layout, so the position needs to be adjusted by the assistance of a further heuristic collision strategy.


## 2.2. Packing Rules

### 2.2.1. Sorting Descending Order

In the graphic preprocessing, all parts have been normalized and matched and stitched, but the matching and stitching process will reorganize some of the layouts (shown in Figure3), so we need to do a stitching process for the recombinant pieces before packing. The processed parts are used as the initial input graphics. The area of each recombinant part is calculated and packed in descending order according to their area.According to Pick’s theorem, we can transformn polygons into n-2 triangles and use the cross multiplication to calculate the area of each triangle in turn. The sum of the areas of triangles is the area of the polygon. The formula for calculating the area of the prepacking piece (polygon) is(1)SA=∑i=1nxiyixi+1yi+12,i=1,…,n,where xiandyi are the coordinates of each vertex of part A.The calculation formula for the centroid of the prepacking piece is(2)xc=∑i=1nxin,yc=∑i=1nyini=1…n,where SA is the area of part A and xcandyc are the centroid coordinates of part A.The algorithm of the packing process is as follows:Step 1: calculate the areas of all the prepacking pieces (SA), total length (LA), and centroid coordinates (xc,yc), extract feature points list (obji_plst), and save them into the data list obji_info_lstSA,LA,xc,yc,obji_plst.Step 2: sort the data listobji_info_lstSA,LA,xc,yc,obji_plst in descending order by SA.Step 3: extract the feature points of the initial layout and record asbase_open_plstplt,plb,prb. Among them, plt is the upper left corner point of the plate, plb is the lower left corner point of the plate, and prb is the lower right corner point of the plate. Set the initial closed points list as close_plst.Step 4: take out a piece from the prepacking pieces information list asobji_info_lst in order, and record it as the currently active prepacking piece as active_obji_lst. Compare the area of the closed area in the current layout with the closed points group. If it can be placed, it will be preferentially located in the closed area. If it cannot be placed, perform virtual mobile packing calculation on the current layout part, virtually move the part to the reference point position of the current packing baseline, and wait for accurate calculation by collision.Step 5: perform virtual precise collision calculation between the current layout position and the current packing baseline. By repeating the iteration of the calculation, the final layout position is determined, and the coordinates of the final layout position are computed.Step 6: move the current part from the initial position to the final layout position to complete packing the current part according to the coordinates of the final layout position in the previous step. Calculate the open points group and closed points group of the current layout, add open points group tobase_open_plst, update, merge, and save the current closed points group into close_plst.Step 7: calculate whether the current part exceeds the plate size; if not, go to Step 4 and continue packing. If it exceeds the plate size, delete the current layout part, go to step 4 to find a suitable prepacking part, until the end of traversing all parts.


### 2.2.2. Discrete Virtual Packing Calculation

In order to save the time of the moving and contacting test, the geometric feature points of the prepacking piece are extracted as the basis for computing of the virtual packing, and the virtual movement and virtual rotation and contacting test are performed through corresponding calculations. As shown in Figure5(a), eight discrete feature points of the part are extracted as the feature information for packing. If you need to perform a moving and touching test on a prepacking piece, you only need to calculate the translation matrix of these points to get the new feature points coordinates after the piece moves. Similarly, after calculating the rotation of the centroid of Figure 5(a), the feature points of the virtual rotating arrangement can be obtained as shown in Figure 5(c). In this way, the computation of the contacting test of packing can be reduced, and the operation process of multiple physical translation can be avoided. It only needs to actually move and rotate once after getting the exact position, so this method can achieve precise packing in one step.Figure 5
Virtual translation, rotation computation of graphics. (a) Original graphic. (b) Graphic after translation. (c) Graphic after rotation.
(a)(b)(c)The virtual translation calculation formula is(3)xmym1=10tx01ty001xy1,where x,y are the original coordinates; xm,ym are the coordinates after moving; tx is the movement in x direction; and ty is the movement in y direction.The virtual rotation calculation formula is(4)xryr1=Mxy1,where x,y are the original coordinates; xr,yr are the coordinates after the centroid rotation; tx,ty are centroid coordinates of the prepacking piece; and θ is the rotation angle:(5)M=10tx01ty001∗cosθ−sinθ0sinθcosθ0001∗10−tx01−ty001=cosθ−sinθ1−cosθtx+ty∗sinθsinθcosθ1−cosθty−tx∗sinθ001.


### 2.2.3. Bottom Left and Center of Gravity Principles and Packing Priorities

In the virtual packing calculation, the BL combined with the lowest center of gravity principle is used as the basis for determining the optimal packing. That is, in the virtual translation packing calculation, try to arrange the layout pieces to the leftmost and bottommost position of the plate, use the packing baseline as the benchmark, and try to squeeze it to the left and bottom. In the calculation of the virtual rotation packing, the rotation angle corresponding to the lowest position of the centroid is used as the angle value required for the optimal layout position.At the same time, material utilization is also an important indicator for evaluating the effect of packing. According to the principle of optimal packing for maximum plate utilization, the following layout priorities are set.(1)
The packing process is from left to right and from bottom to top. That is, when the heights of the center of gravity of the two prepacking pieces are equal, the left one takes precedence, and when the distances of the two prepacking pieces from the left boundary are equal, the lower height of the center of gravity takes precedence.(2)
The ranking of recombinant components priority over the area descending principle.(3)
The principle that the highest point is lower after the part is placed will take precedence over the principle of the lowest center of gravity.(4)
According to the area descending principle, when the current part is placed and exceeds the highest point of the current packing baseline if it meets the plate utilization condition, it is allowed to continue packing once again. If the above situation is not caused by the principle of descending area, there is no such priority.Plate utilization conditions:∑i=insi≥sover=lwidth×hover, where ∑i=insi is the sum of the areas of the remaining pieces to be arranged, sover is the overflow area caused by the current packing, lwidth is the width of the plate, and hover is the height difference between the highest point after the current packed part and the highest point of the current packing baseline.(5)
If there are only two pieces to be packed at present, the principle of the lower highest point after the piece is placed is a priority to any other principles.


## 2.2.1. Sorting Descending Order

In the graphic preprocessing, all parts have been normalized and matched and stitched, but the matching and stitching process will reorganize some of the layouts (shown in Figure3), so we need to do a stitching process for the recombinant pieces before packing. The processed parts are used as the initial input graphics. The area of each recombinant part is calculated and packed in descending order according to their area.According to Pick’s theorem, we can transformn polygons into n-2 triangles and use the cross multiplication to calculate the area of each triangle in turn. The sum of the areas of triangles is the area of the polygon. The formula for calculating the area of the prepacking piece (polygon) is(1)SA=∑i=1nxiyixi+1yi+12,i=1,…,n,where xiandyi are the coordinates of each vertex of part A.The calculation formula for the centroid of the prepacking piece is(2)xc=∑i=1nxin,yc=∑i=1nyini=1…n,where SA is the area of part A and xcandyc are the centroid coordinates of part A.The algorithm of the packing process is as follows:Step 1: calculate the areas of all the prepacking pieces (SA), total length (LA), and centroid coordinates (xc,yc), extract feature points list (obji_plst), and save them into the data list obji_info_lstSA,LA,xc,yc,obji_plst.Step 2: sort the data listobji_info_lstSA,LA,xc,yc,obji_plst in descending order by SA.Step 3: extract the feature points of the initial layout and record asbase_open_plstplt,plb,prb. Among them, plt is the upper left corner point of the plate, plb is the lower left corner point of the plate, and prb is the lower right corner point of the plate. Set the initial closed points list as close_plst.Step 4: take out a piece from the prepacking pieces information list asobji_info_lst in order, and record it as the currently active prepacking piece as active_obji_lst. Compare the area of the closed area in the current layout with the closed points group. If it can be placed, it will be preferentially located in the closed area. If it cannot be placed, perform virtual mobile packing calculation on the current layout part, virtually move the part to the reference point position of the current packing baseline, and wait for accurate calculation by collision.Step 5: perform virtual precise collision calculation between the current layout position and the current packing baseline. By repeating the iteration of the calculation, the final layout position is determined, and the coordinates of the final layout position are computed.Step 6: move the current part from the initial position to the final layout position to complete packing the current part according to the coordinates of the final layout position in the previous step. Calculate the open points group and closed points group of the current layout, add open points group tobase_open_plst, update, merge, and save the current closed points group into close_plst.Step 7: calculate whether the current part exceeds the plate size; if not, go to Step 4 and continue packing. If it exceeds the plate size, delete the current layout part, go to step 4 to find a suitable prepacking part, until the end of traversing all parts.


## 2.2.2. Discrete Virtual Packing Calculation

In order to save the time of the moving and contacting test, the geometric feature points of the prepacking piece are extracted as the basis for computing of the virtual packing, and the virtual movement and virtual rotation and contacting test are performed through corresponding calculations. As shown in Figure5(a), eight discrete feature points of the part are extracted as the feature information for packing. If you need to perform a moving and touching test on a prepacking piece, you only need to calculate the translation matrix of these points to get the new feature points coordinates after the piece moves. Similarly, after calculating the rotation of the centroid of Figure 5(a), the feature points of the virtual rotating arrangement can be obtained as shown in Figure 5(c). In this way, the computation of the contacting test of packing can be reduced, and the operation process of multiple physical translation can be avoided. It only needs to actually move and rotate once after getting the exact position, so this method can achieve precise packing in one step.Figure 5
Virtual translation, rotation computation of graphics. (a) Original graphic. (b) Graphic after translation. (c) Graphic after rotation.
(a)(b)(c)The virtual translation calculation formula is(3)xmym1=10tx01ty001xy1,where x,y are the original coordinates; xm,ym are the coordinates after moving; tx is the movement in x direction; and ty is the movement in y direction.The virtual rotation calculation formula is(4)xryr1=Mxy1,where x,y are the original coordinates; xr,yr are the coordinates after the centroid rotation; tx,ty are centroid coordinates of the prepacking piece; and θ is the rotation angle:(5)M=10tx01ty001∗cosθ−sinθ0sinθcosθ0001∗10−tx01−ty001=cosθ−sinθ1−cosθtx+ty∗sinθsinθcosθ1−cosθty−tx∗sinθ001.


## 2.2.3. Bottom Left and Center of Gravity Principles and Packing Priorities

In the virtual packing calculation, the BL combined with the lowest center of gravity principle is used as the basis for determining the optimal packing. That is, in the virtual translation packing calculation, try to arrange the layout pieces to the leftmost and bottommost position of the plate, use the packing baseline as the benchmark, and try to squeeze it to the left and bottom. In the calculation of the virtual rotation packing, the rotation angle corresponding to the lowest position of the centroid is used as the angle value required for the optimal layout position.At the same time, material utilization is also an important indicator for evaluating the effect of packing. According to the principle of optimal packing for maximum plate utilization, the following layout priorities are set.(1)
The packing process is from left to right and from bottom to top. That is, when the heights of the center of gravity of the two prepacking pieces are equal, the left one takes precedence, and when the distances of the two prepacking pieces from the left boundary are equal, the lower height of the center of gravity takes precedence.(2)
The ranking of recombinant components priority over the area descending principle.(3)
The principle that the highest point is lower after the part is placed will take precedence over the principle of the lowest center of gravity.(4)
According to the area descending principle, when the current part is placed and exceeds the highest point of the current packing baseline if it meets the plate utilization condition, it is allowed to continue packing once again. If the above situation is not caused by the principle of descending area, there is no such priority.Plate utilization conditions:∑i=insi≥sover=lwidth×hover, where ∑i=insi is the sum of the areas of the remaining pieces to be arranged, sover is the overflow area caused by the current packing, lwidth is the width of the plate, and hover is the height difference between the highest point after the current packed part and the highest point of the current packing baseline.(5)
If there are only two pieces to be packed at present, the principle of the lower highest point after the piece is placed is a priority to any other principles.


## 2.3. Adaptive Precise Collision Computing

### 2.3.1. Moving and Collision Computing

In order to achieve two-direction precise moving collision packing, a variable step size for horizontal moving layout is used, and then vertical moving and collision calculation is carried out to obtain the lowest collision position. As shown in Figure6, the leftmost point of the bounding box of piece A is used as the initial position of horizontal movement; then, take accumulative horizontal movement with appropriate steps (δ=0.5box_width), take vertical collision calculations at each moving position, and compute the horizontal position corresponding to the minimum value of the observation point Pbl of the packing piece (position A as shown in Figure 7). Use this position as the positioning reference for subsequent precise movement. Increase the width of the enclosing frame by 0.5 times to the left and right as the range of accurate horizontal movement. Shorten the step size and recalculate Pbl. This method from coarse positioning to precise subdivision collision computing greatly reduces the computation for uniformly discrete and traversal collision. Moreover, in the vertical collision calculation, the calculation of the distances between the linear discrete points is replaced by the projection calculation of several geometric feature points face to face, which greatly reduces the time of the vertical collision distance calculation. In the calculation of the vertical collision distance, a “face-to-face” collision test is carried out by using a bounding box projection of prepacking piece to intercept a part of the packing baseline to reduce the computation.Figure 6
Graphic moving collision computation.Figure 7
Graphical computing of vertical collision detection.There are two types of collision detection calculations: vertical collision detection and horizontal collision detection. The specific detection and calculation processes are as follows: as shown in Figure7, when part A to be scheduled moves to the location to be scheduled (black line frame in Figure 7), the key points (p1,p2,p3,p4) of part A are projected onto the current packing baseline (O1⟶O2⟶O3⟶…⟶O10) for the vertical collision detection; the projection points (t1,t2,o3,t3) are obtained, respectively; and the projection distances are p1t1¯,p2t2¯,p3o3¯,p4t3¯, respectively. Since the “face-to-face” collision detection is mutual, the back projection is performed in the same way, intercept the feature points (o2,o3,o4) located on the packing baseline between the key points of part A, and project these feature points onto part A. The projected points (t4,t4,t5) are obtained, respectively, and the projection distances are o2t4¯,o3t4¯,o4t5¯, respectively. Take the shortest distance of the vertical collision detection as the vertical movement amount, and record as Lv.In Figure7, Lv=minp1t1¯,p2t2¯,p3o3¯,p4t3¯,o2t4¯,o3t4¯,o4t5¯=o2t4¯, there is only one tough point for part A to be arranged, so the current layout position is not completely touched; it needs to cooperate with the horizontal collision detection for further collision computing.In the calculation of the horizontal collision detection, the process is similar to the vertical collision detection, and it also uses two-way mutual projection to compute the shortest projection distance.As shown in Figure8, the movement amount of horizontal collision is Lh=p4t6¯. Because the horizontal collision movement will cause the original vertical tough relationship to be invalidated, in order to automatically and repeatedly detect the vertical and horizontal collision and finally reach the best tough position, a suitable margin is set for the movement amount of the horizontal collision. After tests, when the actual horizontal movement amount is Lh′=0.5Lh, it is beneficial to increase the speed of collision detection. After repeating vertical and horizontal collision detection calculations, the final packing position of part A is A3, as shown in Figure 9.Figure 8
Graphical computing of horizontal collision detection.Figure 9
Graphic rotating collision computation.


### 2.3.2. Rotating and Collision Computing

When computing the lowest layout position, the 90° rotation angle is used for the general rectangular and rectangular-like parts (sδ≥85%) to compute the collision position, and for nonrectangular parts, use any angles to rotate and contact. As shown in Figure 9, A3 is the best position for the two-direction movement after collision, but it is not the lowest position. It can rotate piece A around its centroid, then use vertical and horizontal collision detection, and find the lower position A4 as the final layout position. In order to save the time of packing, the above movements and rotations are performed in the form of virtual movement and rotation computing.


## 2.3.1. Moving and Collision Computing

In order to achieve two-direction precise moving collision packing, a variable step size for horizontal moving layout is used, and then vertical moving and collision calculation is carried out to obtain the lowest collision position. As shown in Figure6, the leftmost point of the bounding box of piece A is used as the initial position of horizontal movement; then, take accumulative horizontal movement with appropriate steps (δ=0.5box_width), take vertical collision calculations at each moving position, and compute the horizontal position corresponding to the minimum value of the observation point Pbl of the packing piece (position A as shown in Figure 7). Use this position as the positioning reference for subsequent precise movement. Increase the width of the enclosing frame by 0.5 times to the left and right as the range of accurate horizontal movement. Shorten the step size and recalculate Pbl. This method from coarse positioning to precise subdivision collision computing greatly reduces the computation for uniformly discrete and traversal collision. Moreover, in the vertical collision calculation, the calculation of the distances between the linear discrete points is replaced by the projection calculation of several geometric feature points face to face, which greatly reduces the time of the vertical collision distance calculation. In the calculation of the vertical collision distance, a “face-to-face” collision test is carried out by using a bounding box projection of prepacking piece to intercept a part of the packing baseline to reduce the computation.Figure 6
Graphic moving collision computation.Figure 7
Graphical computing of vertical collision detection.There are two types of collision detection calculations: vertical collision detection and horizontal collision detection. The specific detection and calculation processes are as follows: as shown in Figure7, when part A to be scheduled moves to the location to be scheduled (black line frame in Figure 7), the key points (p1,p2,p3,p4) of part A are projected onto the current packing baseline (O1⟶O2⟶O3⟶…⟶O10) for the vertical collision detection; the projection points (t1,t2,o3,t3) are obtained, respectively; and the projection distances are p1t1¯,p2t2¯,p3o3¯,p4t3¯, respectively. Since the “face-to-face” collision detection is mutual, the back projection is performed in the same way, intercept the feature points (o2,o3,o4) located on the packing baseline between the key points of part A, and project these feature points onto part A. The projected points (t4,t4,t5) are obtained, respectively, and the projection distances are o2t4¯,o3t4¯,o4t5¯, respectively. Take the shortest distance of the vertical collision detection as the vertical movement amount, and record as Lv.In Figure7, Lv=minp1t1¯,p2t2¯,p3o3¯,p4t3¯,o2t4¯,o3t4¯,o4t5¯=o2t4¯, there is only one tough point for part A to be arranged, so the current layout position is not completely touched; it needs to cooperate with the horizontal collision detection for further collision computing.In the calculation of the horizontal collision detection, the process is similar to the vertical collision detection, and it also uses two-way mutual projection to compute the shortest projection distance.As shown in Figure8, the movement amount of horizontal collision is Lh=p4t6¯. Because the horizontal collision movement will cause the original vertical tough relationship to be invalidated, in order to automatically and repeatedly detect the vertical and horizontal collision and finally reach the best tough position, a suitable margin is set for the movement amount of the horizontal collision. After tests, when the actual horizontal movement amount is Lh′=0.5Lh, it is beneficial to increase the speed of collision detection. After repeating vertical and horizontal collision detection calculations, the final packing position of part A is A3, as shown in Figure 9.Figure 8
Graphical computing of horizontal collision detection.Figure 9
Graphic rotating collision computation.


## 2.3.2. Rotating and Collision Computing

When computing the lowest layout position, the 90° rotation angle is used for the general rectangular and rectangular-like parts (sδ≥85%) to compute the collision position, and for nonrectangular parts, use any angles to rotate and contact. As shown in Figure 9, A3 is the best position for the two-direction movement after collision, but it is not the lowest position. It can rotate piece A around its centroid, then use vertical and horizontal collision detection, and find the lower position A4 as the final layout position. In order to save the time of packing, the above movements and rotations are performed in the form of virtual movement and rotation computing.


## 3. Results

In order to further verify the effectiveness of this proposed algorithm, the algorithm is tested on a general auxiliary design platform AutoCAD. The benchmark problems provided by the ESICUP (EUROSlCUP) are used as test cases. Some commonly used benchmark examples, blaz, marques, shirts, trousers, and so forth, are chosen for the packing test. The packing results are shown in Figures10–13.Figure 10
The packing result of our algorithm (blaz).Figure 11
The packing result of our algorithm (marques).Figure 12
The packing result of our algorithm (shirts).Figure 13
The packing result of our algorithm (trousers).


## 4. Discussion

In order to facilitate comparison, the analysis results of this method, the literature [30, 31], and commercial packing software of SigmaNest and NestLib are shown in Table 1 (packing density is the ratio of the sum of the area of the parts to the area of the plate).Table 1
Computing results of examples (packing density).
CaseSigmaNest (%)NestLib (%)Reference [30] (%)Reference [31] (%)Ours (%)Blaz67.8469.6874.06—75.79Marques75.0383.1577.7280.4385.85Dagli77.9776.8479.41—79.41Fu77.8573.0878.71—79.17Jakobs167.9675.3875.38—75.38Jakobs259.9264.3368.93—68.93Shapes054.2557.8357.83—57.83Shapes154.1761.3859.11—59.18Shirts77.3777.1479.1368.9280.10Trousers82.7382.5080.7884.8583.53It can be seen from Table1 that the descending order packing algorithm is reliable. After comparison with SigmaNest, NestLib, GEFHNA, HAPG_HRG, and other methods, the conclusion is drawn: irregular graphics descending packing algorithm based on geometric feature points is suitable for the problem of two-dimensional irregular graphics packing. The packing density is high, and it has obvious advantages in dealing with the problem of mixed layout of regular and irregular pieces. The algorithm is general, simple to operate, and has good application economics.


## 5. Conclusions

A general geometric packing algorithm suitable for two-dimensional irregular graphics is proposed in this paper. The packing order is guided by the descending order of the area of parts. Through the graphic preprocessing, rectangular pieces and rectangular-like pieces are automatically matched and spliced according to their sizes, which eliminate the waste of space caused by the single packing of pieces and improves the sheet utilization. The packing baseline is constructed by the geometric feature points of the layout parts, prepacking parts are moved according to the BL principle, and the geometric feature points of the part and the packing baseline are used as the key point for bidirectional collision computing. The portion of feature points of the packing baseline are intercepted for face-to-face calculation by way of the bounding box of the layout piece, which greatly reduce the traversal computation cost of the method of converting vector graphics to discrete points. The computing of the lowest packing position of parts is realized by using large-step positioning and small-step accurate collision computation, which avoids the traversal computing of NFP method.This paper has made some contributions in the following aspects:(1)
This algorithm classifies graphics according to their geometric characteristics and performs graphic classification and recombination preprocessing before packing, which solves the problems caused by single packing of previous algorithms.(2)
The adaptive vertical collision detection and horizontal collision detection methods can find more accurate and compact layout positions, which is an innovation of this paper.(3)
The strip layout algorithm is extended, the layered packing strategy is extended, and the strategy of variable packing baseline is used to improve the compactness of the layout.Future research will be carried out in the following aspects: optimize the algorithm for computing the packing baseline and rotation collision to further improve the screening efficiency of the initial packing of the layout pieces; design the adaptive adjustment method of the rotation angle of the graphics, and use the closed free spaces for packing. A better mechanism for rational selection of the layout order based on the principle of highest plate utilization will be studied. The idea of using low-dimensional computing of discrete points of geometrical graphic items to solve complex problems of measurement and positioning between geometric graphics will be applied to more engineering fields, and the approaching of geometrical computing better for solving geometry problems will continue to be promoted.



---

*Source: 8854838-2020-11-03.xml*