用字符串连接板上钉子的算法

Question

我想知道是否存在这个问题的现有算法，或者它是否可以映射到现有的算法。

问题

你是在2D和想做一些字符串艺术使用钉子在木板上。为此，你从固定的钉子开始，所有的钉子都不规则地放在板子上。然后，你在指甲板周围线性地移动，直到你到达钉子的末端。现在，您要收紧字符串，并希望知道字符串的路径以及字符串所接触到的钉子。

Output：紧固字符串及其钉子的路径。

示例：橙色的路径是你绕着板走的线。绿线是最后一根紧固的绳子。请注意，与钉子X开头这样的直接连接是非法的，因为使用了路径。

​

​

另一种类推:你在树林里固定一根绳子。然后你绕着树木一条条地跑过去。你在一棵树前停下来，用力拉绳子，所以绳子被勒紧了。

这个问题似乎是一个最短路径问题，但有一个额外的约束，即只能使用一些节点/钉子。

Answer 1

David Eisenstat提出的潜在解决方案：

多边形最短(同伦)路径(参见https://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/shortest-homotopic-paths.pdf)

这里，我们将该算法应用于原始示例。

步骤1:交叉序列

利用Delaunay三角剖分，我们可以从输入钉子中得到多边形P。然后，我们命名所有的三角形交叉(见图)，并写下路径的顺序。

​

​

结果：ABCBDEFGHIJKLMNOPPQRSTU

步骤2:裁减

移除未完成的循环：

ABCCBDEFGHIJKLMNOPPQRSTU

-> ABBDEFGHIJKLMNOQRSTU

-> ADEFGHIJKLMNOQRSTU

第三步:套筒

套筒只是所有的三角形在减少交叉序列“粘”在一起的顺序。

步骤4:漏斗

基本上，从一开始就查看漏斗的每个对角线，然后迭代地确定到某个点的最短路径，直到到达终点为止。

附加注意事项:本文建议不要按照顺序明确地使用这些步骤，因为您可以一次完成这些步骤。此外，该算法还可以对循环进行一些修改。