如何檢測並保存邊緣頂點的循環連接（孔檢測）？

Question

感謝您花時間閱讀我的問題。

我正在檢測三角形網格中的孔，並用新的三角形填充它們。我已經完成了一些部分，以獲得邊緣頂點列表等。以下是形成孔的頂點/邊緣，請查看圖像。

(9, 62)   => vertex # 9 and 62 makes an edge (left hole) 
(66, 9)   => vertex # 66 and 9 makes an edge (left hole) 
(70, 66)  => vertex # 70 and 66 makes an edge (left hole) 
(62, 70)  => vertex # 62 and 70 makes an edge (left hole) 

(147, 63)  => vertex # 147 and 63 makes an edge (right hole) 
(55, 148) 
(63, 149) 
(149, 55) 
(148, 147) 

，我需要做的第一件事是檢查其頂點構成一個循環（指被檢測孔），然後保存在單獨的一組循環的頂點。

問題是編寫這樣的算法來檢查給定的圖形（頂點/邊）是否包含多少個週期？然後保存到單獨的集合中。

請給我寫一些簡單而優化的算法來解決這個問題。

謝謝。

Answer 1

1. 網

   我們假設你STL網得到n三角形，你需要將其轉換爲索引格式。因此提取所有三角形點並將其轉換爲兩個單獨的表格。一個持有所有積分，第二個持有每個三角形3個點的指數。假設你有m點和n三角形。

   您應該對點表（索引）進行排序並使用二進制搜索將其從O(n.m)加速到O(m.log(n))。

2. _edge結構

   創建結構握着你的網格的所有邊緣。例如：

   struct _edge 
   { 
   int p0,p1; // used vertexes index 
   int cnt; // count of edge usage 
   }; 
   

   其中p0<p1。

3. 創建_edge edge[]表O(n)

   應該保持所有邊緣（3n），所以環的列表通過所有的三角形，並添加每各3個邊。計數設置爲cnt=1這是O(n)。

   現在通過p0,p1對列表進行排序，即O(n.log(n))。之後，只需加上cnt並刪除其中的一個，即可加入與p0,p1相同的所有邊。如果編碼正確，那麼這是O(n)。

4. 檢測孔

   在常規STL每個邊緣必須有cnt=2。如果cnt=1那麼三角形缺失，你找到你的洞。如果cnt>2你的網格中有幾何誤差。

   因此，從您的edge[]表中刪除cnt>=2的所有邊緣即O(n)。

5. 檢測循環

   讓我們假定我們有k邊緣留在我們的edge[]表。現在爲每個共享一個點的2個邊創建三角形。喜歡的東西：

   for (i=0;i<k;i++) 
   for (j=i+1;j<k;j++) 
       { 
       if ((edge[i].p0==edge[j].p0)||(edge[i].p1==edge[j].p0)) add_triangle(edge[i].p0,edge[i].p1,edge[j].p1); 
       if ((edge[i].p0==edge[j].p1)||(edge[i].p1==edge[j].p1)) add_triangle(edge[i].p0,edge[i].p1,edge[j].p0); 
       } 
   

   如果您使用內循環二進制搜索，那麼這將是O(k.log(k))。你也應該避免添加重複的三角形並糾正它們的纏繞，所以首先將三角形添加到單獨的表格（或記住起始索引），然後刪除重複項目（或者可以直接在add_triangle中執行）。

   也處理更大的孔不要忘記添加新的邊緣到您的edge[]表。您可以在處理當前邊緣之後更新邊緣，並重復執行＃4或合併運行中的更改。