Packing Soft Polygons in a Minimum Height Rectangular Target Domain

Abstract

The paper studies packing polygons of variable shapes, regarding the stretching coefficient, in a rectangular target domain of minimum height. Packing objects of a variable shape have a wide spectrum of applications, e.g, in biology, materials science, mechanics, land allocation, and logistics. Interest in these problems is also due to the modeling of the structures of porous media under pressure, e.g., for creating test models of artificial digital cores. Elements of porous media can be deformed under the influence of an external force, but the mass of each particle remains unchanged. This corresponds to conservation of area for the two-dimensional case. Polygonal objects must be completely contained within the target domain (containment constraint) and do not overlap (non-overlapping constraint), provided they have free translations, continuous rotations, stretch transformations, and conserve their area. The phi-function technique is used for an analytical description of the placement constraints for variable shape polygons. Quasi-phi-functions for describing non-overlapping constraints and phi-functions for describing containment constraints are defined. The packing problem is presented in the form of a nonlinear programming model. A solution strategy is proposed, which consists of the following stages: generation of feasible starting points; search for local minima of the problem of packing soft polygons for each starting point using the decomposition algorithm; choosing the best local minimum found at the previous stage. To search for smart starting arrangements, an optimization algorithm for packing original polygons using their homothetic transformations is applied. Decomposition of the problem of packing polygons of variable shapes is based on an iterative procedure that allows reducing a large-scale problem to a sequence of smaller nonlinear programming problems (linear to the number of objects). Numerical examples are provided for oriented rectangles and non-oriented regular polygons.

Keywords

• packing
• polygons
• stretch transformation
• rectangular container
• quasi-phi-functions
• optimization
• decomposition algorithm