Mathematical models and routing algorithms for CAD technological preparation of cutting processes

Resource-conscious technologies for cutting sheet material include the ICP and ECP technologies that allow for aligning fragments of the contours of cutouts. In this work, we show the mathematical model for the problem of cutting out parts with these technologies and algorithms for finding cutting tool routes that satisfy technological constraints. We give a solution for the problem of representing a cutting plan as a plane graph $G=(V,F,E)$, which is a homeomorphic image of the cutting plan. This has let us formalize technological constraints on the trajectory of cutting the parts according to the cutting plan and propose a series of algorithms for constructing a route in the graph $G=(V,F,E)$, which is an image of an admissible trajectory. Using known coordinates of the preimages of vertices of graph $G=(V,F,E)$ and the locations of fragments of the cutting plan that are preimages of edges of graph $G=(V,F,E)$, the resulting route in the graph $G=(V,E)$ can be interpreted as the cutting tool's trajectory.
The proposed algorithms for finding routes in a connected graph $G$ have polynomial computational complexity. To find the optimal route in an unconnected graph $G$, we need to solve, for every dividing face $f$ of graph $G$, a travelling salesman problem on the set of faces incident to $f$.