algorithm - 找到给定几条对角线的所有多边形面

Question

我们有一个多边形，以逆时针方向从最底部(点)开始的顶点列表给出。给出了相同多边形的一些对角线(它们都不相交)，作为一组点对(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. 直到处理完所有对角线。