DISCRETE APPROXIMATION IN THE PROBLEMS OF PLACING VECTOR GRAPHIC OBJECTS ON A PLANE

2025;
: 221-228
https://doi.org/10.23939/cds2025.01.221
Received: February 03, 2025
Revised: February 10, 2025
Accepted: February 18, 2025
1
Lviv Polytechnic National University
2
Lviv Polytechnic National University

This article presents a new approach to finding possible placements of vector objects on a plane using discrete approximation. The proposed method significantly reduces the computational complexity of the problem by converting vector images into a discrete form represented by a pixel grid. This enables faster intersection checks between objects through the analysis of occupied grid elements, thus simplifying the process of modeling graphic placement. The paper describes an intersection-checking algorithm and its implementation in the form of software that allows testing various placement scenarios. An analysis of the accuracy and speed of the new method compared to traditional approaches is provided. The research results, presented in the form of graphs and tables, illustrate the effectiveness of the discrete approximation. Additionally, the modular design of the software simplifies its integration with existing optimization frameworks. Future work will focus on refining the accuracy of discrete representations and further expanding the method's application in parallel and distributed computing environments. The conclusions highlight the high potential of this method for use in optimal graphic placement tasks, particularly in manufacturing, printing, and computer graphics. The proposed approach lays the groundwork for further research into the application of discrete approximation in complex optimization problems.

[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. Issue 1 (68) / 2024. P. 61-70, https://doi.org/ 10.32403/1998-6912-2024-1-68-61-70

[2] Tymchenko O.V., Gavrish B.M. Methods of evolutionary multi-criteria optimization. Scientific notes. Issue 2 (69) / 2024. P. 11-20, https://doi.org/10.32403/1998-6912-2024-2-69-11-20

[3] J. Jiang, "Research and Application of Object Recognition Algorithm in Architectural Engineering Drawing Based on Deep Learning," 2023 Asia-Pacific Conference on Image Processing, Electronics and Computers (IPEC), Dalian, China, 2023, pp. 121-124, https://doi.org/10.1109/IPEC57296.2023.00029.

[4] Pichuhin M. F., Kankin I. O., Vorotnikov V. V. "Computer Graphics." Center for Educational Literature. Kyiv, 2013.

[5] Tolochko O. I., Palis S., Burmelov O. O., Kalugin D. V. "Discrete approximation of continuous dynamic objects in the MATLAB environment." Applied Aspects of Information Technology, 2021, Vol. 4, No. 2, pp. 178–191.

[6] Romanyuk O. N. "Computer Graphics." Study guide. Vinnytsia National Technical University. Vinnytsia, 1999, pp. 39–43.

[7] B. Havrysh, D. Palamarchuk, O. Tymchenko, B. Kovalskyi and O. Khamula. Efficiency of optimization algorithms in the problem of graphic objects placement / AdvAIT-2024: 1st International Workshop on Advanced Applied Information Technologies, December 5, 2024, Khmelnytskyi, Ukraine - Zilina, Slovakia/ p. 46-54. (Vol-3899, urn:nbn:de:0074-3899-X)

[8] Sabelnikov P. Yu. "Approximation of an object's contour in an image using vector operations." Cybernetics and Computer Technologies, 2020, No. 3, pp. 85–89.

[9] Lytvyn V. O. "Methods of discrete approximation in computer graphics tasks." Scientific Bulletin of KNU. Informatics and Computer Technology, 2015, No. 3, pp. 45–52.

[10] Koval I. V. "Algorithmic methods for placing graphic objects on a plane." Collection of Scientific Papers of the National University, 2018, No. 4, pp. 110–118.