查找所有给定几条对角线的多边形

Question

我们有一个多边形，从最底部开始以逆时针方向从顶点列表给出（points）。给出了相同多边形的一些对角线（它们中没有一个相交），作为一组点（diagonals）。

我们必须找到多边形切入的所有面（作为每个面的顶点列表）。

实施例：

输出将包括以下的面：

face1 = [(-68,-36), (-53,-40), (-39,44)] 
face2 = [(-53,-40), (-21,37), (-12, 6), (-5,49)] 
... 

正如你可能已经注意到，对角线切割多边形成monotone polygons相对于x轴。如果这可能有帮助。

我已经在这个问题上好几个小时了。我似乎无法找到与之相关的任何问题。任何帮助将不胜感激，谢谢。

编辑：问题可以简化为查找图中的所有简单循环（即无弦循环）。我发现这些类似的问题：

Finding polygons within an undirected Graph

Find all chordless cycles in an undirected graph

然而，在第二个接受的解决方案似乎并没有工作。

Answer 1

1. 从整个多边形开始。

2. 取第一个对角线并将多边形分成两部分。一个将有点直到对角线的第一个点，然后是包括对角线的第二个点之后的所有点。另一个将具有对角线的第一点，并且所有点都达到（包括）对角线的第二点。

3. 拍摄下斜，决定哪些多边形将得到分（它只能是一个，因为对角线不交叉），并把它在第2步

4. 重复3等中记载，直到所有的对角线被处理。