算法從圖中得到的所有個別地區

Question

由於輸入我們只有一組段，這裏有一個例子：

[AB] = [(0, 0), (0, 4)] ; [BC] = [(0, 4), (2, 6)] 

[CD] = [(2, 6), (4, 0)] ; [DA] = [(4, 0), (0, 0)] 

[CE] = [(2, 6), (5, 6)] ; [EF] = [(5, 6), (5, 3)] 

[FG] = [(5, 3), (3, 3)] ; [HI] = [(2, 1), (4, 5)] 

[JK] = [(1, 3), (2, 3)] ; [KL] = [(2, 3), (1, 1)] 

[LJ] = [(1, 1), (1, 3)] 

（對不起，我已經盡了全力，但我的圖片有點模糊）

我需要找到所有的單個區域。從上圖中我將有3個不同的區域，JKL，CEFG和{ABCD，JKL}：

注意，段不進行任何區域都被忽略（例如[HI] ），以及面積不能由段劃分，如：

我可以做一些意大利麪條代碼將完全效率不容易做，但這樣做之前，你有什麼想法我可以開始工作的算法？我正在尋找儘可能高效的東西...

Answer 1

想法：嘗試從最少的連接節點創建最小的環。隨着我們的進展減少問題的大小。

1. 刪除所有隻有一個段的節點，因爲它們不能成爲任何區域的一部分。
2. 排序段的號碼後按升序排列的節點（你會希望有一個O（N日誌log n）的以下算法）
3. 直到潛在的目標是選擇具有最少段
4. flood fill沿段的節點已經填滿（不留後路）
5. ...（有可能是在這裏完成2個加環）
6. 利潤通過去除連接到所選擇的節點
7. 更新剩餘節點段2級的節點。

TODO：如果至少連接節點是3或更高的...