1
$\begingroup$

I have a list of unordered line segments, some of whose endpoints lie on the same point. How do I connect these segments efficiently to form a minimal amount of paths?

For example, if I have the following lines $(x_1, y_1, x_2, y_2)$: [[0, 0, 2, 2], [4, 0, 2, 1], [2, 2, 4, 0]] the algorithm should be able to join these three segments into one path $(x, y)$: [[0, 0], [4, 0], [2, 1]].

$\endgroup$
  • $\begingroup$ Can you tell us the context in which you encountered this task? $\endgroup$ – D.W. May 19 at 4:14
  • 1
    $\begingroup$ This is something that could be very handy for a traveling salesman who wants to minimize travel distance! $\endgroup$ – Pål GD May 19 at 7:28
  • $\begingroup$ Yes, that's right. The specific application I need this for is for generating code for a 3D printer. A single connected line is a lot faster to traverse because the third axis (which moves a lot slower) doesn't need to be used (and travel distance in general is reduced) $\endgroup$ – Chrisstar May 19 at 7:56
1
$\begingroup$

You could solve this using any algorithm for the traveling salesman problem. Construct a graph with one vertex per line. Add an edge of cost 0 from line to another if they share an endpoint (these correspond to extending an existing path). Add an edge of cost 1 between each other pair of lines (these correspond to starting a new path). Now find the shortest traveling salesman tour of this graph. That will correspond to a minimal set of paths that cover all of the lines; the number of lines will be equal to the weight of the traveling salesman tour. There are standard algorithms and solvers for the TSP.

| cite | improve this answer | |
$\endgroup$

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.