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.

$\endgroup$
4
  • $\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$
    – user856
    Mar 8, 2017 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, 2017 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$
    – user856
    Mar 9, 2017 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, 2017 at 6:11

1 Answer 1

Reset to default
-1
$\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.

$\endgroup$
5
  • 2
    $\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, 2017 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, 2017 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, 2017 at 20:32
  • 2
    $\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, 2017 at 20:55
  • $\begingroup$ In the CPP every valid edge must be traversed at least once. In this problem there are many valid paths which will not be traversed in an optimal solutions. $\endgroup$
    – Erick Wong
    Jan 15, 2020 at 0:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .