查找所有給定幾條對角線的多邊形

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等中記載，直到所有的對角線被處理。