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]].

Improve this question
$\endgroup$
3
  • $\begingroup$ Can you tell us the context in which you encountered this task? $\endgroup$
    – D.W. ♦
    Commented May 19, 2020 at 4:14
  • 1
    $\begingroup$ This is something that could be very handy for a traveling salesman who wants to minimize travel distance! $\endgroup$
    – John Kemeny
    Commented May 19, 2020 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
    Commented May 19, 2020 at 7:56

1 Answer 1

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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