Одержано 09.06.2021; Виправлено 19.06.2021; Прийнято 24.06.2021

Надруковано 30.06.2021; Вперше Online 01.07.2021

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

Попередня  |  Повний текст  |  Наступна

 

УДК 519.85

Опукла багатокутна оболонка для пари нерегулярних об'єктів

В.М. Дубинський ¹,   О.В. Панкратов ¹ ,   Т.Є. Романова ^{1 *} ,   Б.С. Лисенко ²,   Р.В. Каяфюк ²,   О.О. Жмуд ³

¹ Інститут проблем машинобудування ім. А.М. Підгорного НАН України, Харків

² Харківський національний університет радіоелектроніки, Україна

³ Інститут кібернетики імені В.М. Глушкова НАН України, Київ

^* Листування: Ця електронна адреса захищена від спам-ботів. Вам потрібно увімкнути JavaScript, щоб побачити її.

 

Вступ. Задачі оптимального розміщення належать до класу NP-складних проблем оптимізації. З огляду на це, у більшості випадків, пов’язаних із проблемами розкрою та пакування, застосовують евристичні підходи. Розробка аналітичних методів математичного моделювання є актуальною проблемою для розширення класу задач розміщення, що можливо розв’язати оптимально за допомогою сучасних NLP-solvers.

Розглянуто задачу розміщення двох нерегулярних двомірних об’єктів в опуклій багатокутної області мінімального розміру, що являє собою опуклу багатокутну оболонку мінімальної площі або периметру. Дозволяються неперервні повороти та трансляції об’єктів за умови їх неперетину.

Для розв’язання задач оптимальної кластеризації пари об’єктів у статті запропоновано два алгоритми. Перший полягає у послідовному пошуку локальних екстремумів на усіх допустимих підобластях із застосування дерева рішень.  Другий алгоритм здійснює пошук локально-оптимального екстремуму на одній підобласті з використанням «хорошої» стартової точки.

Мета роботи. Показати як будувати мінімальну опуклу багатокутну оболонку для двох неперервно рухомих нерегулярних об’єктів, обмежених дугами кіл та відрізками прямих.

Результати. Побудовано математичну модель у вигляді задачі нелінійного програмування  із застосуванням методу phi-функцій. Запропоновано два алгоритми розв’язання задачі розміщення пари об'єктів з метою мінімізації площі та периметра охоплюючий їх багатокутної області. Наведено результати обчислювальних експериментів.

Висновки. Побудова мінімальної опуклої багатокутної оболонки для пари двовимірних об’єктів, що мають довільну просторову форму та дозволяють перетворення неперервних обертань та трансляцій, дозволяє прискорити процес пошуку допустимих розв’язків задачі розміщення великої кількості об’єктів складної геометрії.

 

Ключові слова: опукла багатокутна оболонка, нерегулярні об’єкті, метод phi-функцій, нелінійна оптимізація.

 

Цитувати так: Дубинський В.М., Панкратов О.В., Романова Т.Є., Лисенко Б.С., Каяфюк Р.В., Жмуд О.О. Опукла багатокутна оболонка для пари нерегулярних об'єктів. Cybernetics and Computer Technologies. 2021. 2. С. 13–24. https://doi.org/10.34229/2707-451X.21.2.2

 

Список літератури

           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. ISBN 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. https://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. https://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)

Попередня  |  Повний текст  |  Наступна