已知若干端點相交的線段，求圍成的所有互相不重疊的封閉多邊形？

01-05

需求出多邊形組成，不僅僅求多邊形個數。
已知所有線段的端點坐標，線段之間僅可能端點相交或無交點，多邊形存在凹多邊形的情況，求所有互相不重疊的封閉多邊形，需求出所有封閉多邊形的組成線段，並不僅僅求出多邊形個數。求演算法思路。
例：五角星的不重疊多邊形有6個，多邊形1由線段a b c d e構成...
下圖存在3個多邊形

算出所有交點
把線段切碎
重新組織交點+通過交點id定義的一大堆不相交的線段
刪掉所有隻跟一條線段相連的交點，以及那些線段
現在每一條線都被兩個多邊形共享（如果你把最外面的無限大的空間也當成一個多邊形的話），所以每條線段計數初始值==2
隨便挑條線，每次你都在一個交點計算所有相連著的交點與他順時針方向的角度，挑一個最小的，往前前進一步，直到回到最初的那條線段為止
多邊形數量+1，將識別出來的這一條路上面的所有線段計數-1，如果線段計數==0就去掉它
條6，直到所有線段都刪掉為止
得到結果之後-1

構個無向圖然後求環的即可得到所有多邊形。如要保證「最小」，可以選擇事後驗證或者講究一下找環的順序……

這個功能完成了，我說說我的方法：

1、先剔除所有不能組成封閉圖的線段，刪除孤立端點所連接的線段，重複此過程，直到所有線段兩端都連有線段。（存在首位相連的線段鏈（一條或一條以上線段組成）的兩端是連接在不同的兩個封閉圖形上的，這種線段鏈也是應該被移除的。暫時沒想到辦法，在獲取封閉圖形的時候再做了處理）

2、遍歷所有線段，對每條線段都順時針找封閉圖，逆時針找封閉圖，即每條線段都能找出兩個封閉圖。在往下找的過程中，若找到的下一條線段已經存在於當前線路中，這放棄這條線路（此處是對1中的特殊情況進行處理）。對找到的封閉圖放到封閉圖集合中比較，若與已經獲取的封閉圖路徑不同，則加入到集合中，否則放棄該路徑。

3、遍歷完所有線段後，再遍歷獲得的封閉圖集合，判斷封閉圖內部有無端點（第一步剔除掉的端點不考慮），無端點則為正確的封閉圖，有端點則說明與其它封閉圖重合，移除（此處處理的目的是移除掉找出來的最外圍封閉圖）。

演算法有點暴力，複雜度有點高，應該還可以優化。

看上去這是一個計算幾何的問題。先用sweep line演算法從左到右預處理所有線段，運算複雜度O(nlogn)就可以得到所有相交線段的信息（演算法的效率在於不用計算具體的交點），每條線段相交的其他線段按順時針或者逆時針形成一個有序的相交序列。

有這個信息後還是用sweep line演算法從左到右開始處理，比如最左邊的一個線段a，按逆時針/順時針方向依次和線段c,f,g相交，a到c是連通的並且中間沒有其他交點。c線段的相交線也一定有a存在，比如c的相交線序列是w, t, a, y, u，按逆時針如果c和a相交後下一個相交線是y，就再到y逆時針找c線一個相交線，如此就相交一個連通的線段序列，如果最後回到a線且交點序號臨近a和c的交點序號就是一個封閉圖，如果最後走到孤立節點就拋棄這個序列（可以把這個序列信息從圖中標記避免以後重複遍歷），如果最後回到序列中已有的節點就是發現一個子封閉圖，整個過程不需要計算任何一個實際交點。然後從a線找下一個交線 f 開始遍歷，直到遍歷完畢a的所有交線。回到sweep line演算法找左邊第二條線段，同樣遍歷交線直到處理完所有線段。

最後輸出如果需要高亮顯示封閉區域再用輸出的線段序列計算具體的交點。

說個思路，僅供參考，演算法工作量比較大。

先把孤立的線條去掉，即刪除某個端點只出現一次的線段、然後不斷遞歸即可

接下來想像一下，有塊鋼板，經過各種切割，最後產生一堆鋼板。那麼問題會變成以下幾個問題

1、每次切割是否會掉下一塊鋼板

2、掉下的鋼板、剩餘的鋼板形狀是啥樣的

3、剩餘的刀路在哪塊鋼板上

4、按照上面三步處理所有切下來的鋼板，直至所有的刀路都走過了

針對問題的解決思路

1、若干線段是否能組成封閉圖形

2、掉下鋼板後，對新的鋼板、剩餘的鋼板信息進行更新

3、判斷線段是否位於多邊形內部

4、遞歸進行以上過程

其中1、3是純粹的普通幾何問題，不難解決，重點在於第2步的更新

由1問題的解決，我們可以得到掉下鋼板的邊界，這樣可以得到新鋼板的信息

而剩餘鋼板的信息為，整個線段集合 - 新鋼板中的邊界線段 + 公共的邊界線段

公共的邊界特徵：新鋼板中的特殊線段（端點在集合中出現過2次以上），並且需要過濾掉新鋼板、舊鋼板位於線段同一邊的情況。所以還需要寫個方法判斷線段與多邊形的位置關係

首先遍歷一遍所有點，當某個點只有一條邊相連接時，刪除該點和這條邊，並且順著這個點向上刪除，直到某個父節點與兩條及以上的邊相連接時停止。這樣剩餘的所有邊圍成了若干個封閉區域。

cnt=0，再將剩餘的點遍歷，噹噹前的點未被訪問過時，cnt+=2，並且從該點開始bfs遍歷，記與點i相連的邊的數目為a[i]，cnt+=a[i]-2。

最後結果為cnt/2

下邊是一個證明

現在若有若干點組成一區域S，S的所有端點均只與兩條邊相連，則該環不可再分割成兩個閉環。在S上取兩點a,b，從a點增加邊，並以b結束，則這些邊與S上ab的路徑新組成了閉環T。

考察新形成的圖形，a,b點均有3條邊，其餘點均為兩條邊。在該圖形的基礎上繼續增加閉環時，仍會使兩個點(可能相同)的邊的數目+1。

把交點求出來後，連邊，求平面圖【感覺這是一道比較基礎的oi題啊

把每條邊拆成帶方向的兩條邊，然後每次找一條未被訪問過的邊，依次選擇逆時針旋轉角度最小的邊，若回到最初的起點，就把這個多邊形記下來，最後對所有的多邊形求一次面積，把面積為負的去掉就行了。

寫一個圖像處理的方法，在整個圖像上面平均取幾百個點，然後依次以點為圓心向外面膨脹，膨脹停止就為一個封閉圖形