1
$\begingroup$

I have a rectangular area filled with vector paths (an SVG document, to be precise). Starting at the origin, I need to visit every part of every path.

For an open path, like a line or an arc, I would most often walk to one end of the path, walk the length of the path, then walk to another path.

For a closed path, like a circle or a square, I would most often walk to a point on the path near my previous stop, walk the perimeter of the path, then walk to another path.

I say "most often" above because it would also be valid to visit a path, not necessarily at an endpoint, walk along part of it, then leave to another path, later coming back to finish the abandoned walk.

The purpose of this problem is to minimize total travel distance for a laser cutter or CNC mill that needs to cut along all the paths.

Are there any existing algorithms (or open source tools) for solving this problem?

EDIT: Two paths never cross. Anywhere that might happen will have been altered from 4 vertices and 2 paths to 5 vertices and 4 paths by a previous step in my workflow.

EDIT2: The set of paths is disjoint. Some steps in the solution will be between pieces of disconnected paths.

|cite|improve this question
$\endgroup$
  • $\begingroup$ I'm fairly sure it only makes sense to walk from one path to another at the points where their separation is (locally) minimal. If that's true, then there are only finitely many valid transitions, and you can reduce this to the usual discrete TSP on a graph. $\endgroup$ – Rahul Mar 8 '17 at 21:46
  • $\begingroup$ @Rahul that seems like a plausible proposition, but I don't see how to reduce it to the usual TSP on a graph because some of the steps are forced (from one end to the other for a given pair of transitions). $\endgroup$ – Sparr Mar 8 '17 at 22:05
  • $\begingroup$ I see what you mean. Maybe it should be modeled as a variation of TSP where some edges are required to be traversed. I wonder if this is a standard variation of the problem. $\endgroup$ – Rahul Mar 9 '17 at 2:53
  • $\begingroup$ You would also need to allow some vertices to be visited twice. Two major changes to the standard TSP, which makes finding an existing variation unlikely :( $\endgroup$ – Sparr Mar 9 '17 at 6:11
0
$\begingroup$

As far as I see, taking all crosspoints as vertices and all parts of pathes as edges we come to the Chinese postman problem. Unlike the Travelling salesman problem the Chinese postman problem is polynomially solvable. You can find $O(n^3)$ solution here.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ I don't see how this can work. The problem is equivalent to TSP in the limit where the paths are short, because visiting a short path is pretty much equivalent to visiting a point. The challenge then becomes to minimise the total travel distance since the distance on the paths that have to be cut out is negligible, i.e. it's a TSP. $\endgroup$ – Jules Mar 9 '17 at 10:08
  • $\begingroup$ You can assume the paths don't cross. Any intersections will have been reduced to four edges with a vertex at the intersection by a previous step in my process. $\endgroup$ – Sparr Mar 9 '17 at 18:29
  • $\begingroup$ All right, I see. I thought that your picture is connected, while now I understand it is completely disconnected. Anyway it is more like CPP for graph (on $n(n - 1)$ vertices if you have $n$ pathes) with selected edges to travel then TSP. $\endgroup$ – Smylic Mar 9 '17 at 20:32
  • 1
    $\begingroup$ Such problem is called Rural postman problem, it is NP-hard. Also I need to work further on my reduction and if I finish I'll edit my answer. $\endgroup$ – Smylic Mar 9 '17 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.