找到给定几条对角线的所有多边形面
Find all polygon faces given a few diagonals
我们有一个多边形，以逆时针方向从最底部开始的顶点列表形式给出 (points)。给出了相同多边形的一些对角线（none 它们相交），作为一组点对（diagonals）。
我们必须找到多边形被切割成的所有面（作为每个面的顶点列表）。
示例：
输出将包括以下面孔：
face1 = [(-68,-36), (-53,-40), (-39,44)]
face2 = [(-53,-40), (-21,37), (-12, 6), (-5,49)]
...
您可能已经注意到，相对于 x 轴，对角线将多边形切割成 monotone polygons。如果这可能有帮助的话。
我已经解决这个问题好几个小时了。我似乎找不到任何与之相关的问题。如有任何帮助，我们将不胜感激。
编辑: 问题可以简化为找出图中所有的简单循环（即无弦循环）。我发现了这些类似的问题：
Finding polygons within an undirected Graph
Find all chordless cycles in an undirected graph
但是，第二个中接受的解决方案似乎不起作用。
从整个多边形开始。
取第一条对角线并将多边形一分为二。一个人将拥有直到对角线第一个点的点，然后是（包括）对角线第二个点之后的所有点。另一个将具有对角线的第一个点和直到（包括）对角线第二个点的所有点。
取下一条对角线，决定要分割哪个多边形（只能是一个，因为对角线不交叉）并按照步骤 2 中的描述进行分割。
重复 3. 直到处理完所有对角线。
我们有一个多边形，以逆时针方向从最底部开始的顶点列表形式给出 (points)。给出了相同多边形的一些对角线（none 它们相交），作为一组点对（diagonals）。
我们必须找到多边形被切割成的所有面（作为每个面的顶点列表）。
示例：
输出将包括以下面孔：
face1 = [(-68,-36), (-53,-40), (-39,44)]
face2 = [(-53,-40), (-21,37), (-12, 6), (-5,49)]
...
您可能已经注意到，相对于 x 轴，对角线将多边形切割成 monotone polygons。如果这可能有帮助的话。
我已经解决这个问题好几个小时了。我似乎找不到任何与之相关的问题。如有任何帮助，我们将不胜感激。
编辑: 问题可以简化为找出图中所有的简单循环（即无弦循环）。我发现了这些类似的问题：
Finding polygons within an undirected Graph
Find all chordless cycles in an undirected graph
但是，第二个中接受的解决方案似乎不起作用。
从整个多边形开始。
取第一条对角线并将多边形一分为二。一个人将拥有直到对角线第一个点的点，然后是（包括）对角线第二个点之后的所有点。另一个将具有对角线的第一个点和直到（包括）对角线第二个点的所有点。
取下一条对角线，决定要分割哪个多边形（只能是一个，因为对角线不交叉）并按照步骤 2 中的描述进行分割。
重复 3. 直到处理完所有对角线。