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

Question

我们有一个多边形，以从最底部(点)开始逆时针方向的顶点列表的形式给出。给出同一多边形的一些对角线(它们都不相交)，作为一组点(对角线)。

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

示例:

输出将包括以下面孔:

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. 直到处理完所有对角线。