| Author(s) | Collection number | Pages | Download abstract | Download full text |
|---|---|---|---|---|
| Tymchenko O. V., Palamarchuk D. Y. | № 2 (90) | 46-54 |
|
|
У статті розглянуто підхід до покращення ефективності розміщення векторних графічних об’єктів на площині шляхом кластеризації фігур за розмірними характеристиками. Існуючі алгоритми розміщення зазвичай розглядають фігури як послідовність, що обробляється у певному порядку, не враховуючи групування за характеристиками. У контексті еволюційних методів, таких як генетичні алгоритми, відсутність структуризації об’єктів обмежує ефективність мутацій і кросоверів, що впливає на швидкість і якість збіжності до оптимального рішення. Кластеризація фігур дозволяє розглядати більш узгоджені підмножини елементів та підвищує ефективність як жорстких алгоритмів розміщення, так і еволюційних підходів до оптимізації. Вибраними елементами кластеризації у даній роботі є площа обмежувального прямокутника фігури, метрика відстані або подібності, яка визначає, наскільки об’єкти близькі між собою (у нашому випадку – різниця площ фігур); порогове значення що визначає межі належності до одного кластера та алгоритм об’єднання об’єктів у підмножини.
Запропонований метод кластеризації дозволяє групувати фігури у підмножини зі схожою площею обмежувального прямокутника, що забезпечує щільніше компонування та зменшує фрагментацію вільного простору. Описано алгоритм кластеризації з використанням порогового значення, залежного від мінімальної та максимальної площ об’єктів, а також подано блок-схему його реалізації. Результати експериментів свідчать про переваги кластерного підходу у порівнянні з традиційним розміщенням без попередньої обробки: підвищується ефективність заповнення площини та зростає ймовірність повного розміщення об›єктів в межах одного носія. Крім того, метод добре інтегрується у структуру генетичного алгоритму, підвищуючи варіативність мутацій і якість комбінування рішень. Запропонований підхід має перспективу для використання в задачах оптимального розміщення у сферах поліграфії, розкрою матеріалів та цифрового виробництва.
Ключові слова: кластеризація, розміщення графічних об’єктів, векторна графіка, оптимізація, генетичний алгоритм, площина, компонування, евристика.
doi: 10.32403/0554-4866-2025-2-90-46-54
- 1. Palamarchuk D. Yu., Tymchenko O. V., Demchenko V. O. Application of Optimization Methods in the Problem of Placing Vector Graphic Objects on a Plane. Scientific Notes of the Ukrainian Academy of Printing, issue 1 (68), pp. 68–75.
- 2. Palamarchuk D. Yu., Tymchenko O. V., Demchenko V. O. Methods of Optimization for Placing Vector Graphic Objects on a Plane. Polygraphy and Publishing Business, 2023, 2(86), pp. 40–48. https://doi.org/10.32403/0554-4866-2023-2-86-40-48.
- 3. Palamarchuk D. Yu., Tymchenko O. V., Demchenko V. O. Application of Optimization Methods in the Problem of Placing Vector Graphic Objects on a Plane. Scientific Notes, No 1 (68), 2024, pp. 61–70. https://doi.org/10.32403/1998-6912-2024-1-68-61-70.
- 4. Havrysh B., Palamarchuk D., Tymchenko O., Kovalskyi B. & Khamula O. Efficiency of Optimization Algorithms in the Problem of Graphic Objects Placement. AdvAIT2024: 1st International Workshop on Advanced Applied Information Technologies, December 5,2024, Khmelnytskyi, Ukraine – Žilina, Slovakia, pp. 46–54. Vol3899. URN: nbn:de:00743899X.
- 5. Oliinyk S. V. & Boiko B. M. Comparison of Clustering Methods for Creating Target Customer Groups in a Dataset. Scientific Bulletin of NLTU Ukraine, 2023, vol.33, no5, pp.77–83.
- 6. Luxburg, U. A Tutorial on Spectral Clustering. Statistics and Computing, 17(4), 2007. https://doi.org/10.48550/arXiv.0711.0189.
- 7. Ikotun, A. M., & Kingravi, H. A. Kmeans Clustering Algorithms: A Comprehensive Review, Variant Analysis, and Advances in the Era of Big Data. Information Sciences, volume 622, 2023, pp.178–210.
- 8. Tykhonov E. S., & Tykhonova K. V. Analysis of Existing Data Clustering Algorithms: Advantages and Disadvantages. Communication, 1(143), 2020, pp.17–20. ISSN24129070.
