Laser cutting is one of the major cutting processes used to manufacture sheet metal products. Lots of researches on tool paths for cutting machines mainly deal with contour by contour cutting. While constructing a path one needs to determine the pierce point and the direction of contour passing. In this case only the length of idle passes may be optimized. To solve this problem generalized travelling salesman problem (GTSP) approach is used. Resource-e cient technologies for cutting sheet materials allow for the contours of cut-o details to be overlapped. It allows reducing the material waste and shortening the length of cuts. Common cuts are also the origin of one more set of precedence constraints. These constraints can be formalized as one general formal restriction called as Ordered Enclosing (OE) for plane graphs that are the homeomorphic images of the cutting plan. In this report we consider the common case of a cutting problem when combination of contours is allowed. We review the polynomial algorithms for all the possible restrictions: (1) part cut o a sheet does not require further cuts (constructing of OE-route); (2) there are no intersections of cuts (constructing of NOE-route); (3) there are some restrictions on placement of pierce points (constructing of PPOE-cover).
Laser cutting is one of the major cutting processes used to manufacture sheet
metal products. A typical production process consists of designing parts, nesting
the parts on metal sheets, and cutting the parts from the sheets [
Lots of researches [
(a) (b) Resource-e cient technologies for cutting sheet materials allow for the contours of cut-o details to be overlapped. It allows reducing the material waste and shortening the length of cuts (see g.1). Nevertheless, some other problems arise.
Besides minimizing the above costs, the tool path problem is subject to
precedence constraints coming from the fact that once a contour is completely cut, it
detaches from the rest of the plate. The detached area can possibly shift
position and hence becomes inaccessible for further cuts [
These precedence constraints come from simple inner-outer contour relations,
that can come from holes in parts, parts nested in holes, and parts nested in
islands [
Common cuts are also the origin of one more set of precedence constraints
[
These two constraints can be formalized as one general formal restriction
called as Ordered Enclosing (OE) formulated in [
One more constraint is absence of intersections between cutter trajectories (touches are allowed). The reason is that after intersecting the trajectory cutter goes through a gap formed what may cause the loss of details quality. To formalize this restriction the de nition of AOE-route is presented (the move continues by a neighbouring contour) and NOE-route (trajectories do not intersect but touches are allowed, and the move is not necessary to continue by a neighbouring contour). Routes belonging to classes AOE and NOE satisfy the condition of ordered enclosing.
Technological constraints may arise because of nesting. In this case some pierce points should be xed. Hence, the recognition problem for opportunity of cutting (a route existence problem) for a given cutting plan arises.
For the tool path problem, elements are de ned by their start and end nodes
and can be cut in both directions. Thus, one does not need any information
on the detail shape to de ne the sequence of detail cutting. This is true if one
does not have to take thermal e ects into account. Therefore, all curves without
self-intersections and contiguities on a plane representing the shape of details
are interpreted as graph edges, and all points of intersection and contiguity are
graph vertices. One needs introduce additional functions to the set of vertices,
faces, and edges of the graph received to analyse the satisfaction of technological
restrictions [
Let us designate some technological de nitions and make an adequate correspondence from graph theory terms.
Cut move (graph edge) be a movement where the laser head is actually cutting. The cutting time can be independent of the chosen tool path.
Air move (additional graph edge) be a movement where the laser head is not cutting. The time required for an air move is considerably less than the time required for the cut move.
Piercing (graph vertex) { every time the laser needs to start cutting in a new section of the sheet some piercing needs to be made. Path (edge-disjoint OE-cover by the ordered set of chains of a graph being the homeomorphic image of a cutting plan) be the instrument trajectory corresponding the shape and nesting of parts on the sheet.
The construction of a path to cut o each component is reduced to the
construction of an ordered Eulerian covering for the given component by
OEchains [
So, contour overlapping allows reductions in the material waste, the length of cutting, and the length of idle paths, due detail border combination.
In this paper the common case of a cutting problem when combination of
contours is allowed [
To solve the stated problem cutting plan should be represented as a plane graph
[
For any J G (part of a cutter trajectory) let the theoretical-set union of
its inner faces be designated as Int(G) (the union of all its components S n J
without outer face). Then Int(G) may be interpreted as a part cut o a sheet.
Let an initial part of a route in graph G be considered as a part of a graph
containing all vertices and edges belonging to this part of a route. This allows
formalizing the claim to a cutter as a condition of absence of initial route part
inner faces of graph G intersection with unpassed graph G edges [
De nition 1. [
De nition 2. [
0 01 10e02:::e0k0 vk00 ;
C1 = v1e11v11e12:::e1k1 vk11 ; : : : ; Cn 1 = vn 1e1n 1v1n 1e2n 1:::eknn 11 vknn 11 ; (1) (2) (3) covering graph G and such that (8m : m < n) ; [m 1 l=0
Int(Cl) \ [n 1 l=m
Cl = ;; be called cover with ordered enclosing (OE-cover).
Constructing of OE-route for graph G solves the stated above tool path
problem. Routes with a minimum number of chains have the major interest
since the transition from one chain to another corresponds to the idle cutter
pass.
De nition 3. [
One needs to de ne the following functions for each edge E 2 E(G) to
represent the image of cutting plan as a plane graph G = (V; E) [
As functions vk(e), fk(e), lk(e), rk(e), k = 1; 2, constructed on graph G = (V; E) edges de ne incident vertices for each edge, incident faces and adjacent edges the following statement holds.
Theorem 1. [
Further we consider that all considered plane graphs are represented by these functions. The space complexity of such a representation is O(jEj log2 jV j). There is no problem to get these functions. In fact, they are de ned on the stage of interpreting the cutting plan in terms of graph G. This is minimal information need to representation of any plane graph up to homeomorphism. Using the known coordinates of graph G = (V; E) vertices images and nesting the fragments of the cutting plan (the images of graph G = (V; E) edges) any route in graph may be interpreted as a tool trajectory.
Let us introduce the following de nition of rank for graph G edges to formalize the technological restrictions on the order of cutting.
De nition 4. [
G = (V; E) then (8e 2 E1) (rank(e) = 1); { let k
Ek(G) = fe 2 E(G) n f[l=0Elgg be a set of rank 1 edges for graph k
Gk V; E n [l=0El then (8e 2 Ek) (rank(e) = k).
The rank of an edge de nes its remoteness from the outer face and de nes
the minimal number of faces to be crossed to get from outer face f0 to this edge.
Algorithms for constructing OE-chains and OE-routes are presented in table 1.
Route type Comp. complexity
Eulerian OE-cycle (alg. Recursive OE) [
De nition 5. [
De nition 7. [
De nition 8. [
De nition 9. [
De nition 10. [
Theorem 2. [
Theorem 3. [
Algorithm AOE-TRAIL [
E(G) :
To de ne the cut-vertices the following properties of 4-regular graphs are used.
Statement 1. A vertex incident to four edges incident to outer face is a cutvertex.
Statement 2. The outer face of partial graph Gk is a union of all faces of rank k in graph G.
De nition 12. [
So, if in advance all the cut-vertices of partial graphs Gk are 'correctly' splitted then as a result we have a graph any partial graph Gk of which has no cutvertices.
The sequence of splitting has no value, as soon as it is the local
operation. The 'correct' splitting means that we move from one arc of a cyclic order
to another and arcs belong to di erent pairs of faces (see g. 2(a)). The
result of splitting is presented in gure 2(b). This procedure may be realized by
Cut-Point-Splitting algorithm [
(a) (b)
From all the above, the e ectiveness of the Cut-Point-Splitting algorithm
used to perform the splitting operation of cut-vertices of all ranks in a plane
connected 4-regular graph follows [
Theorem 4. Algorithm Cut-Point-Splitting needs time O(jV (G)j) to identify and split all the cut-vertices of plane connected 4-regular graph G = (V; E). Theorem 5. Algorithm AOE-TRAIL allow to construct AOE-chain for a plane connected 4-regular graph G by time O(jE(G)j log2jV (G)j). 3.2
Class of NOE-chains and Algorithm for their Constructing Class of AOE-chains describes all the trajectories of the cutting tool by the adjacent contour but does not cover completely all possible routes of the cutting tool with no intersections of cuts. Here the problem of non-intersecting OE-chain (see de nition 14) arises.
De nition 13. [
De nition 14. We say that chain belongs to class NOE-chains if it is OE-chain and non-intersecting chain simultaneously.
De nition 15. Let the transition system corresponding to non-intersecting chain be called a system of non-intersecting transitions.
The proof of the fact of existence of such a starting vertex and nishing edge incident to outer face for a system of transitions corresponding to nonintersecting Eulerian cycle that allow to get the OE-cycle is like the proof of theorem 2 and gives the algorithm of such a chain constructing.
To get a non-intersecting Eulerian OE-chain (or a cycle) for a plane Eulerian graph without xed transitions system (later this chain is called NOE-chain) one may act the following way.
Checked(v) = true; if the vertex is considered; false; otherwise: on the set of graph G vertices.
Let all the vertices be unchecked on the stage Initiate(). Function Non-intersecting(G) (see alg. 1) splits all vertices v 2 V (G), deg(v) 2n, n 3 of graph G to k pseudo-vertices of degree 4 and enters k additional pseudo-edges incident to these pseudo-vertices and forming a cycle. . Look through all the graph edges . Consistently process function of index 1, later - 2 . If vertex is not processed . Process the vertex Algorithm 1 Function Non-intersecting (G) Require: plane Eulerian graph G; Ensure: plane connected 4-regular graph G ; for all (e 2 E(G) ) do k = 1; while (k 2) do if NOT(Checked(vk(e))) then
Handle ( e, vk(e), k); end if k + +; end while end forReturn G ; To realize this trans guration, one needs to look through all the functions vk(e), k = 1; 2 for all the edges and modify the graph encoding. Procedure Handle (e, vk(e), k) (see alg. 2) processes each unchecked vertex of G.
Algorithm 2 Procedure Handle (e,v,k)
Processing of vertex vk(e) means its splitting according to gure 3(a, b).
If degree of checked vertex is equal to 2k then k pseudo-vertices entered by procedure Handle and k pseudo-edges incident to these vertices form a cycle. As a result of processing of all the graph G vertices we get a modi ed graph G which is a plane connected 4-regular graph. Hence, the following theorem holds. Theorem 6. Function Non-Intersecting allows to reduce any plane connected Eulerian graph G to a plane connected 4-regular graph G by time O(jE(G)j log2jV (G)j).
Algorithm AOE-trail may be used for de nition of AOE-chain T . If to delete all pseudo-edges and absorb all splitted vertices to v then we get a nonintersecting chain T for graph G. The obtained chain belongs to OE-class because the procedure of absorbing the vertices does not vanish the sequence of edges in the chain what excludes appearing of a cycle enclosing the unpassed edges. Computing complexity of this reduction algorithm is O(jE(G)j log2jV (G)j). Hence the following theorem holds.
Theorem 7. The computational complexity of constructing a N OE-route for plane graph (V; E) does not exceed O(jE(G)j log2jV (G)j). 4
One of the most common cutting technologies is a plasma cutting technology. Nowadays the most common method for cutting of details using plasma cutting is GTSP-technology (contour by contour cutting). The technology using combination of cuts is not widely used now. Nevertheless it allows save material and reduce the cut length. Plasma cutting technology puts some additional restrictions on the instrument path. One of the major restrictions is necessity of leaving some free space for placement of pierce points. Besides time need for cutting signi cantly a ects on the time of cutting.
The problem of feasibility of cutting with plasma cutting technology for solving the cutting-packing problem arises due to these restrictions. The problem of minimization of pierce points number while constructing the cutter path also arises.
As soon as minimal number of pierce points for a cutting map represented by a plane connected graph is equal to jVoddj=2 in this section we consider only graphs coverable by jVoddj=2 chains, i.e. bridgeless graphs with at least one vertex incident to outer face.
Let us consider the cutting plans in g. 4. We admit that cuts combining technology was used for placement of rectangular parts. So, piercing can be realized from the vertices incident to outer face (in common we may use any face allowing piercing).
Hence, realization of cutting by plasma automata is possible for packing in gure 4(b) and not possible for packing in gure 4(a). We need placement of additional pierce points for cutting the inner rectangles R4 and R5 in g. 4(a). As for cutting plan in gure 4(b) it is possible to place pierce points near the outer contour.
Let us formalize this problem.
Let faces Fin(G) F (G) allow placement of pierce point. Then let us
designate vertices of o degree incident to Fin(G) as Vin(G) V (G). If a route
in graph is OE-route and starting vertex v1 2 Vin(G) then this route may be
a base for constructing the cutting program for plasma cutting machine. This
type of routes be called as P P OE-route [
De nition 16. Let chain C = v1e1v2e2 : : : vk be called P P OE-chain if it is an OE-chain and starting vertex v1 2 Vin(G).
De nition 17. Let P P OE-cover of graph G be the OE-cover of graph G consisting of P P OE-chains.
De nition 18. Minimal cardinality ordered sequence of edge-disjoint P P OEchains in plane graph G is called Eulerian P P OE-cover.
Graphs in gure 4(c) and (d) are the images of cutting maps in gures 4(a) and (b). Vertices Vin are designated by white circles. These vertices allow placement of pierce point nearby. On the other hand placement of pierce points near the black-marked vertices is impossible. Thus, Eulerian P P OEcover exists for graph in gure 4(d). For example, it can consist of the following chains: C1 = v1v3v5v6v9v8v5, C2 = v3v7v8, C3 = v7v11v10v9, C4 = v11v12v10, C5 = v12v4v6, C6 = v4v2v1v2. Such a cover does not exist for graph in gure 4(c).
The problem of de nition the possibility of cutting by plasma instrument may be stated as a problem of checking the existence of Eulerian P P OE-cover for a given graph. According to the mentioned restrictions we may formulate the following necessary condition of P P OE-cover existence.
Statement 3. Let G be a plane graph with 2k odd degree vertices. If there exists Eulerian P P OE-cover then jVin(G)j k.
For example, the graph in gure 5(a) cannot be covered by P P OE-chains. It has eight odd degree vertices and can be covered by minimum four Eulerian chains, and only three of them can start from vertices marked as starting ones for P P OE-chain. As for graph in gure 5(b) there are four vertices that can be starting for P P OE-chain and the same number of nishing vertices. Nevertheless, there is no P P OE-cover for this graph.
Paths realizing P P OE-cover can be represented by a special way ordered set of P P OE-chains with additional idle paths (edges) between the end of the current chain and beginning of the next one. Such transitions form a matching on a bipartite oriented graph D = (Vin [ vout > Vin; E) where Vin is a set of odd degree vertices allowed to be the beginnings of trails (pierce points); Vout is a set of odd degree vertices allowed to be only the ends of constructed chains (leaving points).
Statement 4. It is necessary for existing P P OE-cover to a mixed graph G [ D to have a cycle all additional arcs of which belong to
f(v; u) : v 2 Vout [ Vin; u 2 Ving:
Proof. P P OE-cover is a partial case of OE-cover, hence, it is an oriented cycle consisting of graph G edges and edges of matching M on set of vertices Vodd 2 G (vertices Vin [Vout). As soon as P P OE-cover consists of P P OE-chains then edges of matching M are to be passed in direction Vout [ Vin > Vin, hence, they correspond to arcs in D.
This yields that it is necessary for existing of P P OE-cover the existence of a cycle for mixed graph G [ D in which all additional edges are arcs from Vout [ Vin to Vin, as soon as P P OE-cover has this type of the cycle. Statement now follows.
Statement 5. It is necessary for existence of P P OE-cover of plane connected graph G for cardinality of minimal fVin; Voutg-cut be not more than jVoutj.
Proof. Let there exists P P OE-cover for graph G. Nevertheless, the cardinality of fVin; Voutg-cut is less than jVoutj. As soon as no one of P P OE-chains forming a cover cannot start in u 2 Vout then a cover consists of not less than jVoutj ways from v 2 Vin to u 2 Vout. Then some of these ways may be edge-disjoint what leads to a contradiction with de nition of P P OE-cover. Statement now follows.
The graph in gure 5(b) can be a good example for statement above if we assume that we can begin P P OE-chain only from white vertex. The graph has ten odd degree vertices so we need minimum ve vertices from where Eulerian chain can begin. Five of vertices allow it, but we cannot cover the graph by chains which are began only from these vertices. Not more then three chains, for example, C1 = v5v9v8v10v9, C2 = v3v8v7v6v8, C3 = v4v3v2v6 that can be constructed so that chain begins from white vertex and ends in black one. The minimal cut between black and white vertices has three edges.
Constructing of P P OE-cover for graph G solves the routing problem for a cutter with restrictions on pierce points placement.
The technology of details' edge combination is actual resource-saving cutting technology. However, a few algorithms for its implementation exist. So the question of constructing these algorithms is currently important.
In this article we discussed the technology of details' edge combination from the point of view of cutting tool routing. We raised the question of the possibility of details cutting by plasma cutting machine and presented necessary conditions for it. But the issue of multiple using of one vertex for piercing or nishing a chain and the issue of using even degree vertices for piercing are not considered in this paper and present the aim of further researches.