寻找多边形的最内层路径
Finding the inner-most path of a polygon
给定一个顶点的无向图，我需要找到连接两个特定点的最里面的路径。我最初的想法是只使用类似 Dijkstra 算法的东西来找到最短路径，但是有很多情况下最短路径不是最里面的。这是我想要实现的目标的视觉效果：
最终，我尝试根据程序中绘制的墙壁生成“房间”。所以在这个图像中，虚线是我正在绘制的最后一条边，然后应该找到从顶点 1 到顶点 7 的边路径（遮挡虚线边），这将给我路径 1-2-3-4- 5-6-7。如果按照我现在的方案，最短路径应该是1-2-8-6-7，但是显然，这不是最里面的路径。
我已尝试对此进行广泛研究，但似乎找不到答案。我还尝试在每个节点处选择最小的边缘角度进行遍历，但这只适用于沿一个方向行进，因为我目前没有确定它是顺时针还是逆时针遍历节点的方法。可能值得注意的是，我在 Lua 中尝试这样做，但伪代码或类似的高级语言也将受到赞赏！
如果我能澄清任何问题，请告诉我。
基本上你想要的是枚举入射到平面直线图的一个面上的边。
首先你需要一个嵌入：对于每个节点，按逆时针顺序对进入它的边进行排序，例如，5→6、8→6、12→6、7→6。 （如果你喜欢使用余弦定律，你可以避免三角。）然后将后继存储在一个大地图中：（5→6）：（8→6），（8→6）：（12→6），（12 →6): (7→6), (7→6): (5→6), (1→7): (6→7), 等等
其次，要找到有向边右边的面，按逆时针顺序重复找到下一个有向边并反转它，直到回到起始边。例如，1→7、6→7、7→6、5→6、6→5、4→5、5→4、3→4、4→3、2→3、3→2、1→2 , 2→1, 7→1, 1→7.
现在，这里有点复杂，如果您从 7→1 开始，您将围绕无限面循环：7→1、10→1、1→10、9→10 等. 处理这个问题的方法是计算面部的签名区域。如果它是负的，那么我们很好，因为我们按顺时针顺序枚举有限面。如果是正数，那么我们需要另一个面，因为我们是按照逆时针的顺序来枚举无限面的。
如果两个事件面都是有限的，你必须告诉我你想要什么。
给定一个顶点的无向图，我需要找到连接两个特定点的最里面的路径。我最初的想法是只使用类似 Dijkstra 算法的东西来找到最短路径，但是有很多情况下最短路径不是最里面的。这是我想要实现的目标的视觉效果：
最终，我尝试根据程序中绘制的墙壁生成“房间”。所以在这个图像中，虚线是我正在绘制的最后一条边，然后应该找到从顶点 1 到顶点 7 的边路径（遮挡虚线边），这将给我路径 1-2-3-4- 5-6-7。如果按照我现在的方案，最短路径应该是1-2-8-6-7，但是显然，这不是最里面的路径。
我已尝试对此进行广泛研究，但似乎找不到答案。我还尝试在每个节点处选择最小的边缘角度进行遍历，但这只适用于沿一个方向行进，因为我目前没有确定它是顺时针还是逆时针遍历节点的方法。可能值得注意的是，我在 Lua 中尝试这样做，但伪代码或类似的高级语言也将受到赞赏！
如果我能澄清任何问题，请告诉我。
基本上你想要的是枚举入射到平面直线图的一个面上的边。
首先你需要一个嵌入：对于每个节点，按逆时针顺序对进入它的边进行排序，例如，5→6、8→6、12→6、7→6。 （如果你喜欢使用余弦定律，你可以避免三角。）然后将后继存储在一个大地图中：（5→6）：（8→6），（8→6）：（12→6），（12 →6): (7→6), (7→6): (5→6), (1→7): (6→7), 等等
其次，要找到有向边右边的面，按逆时针顺序重复找到下一个有向边并反转它，直到回到起始边。例如，1→7、6→7、7→6、5→6、6→5、4→5、5→4、3→4、4→3、2→3、3→2、1→2 , 2→1, 7→1, 1→7.
现在，这里有点复杂，如果您从 7→1 开始，您将围绕无限面循环：7→1、10→1、1→10、9→10 等. 处理这个问题的方法是计算面部的签名区域。如果它是负的，那么我们很好，因为我们按顺时针顺序枚举有限面。如果是正数，那么我们需要另一个面，因为我们是按照逆时针的顺序来枚举无限面的。
如果两个事件面都是有限的，你必须告诉我你想要什么。