Algorithm for connecting nails on a board with a string

Question

I want to know whether there exists an existing algorithm for this problem or if it can be mapped to an existing one.

Problem

You are in 2D and want to make some string art using nails on wooden board. For that, you start at a certain nail from the set, all of which are irregularly placed on the board. You then linearly move in discrete steps around the nail board until you reach the end nail. Now, you tighten the string and want to know the path of the string and also which nails the string touches.

Output: Path of the tightened string and its nails.

Example: The orange path is the line that you took around the board. The green line is the final tightened string. Note that direct connections like the start with the nail X are illegal because of the taken path.

An alternative analogy: You fix a rope around a tree in a wood. Then you dash around the trees in linear pieces. You stop at a certain tree and pull really hard at the rope, so it is tightened.

The problem seems a shortest path problem, but with an extra constraint, i.e. only some nodes/nails may be used.

Answer 1

Potential Solution proposed by David Eisenstat:

Shortest (Homotopic) Paths in Polygons (see https://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/shortest-homotopic-paths.pdf)

Here, we are applying the algorithm to the original example.

Step 1 : Crossing Sequences

Using Delaunay triangulation we can get the polygon P from the input nails. Then, we name all the triangle crossings (see image) and write down the sequence of the path.

Result: ABCBDEFGHIJKLMNOPPQRSTU

Step 2 : Reduction

Removing unncessary loops:

ABCCBDEFGHIJKLMNOPPQRSTU

--> ABBDEFGHIJKLMNOQRSTU

--> ADEFGHIJKLMNOQRSTU

Step 3 : Sleeve

The sleeve is just all triangles in the reducing crossing sequence "glued" together in order.

Step 4 : Funnel

You basically look at every diagonal of the funnel from the start and iteratively determine the shortest path up to a certain point until you reach the end point.

Additional notes: The paper advises to not use these steps explicitly in order, because you can do them in one go. Also, the algorithm can work with loops with some modifications.