| Author(s) | Collection number | Pages | Download abstract | Download full text |
|---|---|---|---|---|
| Sabat V. I., Богоніс О. О. | № 1 (70) | 21-34 |
|
|
This paper addresses the problem of optimal placement of vector graphic objects on a two-dimensional plane, a task with practical relevance in fields such as printing and material processing. The primary objective is to minimize the occupied area while preventing overlaps between objects and allowing their rotation. Due to the high computational cost of traditional geometric intersection checks, we propose an enhanced genetic algorithm that integrates evolutionary optimization with two key modifications: discretization and clustering. Discretization is achieved by converting vector shapes into binary pixel matrices using a configurable grid size, which significantly accelerates intersection testing. Clustering is applied to sort objects by size prior to placement, thereby improving packing density and layout structure.
The algorithm incorporates standard genetic operators such as selection, crossover, mutation, and structured population generation based on a mix of elite, random, and recombined chromosomes. To evaluate the effectiveness of the proposed approach, an experiment was conducted that varied the discretization cell size under fixed conditions. The results demonstrate a clear trade-off between accuracy and performance: smaller cell sizes yield better placement quality but increase computation time. Optimal parameter ranges were identified to provide a practical balance between precision and execution speed.
The implemented approach takes into account geometric constraints, allows you to adapt the order, position and rotation of each figure, and also provides flexible formation of new populations based on combining solutions.
Experimental research has shown that the size of the discretization cell significantly affects the results: with a decrease in the cell, the placement quality increases, but the processing time increases. The best compromise between accuracy and speed under the study conditions were the values 3×3 mm and 5×5 mm. The proposed solution demonstrates high flexibility and scalability, which makes it well suited for applications that require automated placement of complex vector objects on surfaces with constraints.
Keywords: genetic algorithm, vector object placement, discrete approximation, clustering, fitness function, optimization.
doi: 10.32403/1998-6912-2025-1-70-11-20
- 1. Carr, J. (2014). An Introduction to Genetic Algorithms. Whitman College. https://www.academia.edu/39261907/An_Introduction_to_Genetic_Algorithms.
- 2. Hruschka, E. R. & Ebecken, N. F. F. (2003). A genetic algorithm for cluster analysis. Intelligent Data Analysis, 7(1), 15–25.
- 3. Palamarchuk D. Yu., Timchenko O. V., Demchenko V. O. (2024) Application of optimization methods in the problem of placing vector graphic objects on a plane. Scientific Notes No. 1 (68). P. 61-70, doi: 10.32403/1998-6912-2024-1-68-61-70.
- 4. Pichugin M. F., Kankin I. O., Vorotnikov V. V. (2019) Computer Graphics. Textbook. Kyiv. 346 p.
- 5. Cheng, F. Y., & Li, D. (1998). Genetic Algorithm Development for Multiobjective Optimization of Structures. Journal of Structural Engineering, 124(6), 749–757.
- 6. De Jong, K.A.: (1987) On using genetic algorithms to search program spaces. Proceedings of the Second International Conference on Genetic Algorithms, Hillsdale, NJ.
- 7. Lytvyn V. O.(2015) Methods of discrete approximation in computer graphics problems. Scientific Bulletin of KNU Informatics and Computing Technology, No. 3, pp. 45–52.
- 8. Palamarchuk D. Yu., Tymchenko O. V. (2025) Discrete approximation in problems of placing vector graphic objects on a plane // Computer Design Systems. Theory and Practice. Issue 7, Number 1,. P.221-228. doi: https://doi.org/10.23939/cds2025.01.221.