## 3 Two-Dimensional Cutting Stock Problem (2 DCSP) Algorithm
### No-Fit Polygon  
The basic idea behind the no-fit polygon (NFP) was originally proposed by [PERSON] [32]. The NFP is a tool that can be used for identifying the position in which two can be close with no overlaps. This method has been acknowledged for its efficiency and has been used to solve problems, such as identifying motions of robots. The NFP is generated by two polygons in which the first polygon is fixed, while the second polygon is orbiting. The direction of this movement is called an NFP. If the reference point of the second polygon is in the NFP, an overlay has occurred. If the reference point is outside the NFP, the polygons are not touching. And if the reference point is on the NFP, this shows that both polygons are attached perfectly. Figure 7 illustrates that polygon A is fixed and B is moving. The dot lined shape represents the NFP and its position. Polygon B is in a position of close arrangement with polygon A.  
A polygon can be categorized into 2 types, convex and non-convex. For a convex polygon, the edges are arranged by the angle consecutively in a clockwise direction, as shown in Figure 8a. A non-convex polygon is more complicated as its edges are not arranged in sequence. An example of a convex and non-convex polygon is shown in Figure 8. As seen in Figure 8b, the 4 th and 5 th edges have a narrower angle than the 3 rd edge, and this represents a non-convex polygon.  
Figure 6: The multi-phases arrangement strategies [31] are MinCenterDistance (**a**) and MinLength (**b**).  
The no-fit polygon convex type can be calculated by [PERSON]'s Different [33; 34], which states that an NFP is equal to the difference of both polygons.  
\[NFP_{AB}=\mathbf{A}\oplus-\mathbf{B}, \tag{1}\]  
which  
\[\mathbf{A}\oplus\mathbf{B} =\{a+b|a\in\mathbf{A},b\in\mathbf{B}\}\] \[-\mathbf{A} =\{-a|a\in\mathbf{A}\} \tag{2}\]  
\(\mathbf{A}\) and \(\mathbf{B}\) represent sets of edges in polygon A and B, respectively. \(a\) and \(b\) are the edge inside \(\mathbf{A}\) and \(\mathbf{B}\), respectively.  
The NFP convex type is formed by merging of the edges of two polygons. The first polygon has a counterclockwise direction, while the second polygon has a clockwise direction which is arranged by its angle from 0 to 180 degrees, respectively, as shown in Figure 9.  
Polygon A and B move in a counterclockwise direction. The NFP calculation is used to find the combined edges between \(\mathbf{A}\) and \(-\mathbf{B}\), in which \(-\mathbf{B}\) contains the same edges as \(\mathbf{B}\) but moves in a clockwise direction. The NFP of polygon A and B is retrieved when the edges of both polygons are arranged and connected at each angle. For the non-convex type  
Figure 8: Convex polygon (**a**) and non-convex polygon (**b**) [31].  
Figure 7: An example of the no-fit polygon (NFP) (thick border) of polygon B in relation to polygon A. The reference point of B is not allowed inside the NFP if overlap is to be avoided.  
polygon, the calculation requires various methods that have been presented by numerous researchers. The calculation example is shown in [PERSON] et al. [35] and [PERSON] [36].