# Heuristic Approach for Packing Identical Rectangular Tiles in an Irregular Marble Slab

Authors: Zhe Yuan; Xiaocun Song; Dong An
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

Packing identical rectangular tiles in a large marble slab is a necessary task. However, when the region of the marble slab is a concave set, the characteristics of the concave set make it difficult to determine whether the rectangular tiles are in the region. For this purpose, this article proposes a heuristic approach to the problem of packing identical rectangular items with orthogonal constraints in a concave irregular region. The heuristic approach uses a tree-search structure, and the final layout is built by inserting a new item in an irregular polygon. The newly inserted item must satisfy the containment and the nonoverlapping constraints associated with the irregular polygon. Regarding the containment constraint, we propose an improved slope algorithm to obtain the inner-fit polygon (IFP) of irregular polygons and rectangular items and apply IFP to determine the relative position of a rectangular item and an irregular polygon to guarantee containment constraint. Compared with existing methods, this approach can not only be used in convex regions but also in concave regions. Numerical experiments and application examples illustrate the effectiveness of the approach.


---

## Body

## 1. Introduction

As a fundamental mathematical problem, the rectangular packing problem [1] has many application backgrounds in scientific research, engineering practice, and even daily life. For example, the rectangular packing problem is applied in several commercial and industrial contexts, like stone manufacturing, shoe manufacturing, and furniture making. In the stone industry, slates cut from natural rocks often have irregular contours, which pose challenges for stone processing. At present, the natural stone processing schemes adopt the traditional manual arrangement, which takes a long time and has a low use rate. Therefore, the intelligent packing of irregular natural stone has become an urgent requirement of the stone industry.The solution to the rectangle packing problem is to use an optimization approach to find a favorable or workable solution in a reasonable amount of time. The goal of packing rectangle items in a container is to find the greatest density of a set of small rectangles arranged in a container. The maximum density depends on the algorithm and is related to the size of the rectangles. For example, if the size of the rectangles becomes smaller, the density will increase. Sometimes, the container’s shape is also a big problem, because when the container has an irregular shape, it is difficult to judge whether the rectangles are in the region.Cutting rectangular tiles from natural marble plates is a common factory operation. When the shape of a marble slab is rectangular, it is the most common two-dimensional rectangular layout problem, which is packing as many rectangular items as possible into a large fixed rectangle without any two items overlapping. The so-called bottom-left (BL) heuristic [2], which involves placing a rectangle at its lowest possible place and left-justifying. Some algorithms improve the BL algorithm, such as the bottom-left fill (BLF) heuristic [3], deepest bottom-left-fill (DBLF) [4], improved bottom-left (IBL) [5], and bottom-left decreasing (BLD) [6]. However, because of the lack of an iterative optimization process, the heuristic method makes it difficult to get the optimal solution. Some scholars use a combination of meta-heuristic algorithms and layout representation to optimize the layout order. Genetic algorithm [7], simulated annealing [8], tabu search [9], crow search algorithm [10], and other meta-heuristics are often used for packing problems. For example, Fırat and Alpaslan [11] uses the bottom-left filling and no-fit polygon heuristic and the simulated annealing meta-heuristic to solve the two-dimensional packing problem of rectangular shapes. For some exact algorithm, Ahn et al. [12] proposed an improved best-first branch-and-bound algorithm. To improve the algorithm’s performance, they introduced efficient ways of removing dominated and duplicated patterns in the staircase structure. Chen et al. [13] provided a deterministic heuristic approach for maximizing the filling rate of a rectangular. The key component of the proposed algorithm is a best-fit constructive procedure, according to which each rectangle is packed into the sheet at an angle-occupying placement with a maximum fit degree. Based on the tree search algorithm proposed by Fanslau and Bortfeldt [14] for container loading problems, Bortfeldt and Jungmann [15] proposed a tree search algorithm for rectangular layout problems with guillotine cutting constraints. Libralesso and Fontan [16] presented a new anytime tree search algorithm called IMBA Liu et al. [17] proposed a binary tree search algorithm for the problem of how to load a subset of a given rectangular box into a rectangular container to maximize the packaging volume.However, marble slabs are cut from mountains, so their shapes are often irregular. In contrast to regular containers, packing rectangular items in irregular containers is more difficult. To solve the problem of packing rectangular items in an arbitrary convex region, starting with that of Feng et al. [18], the authors solved the problem using graph theory, group theory and global optimization. Sun and Teng [19] proposed a two-phase heuristic based on nonlinear programming. Xu et al. [20] designed a constructive heuristic algorithm and embedded it into a genetic algorithm to solve the rectangular layout problem. Wang et al. [21] proposed a genetic algorithm (GA)-based method to solve this 2D BPP with rectangular and circular regions. Bouzid and Salhi [22] present a novel constructive heuristic that builds a feasible packing starting from an ordered list of rectangles. Chen et al. [23] proposed a packing algorithm based on the HL heuristic and genetics to solve this problem. Cassioli and Locatelli [24] formulated the orthogonal packing of equal rectangles within a convex region as an unconstrained mixed-integer global optimization problem and solved it using an iterated local search combined with the L-BFGS algorithm of Liu and Nocedal [25]. Lopez et al. [26] based on the mixed integer nonlinear programming model, a formula space search heuristic algorithm is proposed to solve the problem of packing unequal rectangles or squares. Birgin and Lobato [27] provided a solution based on a combination of branch-and-bound and active-set strategies for bound-constrained minimization of smooth functions for the problem of orthogonallypacking identical rectangles within an arbitrary convex region.As described in the literature review, packing rectangular items in a regular container is much more common than in irregular containers. Moreover, studies on irregular containers only focus on convex containers. There are a few articles tackling the problem of packing identical rectangular items in concave irregular regions.In this paper, a heuristic approach is proposed to the problem of packing identical rectangular items with orthogonal constraints into a concave irregular marble slab. Different from regular-container packing, packing items into irregular shapes is more difficult because of the complex boundary contours and the corresponding geometric calculations. In recent years, the most widely methods for dealing with irregular shapes have been no-fit polygons (NFPs) and inner-fit polygons (IFPs). In the new approach, the final layout is built by adding a new item to the container with the constraint that the new item must be completely inside the container and not overlap with items already packed in the container. The IFP method is applied to solve the concave containment constraint, and the NFP method is applied to decide the position of the newly inserted item.


## 2. Supporting Concepts

The concepts of NFPs and the analogous IFPs [28] will need to be introduced. The NFP method is applied to find the best position of the newly inserted item, and the IFP method is applied to determine the relative position of rectangular items and the container. When applying NFPs and IFPs to packing problems, a key step is to determine the relative position between the reference point and the polygon.


### 2.1. The No-Fit Polygon

For the two-dimensional packing and cutting problem involving irregular shapes in which no items overlap or protrude from the container is a difficult task for which an essential element is required in any solution approach. An efficient geometric tool to determine the relative position of a pair of pieces, touching, separating, or colliding, must be considered. The no-fit polygon (NFP) method can be applied to packaging problems involving regular or irregular shapes. The NFP and methodologies for implementing this notion in cutting and packing were discussed by Bennell et al. [29].For a pair of irregular shapes, for example, two polygons A and B, NFPAB is a polygon derived from the polygons A and B. As seen in Figure 1(a), A is a stationary polygon, while B is a tracing polygon that glides around A without rotating. In Figure 1(a), given a reference point on B, when the bottom-left corner of B is selected as the reference point, the locus of the reference point of B forms an NFPAB.Figure 1
The form of a no-fit polygon: (a) NFPAB formed by the locus of reference points of B; (b) relative positions of B and A, represented by B1, B2, and B3.
(a)(b)For each pair of pieces, A and B, the properties of NFPAB are subject to the interaction between A and B, summarized as follows: A and B will overlap if the reference point of B is put inside NFPAB; if the reference point of B is placed on the boundary of NFPAB, A and B will touch but not overlap; and if the reference point of B is placed outside NFPAB, A and B will not touch or overlap. Figure 1(b) shows a simple case: B1 has its reference point-inside NFPAB; B2 has its reference point touching NFPAB; and B3 has its reference point outside NFPAB. Hence, the boundary and interior of NFPAB represent all possible touching positions between A and B.


### 2.2. Inner-Fit Polygon

IFPAB is a concept related to NFPAB for a pair of polygons A and B. It is generated in a similar way to NFPAB, that is, the locus of the reference point on B that slides along the internal contour of A without overlapping. An example can be seen in Figure 2(a). As with NFPAB, the properties of IFPAB illustrate the feasible placement position of B placed inside A. Assuming that the reference point of polygon B is within or on the side of IFPAB, B will always be inside polygon A. Otherwise, B will interact with A or lie outside of A, as shown in Figure 2(b).Figure 2
The form of an IFP: (a) IFP formed by A and B; (b) relative positions of B and A represented by B1, B2, and B3.
(a)(b)


## 2.1. The No-Fit Polygon

For the two-dimensional packing and cutting problem involving irregular shapes in which no items overlap or protrude from the container is a difficult task for which an essential element is required in any solution approach. An efficient geometric tool to determine the relative position of a pair of pieces, touching, separating, or colliding, must be considered. The no-fit polygon (NFP) method can be applied to packaging problems involving regular or irregular shapes. The NFP and methodologies for implementing this notion in cutting and packing were discussed by Bennell et al. [29].For a pair of irregular shapes, for example, two polygons A and B, NFPAB is a polygon derived from the polygons A and B. As seen in Figure 1(a), A is a stationary polygon, while B is a tracing polygon that glides around A without rotating. In Figure 1(a), given a reference point on B, when the bottom-left corner of B is selected as the reference point, the locus of the reference point of B forms an NFPAB.Figure 1
The form of a no-fit polygon: (a) NFPAB formed by the locus of reference points of B; (b) relative positions of B and A, represented by B1, B2, and B3.
(a)(b)For each pair of pieces, A and B, the properties of NFPAB are subject to the interaction between A and B, summarized as follows: A and B will overlap if the reference point of B is put inside NFPAB; if the reference point of B is placed on the boundary of NFPAB, A and B will touch but not overlap; and if the reference point of B is placed outside NFPAB, A and B will not touch or overlap. Figure 1(b) shows a simple case: B1 has its reference point-inside NFPAB; B2 has its reference point touching NFPAB; and B3 has its reference point outside NFPAB. Hence, the boundary and interior of NFPAB represent all possible touching positions between A and B.


## 2.2. Inner-Fit Polygon

IFPAB is a concept related to NFPAB for a pair of polygons A and B. It is generated in a similar way to NFPAB, that is, the locus of the reference point on B that slides along the internal contour of A without overlapping. An example can be seen in Figure 2(a). As with NFPAB, the properties of IFPAB illustrate the feasible placement position of B placed inside A. Assuming that the reference point of polygon B is within or on the side of IFPAB, B will always be inside polygon A. Otherwise, B will interact with A or lie outside of A, as shown in Figure 2(b).Figure 2
The form of an IFP: (a) IFP formed by A and B; (b) relative positions of B and A represented by B1, B2, and B3.
(a)(b)


## 3. Mathematical Model

This article packs as many identical rectangular items as possible into an irregular region. The rectangular items must be parallel to each other in the cutting process without rotation. Without loss of generality, each rectangle will be parallel to the naturalx and y axes of the Cartesian coordinate system. Considering that all formulations of the packing problem consist of two types of constraints: those preventing the collection of items from exceeding the dimensions of the container and those forbidding the items from overlapping with each other.


### 3.1. Point Inclusion

When using NFP or IFP with a heuristic method, the challenge of determining the relative position of two polygons is translated into a point-inside test, as mentioned above. As a result, a mathematical algorithm for the point-inside test is required.If the detecting point isP (x, y) and the polygon has M sides, then the M vertices are represented by P1,…, PM, whose coordinates are (xi, yi), and PM+1 = P1. When joining the vertex Pi and the judged point P, if side PiP moves to side PPi+1 in a clockwise orientation then ∠PiPPi+1 is positive, otherwise, it is negative for all i = 1,…, M. The absolute value of each angle is less than π. It can be defined as:(1)fx,y=∑i=1M−1∠PiPPi+1+∠PMPP1.The relative position of a pointP and a polygon with M vertices can be obtained using the value of f (x, y) from (1). If f (x, y) = 2π, then P is inside the polygon, see Figure 3(a). If f (x, y) = π, then P is on the side of the polygon, see Figure 3(b). If f (x, y) = 0, then P is outside the polygon, as shown in Figure 3(c).Figure 3
The locus of the point P (a) point P inside a polygon with five sides; (b) point P on the side of a polygon with five sides; and (c) point P outside a polygon with five sides.
(a)(b)(c)To calculate (1), the points P (x, y) and Pi (xi, yi) form the vector vi⟶, then vi⟶=Pi⟶−P⟶. The dot product formula is as follows:(2)vi⟶⋅vi+1⟶=|vi⟶|−|vi+1⟶|cosθ.From (2), the value of θ can be calculated as:(3)θ=arccosxi−x×xi+1−x+yi−y×yi+1−yxi−x2+yi−y2×xi+1−x2+yi+1−y2.Because when thePiP moves to PPi+1 in a clockwise orientation then ∠PiPPi+1 is positive, otherwise, it is negative for all i = 1,…, M. Therefore, the formula for ∠PiPPi+1 is as follows:(4)∠PiPPi+1=arccosxi−x×xi+1−x+yi−y×yi+1−yxi−x2+yi−y2×xi+1−x2+yi+1−y2×sgnxi−x×yi+1−y−xi+1−x×yi−y.Therefore, based on Equation (4), Equation (1) can be reformulated as follows:(5)fx,y=∑i=1Marccosxi−x×xi+1−x+yi−y×yi+1−yxi−x2+yi−y2×xi+1−x2+yi+1−y2×sgnxi−x×yi+1−y−xi+1−x×yi−y.From (5), the value of f (x, y) can be calculated. Then, the relative position of a point and a polygon can be detected. Additionally, if the detection point is on the vertex of the polygon, (5) cannot generate a value since the denominator is zero.


### 3.2. Containment Constraint

In contrast to convex regions, for concave regions, determining that all vertices of a rectangular item are in an irregular region is not enough to guarantee that the item is in the region, when the region is a concave region, the IFP is used. As described in Section2.2, the containment constraint is reduced to a point-inclusion test to determine whether the reference point of the item is inside the IFP formed by the rectangular item and the container.In this paper, an IFP is applied to determine the relative position of a rectangular item and an irregular polygon; an algorithm for calculating the IFP of a convex polygon and a concave polygon is proposed. An improved slope algorithm is proposed to obtain the IFP of an irregular polygon and a rectangular item. The biggest difference between the improved IFP algorithm and Ghosh’s slope algorithm [30] is the orders of edge vectors and their orientations. In the improved algorithm, the container is a fixed polygon, the item is a tracing polygon, and both of them are oriented counter-clockwise.To illustrate the improved algorithm in detail, an example is given in Figure4. Figure 4(a) shows a container Ω, a polygon with five sides, and its slope diagram. Figure 4(b) shows a rectangular item and its slope diagram. To visit the edge vectors in the correct order, a merged diagram is obtained on the basis of the diagrams of the component polygons, see Figure 4(c). The visiting order of all vectors is e⟶1,r⇀1,e⟶2,r⇀2,r⇀3,e⟶3,−r⇀3,e⟶4,r⇀3,r⇀4,e⟶5,−r⇀4. Different from Ghosh’s slope algorithm, the directions of all vectors of rectangular items are changed to the opposite without changing the order of the vectors. Therefore, the final order of the edge vectors is e⟶1,−r⇀1,e⟶2,−r⇀2,−r⇀3,e⟶3,r⇀3,e⟶4,−r⇀3,−r⇀4,e⟶5,r⇀4. Figure 4(d) shows a polygon formed by the edge vectors in the correct order.Figure 4
An example of the slope algorithm: (a) a container with five edges and its slope diagram; (b) a rectangular item and its slope diagram; (c) the merged slope diagram; and (d) polygon formed by the edge vectors in the visiting order.
(a)(b)(c)(d)To obtain the IFP, the external loops of the polygon should be removed as shown in Figure4(d), and the boundary of the IFP can be obtained as shown in Figure 5(a). Let the center point of the item be the reference point, and move the boundary of the IFP to get the final IFP; see Figure 5(b).Figure 5
The boundary of the IFP is obtained by the slope algorithm: (a) boundary of the IFP; (b) the final IFP formed by the container and the item.
(a)(b)


### 3.3. Nonoverlapping Constraint

Based on the heuristic approach, the newly inserted rectangular item does not overlap with already packed items. Supposem items have been packed in the container, and the newly inserted item is item m + 1. For a pair of rectangular items i and j whose center coordinates are Ci=Cxi,Cyi and Cj=Cxj,Cyj, respectively, the nonoverlapping constraint can be modeled as follows: Figure 6 illustrates overlapping constraints diagrammatically.(6)Cxi−Cxj≥a,(7)Cyi−Cyj≥b.Figure 6
Cases of the nonoverlapping constraint: (a) item (i) and item (j) satisfying Equation (6); (b) item (i) and item (j) satisfying Equation (7).
(a)(b)To simplify the constraint to prevent overlap, (6) and (7) are changed to one side, as follows:(8)a2−Cxi−Cxj2≤0,b2−Cyi−Cyj2≤0.Then,t ≤ 0 is substituted with max{0, t}2 = 0 and the two equalities are combined by multiplication. Thus, the nonoverlapping constraint for item i and j can be defined as follows:(9)max0,a2−Cxi−Cxj22×max0,b2−Cyi−Cyj22=0.It is obvious that if the center points of any pair of rectangular items satisfy Eq. (10), they will not overlap with each other. The formulation that item m + 1 does not overlap with the m item already packed in the container on the basis of Equation (10) is given as follows:(10)∑i=1mmax0,a2−Cxi−Cxm+122×max0,b2−Cyi−Cym+122=0.


## 3.1. Point Inclusion

When using NFP or IFP with a heuristic method, the challenge of determining the relative position of two polygons is translated into a point-inside test, as mentioned above. As a result, a mathematical algorithm for the point-inside test is required.If the detecting point isP (x, y) and the polygon has M sides, then the M vertices are represented by P1,…, PM, whose coordinates are (xi, yi), and PM+1 = P1. When joining the vertex Pi and the judged point P, if side PiP moves to side PPi+1 in a clockwise orientation then ∠PiPPi+1 is positive, otherwise, it is negative for all i = 1,…, M. The absolute value of each angle is less than π. It can be defined as:(1)fx,y=∑i=1M−1∠PiPPi+1+∠PMPP1.The relative position of a pointP and a polygon with M vertices can be obtained using the value of f (x, y) from (1). If f (x, y) = 2π, then P is inside the polygon, see Figure 3(a). If f (x, y) = π, then P is on the side of the polygon, see Figure 3(b). If f (x, y) = 0, then P is outside the polygon, as shown in Figure 3(c).Figure 3
The locus of the point P (a) point P inside a polygon with five sides; (b) point P on the side of a polygon with five sides; and (c) point P outside a polygon with five sides.
(a)(b)(c)To calculate (1), the points P (x, y) and Pi (xi, yi) form the vector vi⟶, then vi⟶=Pi⟶−P⟶. The dot product formula is as follows:(2)vi⟶⋅vi+1⟶=|vi⟶|−|vi+1⟶|cosθ.From (2), the value of θ can be calculated as:(3)θ=arccosxi−x×xi+1−x+yi−y×yi+1−yxi−x2+yi−y2×xi+1−x2+yi+1−y2.Because when thePiP moves to PPi+1 in a clockwise orientation then ∠PiPPi+1 is positive, otherwise, it is negative for all i = 1,…, M. Therefore, the formula for ∠PiPPi+1 is as follows:(4)∠PiPPi+1=arccosxi−x×xi+1−x+yi−y×yi+1−yxi−x2+yi−y2×xi+1−x2+yi+1−y2×sgnxi−x×yi+1−y−xi+1−x×yi−y.Therefore, based on Equation (4), Equation (1) can be reformulated as follows:(5)fx,y=∑i=1Marccosxi−x×xi+1−x+yi−y×yi+1−yxi−x2+yi−y2×xi+1−x2+yi+1−y2×sgnxi−x×yi+1−y−xi+1−x×yi−y.From (5), the value of f (x, y) can be calculated. Then, the relative position of a point and a polygon can be detected. Additionally, if the detection point is on the vertex of the polygon, (5) cannot generate a value since the denominator is zero.


## 3.2. Containment Constraint

In contrast to convex regions, for concave regions, determining that all vertices of a rectangular item are in an irregular region is not enough to guarantee that the item is in the region, when the region is a concave region, the IFP is used. As described in Section2.2, the containment constraint is reduced to a point-inclusion test to determine whether the reference point of the item is inside the IFP formed by the rectangular item and the container.In this paper, an IFP is applied to determine the relative position of a rectangular item and an irregular polygon; an algorithm for calculating the IFP of a convex polygon and a concave polygon is proposed. An improved slope algorithm is proposed to obtain the IFP of an irregular polygon and a rectangular item. The biggest difference between the improved IFP algorithm and Ghosh’s slope algorithm [30] is the orders of edge vectors and their orientations. In the improved algorithm, the container is a fixed polygon, the item is a tracing polygon, and both of them are oriented counter-clockwise.To illustrate the improved algorithm in detail, an example is given in Figure4. Figure 4(a) shows a container Ω, a polygon with five sides, and its slope diagram. Figure 4(b) shows a rectangular item and its slope diagram. To visit the edge vectors in the correct order, a merged diagram is obtained on the basis of the diagrams of the component polygons, see Figure 4(c). The visiting order of all vectors is e⟶1,r⇀1,e⟶2,r⇀2,r⇀3,e⟶3,−r⇀3,e⟶4,r⇀3,r⇀4,e⟶5,−r⇀4. Different from Ghosh’s slope algorithm, the directions of all vectors of rectangular items are changed to the opposite without changing the order of the vectors. Therefore, the final order of the edge vectors is e⟶1,−r⇀1,e⟶2,−r⇀2,−r⇀3,e⟶3,r⇀3,e⟶4,−r⇀3,−r⇀4,e⟶5,r⇀4. Figure 4(d) shows a polygon formed by the edge vectors in the correct order.Figure 4
An example of the slope algorithm: (a) a container with five edges and its slope diagram; (b) a rectangular item and its slope diagram; (c) the merged slope diagram; and (d) polygon formed by the edge vectors in the visiting order.
(a)(b)(c)(d)To obtain the IFP, the external loops of the polygon should be removed as shown in Figure4(d), and the boundary of the IFP can be obtained as shown in Figure 5(a). Let the center point of the item be the reference point, and move the boundary of the IFP to get the final IFP; see Figure 5(b).Figure 5
The boundary of the IFP is obtained by the slope algorithm: (a) boundary of the IFP; (b) the final IFP formed by the container and the item.
(a)(b)


## 3.3. Nonoverlapping Constraint

Based on the heuristic approach, the newly inserted rectangular item does not overlap with already packed items. Supposem items have been packed in the container, and the newly inserted item is item m + 1. For a pair of rectangular items i and j whose center coordinates are Ci=Cxi,Cyi and Cj=Cxj,Cyj, respectively, the nonoverlapping constraint can be modeled as follows: Figure 6 illustrates overlapping constraints diagrammatically.(6)Cxi−Cxj≥a,(7)Cyi−Cyj≥b.Figure 6
Cases of the nonoverlapping constraint: (a) item (i) and item (j) satisfying Equation (6); (b) item (i) and item (j) satisfying Equation (7).
(a)(b)To simplify the constraint to prevent overlap, (6) and (7) are changed to one side, as follows:(8)a2−Cxi−Cxj2≤0,b2−Cyi−Cyj2≤0.Then,t ≤ 0 is substituted with max{0, t}2 = 0 and the two equalities are combined by multiplication. Thus, the nonoverlapping constraint for item i and j can be defined as follows:(9)max0,a2−Cxi−Cxj22×max0,b2−Cyi−Cyj22=0.It is obvious that if the center points of any pair of rectangular items satisfy Eq. (10), they will not overlap with each other. The formulation that item m + 1 does not overlap with the m item already packed in the container on the basis of Equation (10) is given as follows:(10)∑i=1mmax0,a2−Cxi−Cxm+122×max0,b2−Cyi−Cym+122=0.


## 4. Solution Method

In this section, a heuristic algorithm is proposed to solve the problem of packing as many identical rectangles as possible without rotation in an irregular region. The heuristic algorithm has two issues to consider. One is to decide the position of the newly inserted item, and the other is to decide the position of the previously packed item. In general, the final layout is obtained by adding a new item to a partial solution of already placed items until no item can be inserted into the container. When the position of the first packed item is decided, the final layout can be decided as well. Therefore, different positions of the first packed item will produce different packing layouts.


### 4.1. Gridding of NFP and IFP

In the packing problem, the position in the coordinate system of the corresponding item is determined by the center point C of the rectangular item. The values for the horizontal and vertical directions of the rectangular item are a and b, respectively. Itemi is the ith packed item in the container, whose center point is Cxi,Cyi, as shown in Figure 7(a). NFP (i) is defined as the NFP of item i, whose reference point is the center point of item i. Obviously, NFP (i) is a rectangle whose dimensions are 2 × a and 2 × b with the same center point as item i (Figure 7(b)). Due to all items being identical rectangles, the corresponding NFPs are identical in dimension with different center positions. NFP (i) provides all possible touching positions of each item touching item i. On this basis, all possible positions of the next packed item, item i + 1, can be decided.Figure 7
The center point of item i and its NFP rectangle: (a) description of item (i); (b) the corresponding NFP (i) of item i.
(a)(b)A grid is constructed on NFP (i). The grid has appropriate resolutions Δx in the x dimension and Δy in the y dimension. It is assumed that Δx divides a and Δy divides b, that is, a = k1 Δx and b = k2 Δy, where k1 and k2 are both positive integers; see Figure 8(a). All nodes of the grid form a set T1. Nodes on the edge of NFP (i) represent all admitted positions where each item touches item i. These nodes can be defined as NFP_1(i) (see Figure 8(b)).Figure 8
The nodes on the edge of NFP (i) obtained by gridding: (a) gridding of NFP (i); (b) set of nodes on the edge of NFP (i).
(a)(b)A grid is constructed on IFP, formed by a rectangular item and the container. The grid has the same resolutions as a grid over NFP; the bottom-left node of the grid and the bottom-left point of the minimum enclosed rectangle of IFP coincide with each other (Figure9(a)). Using Eq. (5), some dots of the grid that lie outside the IFP are deleted; the remaining dots form a set T2, where the reference point of the rectangular item can be positioned such that, the item is totally in the container (Figure 9(b)).Figure 9
The nodes inside the IFP rectangle obtained by gridding: (a) gridding of IFP; (b) set of nodes inside IFP.
(a)(b)


### 4.2. Position of Next Packed Item

Assuming a partial solution withm already packed rectangular items in the container, there may be many positions for the next item inside the container not overlapping with the previously packed items. The reference point of item m + 1 must belong to T2 and the coordinates of the center points must satisfy (8). On this basis, the positions where item m + 1 touches item m are selected to decrease computational time and obtain better partial solutions. As described in section 4.1, grids on NFPs and IFPs have the same resolution, so if the reference point of an item is on the node T2, the contour of the corresponding NFP has 4(k1 + k2) nodes belonging to T2. Therefore, positions where item m + 1 touch item m are those nodes belonging to NFP (i). Afterward, one of the nodes for the position of item m + 1 is selected on the basis of the bottom-left approach.Provided that two items (item 1 and item 2) have been packed in the container, the position of item 3 needs to be decided; see Figure10. The nodes marked with the symbol × represent those satisfying the containment constraint, nonoverlapping constraint, and touching item 2. The next step is to select a node from these that satisfies the bottom-left approach as the position of item 3. The bottom-left approach is to select a node whose x coordinate is the minimum. If more than one node can be selected, the one whose y coordinate is the minimum is the best choice.Figure 10
Process of selecting the position of item 3.


### 4.3. Positions of the First Packed Item

As described above, different positions of the first packed item represent different layouts. To find the best layout, all positions where the first packed item could be packed need to be searched. Based on the IFP gridding, nodes inside the IFP represent all possible positions. The nodes marked with the symbol × may represent all possible positions of the first packed item in Figure11. These nodes belong to T2. The rectangle has dimensions 2a × 2b, and the center point is the bottom-left node of the grid over the IFP.Figure 11
Nodes representing all possible positions of the first packed item.


### 4.4. The Heuristic Approach

The heuristic approach uses a tree-search structure. In the search tree, nodes represent the positions of rectangle items. Different nodes on the same level correspond to different possible positions of the same rectangular item, and the level of the search tree represents the number of rectangles packed in the container. Thus, the depth of the tree is the maximum number of rectangles the container can contain. Child nodes represent the positions of the next packed item compared with its parent nodes. Each parent node generates 4 (k1 + k2) child nodes, representing positions where the item represented by the child nodes touches the item represented by the parent node, as described in Section 4.2.The process of building the search tree is as follows; see Figure12. Generating the root node by selecting the bottom-left node of the IFP grid, as described in Section 4.1, is the first step of constructing the search tree. Figure 13.Figure 12
Illustration of the heuristic.Figure 13
Flow diagram of the algorithm.Nodes on level 1, the child nodes of the root node, are those points marked with an × as described in Section4.3. The number of nodes on level 1 is set to N1. Suppose k = 4(k1 + k2), then each node on level 1 generates k child nodes. Only one child node that belongs to T1 and T2 satisfies the bottom-left approach, as described in Section 4.2. Nodes on the subsequent levels are generated in the same fashion. Nodes of different branches represent different layouts of packing identical rectangular items, and the branch whose depth is the largest will be the final layout.There may be some nodes in the IFP that have not been searched. In order to solve the drawbacks, the process of building the search tree will be looped. The layout of the first search is saved as a partial solution. The remaining nodes represent positions, where the newly inserted item will not overlap with items already packed in the container. The branching tree is re-established for the unselected nodes until the set of remaining nodes in the IFP is empty. All partial solutions form the final layout. Figure13 gives a graphical representation of the approach.


## 4.1. Gridding of NFP and IFP

In the packing problem, the position in the coordinate system of the corresponding item is determined by the center point C of the rectangular item. The values for the horizontal and vertical directions of the rectangular item are a and b, respectively. Itemi is the ith packed item in the container, whose center point is Cxi,Cyi, as shown in Figure 7(a). NFP (i) is defined as the NFP of item i, whose reference point is the center point of item i. Obviously, NFP (i) is a rectangle whose dimensions are 2 × a and 2 × b with the same center point as item i (Figure 7(b)). Due to all items being identical rectangles, the corresponding NFPs are identical in dimension with different center positions. NFP (i) provides all possible touching positions of each item touching item i. On this basis, all possible positions of the next packed item, item i + 1, can be decided.Figure 7
The center point of item i and its NFP rectangle: (a) description of item (i); (b) the corresponding NFP (i) of item i.
(a)(b)A grid is constructed on NFP (i). The grid has appropriate resolutions Δx in the x dimension and Δy in the y dimension. It is assumed that Δx divides a and Δy divides b, that is, a = k1 Δx and b = k2 Δy, where k1 and k2 are both positive integers; see Figure 8(a). All nodes of the grid form a set T1. Nodes on the edge of NFP (i) represent all admitted positions where each item touches item i. These nodes can be defined as NFP_1(i) (see Figure 8(b)).Figure 8
The nodes on the edge of NFP (i) obtained by gridding: (a) gridding of NFP (i); (b) set of nodes on the edge of NFP (i).
(a)(b)A grid is constructed on IFP, formed by a rectangular item and the container. The grid has the same resolutions as a grid over NFP; the bottom-left node of the grid and the bottom-left point of the minimum enclosed rectangle of IFP coincide with each other (Figure9(a)). Using Eq. (5), some dots of the grid that lie outside the IFP are deleted; the remaining dots form a set T2, where the reference point of the rectangular item can be positioned such that, the item is totally in the container (Figure 9(b)).Figure 9
The nodes inside the IFP rectangle obtained by gridding: (a) gridding of IFP; (b) set of nodes inside IFP.
(a)(b)


## 4.2. Position of Next Packed Item

Assuming a partial solution withm already packed rectangular items in the container, there may be many positions for the next item inside the container not overlapping with the previously packed items. The reference point of item m + 1 must belong to T2 and the coordinates of the center points must satisfy (8). On this basis, the positions where item m + 1 touches item m are selected to decrease computational time and obtain better partial solutions. As described in section 4.1, grids on NFPs and IFPs have the same resolution, so if the reference point of an item is on the node T2, the contour of the corresponding NFP has 4(k1 + k2) nodes belonging to T2. Therefore, positions where item m + 1 touch item m are those nodes belonging to NFP (i). Afterward, one of the nodes for the position of item m + 1 is selected on the basis of the bottom-left approach.Provided that two items (item 1 and item 2) have been packed in the container, the position of item 3 needs to be decided; see Figure10. The nodes marked with the symbol × represent those satisfying the containment constraint, nonoverlapping constraint, and touching item 2. The next step is to select a node from these that satisfies the bottom-left approach as the position of item 3. The bottom-left approach is to select a node whose x coordinate is the minimum. If more than one node can be selected, the one whose y coordinate is the minimum is the best choice.Figure 10
Process of selecting the position of item 3.


## 4.3. Positions of the First Packed Item

As described above, different positions of the first packed item represent different layouts. To find the best layout, all positions where the first packed item could be packed need to be searched. Based on the IFP gridding, nodes inside the IFP represent all possible positions. The nodes marked with the symbol × may represent all possible positions of the first packed item in Figure11. These nodes belong to T2. The rectangle has dimensions 2a × 2b, and the center point is the bottom-left node of the grid over the IFP.Figure 11
Nodes representing all possible positions of the first packed item.


## 4.4. The Heuristic Approach

The heuristic approach uses a tree-search structure. In the search tree, nodes represent the positions of rectangle items. Different nodes on the same level correspond to different possible positions of the same rectangular item, and the level of the search tree represents the number of rectangles packed in the container. Thus, the depth of the tree is the maximum number of rectangles the container can contain. Child nodes represent the positions of the next packed item compared with its parent nodes. Each parent node generates 4 (k1 + k2) child nodes, representing positions where the item represented by the child nodes touches the item represented by the parent node, as described in Section 4.2.The process of building the search tree is as follows; see Figure12. Generating the root node by selecting the bottom-left node of the IFP grid, as described in Section 4.1, is the first step of constructing the search tree. Figure 13.Figure 12
Illustration of the heuristic.Figure 13
Flow diagram of the algorithm.Nodes on level 1, the child nodes of the root node, are those points marked with an × as described in Section4.3. The number of nodes on level 1 is set to N1. Suppose k = 4(k1 + k2), then each node on level 1 generates k child nodes. Only one child node that belongs to T1 and T2 satisfies the bottom-left approach, as described in Section 4.2. Nodes on the subsequent levels are generated in the same fashion. Nodes of different branches represent different layouts of packing identical rectangular items, and the branch whose depth is the largest will be the final layout.There may be some nodes in the IFP that have not been searched. In order to solve the drawbacks, the process of building the search tree will be looped. The layout of the first search is saved as a partial solution. The remaining nodes represent positions, where the newly inserted item will not overlap with items already packed in the container. The branching tree is re-established for the unselected nodes until the set of remaining nodes in the IFP is empty. All partial solutions form the final layout. Figure13 gives a graphical representation of the approach.


## 5. Numerical Experiments and Application

In this section, the algorithm is applied to a computational simulation and stone-plate packing experiment.


### 5.1. Packing Rectangles in Polygons

The algorithm involved in the experiment was simulated by MatlabR2018b and calculated on an Intel Corei7 CPU with 16 GB memory and 2.6 GHz. To prove the effectiveness of the heuristic algorithm, 12 instances with different polygons were considered, including convex polygons and concave polygons. Table1 shows the description of each problem, including vertices and areas of Ω, dimensions, and area of the rectangles to be packed, the number of packed items, and the operation time. All problems are randomly generated. Figure 14 shows the solutions.Table 1
Computational results.
No.Irregular regionRectangle itemNumber of itemsCPU time in secondsDescriptionAreaDimensionsArea1{(0,0), (40,0), (20,20)}4003 × 265610.2112{(0,0), (20,0), (18,20),(2,20)}3604 × 416202.0223{(0,0), (15,0), (18,12), (3,12)}1802 × 36283.4114{(0,0), (30,0), (15,15), (15,30)}337.53 × 39291.2525{(0,0), (20,0), (24,24), (10,16), (0,22)}4224 × 312294.4296{(0,0), (14,0), (30,−10), (26,20), (6,16)}5083 × 39429.7747{(0,0), (21,0), (30,20), (6,30), (−4,20)}7204 × 3125017.7198{(0,0), (10,0), (15,12), (10,24), (0,24), (−5,12)}3603 × 39327.8419{(0,0), (15,0), (7.5,18), (15,36), (0,36), (−7.5,18)}5404 × 3123611.01210{(0,0), (24,0), (21.6,12), (24,24), (0,24), (4.8,12)}489.64 × 285413.03311{(0,0), (10,0), (15,−6), (22,10), (14,24), (0,24), (−5,12)}5263 × 394623.23412{(0,0), (6,−6), (4,−20), (20,−12), (36,−20), (30,−6), (40,0), (24,0), (20,16), (10,0)}5682 × 2410544.236Figure 14
Graphical representation of the solutions.


### 5.2. Packing Rectangles in a Stone Plate

After the numerical simulation, the heuristic algorithm is applied to packing rectangles in a stone plate. The image of the stone plate, shown in Figure15, was captured with a CCD camera. The boundary of the stone plate is an irregular curve, and it can be fitted onto a polygon. The polygon is shown in Figure 16.Figure 15
The image of the stone plate.Figure 16
Using a polygon to fit the stone boundary.The size of the small stone piece is 25 mm × 30 mm. The layout result is shown in Figure17:Figure 17
The result of packing in the stone plate.


## 5.1. Packing Rectangles in Polygons

The algorithm involved in the experiment was simulated by MatlabR2018b and calculated on an Intel Corei7 CPU with 16 GB memory and 2.6 GHz. To prove the effectiveness of the heuristic algorithm, 12 instances with different polygons were considered, including convex polygons and concave polygons. Table1 shows the description of each problem, including vertices and areas of Ω, dimensions, and area of the rectangles to be packed, the number of packed items, and the operation time. All problems are randomly generated. Figure 14 shows the solutions.Table 1
Computational results.
No.Irregular regionRectangle itemNumber of itemsCPU time in secondsDescriptionAreaDimensionsArea1{(0,0), (40,0), (20,20)}4003 × 265610.2112{(0,0), (20,0), (18,20),(2,20)}3604 × 416202.0223{(0,0), (15,0), (18,12), (3,12)}1802 × 36283.4114{(0,0), (30,0), (15,15), (15,30)}337.53 × 39291.2525{(0,0), (20,0), (24,24), (10,16), (0,22)}4224 × 312294.4296{(0,0), (14,0), (30,−10), (26,20), (6,16)}5083 × 39429.7747{(0,0), (21,0), (30,20), (6,30), (−4,20)}7204 × 3125017.7198{(0,0), (10,0), (15,12), (10,24), (0,24), (−5,12)}3603 × 39327.8419{(0,0), (15,0), (7.5,18), (15,36), (0,36), (−7.5,18)}5404 × 3123611.01210{(0,0), (24,0), (21.6,12), (24,24), (0,24), (4.8,12)}489.64 × 285413.03311{(0,0), (10,0), (15,−6), (22,10), (14,24), (0,24), (−5,12)}5263 × 394623.23412{(0,0), (6,−6), (4,−20), (20,−12), (36,−20), (30,−6), (40,0), (24,0), (20,16), (10,0)}5682 × 2410544.236Figure 14
Graphical representation of the solutions.


## 5.2. Packing Rectangles in a Stone Plate

After the numerical simulation, the heuristic algorithm is applied to packing rectangles in a stone plate. The image of the stone plate, shown in Figure15, was captured with a CCD camera. The boundary of the stone plate is an irregular curve, and it can be fitted onto a polygon. The polygon is shown in Figure 16.Figure 15
The image of the stone plate.Figure 16
Using a polygon to fit the stone boundary.The size of the small stone piece is 25 mm × 30 mm. The layout result is shown in Figure17:Figure 17
The result of packing in the stone plate.


## 6. Conclusion

In this article, we presented a heuristic approach using tree search structures for packing identical rectangles in irregular regions. The final layout is built by inserting a new item into an irregular polygon. In the search tree, nodes represent the positions of rectangle items. Different nodes on the same level correspond to different possible positions of the same rectangular item, and the level of the search tree represents the number of rectangles packed in the container. The model considers containment and nonoverlapping constraints. An IFP is used to overcome the containment constraint. Compared to the existing packing algorithms, the most obvious advantage is packing rectangles in an irregular shape, including convex and concave shapes. In contrast, most algorithms work only with restricted shapes such as rectangles and circles. Numerical simulations and practical experiments proved that the approach can effectively pack identical rectangular tiles into an irregular marble slab.



---

*Source: 9038402-2022-09-02.xml*