Minimizing pens in a plotter or similar device

Question

I am looking for links to algorithms for building on a mechanical mail plotter.

In particular, I have a list of direct vectors, each of which represents a string to be constructed. First I want to remove duplicate vectors, so each line is displayed only once. It is easy enough.

Secondly, there are many vectors that intersect, sometimes at endpoints, but not always. They can be built in any order, but I want to find an order that reduces the number of times the pen needs to be raised, preferably to a minimum, although I understand that it can take a long time to calculate, if it calculates at all. Vectors that intersect can be broken down into smaller vectors if that helps. But in general, if the pen moves in a straight line, it is best to keep it that way for as long as possible. Thus, two parallel vectors connected to each other can be combined into one vector, etc.

This sounds like some sort of graph theory problem, but I know little about it. Can someone point me to links or algorithms that I need to learn? Or maybe an example code?

Thanks,

Neil

Answer 1

The problem is an example of the problem of the Chinese postman , which is an NP-complete problem. The most famous NP-complete issue is Traveling Salesman . Common to all NP-complete problems is that they can all be translated into each other. Known algorithms for solving any of them in a time that depends on the number of nodes in the input are not polynomial (NP).

In your case, I would suggest some simple heuristics. Do not overdo it, just select something very simple, as far as possible, in a straight line, and then raise the handle to the nearest accessible starting point and go from there.