在一大組連接線中查找單個閉合線組的算法

Question

我目前正在嘗試編寫一個算法，可以在更大的一組線中找到單個連接線組。下面的圖片應該更清楚地說明這一點。

在第一個圖像，你可以看到一組線。我想要做的是將這些行分成3組，如第二張圖片所示。紅色和綠色組合共用一條線。

我可以假設每一行都有一個開始和一個結束座標，並且每一行可以屬於一個或多個組。

我目前正在嘗試編寫一個遞歸函數，每行之後直到它到達一個或多個可以遵循的行的終點。在這一點上，函數會自行回顧它，直到它沿着回到分割點的線。然而這證明是不成功的。

該示例的輸出（如第二張圖所示）應該是3個獨立的行組，存儲在列表中。我目前正在使用c＃，但是我應該能夠使用任何語言的合適算法，包括僞代碼。我知道必須有一個算法可以實現這一點，但我似乎無法解決它或在網上找到它。

Answer 1

在圖論的語言中（頂點都是線端點，每條邊是線），你的問題是要找到平面圖的所有面。這有時稱爲平面人臉遍歷。有一些資源可以諮詢這方面的信息，包括this mathoverflow question。儘管它是一個C++庫而不是C＃，但是Boost Graph Library有一個用於平面遍歷的API，查閱它的文檔可能會有所幫助。