用绳子连接板上钉子的算法
Algorithm for connecting nails on a board with a string
我想知道这个问题是否存在现有算法，或者是否可以映射到现有算法。
问题
你是二维的，想在木板上用钉子做一些弦乐艺术。为此，您从布景中的某个钉子开始，所有这些钉子都被不规则地放置在棋盘上。然后，您围绕钉板以不连续的步骤线性移动，直到到达末端钉子。现在，您拉紧绳子并想知道绳子的路径以及绳子接触到的钉子。
输出：拉紧的绳子及其钉子的路径。
示例：
橙色路径是您绕过棋盘的路线。绿线是最后收紧的弦。请注意，由于采用的路径，直接连接（例如从钉子 X 开始）是非法的。
另一个类比：你在树林里的一棵树上系一根绳子。然后你以线性的方式绕着树木飞奔。你停在某棵树上，用力拉绳子，所以它被拉紧了。
这个问题似乎是最短路径问题，但是有一个额外的限制，即只能使用一些nodes/nails。
David Eisenstat 提出的潜在解决方案：
多边形中的最短（同伦）路径（参见https://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/shortest-homotopic-paths.pdf）
在这里，我们将算法应用于原始示例。
第 1 步：交叉序列
使用 Delaunay 三角剖分我们可以从输入的指甲中得到多边形 P。然后，我们命名所有的三角形交叉口（见图）并写下路径的顺序。
结果：ABCBDEFGHIJKLMNOPPQRSTU
第 2 步：减少
删除不必要的循环：
ABCCBDEFGHIJKLMNOPPQRSTU
--> ABBDEFGHIJKLMNOQRSTU
--> ADEFGHIJKLMNOQRSTU
第 3 步：袖子
袖子只是按顺序“粘合”在一起的递减交叉序列中的所有三角形。
第 4 步：渠道
您基本上是从头开始查看漏斗的每条对角线，然后迭代确定到达某个点的最短路径，直到到达终点。
附加说明：本文建议不要明确按顺序使用这些步骤，因为您可以一次完成。此外，该算法可以通过一些修改来处理循环。
我想知道这个问题是否存在现有算法，或者是否可以映射到现有算法。
问题
你是二维的，想在木板上用钉子做一些弦乐艺术。为此，您从布景中的某个钉子开始，所有这些钉子都被不规则地放置在棋盘上。然后，您围绕钉板以不连续的步骤线性移动，直到到达末端钉子。现在，您拉紧绳子并想知道绳子的路径以及绳子接触到的钉子。
输出：拉紧的绳子及其钉子的路径。
示例： 橙色路径是您绕过棋盘的路线。绿线是最后收紧的弦。请注意，由于采用的路径，直接连接（例如从钉子 X 开始）是非法的。
另一个类比：你在树林里的一棵树上系一根绳子。然后你以线性的方式绕着树木飞奔。你停在某棵树上，用力拉绳子，所以它被拉紧了。
这个问题似乎是最短路径问题，但是有一个额外的限制，即只能使用一些nodes/nails。
David Eisenstat 提出的潜在解决方案：
多边形中的最短（同伦）路径（参见https://jeffe.cs.illinois.edu/teaching/comptop/2009/notes/shortest-homotopic-paths.pdf）
在这里，我们将算法应用于原始示例。
第 1 步：交叉序列
使用 Delaunay 三角剖分我们可以从输入的指甲中得到多边形 P。然后，我们命名所有的三角形交叉口（见图）并写下路径的顺序。
结果：ABCBDEFGHIJKLMNOPPQRSTU
第 2 步：减少
删除不必要的循环：
ABCCBDEFGHIJKLMNOPPQRSTU
--> ABBDEFGHIJKLMNOQRSTU
--> ADEFGHIJKLMNOQRSTU
第 3 步：袖子
袖子只是按顺序“粘合”在一起的递减交叉序列中的所有三角形。
第 4 步：渠道
您基本上是从头开始查看漏斗的每条对角线，然后迭代确定到达某个点的最短路径，直到到达终点。
附加说明：本文建议不要明确按顺序使用这些步骤，因为您可以一次完成。此外，该算法可以通过一些修改来处理循环。