6

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.

Example

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.

Close Call
  • 653
  • 1
  • 6
  • 18
  • 5
    I guess you're looking for [shortest homotopic paths](https://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/shortest-homotopic-paths.pdf)? Hard to tell if the pulling analogy directly translates this way. – David Eisenstat Sep 28 '20 at 13:19
  • @DavidEisenstat This looks very promising! One assumption is an input polygon P, which we not have yet. I will try out Delaunay triangulation on my example to generate one. – Close Call Sep 28 '20 at 14:10
  • @DavidEisenstat I wish I could mark your comment as the answer. I added my Delaunay example below. – Close Call Sep 28 '20 at 16:03
  • 1
    You took the time to make it not just a name and a link, feel free to take the credit. – David Eisenstat Sep 28 '20 at 19:18

1 Answers1

2

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.

Polygon P and the path crossing triangles.

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.

Close Call
  • 653
  • 1
  • 6
  • 18