用绳子连接板上钉子的算法

Question

我想知道是否存在针对此问题的现有算法，或者是否可以将其映射到现有算法。

问题

您在 2D 环境中，想使用木板上的钉子制作一些弦乐艺术。为此，您从集合中的某个钉子开始，所有这些钉子都被不规则地放在板上。然后围绕钉板以离散的步骤线性移动，直到到达末端钉子。现在，您拧紧绳子并想知道绳子的路径以及绳子接触的钉子。

输出：拉紧的绳子及其钉子的路径。

示例：橙色路径是您绕着棋盘走的那条线。绿线是最后收紧的绳子。请注意，由于采用的路径，直接连接（如以钉子 X 开头）是非法的。

另一个类比：你在树林里的一棵树上固定一根绳子。然后你以线性块在树上奔跑。你停在一棵树上，用力拉绳子，所以它被拉紧了。

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

Answer 1

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

多边形中的最短（同伦）路径（请参阅https://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/shortest-homotopic-paths.pdf）

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

第 1 步：交叉序列

使用 Delaunay 三角剖分，我们可以从输入的钉子中获取多边形 P。然后，我们命名所有三角形交叉点（见图）并写下路径的顺序。

结果：ABCBDEFGHIJKLMNOPPQRSTU

第 2 步：减少

删除不必要的循环：

AB CC BDEFGHIJKLMNO PP QRSTU

--> BB DEFGHIJKLMNOQRSTU

--> ADEFGHIJKLMNOQRSTU

第 3 步：袖子

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

第 4 步：漏斗

您基本上从起点开始查看漏斗的每条对角线，并迭代确定到达某一点的最短路径，直到到达终点。

附加说明：本文建议不要按顺序明确使用这些步骤，因为您可以一次性完成它们。此外，该算法可以通过一些修改来处理循环。