ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 3. Vol. 29. 2023

DOI: 10.17587/it.29.143-148

V. N. Markov, Dr. of Tech. Sc., Professor,
Kuban State Technological University, Krasnodar, 350000, Russian Federation

Umbrella Trees for Nesting Problem

The problem of irregular-shaped pieces representation in order to minimize the nesting time is considered. A representation in the form of umbrella tree with a square crown consisting of tricolor nodes and bicolor leaves equidistant from the root is proposed. The construction of an umbrella tree from a image based on the transformation of Cartesian pixel coordinates into reference coordinates of tree leaves is shown. The translation and rotation of pieces functions on umbrella trees with quadratic estimates of computational complexity are determined. Examples of rounding coordinates heuristics and the experimental values of the threshold recoloring leaves during rotating a piece are given. The quadratic problem of intersection localization of the slab contents and the piece is reduced to the evaluating of color mutual exclusivity predicate of the pairs of nodes of the slab tree and the piece tree with linearrhythmic estimation of time in the applied cases. A pair of nodes is mutually exclusive if at least one of the nodes is white, and it isn't mutually exclusive if both are black. In other cases a pair of nodes is considered mutually exclusive if all four pairs of child nodes are mutually exclusive.
The price of reducing the computational complexity of intersection localization is an increase of the required memory size by 33 % compared to the raster representation. Umbrella trees make it possible to use photo and video frames of pieces and slabs without converting them into a vector representation.
Keywords: nesting; irregular-shaped pieces; tree representation, estimate of computational complexity

P. 143–148

References

1. Makhonina Yu. V., Neymark E. A. Cutting-packing problem solution using a combined evolutionary-genetic algorithm, Trudy NGTU im. R. Å. Alekseeva, 2021, no. 2, pp. 24—31 (in Russian).
2. Chekanin V. A. Multimethod genetic algorithm for solving the rectangular cutting and orthogonal packing problems, Vestnik MGTU "STANKIN", 2019, no. 4 (51), pp. 14—18 (in Russian).
3. Rogers D. F., Adams J. A. Mathematical elements for computer graphics, 2nd ed., NY USA, McGraw-Hill, 1989, 611 p.
4.   Rocha P. Geometrical models and algorithms for irregular shapes placement problems, PhD thesis, INESC, University of Porto, Portugal, 2014, 184 pp.
5.   Xu Y., Yang G., Pan C. An Approach Based on Evaluation Particle Swarm Optimization Algorithm for 2D Irregular Cutting Stock Problem, International Conference in Swarm Intelligence. Lecture Notes in Computer Science, 2013, vol. 7928, pp. 168—175.
6.   Guo B., Peng Q., Cheng X., Dai N. Free-Form Contour Packing Based on Material Grid Approximation and Lowest-Gravity-Center Methods, Expert Systems with Applications, 2015, vol. 42, no. 4, pp. 1864—1871.
7. Babu A. R., Babu N. R. A Generic Approach for Nesting of 2-D Parts in 2-D Sheets Using Genetic and Heuristic Algorithms, Computer-Aided Design, 2001, vol. 33, no. 12, pp. 879—891.
8. Bennell J. A., Oliveira J. F. The Geometry of Nesting Problems: A Tutorial, European Journal of Operational Research, 2008,  vol. 184, no. 2, pp. 397—415.
9. Bennell J. A., Oliveira J. F. A Tutorial in Irregular Shape Packing Problems, The Journal of the Operational Research Society, 2009, vol. 60, suppl. 1, pp. s93—s105.
10. . Boehm W., M ller A. On de Casteljau's Algorithm, Computer Aided Geometric Design, 1999, vol. 16, no. 7, pp. 587—605.   
11. Lur'e A. I. Analytical mechanics, Moscow, Fizmatlit, 1961, 824 p. (in Russian).

To the contents