In this paper problems of cutting and packing objects of complex geometric shapes are considered. To solve these NP-hard problems, it is proposed to use an approach based on geometric transformation of polygonal objects to composite objects (orthogonal polyhedrons) made up of rectangles or parallelepipeds of a given dimension. To describe the free space inside a voxelized container, a model of potential containers is used as the basic model that provides the ability of packing orthogonal polyhedrons. A number of specialized algorithms are developed to work with orthogonal polyhedrons including: algorithms for placing and removing composite objects, an algorithm for forming a packing with a given distance between objects to be placed. Two algorithms for the placement of orthogonal polyhedrons are developed and their efficiency is investigated. An algorithm for obtaining a container of complex shape presented as an orthogonal polyhedron based on a polygonal model is given. The article contains examples of placement schemes obtained by the developed algorithms for solving problems of packing two-dimensional and three-dimensional non-rectangular composite objects. Orthogonal polyhedron, voxelization, packing problem, irregular cutting
applications are [1–7]:
The problem of finding the best way to place objects of complex geometric shapes is characterized by a wide range of its practical applications. Among the most common areas of such practical cutting industrial materials (metal sheets, cardboard, plywood and etc.); rational usage of free spaces (for example, spaces of aircraft, tankers, spaceships and etc.); geometric surface coverage with specified shapes; modeling the microstructure of composite materials; generation of active electronically scanned arrays.
All packing problems are NP-hard optimization problems for which there are no algorithms of polynomial complexity to solve them [1, 8], which makes it urgent to develop algorithms that provide suboptimal solutions in an acceptable time. Modern methods for solving problems of packing objects of complex geometric shape require usage of the hodograph vector function of dense placement, which requires the subsequent application of nonlinear programming methods characterized by high computational complexity [9–15]. The paper proposes an approach that allows you to reduce the complexity of the problem. It consists in voxelization of objects to be packed [16–18], subsequent transforming the obtained voxelized objects to orthogonal polyhedrons after their decomposition [19] and finally application of algorithms especially developed for placement of orthogonal polyhedrons.
2021 Copyright for this paper by its authors.
We will consider the problem of placement orthogonal polyhedrons in the general D -dimensional (the superscript in formulas means the number of the coordinate axis). Objects to be packed are specified by a set of n compound objects Oi as orthogonal polyhedrons ( i 1; n). Every compound object consists from a set of mi simple objects (rectangles or parallelepipeds) at the same time, each simple object oik , k 1; mi has the overall dimensions w1ik ; wi2k ;; wiDk as well is located at point 1 zik ; zi2k ;; ziDk of the considered orthogonal polyhedron. When all compound objects consist of only one simple object, then the problem is reduced to the classical problem of orthogonal packing or rectangular cutting [2, 20].
To describe a packing entire is used the developed model of potential containers [20, 21]. A potential container is an imaginary orthogonal region ( D -dimensional parallelepiped) for which there is free space inside a packing. The model of potential containers used forms the set of all possible potential containers of minimum capacity. The designation p1h ; ph2 ;; phD is used to indicate the overall dimensions of a potential container Ph and its position inside the considered packing is determinate by a set of values x1h ; xh2 ;; xhD . When a new orthogonal object has to be put into a container it is necessary to check the condition that it does not intersect with objects already placed in the placement scheme. When using the model of potential containers, it is possible to guarantee the correctness of the resulting packing if each placed object can be completely placed inside at least one potential container. Obviously, this check is performed quickly, and the speed of orthogonal packing formation is high.
To update a set of potential containers after placing an orthogonal polyhedron Oi at the point X i1, X i2 ,, X iD of a D -dimensional container, the entire of which is fully described by a set of potential containers 0 , the following algorithm is performed.
Step 1. Create a set 0 0
of potential containers h : d 1,, D: xhd X id Sid , where Si1, Si2 ,, SiD denotes the overall dimensions of a D -dimensional parallelepiped bounding the orthogonal polyhedron O : Sid max zidk wik , d 1; D , k 1; mi .
d i
Step 2. Place an orthogonal polyhedron Oi in the specified position X i1, X i2 ,, X iD of a new identical empty container, as a result of which a set of potential containers will be formed in it. Placement of the orthogonal polyhedron is performed by sequentially placing of all its orthogonal objects oik , k 1; mi .
Step 3. Apply the intersection operation [19] to sets of potential containers 0 and to get a set of potential containers 0 0 that describes all free spaces of the original container in the area of the compound object Oi . The operation of intersection of sets of potential containers is implemented in the same way as the operation of intersection of two orthogonal polyhedrons, each of which contains the same parameters (position, overall dimensions) of orthogonal objects as the corresponding parameters of potential containers.
Step 4. Replace in the set 0 all potential containers that are also in the set 0 with potential containers from the set 0 .
This algorithm for updating potential containers is presented in Figure 1.
Two algorithms have been developed for packing an orthogonal polyhedron into a container, which are implemented with a generalization in dimension.
Algorithm 1 consists in the sequential formation of an orthogonal polyhedron and performing a series of offsets during its placement in the container [22]. Figure 2 presents an example of the sequential formation of a composite object when it is placed inside a container with geometrical restrictions (shown in gray in the figure). (a ) (b ) (c ) (d )
The second algorithm (denoted by Algorithm 2) for placing an orthogonal polyhedron is based on determining the common area of acceptable placement for intermediate orthogonal polyhedrons composed of separate objects of the original composite object [19].
Table 1 contains the results of computational experiment which was conducted for comparing these two algorithms.
In the course of the computational experiment, the problem of placing two identical orthogonal polyhedrons into a container was solved, the height (W 2 ) of which coincides with the height of the rectangle bounded around the placed orthogonal polyhedron. When solving the problem, a personal computer was used (processor – Intel Core i5-8400, 2.8 GHz; RAM – 8 GB).
Table 1 uses the following notation: m – the number of simple objects in the orthogonal polyhedron; T1 – the time spent on the placement of orthogonal polyhedrons by Algorithm 1; T2 – the time spent on the placement of orthogonal polyhedrons by Algorithm 2.
The computational experiment was performed for various intermediate orthogonal polyhedrons consisting of orthogonal objects. When placing an orthogonal polyhedron consisting of objects whose T1, s number is less than 11, both algorithms ensure the placement of composite objects in the same time (0.03-0.04 s), so Table 1 shows the results obtained when m 11;28.
The results obtained showed that for all problems, Algorithm 2 provides placement in a time that is not less than the time spent by Algorithm 1, while for all values m 11;28, Algorithm 2 provides placement of objects at a speed that is on average two orders of magnitude higher.
Since Algorithm 2 places orthogonal polyhedrons without shifting, their optimal placement is obtained without using the algorithm for determining the optimal position described in article [22].
In Figure 3, a is presented an example of packing 11 ellipses in a rectangular container. It was obtained by Algorithm 2 in 2.8 s while Algorithm 1 did not provide a solution in a time limited to 300 s.
Algorithm 2 provides a significant increase in the speed of placement of both two-dimensional and three-dimensional orthogonal polyhedrons. As an example, consider the problem of placing two identical orthogonal bowl-shaped polyhedrons consisting of 110 orthogonal objects in a threedimensional container (Figure 3, b). Algorithm 1 provides placement of these orthogonal polyhedrons in 13.32 seconds, while Algorithm 2 spends only 0.40 seconds.
1 X ij , X i2j ,, X iDj .
To increase the density of a placement of orthogonal polyhedrons, their local redistribution within the formed packing can be performed. In this case, after removing some orthogonal polyhedron of a given dimension, it is necessary to perform the procedure for updating the set of potential containers in the area of its initial placement.
The algorithm for deleting one object which described in article [23] can be used to implement the algorithm for deleting a compound object represented by a set of simple objects.
We assume that the orthogonal polyhedron Oi being removed is located in the container j at point The developed algorithm for updating the set of potential containers after removing an orthogonal polyhedron of arbitrary dimension D contains 10 steps.
Step 1. Create an empty copy of container j and denote it as a container j .
Step 2. Set the number k : 1 for the currently deleted simple object oik .
Step 3. Place the simple object oik at the point X i1j z1ik , X i2j zi2k ,, X iDj ziDk of the container j .
Step 4. Increase the number of the current simple object ( k : k 1 ). If k m then go to step 3, otherwise go to step 5.
Step 5. Select in the container j potential containers, the overall dimensions of which can be changed after deleting the composite object. This set 1 includes potential containers for which the inequality xkd X idj Sid is true (the vector Si1, Si2 ,, SiD stores overall dimensions of the AABB parallelepiped bounding the orthogonal polyhedron Oi ).
Step 6. Fill the container j with objects that completely fill the space described by a set 1 of potential containers. Denote the set of remained potential containers in the container j by 2 .
Step 7. Create an empty copy of container j and denote it as a container j .
Step 8. Fill the container j with objects that completely fill the space described by a set 1 of potential containers. Denote the set of remained potential containers in the container j by 3 .
Step 9. Remove the compound object Oi from the container j .
Step 10. Remove all potential containers from set 1 from the container j and add into it all potential containers from set 3 .
To transform a container represented in the form of a D -dimensional parallelepiped into an orthogonal polyhedron, it is proposed to place a set of virtual orthogonal objects into it (they are denoted as constraint objects) before forming the placement scheme. The set of constraint objects will be represented finally by a single orthogonal polyhedron Oˆ of geometric constraints of a container.
We will consider a container in the form of a D -dimensional parallelepiped with overall dimensions W1,W 2,,W D , as well as an original set A of orthogonal constraint objects. The constraint object with a number k in the form of a D -dimensional parallelepiped will be denoted by oˆk , its position in the coordinate system of the container will determine the vector z1k , zk2 ,, zkD , and its overall dimensions will determine the vector w1k , wk2 ,, wkD . For each constraint object oˆk , the type of operation applied to it (addition or subtraction of an orthogonal object [19]), which is set when it is created, is known in advance.
All constraint objects from the set A are transformed according to the overall dimensions of the container, so that no constraint object extends beyond the container boundaries. To do this, the following algorithm is performed (steps 1-5).
Step 1. Create an empty set Aˆ of orthogonal constraint objects ( Aˆ ).
Step 2. Set the number of the current constraint object k : 1 .
Step 3. For the constraint object oˆk , perform a check for its placement entirely outside the container boundaries: zkd W d or zkd wkd 0 for everyone d 1,, D. If the constraint object is located outside the container, then go to step 5, otherwise go to step 4.
Step 4. Based on the constraint object oˆk , create a new constraint object oˆ whose position vector zˆ1, zˆ2,, zˆ D and overall dimensions wˆ1, wˆ 2,, wˆ D are defined as follows: zˆd 0 and wˆ d wkd zkd if zkd 0 d 1,, D; zˆd zkd and wˆ d W d zkd if zkd W d
d 1,, D.
The same operation (addition or subtraction) is set for the constraint object oˆ as for the original constraint object oˆk .
Place the constraint object oˆ in the set Aˆ .
Step 5. Go to the next constraint object k : k 1 . If k A then go to step 3, otherwise stop the algorithm.
When creating an orthogonal polyhedron of geometric constraints, the following sets are formed based on the resulting set Aˆ : a set of constraint objects Aˆ to which the set-theoretic addition operation is applied; a set of constraint objects Aˆ to which the set-theoretic subtraction operation is applied.
To form an orthogonal polyhedron Oˆ of geometric constraints with the sets Aˆ and Aˆ , the algorithms described in the article [19] are used. This orthogonal polyhedron of geometric constraints of the container may include constraint objects that will not have common points with each other.
The process of creating a container based on a polygonal model includes the following steps. 1. Voxelization of the model contour and filling the voids of the resulting orthogonal polyhedron. 2. Decomposition of the resulting orthogonal polyhedron of geometric constraints into large objects to increase the speed of packing formation. 3. Apply a subtraction operation with an orthogonal polyhedron of geometric constraints to a AABB parallelepiped bounding the given polygonal model.
Figure 5 presents an example of a container based on a three-dimensional model of the Latin letter R, as well as the result of packing a set of orthogonal polyhedrons into it.
(a) (b) (c)
To obtain a packing with a given fixed gap between orthogonal polyhedrons (an equidistant packing), the position and overall dimensions of all orthogonal objects that are part of these orthogonal polyhedrons are corrected during their placement.
When placing a D -dimensional orthogonal polyhedron O at a point X 1, X 2,, X D of a container, each orthogonal object ok O will be placed at a point with the gap in the direction of the origin: X 1 z1k , X 2 zk2 ,, X D zkD , and also will have an increased overall size by an amount 2 : w1k 2, wk2 2,, wkD 2 . After obtaining a set of potential containers describing free entire of the container (which formed as a result of placing this orthogonal polyhedron), the original values of the vectors describing the position and overall dimensions of its orthogonal objects are restored.
Figure 6 shows examples of the formation of an equidistant packing of a large number of objects when setting different gaps (the overall dimensions of a rectangle bounding the container are 300300). (a ) (b ) (c )
The article presents a number of algorithms designed for packing objects of complex shape, represented as orthogonal polyhedrons. These algorithms are the basis for a new method for solving problems of cutting and packing irregular objects, which consists in reducing the solved problems to the problems of placing orthogonal polyhedrons of a given dimension, which can be solved in significantly less time.
An algorithm for placing orthogonal polyhedrons of arbitrary dimension was proposed, based on the sequential formation of an orthogonal polyhedron and performing a series of displacements during its placement in the container (Algorithm 1). This algorithm provides fast production of dense placement schemes of orthogonal polyhedrons made up of a small number of orthogonal objects (usually consisting of no more than 10 objects). To increase the speed of placement of orthogonal polyhedrons with a larger number of orthogonal objects, an improved algorithm (Algorithm 2) is developed, based on the creation of orthogonal polyhedrons that determine the areas of acceptable placement for each object from this compound object. Algorithm 2 significantly increases the speed of packing formation (on average by two orders of magnitude) without losing the quality of placement, which makes it advisable to use it in solving any types of problems of pacing orthogonal polyhedrons.
The developed algorithm for removing an orthogonal polyhedron and the use of the model of potential containers that describes all existing free areas inside the containers makes it possible to apply methods for local reallocation of compound objects placed in the container.
A method for forming an equidistant packing where all objects are located at a given minimum distance from each other has been developed. This method is used, in particular, when forming the arrangement of complex-shaped parts on a 3D printer platform.
An important distinguishing feature of the presented algorithms is their implementation for the case of an arbitrary dimension of the problem. All the described algorithms are programmatically implemented and tested in the author's software «Packer» [20, 24, 25].
[4] R. J. Mailloux, S. G. Santarelli, T. M. Roberts, D. Luu, Irregular polyomino-shaped subarrays for
space-based active arrays, International Journal of Antennas and Propagation (2009).
doi:10.1155/2009/956524.
[5] S. Plankovskyy, Y. Tsegelnyk, O. Shypul, A. Pankratov, T. Romanova, Cutting irregular objects
from the rectangular metal sheet, in: M. Nechyporuk, V. Pavlikov, D. Kritskiy (Eds), Integrated
Computer Technologies in Mechanical Engineering, volume 1113, Springer, Cham, 2020,
pp. 150-157. doi:10.1007/978-3-030-37618-5_14.
[6] C. Zhao, L. Jiang, K. L. Teo, A hybrid chaos firefly algorithm for three-dimensional irregular
packing problem, Journal of Industrial & Management Optimization 16(
Extra Volume ISMP (2012) 359–376. URL: https://elibm.org/article/10011465.
[9] S. C. Leung, Y. Lin, D. Zhang, Extended local search algorithm based on nonlinear programming
for two-dimensional irregular strip packing problem, Computers & Operations Research 39(
International Transactions in Operational Research 20(