在無向圖中尋找獨特的循環

Question

我目前正在爲Unity開發基於節點的房屋建造者。該系統的工作流程非常簡單：用戶可以創建簡單的立方體節點，並將它們相互連接以創建牆壁。網格處理已經完成，它工作得很好，平穩。

我現在要做的是檢測已創建了多少封閉房間以及每個房間中包含了哪些頂點。可能的輸入可以看出，在以下圖象：

在第一張照片，環將是

（1,5,3,4），（1， （6,9,12,11,10,8），（8,10,14,13）和（10,11,17,16,15,14）。

在第二個他們會

（1,2,5,6,8,7），（2,3,4,14,13,6,5）， （6,13,12,11,10）和（8,6,10,9）。

每個節點最多可連接四個其他節點，每個基數一個，每個鏈路都存儲在兩側。我不需要節點以任何特定的順序進來。

我想我可以使用通用的循環檢測算法並遞歸搜索子循環，直到找到的循環沒有內部連接，但這會非常耗費資源。必須有一些屬性可以用來檢測沒有內部連接的循環，而無需迭代圖表多次，但我一直無法找到它。

你有什麼建議嗎？

Answer 1

對於下面的算法工作，你需要以下條件：

• 邊緣的一個獨特的方向（你可能已經有了）
• 兩個標誌用於指定如果邊緣一直逢緣在向前和向後方向
• 頂點列表用於與未使用的邊緣

然後想法如下。採取任何有未使用邊緣的節點，並沿着任何未使用的邊緣去鄰居（記住方向）。這樣做時，立即按照使用的相應方向標出邊緣。在這個鄰居，你知道你來的方向。按照逆時針順序查看，直到找到第一個未使用的邊（再次注意邊的方向）。您也可以按順時針順序搜索，這將定義所有輸出面的順序。例如。如果您從左邊緣出來，則分別檢查底部，右側，頂部邊緣。穿過這條邊（標記爲已用）並重復，直到到達起始頂點。所有訪問過的頂點形成你的房間。

這樣做，您應該相應地更新未使用邊的頂點列表。

最終，您還將爲邊框創建一個面。你可以檢測到這個通過計算其取向：

v1 x v2 + v2 x v3 + v3 x v4 + ... + vn x v1 

，其中v是頂點的位置和x表示叉積的z分量（其表示臉部朝向）：

(x1, y1) x (x2, y2) = (x1 * y2) - (x2 * y1) 

邊界面對於這個方向將會有一個不同於其他所有面孔的符號。實際符號取決於您在邊緣遍歷期間是使用逆時針還是順時針順序。

Answer 2

這只是第一個問題的答案，但它可能會幫助第二個問題。關閉房間的數量實際上有一個閉合公式： 1 - V + E其中V是頂點的數量，E是邊的數量。在第二個例子中，有14個頂點，17個邊和4個房間。 數學有點複雜，但關鍵詞是Euler characteristic。