計算幾何（多邊形）

Question

如果我們給出了一組S段，我們可以設計一個算法來測試集合S中的段是否可以形成一個多邊形，如果它們與多邊形相交，我不感興趣，我只是想知道關於我可以測試什麼標準，

任何建議

Answer 1

構造一個圖形數據結構，其中節點表示在集合S連接段A和鏈段B與如果A和B相交的邊緣區段。遍歷圖來確定是否有任何循環。每個週期對應一個候選多邊形。

Answer 2

爲了記錄，這裏是一個可能更直接的解決方案（第一個答案是構造雙圖可能不太明顯）。

構造一個圖形，其中來自給定線段的每個（不同的）端點都是一個頂點，並且每個給定的線段都是一條邊線。對此圖進行深度優先搜索遍歷以查找循環。這些週期是候選多邊形。