Received 09.06.2021; Revised 19.06.2021; Accepted 24.06.2021

Published 30.06.2021; First Online 01.07.2021

https://doi.org/10.34229/2707-451X.21.2.2

Previous  |  Full text (in Ukrainian)  |  Next

 

UDC 519.85

Convex Polygonal Hull for a Pair of Irregular Objects

V.M. Dubynskyi ¹,   O.V. Pankratov ¹ ,   T.E. Romanova ^{1 *} ,   B.S. Lysenko ²,   R.V. Kayafyuk ²,   O.O. Zhmud ³

¹ A.M. Pidgorny Institute of Mechanical Engineering Problems of the NAS of Ukraine, Kharkiv

² Kharkiv National University of Radio Electronics, Ukraine

³ V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv

^* Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.

 

Introduction. Optimization placement problems are NP-hard. In most cases related to cutting and packing problems, heuristic approaches are used. The development of analytical methods for mathematical modeling of the problems is of paramount important for expanding the class of placement problems that can be solved optimally using state of the art NLP-solvers.

The problem of placing two irregular two-dimensional objects in a convex polygonal region of the minimum size, which is a convex polygonal hull of the minimum area or perimeter, is considered. Continuous rotations and translations of non-overlapping objects are allowed.

To solve the problem of optimal compaction of a pair of objects, two algorithms are proposed. The first is a sequentially search for local extrema on all feasible subdomains using a solution tree. The second algorithm searches for a locally optimal extremum on a single subdomain using a "good" feasible starting point.

Purpose of the paper. Show how to construct a minimal convex polygonal hull for two continuously moving irregular objects bounded by circular arcs and line segments.

Results. A mathematical model is constructed in the form of a nonlinear programming problem using the phi-function technique. Two algorithms are proposed for solving the problem of placing a pair of objects in order to minimize the area and perimeter of the enclosing polygonal area. The results of computational experiments are presented.

Conclusions. The construction of a minimal convex polygonal hull for a pair of two-dimensional objects having an arbitrary spatial shape and allowing continuous rotations and translations makes it possible to speed up the process of finding feasible solutions for the problem of placing a large number of objects with complex geometry.

 

Keywords: convex polygonal hull, irregular objects, phi-function technique, nonlinear optimization.

 

Cite as: Dubynskyi V.M., Pankratov O.V., Romanova T.E., Lysenko B.S., Kayafyuk R.V., Zhmud O.O. Convex Polygonal Hull for a Pair of Irregular Objects. Cybernetics and Computer Technologies. 2021. 2. P. 13–24. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.2.2

 

References

           1.     Preparata F.P., Shamos M.I. Computational Geometry: An Introduction. Springer. 1985. 400 p. doi.org/10.1007/978-1-4612-1098-6

           2.     Avis D., Bremner D., Seidel R. How good are convex hull algorithms? Computational Geometry: Theory and Applications. 1997. 7 (5–6). P. 265–301. doi.org/10.1016/S0925-7721(96)00023-5

           3.     Cormen T.H., Leiserson C.E., Ronald L. Rivest R.L., Stein C. Introduction to Algorithms, Second Edition. Section 33.3: Finding the convex hull. MIT Press and McGraw-Hill. 2001. P. 947–957. ISBN 0-262-03293-7.

           4.     De Berg M., Cheong O., Van Kreveld M., Overmars M. Computational Geometry Algorithms and Applications. Berlin: Springer. 2008. P. 2–14. doi:10.1007/978-3-540-77974-2

           5.     Scheithauer G. Introduction to Cutting and Packing Optimization. Problems, Modeling Approaches. Solution Methods. Springer. 2018. 410 p. doi.org/10.1007/978-3-319-64403-5

           6.     Alt H., de Berg M., Knauer C. Approximating Minimum-Area Rectangular and Convex Containers for Packing Convex Polygons. In: Bansal N., Finocchi I. (eds) Algorithms. ESA 2015. Lecture Notes in Computer Science. Springer, Berlin, Heidelberg. 2015. 9294. P. 25–34. doi.org/10.1007/978-3-662-48350-3_3

           7.     Yagiura M., Umetani S., Imahori S. Cutting and Packing Problems ‑ From the Perspective of Combinatorial Optimization. Springer. 2021. 300 p. ISBN 978-4-431-55291-8

           8.     Tang K., Wang C.C.L., Chen D.Z. Minimum area convex packing of two convex polygons. International Journal of Computational Geometry & Applications. 2006. 16 (1). P. 41–74. doi.org/10.1142/S0218195906001926

           9.     Kallrath J. Cutting Circles and Polygons from Area-Minimizing Rectangles. Journal of Global Optimization. 2009. 43. P. 299–328. doi.org/10.1007/s10898-007-9274-6

       10.     Ahn H.K., Cheong O. Aligning Two Convex Figures to Minimize Area or Perimeter. Algorithmica. 2012. 62. P. 464–479. doi.org/10.1007/s00453-010-9466-1

       11.     Park D., Bae S.W., Alt H., Ahn H.K. Bundling three convex polygons to minimize area or perimeter. Computational Geometry. 2016. 51. P. 1–14. doi.org/10.1016/j.comgeo.2015.10.003

       12.     Kallrath J., Frey M.M. Packing Circles into Perimeter-Minimizing Convex Hulls. Journal of Global Optimization. 2019. 73 (4). P. 723–759. doi.org/10.1007/s10898-018-0724-0

       13.     Kallrath J., Frey M.M. Minimal surface convex hulls of spheres. Vietnam J. Math. 2018. 46. P. 883–913. doi.org/10.1007/s10013-018-0317-8

       14.     Chernov N., Stoyan Yu, Romanova T. Mathematical model and efficient algorithms for object packing problem. Computational Geometry. 2010. 43 (5). P. 535–553. doi.org/10.1016/j.comgeo.2009.12.003

       15.     Stoyan Y., Pankratov A., Romanova T. Placement Problems for Irregular Objects: Mathematical Modeling, Optimization and Applications. In: Butenko S., Pardalos P., Shylo V. (eds) Optimization Methods and Applications. Springer Optimization and Its Applications. 2017. 130. P. 521–559. Springer, Cham. doi.org/10.1007/978-3-319-68640-0_25

       16.     Chernov N., Stoyan Y., Romanova T., Pankratov A. Phi-functions for 2D objects formed by line segments and circular arcs. Advances in Operations Research. 2012. doi.org/10.1155/2012/346358

       17.     Stoyan Yu., Pankratov A., Romanova T. Cutting and Packing problems for irregular objects with continuous rotations: mathematical modeling and nonlinear optimization. J. Oper. Res. Soc. 2016. 67 (5). P. 786–800. doi.org/10.1057/jors.2015.94

       18.     Wächter A., Biegler L.T. On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming. Mathematical Programming. 2006. 106 (1). P. 25–57. doi.org/10.1007/s10107-004-0559-y

 

 

ISSN 2707-451X (Online)

ISSN 2707-4501 (Print)

Previous  |  Full text (in Ukrainian)  |  Next