# Drawing all lines from right to left - fast

I have several drawings from SVG files which basically contain basic outlines of figures. They are constructed in segments of various shapes (lines, ellipse arcs, Bezier curves ect.) Something like this (maybe not the best example):

I want to create an algorithm that traces (draws over) the countour of all shapes once. This means that it has to jump from one figure to an other (or to the same figure) at various points. Also it should prefer go from right to left. I guess it could be represented by a weighted undirected graph where the edges represent the shapes, but each node is also connected to all other nodes via jump. The jump could then have high weights as well as the nodes to the right. I would then have to create a trail, except that the jumps would have to be visited. I don't know... I not good at graph theory.

I know this is vague, but maybe someone knows of a path (or trail)-finding algorithm where expensive jumps are allowed or something like that. Maybe some network or complexity stuff?

EDIT: Thanks for all the response. It is already very useful. But I see that it wasn't clear at all what I meant and how anyone could answer. So, Let me clarify:

I'm making software for a laser die cutter. It has to cut shapes from an SVG file on a long scrolling sheet of paper beneath. The laser cutter can cut lines and ellipse arcs (not bezier curves :-( ) with simple instructions, as well as making jumps; basically lines with the laser off, but a little faster. It also auto-corrects for the motion of the paper below.

So my first approach is to take each segment from the SVG and translate it to a single instruction for the laser (maybe I'll translate Bezier curves to elliptical arcs, but I can't seem to fin a good approximation that way). The question is then: Which order should I execute the instructions? and derived from that: How fast can I scroll the paper?

• What actual problem are you trying to solve with this algorithm? Commented Feb 5, 2021 at 1:35
• @whatsisname looks like related to CNC planning: en.wikipedia.org/wiki/Numerical_control , printing (plotting), or something having to do with a constrained mechanical environment. Correct me if wrong. Commented Feb 5, 2021 at 1:49
• Is it preferable to complete the drawing of one shape before moving over to a second shape? If so, you should group shapes (strokes) first by connected component, then by nesting (which can also be computed by some implementations of connected component), and finally by minimum spanning tree (to find the shortest gap distances between a cluster of strokes). Note that, for the last step, what you ask for is closely resembling a Travelling salesman problem (if starting shape is A, you can't have both A-to-B and A-to-C; you have to pick one), not a minimum spanning tree problem. Commented Feb 5, 2021 at 1:53

For an outline, let us ignore ellipses and stick to lines.

The laser cutter can cut lines [...] with simple instructions, as well as making jumps

Let me assume you mean "straight line segments" and "polygons made of straight line segments.

So my first approach is to take each segment from the SVG and translate it to a single instruction for the laser

Well, sounds like a rough step into the right direction, but what I would do is probably this:

• Approximate each SVG segment by a polygon which fullfills your expectations of accuracy. You will need the parametric formulas for Bézier curves for this.

• Make sure the line segments of those polygon are not shorter than necessary (you may consider to apply something like the Ramer-Douglas-Peuker algorithm). You may also decide for the opposite, split "long" lines and break them down into smaller ones, for allowing jumps in the middle of some line, if that improves the results.

• Dissemble the polygons into their line segments.

Now your goal is to determine an order for the line segments in which you want the laser cutter to process them, as well as an direction (orientation) for each segment, which minimizes the total processing time.

First, you need to define some cost function which is proportional to the time the laser cutter requires to cut a certain line segment, as well as the cost for a jump from one line end to the next end. If "left-right" movements shall be preferred, make this part of the cost function (probably the cutter is faster in that direction than in the "up-down" direction).

Finding the optimal processing order is probably NP-hard, since the task seems to be very similar to the well-known Traveling Salesman problem. That, however, should not stop you from implementing an approximate algorithm which can find you "good" solutions with "small" total costs. I would suggest to

The former step requires to apply a "small random modication" to the formerly found order. Such an operation can be implemented by picking randomly two points (end points of line segments) in the current cutting order, and invert the cutting path between those two points. That is standard operation for the "Traveling Salesman" problem which might work here as well.

Good Luck!

• Thanks Doc! This is actually very much along the lines I was thinking in. I wasn't sure about the parallel to the traveling salesman, since I can jump and any time, which would be equivalent to edges with relatively high cost which doesn't have to be traversed unlike the actual cut-edges. But I'll look into your suggestions. Commented Feb 5, 2021 at 14:46
• @DrDress: in TSP, one has to visit all places, each one once, and there are paths with costs between the places. Here, one has to visit the "line segments" (not just their end points), so those segments correspond to the places. The "jumps" correspond to the paths in TSP, and we have costs for the "places/lines", for the paths (jumps) and maybe different costs for the line orientation. So it is actually a variant of TSP with a slightly more complex cost function. Commented Feb 5, 2021 at 15:14

SVG shapes are a collection of (mainly bezier) curves. To draw a curve from right to left, you'd need to find all the points where the curve has local maxima on the x-axis, split the curve into two at each of those points, and reverse one of the segments. Further work is required to draw each curve with the same x-velocity.

While this is all possible to do with some calculus and elbow-grease, a much easier solution is to draw all the SVG shapes into a bitmap buffer, then draw that bitmap to the screen from right-to-left.