如何检测并保存边缘顶点的循环连接（孔检测）？

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或合并运行中的更改。