Drawing all lines from right to left - fast

Question

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?

Answer 1

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

• Start with an initial order created by the nearest-neighbour heuristics

• Then improve the result by some randomized algorithm like Simulated Annealing or Threshold Accepting, which are both pretty simple to implement.

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!

Answer 2

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.