=Paper=
{{Paper
|id=Vol-2744/paper50
|storemode=property
|title=Solving the Problem of Packing Objects of Complex Geometric Shape into a Container of Arbitrary Dimension
|pdfUrl=https://ceur-ws.org/Vol-2744/paper50.pdf
|volume=Vol-2744
|authors=Vladislav Chekanin
}}
==Solving the Problem of Packing Objects of Complex Geometric Shape into a Container of Arbitrary Dimension==
https://ceur-ws.org/Vol-2744/paper50.pdf
Solving the Problem of Packing Objects of Complex
Geometric Shape into a Container of Arbitrary
Dimension*
Vladislav Chekanin1[0000-0001-9448-0583]
1 Moscow State University of Technology «STANKIN», Moscow, Russia
vladchekanin@rambler.ru
Abstract. The article is devoted to algorithms developed for solving the prob-
lem of placement orthogonal polyhedrons of arbitrary dimension into a contain-
er. To describe all free areas of a container of complex geometric shape is ap-
plied the developed model of potential containers. Algorithms for constructing
orthogonal polyhedrons and their subsequent placement are presented. The de-
composition algorithm intended to reduce the number of orthogonal objects
forming an orthogonal polyhedron is described in detail. The proposed place-
ment algorithm is based on the application of intersection operations to obtain
the areas of permissible placement of each considered object of complex geo-
metric shape. Examples of packing sets of orthogonal polyhedrons and
voxelized objects into containers of various geometric shapes are given. The ef-
fectiveness of application of all proposed algorithms is presented on an example
of solving practical problems of rational placement of objects produced by 3D
printing technology. The achieved layouts exceed the results obtained by the
Sinter module of the software Materialise Magics both in speed and density.
Keywords: Orthogonal Polyhedron, Voxelized Object, Packing Problem,
3D Printing.
1 Introduction
The problem of packing objects of irregular geometric shape has a large number of
practical applications in various fields, including cutting of industrial materials, layout
of spaces (spaces of aircraft, ships and etc.), covering problems, modeling the micro-
structure of materials, active electronically scanned arrays generation and other rele-
vant problems [1–5]. All the packing problems including the classic orthogonal pack-
ing problem are NP-hard [6, 7] and require the use of heuristic [8, 9] or metaheuristic
optimization algorithms [10–14]. Therefore, it is important to develop effective algo-
rithms that provide good layout of objects at an acceptable time.
Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons Li-
cense Attribution 4.0 International (CC BY 4.0).
* Publication financially supported by RFBR grant №20-01-00547
2 V. Chekanin
The use of polygonal modeling in describing the geometric shape of objects re-
quires the subsequent use of time-consuming algorithms for nonlinear programming
when solving the problem of placing these objects using the hodograph of a vector
function of dense placement [15, 16]. Due to the high computational complexity,
nonlinear programming methods practically ineffective when increasing the number
of packed objects. To solve the problem of packing objects of irregular geometric
shape is proposed to present the objects as the orthogonal polyhedrons which combine
non-overlapping orthogonal objects (rectangles or parallelepipeds in the two-
dimensional or three-dimensional case, respectively) with a fixed position relative to
each other [17–20]. This approach makes it possible to solve the problems of packing
voxelized objects of complex geometric shape [21, 22].
We will consider the problem of placement orthogonal polyhedrons in the general
D -dimensional case. A container is specified in the form of D -dimensional parallel-
1
epiped with the dimensions W ;W ;;W
2
D
(the superscript in formulas means the
number of the coordinate axis) as well as specified a set of n orthogonal polyhedrons
Oi , i 1, , n, each of which consists of mi orthogonal objects in the form of D -
dimensional parallelepipeds oi ,k , k 1,, mi with the dimensions
w ; w ;; w , the position of which relative to each other is specified using vec-
1
i ,k
2
i ,k
D
i ,k
tors z ; z ;; z containing the coordinates of orthogonal objects in the local
1 2 D
i ,k i,k i,k
coordinate system associated with each orthogonal polyhedron Oi . In the particular
case, when all orthogonal polyhedrons consist of only one orthogonal object
mi = 1 i 1, , n , the considered problem will be reduced to the classic D -
dimensional orthogonal packing problem [1, 2].
2 Representation of Objects and Description of a Packing
2.1 Set-theoretic Operations for Working with Orthogonal Polyhedrons
To work with orthogonal polyhedron of arbitrary dimension, the set-theoretic opera-
tions of addition and intersection were implemented. When performing operation of
addition of orthogonal objects, the following sets of objects are used: A – the initial
+
set of objects, A – set of objects to which the addition operation is applied, B – an
intermediate set of objects, C – the resulting set of orthogonal objects. The size of a
set of objects is indicated as A (for a set A ).
The operation of addition orthogonal objects (Figure 1) includes the following steps.
+
1. Place all objects from the set A into the set A . Create sets B = , C = .
+
2. Sort the set A in descending order of volumes (areas) of objects.
3. Include the first object o1 A + in the set C .
Solving the Problem of Packing Objects of Complex Geometric Shape into a Container… 3
4. For each current object ok A+ (k = 2 A+ ) check for overlapping with the
object o1 . If the objects do not overlap each other, then place the current object o k in
the set B ; otherwise, perform the cutting off procedure for all objects, and then place
the obtained objects in the set B .
5. Clear the set A+ . If the set B , then move all the objects from the set B to
the set A+ , and then go to step 2.
(a) (b)
Fig. 1. The addition operation: (a) original objects; (b) result
The result of the intersection operation of orthogonal polyhedrons O1 O2 is a
new orthogonal polyhedron, the points of which occupy a space that belongs simulta-
neously to two original orthogonal polyhedrons (Figure 2).
(a) (b)
Fig. 2. The intersection operation: (a) original objects; (b) result
2.2 Model of Potential Containers
To describe a packing is used the developed model of potential containers [23, 24].
Under a potential container (PC) placed in a container at some its point is understood
an imaginary orthogonal object with the largest possible dimensions that can be
placed at this point without overlapping with any packed into the container object and
edges of the container. Each potential container h is described with a vector
p1h ; ph2 ;; phD containing its dimensions and a vector x1h ; xh2 ;; xhD containing
coordinates of its point which is nearest to the origin of the container containing it.
4 V. Chekanin
All existing free orthogonal spaces located in a container are described by a set of
potential containers. When a new orthogonal object is put into a container it is neces-
sary to verify the correctness of the placement. The model of potential containers
guarantees the correct placement of an orthogonal object if it overlaps no borders of
the potential container in which it is located. In this case when an object is put at
some point of a container instead of checking on the intersection with all placed into
the container objects is required to check only one condition of placement of this
object entirely within the potential container, located at this point. This ensures a
higher speed of formation the orthogonal packing. When an orthogonal object i with
the dimensions wi1 ; wi2 ;; wiD is placed at a point xi1 ; xi2 ;; xiD it divides the po-
tential container h into a set of smaller potential containers from two sets:
− a set of D potential containers with the dimensions
1
2 d −1 d d
ph ; ph ;; ph ; xi − xh ; phd +1 ;, phD located in the origin
x ; x ;; x ;; x of the potential container h produced under the fol-
1
h
2
h
d
h
D
h
lowing conditions: xid xhd and xid xhd + phd d 1, , D ;
− a set of D potential containers with the dimensions
1 2 d −1 d
ph ; ph ;; ph ; xh + phd − xid − wid ; phd +1 ;; phD located at D points with
coordinates x ; x ;; x ; x + w ; x ;; x produced under the fol-
1
h
2
h
d −1
h
d
i
d
i
d +1
h
D
h
lowing conditions: xid + wid xhd and xid + wid xhd + phd d 1, , D .
Figure 3 presents all new potential containers (gray) which are formed in a three-
dimensional potential container after placing an orthogonal object inside it.
Fig. 3. New potential containers
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 free spaces of which
are described by a set of potential containers 0 , the following algorithm is per-
formed.
Step 1. Create a set 0 0 of potential containers
h : d 1,, D: xhd X id + Sid , where S i1 , S i2 ,, S iD denotes the overall dimen-
sions of a D -dimensional parallelepiped bounding the orthogonal polyhedron Oi :
( )
S id = max z id, k + wid, k , d 1, , D , k 1, , mi .
Step 2. Place an orthogonal polyhedron Oi in the specified position
X , X ,, X of a new identical empty container, as a result of which a set of
1
i i
2
i
D
Solving the Problem of Packing Objects of Complex Geometric Shape into a Container… 5
potential containers will be formed in it. Placement of the orthogonal polyhedron
is performed by sequentially placing of all its orthogonal objects oi ,k , k 1,, mi .
Step 3. Apply the intersection operation 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 placed orthogonal polyhedron Oi . During the
intersection operation, each set of potential containers is considered as an orthogonal
polyhedron, consisting of orthogonal objects whose parameters coincide with the
parameters of the corresponding 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 .
2.3 Decomposition of Orthogonal Polyhedron
To reduce the number of orthogonal objects forming an orthogonal polyhedron, a
decomposition algorithm has been developed. The algorithm provides the decomposi-
tion of a D -dimensional orthogonal polyhedron V into a set of large orthogonal
objects includes steps 1–6.
Step 1. Create an empty D -dimensional orthogonal container 1 with the overall
dimensions W11 ,W12 ,,W1D matching the dimensions of a D -dimensional parallel-
epiped bounding the original orthogonal polyhedron V ( W1d = S d , d 1,, D ,
where S d is the length of the packing measured along the axis d .
Step 2. Place the orthogonal polyhedron V into container 1.
As a result in the container 1, a set of potential containers 1 with the overall di-
1 1 1
1 1 1
mensions w1k , wk2 , , wkD , k1 1 located at points p1k , pk2 ,, pkD will be formed.
The set of potential containers 1 describes the space of container 1, which does not
belong to the placed orthogonal polyhedron V .
Step 3. Create an empty D -dimensional orthogonal container 2 with the overall
dimensions that match the overall dimensions of the container 1 ( W2d = W1d ,
d 1, , D ).
Step 4. Place in the container 2 a set of D -dimensional orthogonal objects with
parameters matching the parameters of potential containers from the container 1
(when placing objects, their mutual overlap is allowing): xid = pkd and wid = wkd 1 1
d 1,, D , i = 1 1 . As a result in the container 2, a set of potential contain-
2 2 2
ers 2 with the overall dimensions w1k , wk2 ,, wkD , k 2 2 , located at points
p , p ,, p , will be formed. The set describes the space of container 2,
1
k2
2
k2
D
k2 2
which belongs to the orthogonal polyhedron V .
Step 5. Create a D -dimensional orthogonal polyhedron V , consisting of orthog-
onal objects with parameters matching the parameters of potential containers from the
container 2: z id = p kd and wid = wkd d 1,, D , i = 1 2 , so the orthogonal
2 2
6 V. Chekanin
polyhedron V will contain the set of all orthogonal objects into which it can be de-
composed.
Step 6. Apply the addition operation to all orthogonal objects that are part of the
orthogonal polyhedron V . As a result, an orthogonal polyhedron O will be obtained,
consisting of the largest orthogonal objects that do not overlap each other.
Examples of decomposition of two-dimensional and three-dimensional orthogonal
polyhedrons are presented in Figure 4.
To speed up the decomposition of a voxelized object, it is proposed to use a two-
stage algorithm. At the first stage, the fast algorithm of objects clustering described
below is applied, after which the developed decomposition algorithm is applied to the
resulting orthogonal polyhedron.
(a) (b)
(c) (d)
Fig. 4. Examples of decomposition of orthogonal polyhedrons: (a) original orthogonal polyhe-
dron (1398 objects); (b) decomposed orthogonal polyhedron (72 objects); (c) original orthogo-
nal polyhedron (2259 objects); (d) decomposed orthogonal polyhedron (308 objects)
Algorithm of clustering a voxelized object O i includes three steps.
Step 1. Set current axis number d := 1 .
Step 2. For each pair of orthogonal objects oi, k Oi and oi , j Oi ( k , j Oi ) cre-
ate a new orthogonal object o with overall dimensions
w + w , w + w ,, w + w located at a point z , z ,, z under the
1
i,k
1
i, j
2
i,k
2
i, j
D
i,k
D
i, j
1
i,k
2
i,k
D
i,k
d d d d
conditions zi , j = zi , k , wi , j = wi , k d d and zi , j = zi , k + wi , k . Replace in the orthog-
d d d
onal polyhedron Oi the objects oi , k and oi , j with the object o . If there are no ob-
jects oi , k and oi , j satisfying the above conditions in the orthogonal polyhedron O i ,
then go to step 3, otherwise repeat step 2.
Step 3. Set d := d + 1 . If d D then go to step 2.
Solving the Problem of Packing Objects of Complex Geometric Shape into a Container… 7
Figure 5 presents an example of clustering and decomposition of a voxelized ob-
ject. The voxelized object was clustered in 0.03 s (Figure 5, d). Two-stage algorithm
decomposes it in 6.45 s (Figure 5, e) while decomposition algorithm without cluster-
ing spends 15.11 s. The computational experiments were carried out on a personal
computer (Intel Core i5-8400 2.80 GHz, RAM 8.00 GB).
(a) (b) (c)
(d) (e)
Fig. 5. Two-stage algorithm of decomposition of a voxelized object: (a) original orthogonal
polyhedron (13238 objects); (b) clustered orthogonal polyhedron when d = 1 (2503 objects);
(c) clustered orthogonal polyhedron when d = 2 (800 objects); (d) clustered orthogonal poly-
hedron when d = 3 (521 objects); (e) decomposed orthogonal polyhedron (483 objects)
3 Placement of Orthogonal Polyhedrons
Figure 6 presents the developed algorithm for packing orthogonal polyhedrons of
arbitrary dimension into a container.
This algorithm is based on the creation of orthogonal polyhedrons that determine
the possible placement areas for each object of complex shape. To reduce the com-
plexity of the block diagram, in Figure 6 is presented a part of the algorithm which
provides placing of an orthogonal polyhedron inside only one current container. Algo-
rithm for packing orthogonal polyhedrons in a set of containers in presented in the
paper [25].
The steps for sequentially determining the region of possible placement of an or-
thogonal polyhedron in a given potential container are shown in Figure 7. The final
orthogonal polyhedron is obtained after application the intersection operation to all
orthogonal polyhedrons describing areas of possible placement:
U i = U i ,1 U i , 2 U i ,3 U i , 4 .
8 V. Chekanin
Start
Select the first PC in the container
as the current PC
Is it possible to yes
place OP Oi entirely in A
the current PC? Create OP Ui,1,
describing the area of Select the
no possible placement of point of the OP
the first object inside the Ui which is
current PC closest to the
Is it possible
yes origin of the
to place the first object
k: 2, mi, 1 container for
from OP Oi in the
placing OP Oi
current PC?
no Define a set of PCs {P} Search for a
in which an object oi,k PC to place the
can be placed OP Oi entirely
yes Were checked closer to the
B all existing potential Create OP Ui,k, origin of the
containers? describing the areas of container
possible placement of
OP, composed with
no Shift the OP Oi
objects o1 and ok, in the
closer to the
coordinate system of the
Select the next PC as the origin of the
current PC when the set
current PC container
of PCs {P} to place the
object oi,k is used
A
Create OP Ui as a result
of intersection of all OP Place the OP
Ui,k (k=1…mi) Oi in the found
position
no Is the OP Ui yes
not empty?
B End
Fig. 6. Algorithm of placing an orthogonal polyhedron (OP) Oi in a container
Solving the Problem of Packing Objects of Complex Geometric Shape into a Container… 9
(a) (b) (c)
(d) (e)
Fig. 7. Determining the area of possible placement of an orthogonal polyhedron (filled with a
gradient fill) for the current potential container located in the upper left corner of the container:
(a) Ui,1; (b) Ui,2; (c) Ui,3; (d) Ui,4; (e) resulting placement area Ui
To convert a container represented in the form of a D -dimensional parallelepiped
into an orthogonal polyhedron, it is proposed to place a set of fictitious orthogonal
objects in it that are combined into one orthogonal polyhedron of geometric con-
straints. Figure 8 shows a set of constraints that transform a rectangular container into
an ellipse, as well as the result of packing various objects into it.
Examples of placement of orthogonal objects and orthogonal polyhedrons inside
containers of complex geometric shapes are presented in Figure 9.
(a)
(b)
Fig. 8. Container in the form of ellipse: (a) original container with geometric constraints;
(b) placement of objects in the container
10 V. Chekanin
(a) (b)
Fig. 9. Packing of objects in a container of complex geometric shape: (a) waste-free packing of
parallelepipeds in a cone; (b) compact placement of balls in a sphere
4 Solving the Layout Problem
The developed algorithm for packing orthogonal polyhedrons was applied to solve
practical problems of rational placement of objects produced by 3D printing.
Solving the problem of optimizing the layout of objects is of great importance in
additive technologies, since it can significantly reduce the consumption of material,
reduce the time spent on preparing the layout of objects inside the platform (contain-
er) of a 3D printer, as well as the time spent on their direct manufacture. The use of
denser layouts additionally leads to a reduction in energy costs in the process of man-
ufacturing objects, and also reduces the equipment depreciation used.
At present, the richest functionality for solving the problems of additive manufac-
turing is provided by the software Materialise Magics (Materialise NV, Lovaine, Bel-
gium), which is used by the world's leading manufacturers of equipment for 3D print-
ing [26]. The widespread recognition of this tool in the global market for additive
technologies explains its choice for a comparative analysis of the obtained results.
We consider a three-dimensional container with the following parameters: length:
340 mm, width: 340 mm, height: 620 mm, the gap from the bottom of the container is
9 mm, the gap from the side faces of the container is 10 mm, minimum distance be-
tween placed objects is 6 mm. Objects can be rotated by multiples of 90 when
placed. Figure 10 (a) shows the best solution obtained by the Sinter module of the
software Materialise Magics, version 23.0.1.19 (packing height: 318.0 mm, solution
time: 300 seconds). The packing consists of 100 objects of 8 different types specified
in STL format. To solve this problem, using the developed placement algorithm, all
objects were voxelized and decomposed. Figure 10 (b) presents the denser placement
of orthogonal polyhedrons found by the developed software Packer [27] (packing
height: 298.4 mm, solution time: 96 seconds). Based on the found solution, a 3D
printing layout was built, it is shown in Figure 10 (c).
Solving the Problem of Packing Objects of Complex Geometric Shape into a Container… 11
(a) (b) (c)
Fig. 10. Placement of irregular objects at a given minimum distance from each other: (a) the
best placement obtained by Materialise Magics; (b) dense placement of orthogonal polyhedrons
(decomposed voxelized objects) obtained by the developed algorithms; (c) layout for 3D print-
ing in Materialise Magics based on the found placement of orthogonal polyhedrons
5 Conclusion
Using the developed model of potential containers to describe the free spaces inside a
container, it is possible to obtain the best area for placing irregular objects inside ge-
ometrically complex containers. This model allows switch from use the time-
consuming nonlinear programming methods (which are applied for placing objects
specified by polygonal modeling, the practical application of which is limited only by
the small size of the problem) to methods developed for placing voxelized objects.
Unlike decomposition algorithms developed by other authors [28–30], the pro-
posed algorithm is described and programmatically implemented invariantly with
respect to the dimension of the problem to be solved. The developed algorithm pro-
vides decomposition of orthogonal polyhedrons of arbitrary shape, including those
with holes or internal cavities. The developed decomposition algorithm of the orthog-
onal polyhedrons provides an increase in the speed of placing voxelized objects by an
average of two orders of magnitude.
The practical application of the developed algorithms is demonstrated by the ex-
ample of solution the layout problem of objects produced by 3D printing. The found
solution exceeds the best solution obtained by the software Materialise Magics both in
terms of speed and packing dense.
12 V. Chekanin
References
1. Wäscher, G., Haußner, H., Schumann, H.: An improved typology of cutting and packing
problems. European Journal of Operational Research 183(3), 1109–1130 (2007).
2. Bortfeldt, A., Wäscher, G.: Constraints in container loading - A state-of-the-art review.
European Journal of Operational Research 229(1), 1–20 (2013).
3. Chekanin, V.A., Chekanin, A.V.: Algorithms for management objects in orthogonal pack-
ing problems. ARPN Journal of Engineering and Applied Sciences 11(13), 8436–8446
(2016).
4. Crainic, T.G., Perboli, G., Tadei, R.: Recent advances in multi-dimensional packing prob-
lems. In: Volosencu, C. (ed.) New Technologies–Trends, Innovations and Research,
pp. 99–110. InTech (2012).
5. Mailloux, R.J., Santarelli, S.G., Roberts, T.M., Luu, D.: Irregular polyomino-shaped subar-
rays for space-based active arrays. International Journal of Antennas and Propagation
(2009). https://doi.org/10.1155/2009/956524.
6. Garey, M, Johnson, D.: Computers Intractability: a Guide to the Theory of NP-
completeness. W.H.Freeman, San Francisco (1979).
7. Johnson, D.S.: A brief history of NP-completeness, 1954–2012. Documenta Mathematica
Extra Volume ISMP, 359–376 (2012).
8. Oliveira, J.F., Neuenfeldt, Júnior A., Silva, E., Carravilla, M.A.: A survey on heuristics for
the two-dimensional rectangular strip packing problem. Pesquisa Operacional 36(2), 197–
226 (2016).
9. Chen, D., Liu, J., Fu, Y., Shang, M.: An efficient heuristic algorithm for arbitrary shaped
rectilinear block packing problem. Computers & Operations Research 37(6), 1068–1074
(2010).
10. Gao, Y.Q., Guan, H.B., Qi, Z.W., Hou, Y., Liu, L.: A multi-objective ant colony system
algorithm for virtual machine placement in cloud computing. Journal of Computer and
System Sciences 79(8), 1230–1242 (2013).
11. Martinez, M.A.A., Clautiaux, F., Dell’Amico, M., Iori, M.: Exact algorithms for the bin
packing problem with fragile objects. Discrete Optimization 10(3), 210–223 (2013).
12. Kierkosz, I., Luczak, M.: A hybrid evolutionary algorithm for the two-dimensional pack-
ing problem. Central European Journal of Operations Research 22(4), 729–753 (2014).
13. Chekanin, V.A., Chekanin, A.V.: Development of the multimethod genetic algorithm for
the strip packing problem. Applied Mechanics and Materials 598, 377–381 (2014).
14. Chekanin, V.A., Chekanin, A.V.: Design of library of metaheuristic algorithms for solving
the problems of discrete optimization. In: Evgrafov, A. (eds.) Advances in Mechanical En-
gineering. Lecture Notes in Mechanical Engineering, pp. 25–32. Springer, Cham (2018).
15. Stoyan, Y., Romanova, T., Pankratov, A., Chugay, A.: Optimized object packings using
quasi-phi-functions . Optimized packings with applications. In: Fasano, G. Pintér, J. (eds.)
Optimized Packings with Applications, pp. 265–293. Springer, Cham (2015).
16. Ma, Y., Chen, Z., Hu, W., Wang, W.: Packing irregular objects in 3D space via hybrid op-
timization. Computer Graphics Forum 37(5), 49–59 (2018).
17. Alvarez-Valdes, R., Carravilla, M.A., Oliveira, J.F.: Cutting and packing. In: Martí, R.,
Panos, P., Resende, M. (eds) Handbook of Heuristics, pp. 1–46. Springer, Cham (2018).
https://doi.org/10.1007/978-3-319-07153-4_43-1.
18. Chekanin, V.A., Chekanin, A.V.: Development of Algorithms for the Correct Visualiza-
tion of Two-Dimensional and Three-Dimensional Orthogonal Polyhedrons. In: Radi-
onov, A., Karandaev, A. (eds) Advances in Automation. RusAutoCon 2019. Lecture Notes
in Electrical Engineering, vol. 641, pp. 891–900. Springer, Cham (2020).
Solving the Problem of Packing Objects of Complex Geometric Shape into a Container… 13
19. Aldana-Galván, I., Álvarez-Rebollar, J.L.,„ Catana-Salazar, J.C., Marín-Nevárez, N., Sol-
ís-Villarreal, E., Urrutia, J., Velarde, C.: Beacon coverage in orthogonal polyhedra. In:
29th Canadian Conference on Computational Geometry (CCCG 2017), pp. 166–171. Ot-
tawa (2017).
20. Bournez, O., Maler, O., Pnueli, A.: Orthogonal polyhedra: Representation and computa-
tion. In: Vaandrager, F.W., van Schuppen, J.H. (eds) Hybrid Systems: Computation and
Control. HSCC 1999. Lecture Notes in Computer Science, vol. 1569, pp. 46–60. Springer,
Berlin, Heidelberg (1999).
21. De Korte, A.C.J., Brouwers, H.J.H.: Random packing of digitized particles. Powder tech-
nology 233, 319–224 (2013).
22. Tolok, A.V., Tolok, N.B.: Mathematical Programming Problems Solving by Functional
Voxel Method. Automation and Remote Control 79(9), 1703–1712 (2018).
23. Chekanin, V.A., Chekanin, A.V.: Deleting objects algorithm for the optimization of or-
thogonal packing problems. In: Evgrafov, A. (eds.) Advances in Mechanical Engineering.
Lecture Notes in Mechanical Engineering, pp. 27–35. Springer, Cham (2017).
24. Chekanin, V.A., Chekanin, A.V.: An efficient model for the orthogonal packing problem.
In: Evgrafov, A. (eds.) Advances in Mechanical Engineering. Lecture Notes in Mechanical
Engineering, pp. 33–38. Springer, Cham (2015).
25. Chekanin, V.A., Chekanin, A.V.: Algorithm for the Placement of Orthogonal Polyhedrons
for the Cutting and Packing Problems. In: Evgrafov, A. (eds.) Advances in Mechanical
Engineering. Lecture Notes in Mechanical Engineering, pp. 41–48. Springer, Cham
(2020).
26. Hällgren, S., Pejryd, L., Ekengren, J.: 3D data export for additive manufacturing-
improving geometric accuracy. Procedia CIRP 50, 518–523 (2016).
27. Chekanin, V.A., Chekanin, A.V.: Implementation of packing methods for the orthogonal
packing problems. Journal of Theoretical and Applied Information Technology 88(3),
421–430 (2016).
28. Durocher, S., Mehrabi, S.: Computing conforming partitions of orthogonal polygons with
minimum stabbing number. Theoretical Computer Science 689, 157–168 (2017).
29. Biedl, T., Derka, M., Irvine, V., Lubiw, A., Mondal, D., Turcotte, A.: Partitioning Orthog-
onal Histograms into Rectangular Boxes. In: Bender M., Farach-Colton M., Mosteiro M.
(eds.) LATIN 2018: Theoretical Informatics. LATIN 2018. Lecture Notes in Computer
Science, vol. 10807, pp. 146–160. Springer, Cham (2018)
30. Floderus, P., Jansson, J., Levcopoulos, C., Lingas, A., Sledneu, D.: 3D rectangulations and
geometric matrix multiplication. Algorithmica 80(1), 136–154 (2018).